辅导CSCI-1200、C++程序写作、辅导Data Structures

” 辅导CSCI-1200、C++程序写作、辅导Data StructuresCSCI-1200 Data StructuresTest 2 Practice ProblemsNote: This packet contains practice problems from three previous exams. Your exam will contain approximatelyone third as many problems.11 Checking It Thrice [ / 22 ]Each row in the table below contains two statements labeled A and B. Put a checkmark 2 in up to threeboxes per row. Each correct checkmark is worth +1, each blank checkbox is worth +0, and to discouragerandom guessing each incorrect checkmark is worth 2 points. Your score on this problem will not gobelow 0. Only two A statements are true because of their corresponding B statements.A is B is A is truebecause of BStatemtents True False True False2 2 2 2 2A: STL vector erase() may invalidate an iterator.B: For programs that need to do a lot of erasing, you shoulduse an STL list instead of an STL vector.2 2 2 2 2A: A memory debugger like Valgrind or Dr. Memory canhelp find leaked memory.B: A memory debugger like Valgrind or Dr. Memory showsyou the line you should have written delete/delete[] on to fixthe memory leak.2 2 2 2 2A: Vec push back() on Average takes O(n)B: Vec push back() sometimes has to allocate a new arraythats 2*m alloc2 2 2 2 2A: If std::listint::iterator itr points to a valid location inlist l1, writing l1.erase(itr)++ may cause a memory error.B: Incrementing the end() iterator in any STL list hasundefined behavior2 2 2 2 2A: STL lists / dslist do not have operator[] definedB: Using operator[] on a pointer is the same as using pointerarithmetic and then dereferencing the result.2 2 2 2 2A: Assuming std::vectorint::iterator itr points to avalid location in vector v1, writing v1.insert(itr,5);std::cout *itr; will always cause a memory error.B: std::vectorT::insert() returns an iterator becauseinsert() may invalidate The iterator passed in.2 2 2 2 2A: If std::vectorint v1 is an empty vector, v1.end()–will result in undefined behavior.B: Decrementing the end() iterator in any STL vector hasundefined behavior.2 2 2 2 2A: If a recursive function does not use array indexes orpointers, and theres a segmentation fault in that function, itmeans you must have infinite recursion.B: Infinite recursion can result in a segmentation fault.2 2 2 2 2A: Writing int* x=5; will result a compiler error.B: Memory addresses are not numbers, so you cannot storea number in a pointer.2 2 2 2 2A: Writing dslistint x; x.push back(5);dslistint y = x; will not result in callingy.operator=(x) even though there is an = sign in thelast statement.B: operator= can only be called on objects that are alreadyconstructed.22 Hop Lists [ / 37 ]In this problem we will consider hop lists, a made-up data structure based on skip lists. A hop list isa linked list using the Node Class listed below. For simplicity we will not make it templated and our Nodeswill only contain integers. The next pointer works the same way as in the singly and doubly-linked listswe have studied so far. However, the prev odd pointer is NULL for the 1st element in the list, and for allother elements in an odd position (3rd in the list, 5th in the list, and so on), the prev odd pointer pointstwo elements back. There is a diagram below to illustrate how this would look for a list with five nodescontaining the values 10, 20, 30, 40, 50 in that order.class Node{public:Node(int v) : val(v), next_(NULL), prev_odd_(NULL) {}Node(int v, Node* next) : val(v), next_(next), prev_odd_(NULL) {}int val;Node* next_;Node* prev_odd_;};val 10 20 30 40 50next_prev_odd_In the following sections you will write two different versions of AddPrevOddPointers. Both versions takea Node pointer called head which points to the first Node in a hop list, and a Node pointer called tail.After the function is done, all of the prev odd pointers should be set correctly, and tail should point tothe last element (furtherst from head) that is in an odd position. If there are not at least 3 Nodes in thelist, then tail should be NULL. You can assume that all Nodes have their next pointer correctly set beforeAddPrevOddPointers is called.An example of calling the function might look like://Start a new listNode* head = new Node(2561);/////Code to make the rest of the Nodes/link forward omittedPrintListForward(head); //Printing forward list…Node* tail;AddPrevOddPointers(head,tail);PrintHopListBackwards(tail); //Printing backwards…std::cout std::endl;Here are two examples:Printing forward list: 10 20 30 40 50 60 70 80 90 100 110Value at tail: 110Printing backwards every-other list: 110 90 70 50 30 10Printing forward list: 31 32 33 34 35 36 37 38 39 301Value at tail: 39Printing backwards every-other list: 39 37 35 33 3132.1 AddPrevOddPointers (Recursive Version) [ / 18 ]Write a version of AddPrevOddPointers that uses recursion.sample solution: 23 line(s) of code42.2 AddPrevOddPointers (Iterative Version) [ / 15 ]Write a version of AddPrevOddPointers that does not use any recursion.sample solution: 20 line(s) of code2.3 AddPrevOddPointers Complexity [ / 4 ]If the hop list has n elements, what is the running time order notation of the iterative version ofAddPrevOddPointers? What about for the recursive version?53 Shape Overlays [ / 14 ]Given a series of Shape objects in a vectorShape shapes, the code below should allocate and fill a 2Ddynamic array of integers, overlay that represents an overlay of all the shapes. If all of the shapes wereto be put on top of each other, an overlay would show for every position (x,y) how many shapes had apixel on at that position. You can assume that shapes is not empty and each shape is at least 1×1 in size.The coordinates use the Cartesian coordinate system, where (0,0) is the origin, x = 1 is to the right of theorigin, and y = 1 is above The origin. You can also assume non-negative x,y coordinates for everything andthat the overlay starts with the bottom left corner at (0,0). The example shapes and overlay output have(0,0) in the bottom left corner for easy visualization.Shape 1 (outline rectangle)Printing 4 x 4 overlay:XXXXX..XX..XXXXXLower left is at (0, 1)Shape 2 (outline rectangle)Printing 4 x 4 overlay:XXXXX..XX..XXXXXLower left is at (1, 1)Shape 3 (filled in rectangle)Printing 5 x 2 overlay:XXXXXXXXXXLower left is at (1, 0)Printing 5 x 5 overlay:1332112111121111332101100class Point{public:Point(int x=0, int y=0) : m_x(x), m_y(y) {}int m_x, m_y;};class Shape{public:bool pixelOn(int x, int y) const;void getDimensions(int Width, int height, Point corner) const;…};(1,0)(0,1)(1,1)+ +(0,0)int** overlay=Shape 1 Shape 2 Shape 3void MakeOverlay(int** overlay, int height, const std::vectorShape shapes){int shape_height, shape_width, width;height = width = 0; //Start by assuming a 0x0 overlayPoint shape_corner; //Holds the lower left corner of the shape//Cycle through each shape and find the further-upper-right pointfor(unsigned int i=0; ishapes.size(); i++){shapes[i].getDimensions(shape_width, shape_height, shape_corner);height = std::max(height, shape_corner.m_y + shape_height);width = std::max(width, shape_corner.m_x + shape_width);}//STUDENT PORTION #1: ALLOCATE OVERLAY, first box on next page goes here//STUDENT PORTION #2: FILL IN OVERLAY, second box on next page goes herePrintOverlay(overlay, width, height); //DO NOT WRITE THIS FUNCTION}63.1 #1: Allocate Overlay [ / 8 ]Write the code that should go under the STUDENT PORTION #1 comment in MakeOverlay.sample solution: 7 line(s) of code3.2 #2: Fill In Overlay [ / 6 ]Write the code that should go under the STUDENT PORTION #2 comment in MakeOverlay.sample solution: 13 line(s) of Code74 Pivoting Lists [ / 24 ]Write a void function MovePivots that takes an STL liststring a and a constant STL liststringpivots. The function should rearrange a so that all instances of strings that are in both a and pivots are atthe front of a. The order of other elements in a should not be changed, and the elements that were movedto the front should be in the order they were found in originally in a. The elements in a are not guaranteedto be unique. Do not create any new lists/vectors/arrays. Do not use anything from algorithm. Yourfunction does not need to print anything.Here are some examples of before and after the function, with five strings in pivots: ant bear cat dog eelBefore List (size 3): bob ant codAfter List (size 3): ant bob codBefore List (size 3): eel ant catAfter List (size 3): eel ant catBefore List (size 9): bob blob cod eel cod ant eel eel antAfter List (size 9): eel ant eel eel ant bob blob cod cod4.1 MovePivots Implementation [ / 20 ]sample solution: 18 line(s) of code4.2 MovePivots Complexity [ / 4 ]If there are p strings in pivots, and w strings in a, what is the running time order notation for MovePivots?Explain your analysis.85 Time Complexity [ / 20]For each of the functions, write the time complexity assuming there are n elements stored in the container.If there is a difference between C++98 and C++11, you should assume C++11. For the singly-linked list,assume that we only have the head pointer and no other member variables. For the singly-linked list,assume that erase() is given a pointer to the node we want to erase and a pointer to the node before theone we want to erase.STL vectoror VecTSingly-linkedListSTL list ordslistTsize()push back()erase()insert()pop back()Write 2-3 complete sentences About one of the above methods which is more efficient for STL lists thanfor STL vectors and why this is the case.96 Pokemon Battles [ / 16]Players, known as trainers, collect teams of Pokemon. Trainers then have battles against each other wherethey use one Pokemon at a time from their team to try and defeat their opponents team. Each face-offbetween two Pokemon is considered a fight. A series of fights between two trainers is called a battle.When a Pokemon loses a fight, it cannot be used again in the same battle. A battle is not over until oneof the trainers has no more usable Pokemon, at which point their opponent wins.Each monster is represented by an instance of the class Pokemon. You do not need to know the details ofthe class. To determine which Pokemon will win in a fight, the following function is used – it returns anegative number if p1 wins, and a positive number if p2 wins. There are no ties.int pokemonFight(const Pokemon p1, const Pokemon p2);In this problem you will be completing an implementation for the recursive function TrainerOneWins().The function takes in two Node pointers which represent two lists of Pokemon, trainer1 represents thePokemon belonging to Trainer 1, and trainer2 represents the Pokemon belonging to Trainer 2. Thefunction returns true if Trainer 1 wins, and false if Trainer 2 wins. A trainer wins if they still haveusable Pokemon but their opponent does not. If a trainers Pokemon loses, the trainer will use the nextPokemon in their list.In this problem, the Node class is defined as follows:template class T class Node {public:T data;Node* next;};As an example consider the following case. You do not need to know anything about specific Pokemon tosolve this problem.NodePokemon* list1 has Bulbasuar, Ivysaur, GeodudeNodePokemon* list2 has Squirtle, CharmanderRunning the following code:if(TrainerOneWins(list1,list2)){std::cout Trainer 1 wins. std::endl;}else{std::cout Trainer 2 wins. std::endl;}A possible run using might look Something like this. The output is handled in pokemonFight(), you shouldnot write any output statements:Bulbasuar wins against SquirtleCharmander wins against BulbasaurCharmander wins against IvysaurGeodude wins against CharmanderTrainer 1 wins.106.1 TrainerOneWins Implementation [ /12]Fill in the blanks to finish TrainerOneWins():bool TrainerOneWins( trainer1, trainer2){if(trainer1 == NULL || trainer2 == NULL){return ;}int fight_result = pokemonFight( );if(fight_result 0){return ;}else{return ;}}6.2 TrainerOneWins Complexity [ /4]If pokemonFight() is O(1), and there are m pokemon in Trainer 1s list and n pokemon in Trainer 2s list,what is the time complexity for TrainerOneWins()?117 Print-and-Modify Functions [ / 20]In this problem you must infer the behavior of two functions from the code sample and output providedbelow. You should not hard-code any values. Hint: Write out the relationship between the numbers beforeand after AddByPositionAndPrint().Running this code:int main(){std::listint counts = std::listint(3,0);AddOneAndPrint(counts);AddOneAndPrint(counts);counts.push_back(9);counts.push_front(11);AddOneAndPrint(counts);std::listint add_amounts;add_amounts.push_back(4); add_amounts.push_back(1); add_amounts.push_back(-3);add_amounts.push_back(0); add_amounts.push_back(4);AddByPositionAndPrint(counts,add_amounts);AddOneAndPrint(add_amounts);return 0;}Produces this output, with one line Coming from each non-STL function call:Elements after updates: 1 1 1Elements after updates: 2 2 2Elements after updates: 12 3 3 3 10Elements after updates: 16 4 0 3 14Elements after updates: 5 2 -2 1 5Your answers should go in the boxes on the next page.127.1 AddByPositionAndPrint [ / 14]Start by implementing AddByPositionAndPrint. Assume that the two arguments have the same size.sample solution: 10 line(s) of code7.2 AddOneAndPrint [ / 6]Now implement AddOneAndPrint. Do not write any duplicate code.sample solution: 3 line(s) of code138 Mystery List Function [ / 20]This problem focuses on a couple similar functions that are used to manipulate a collection of doubly linkednodes:template class Tclass Node{public:Node(const T v) : value(v), next(NULL), prev(NULL) {}T value;NodeT *next, *prev;};We also define a function for printing nodes:template class Tvoid PrintList(NodeT* head){std::cout List:;while(head){std::cout head-value;head = head-next;}std::cout std::endl;}Here is the mystery function you will be working with:1 void MysteryA(Nodeint* ptr1, Nodeint* ptr2){2 while(ptr2 (ptr2-value % 2 == 0 || ptr2-value % 7))3 ptr2 = ptr2-next;4 if(ptr2 ptr2 != ptr1){5 Nodeint* ptr3 = ptr2-next;6 Nodeint* ptr4 = ptr2-prev;7 ptr2-next = ptr1;8 ptr1-prev = ptr2;9 ptr1 = ptr2;10 if(ptr3)11 ptr3-next = ptr4;12 if(ptr4)13 ptr4-prev = ptr3;14 ptr1-prev = NULL;15 }16 }148.1 Visualizing MysteryA [ / 14]In the box below, a list is shown. Below it is a copy of the nodes with none of the pointers added. Updatethe bottom list to illustrate how the list has changed after a call to MysteryA(head,head).5 4 7 8head5 4 7 8headThe function is supposed to find the first odd multiple of 7 by using ptr2 and if its not already at the head,the function should make ptr2 the new head by moving it to the front and updating links accordingly. Italso has to update the pointer passed in. Assume that ptr1 is a list head and that ptr2 belongs to the samelist as ptr1.158.2 Fixing MysteryA [ / 6]Consider the original list given in 4.1 and the following code fragment:PrintList(head);MysteryA(head,head);PrintList(head);Explain what will happen when this code runs. If there are bugs, explain which lines of code need to bechanged and what the corrected lines of code should be. Use the line numbers provided in the left marginof the code.169 Acrostic Printing [ / 21]An acrostic is a word that is found by a column reading top-to-bottom when looking at several wordsstacked on top of each other. For example, if our input is a vector of 4 strings:HadaNiceDaythen we could look at the first letter in each word to see that they spell a new word: HaND. Similarly,we could look at the second letter in each word and see they spell: aia. Your task is to write a function,acrostics(), which takes a vector of strings (each string contains exactly one word) and returns an arrayof C-style strings where each string is one column of the acrostic. For the input shown above, the returnarray should contain the following strings:HaNDaiadcyeYou can ignore the null-terminating character, \0 for simplicity. We have given you a partial implementation,you will need to fill in the rest of it. You should not use any arrays besides ret, and you should notcall the delete keyword. You cannot declare any new vectors/lists in your code. Finally, keep in mindthat you should be memory efficient and not allocate more space than you need in the return array.Your answer should go in the box on the next page.179.1 acrostic Implementation [ / 16]char** acrostics(const std::vectorstd::string v){unsigned int max_return_length = 0;for(unsigned int i=0; iv.size(); i++){max_return_length = std::max(max_return_length, (unsigned int)v[i].size());}std::vectorint characters_per_string(max_return_length,0);for(unsigned int i=0; iv.size(); i++){for(unsigned int j=0; jv[i].size(); j++){characters_per_string[j]++;}}return ret;}9.2 acrostic Performance [ / 5 ]If there are m input strings, the length of the longest input string is n, and there are c characters in allinput strings combined, what is the time complexity and the space (memory) complexity of acrostic?1810 Iterating Over a List and Inserting New Points [ /21]In this question you are asked to write two functions that use iterators to traverse and manipulate STLlists.Dont worry about #include or #define statements. You may assume using namespace std.10.1 Lists Finding Zeros [ /6]First, write a function that will be passed a const reference to an STL list of ints and returns a new list ofints containing the positions of zeros in the input list. The function should iterate through the list usinga list iterator. It should not use find() or similar STL functions.For example, if the original list contained 1 0 11 16 0 0 50 75 85 90 0, the returned list should contain 1 45 10.sample solution: 12 line(s) of code1910.2 Lists Replacing Zeros[ /15]Now, write a second function. This void function will be passed a reference to an STL list of ints. In thisfunction each zero in the list should be replaced with the sum of the adjacent numbers. A zero in the firstor last position of the list should not be replaced. For example, if the list originally contained 1 0 11 160 0 50 75 85 90 0, the returned list will contain 1 12 11 16 16 66 50 75 85 90 0. Iterate through the listfrom left to right and replace the elements sequentially. Notice how consecutive zeros are handled. Thefirst zero is replaced and the replacement value becomes the adjacent value for the next zero. That is, alist containing x 0 0 0 y will become x x x x+y y, where x and y are integers.The zeros are to be replaced in the original list. Do not make a copy of the list. Iterate through the listand replace the elements. Do not use std::replace or std::find.sample solution: 15 line(s) of code2011 Recursive Lists [ /25]In this question, dont worry about #include or #define statements. You may assume using namespacestd.11.1 Recursive Lists Delete a List[ /6]A templated class for Nodes is defined as:template class Tclass Node {public:T value;NodeT* next;};First, write a templated recursive function to delete a list of Node T s.sample solution: 8 line(s) of code2111.2 Recursive Lists Recursive Merge [ /19]Merging two or more sorted lists is a common operation. It is a basic part of the merge sort which werecently covered in lecture. The idea behind merging two lists is to travel through the two sorted inputlists and produce a third sorted list containing all of the elements of the two original lists.For example, if the first list contains apple cow rhino tree and the second list contains cat dog mongoosezebra, the merged list should contain apple cat cow dog mongoose rhino tree zebra.Write a templated recursive function that takes two pointers to sorted singly linked lists of Nodes, definedon the previous page, and a reference to a pointer to a singly linked list of Nodes. On return from thefunction, the third list should contain the merged sorted list. Your merged list must copy the data in thesorted lists.The function must be recursive. Do not sort the list. Merge the lists, dont sort. These are not STL lists,use the pointers to iterate through the lists. You may include any helper functions that you find necessary.Do not edit the Node class. You dont have to write a main() function.sample solution: 20 line(s) of code2212 Templating and Flattened Matrices [ /19]In Homework 3 we explored a matrix based around a 2D data structure. We will not be using the Matrixclass we designed, but instead will be using a templated T** data 2D data structure to represent a matrix.The layout should look familiar.In addition to the 2D representation, we would like to have the option to work on a flattened versionof the matrix, which is implemented in a T* data 1D structure. Both structures are depicted below. Wewould like to be able to go between the two data structures.T* data_1D1 2T** data_2Dheap251 34 63 4 5 61 2 34 5 6 Below is an example of how the two functions we will write might be used, along with the output fromthis code fragment.int** data_2D = new int*[2];data_2D[0] = new int[3];data_2D[1] = new int[3];data_2D[0][0] = 1; data_2D[0][1] = 2;data_2D[0][2] = 3; data_2D[1][0] = 4;data_2D[1][1] = 5; data_2D[1][2] = 6;int* data_1D = Flatten(data_2D,2,3);for(int i=0; i2; i++){for(int j=0; j3; j++){int index;int readval = Read1D(data_1D,2,3,i,j,index,-1);std::cout ( index , readval ) ;}}//Assume and Delete1D/2D are already writtenDelete2D(data_2D,2,3);Delete1D(data_1D);Output:(0,1) (1,2) (2,3) (3,4) (4,5) (5,6)2312.1 Flattening the Matrix [ /10]Your first task is to implement the templated flatten function. flatten should take in data 2D as shown onthe previous page, and two integers m and n, which are the number of rows and the number of columns inthe data respectively. flatten should return a pointer to an equivalent 1D data structure.If either the number of rows or columns is non-positive, the function should return a NULL pointer.Do not change data 2D. Only use const and when needed. Remember that since flatten is templated itshould work with any datatype. Do not leak any memory, any memory still allocated must be reachablefrom the returned pointer.sample solution: 14 line(s) of codeIf the 2D matrix reprensentation contains m rows and n columns, what is the running time of the flattenfunction?2412.2 Reading From the Flattened Matrix [ /9]Another important task is to be able to read from the data structure. Write a function Read1D that takesin a 1D representation of data data 1D, two integers m and n which are the number of rows and columnsrespectively, two integers row and col which are the row and column position we are trying to extract datafrom, a reference to an integer index, and a failure value which will be returned in case of an error.Just like in Homework 3, we will number the upper left corner of a 2D structure as (0, 0) or row= 0,col= 0.The function should do two things. If the dimensions are legal (i.e. there are a positive number of rowsand columns), and the requested position can exist within the given bounds, then the function shouldreturn the data stored at that position and set index to the index in data 1D where the data came from.If the dimensions are illegal or the requested position is out of bounds, the index should be set to -1 andfailure value should be returned.Keep in mind that the same data 1D object can be viewed different ways. For example, if there is a 23data 2D example and data 1D example = flatten(data 2D example,. . . ), then after callingRead1D(data 1D example,1,6,1,1,index,-1), index will be -1, because in this example call we specified thatm= 1, n= 6, and there is no position (1, 1) inside of a 16 matrix.On the other hand, using the same data 1D example, Read1D(data 1D example,2,3,1,1,index,-1) wouldset index= 4.Do not call any STL functions. Only use const and when needed. Remember that since Read1D istemplated it should work with any datatype.sample solution: 11 line(s) of code2513 Memory Errors [ /9]For each function or pair of functions below, choose the letter that best describes the memory error thatyou would find. You can assume using namespace std and any necessary #include statements.A ) use of uninitialized memoryB ) mismatched new/delete/delete[]C ) memory leakD ) already freed memoryE ) no memory errorF ) invalid writechar* a = new char[6];a[0] = B; a[1] = y;a[2] = e; a[3] = \0;cout a endl;delete a;int a[10];int b[5];for(int i=10; i5; i–){a[((i-6)*2+1)] = i*2;a[((i-6)*2)] = b[i-6];cout a[(i-6)*2] endl;}bool* is_even = new bool[10];for(int i=0; i=10; i++){is_even[i] = ((i%2)==0);}delete [] is_even;int a[2];float** b = new float*[2];b[0] = new float[1];a[0] = 5; a[1] = 2;b[0][0] = a[0]*a[1];delete [] b[0];b[0] = new float[0];delete [] b;string* str1 = new string;string* str2;string* str3 = new string;*str1 = Hello;str2 = str1;*str3 = *str1;delete str1;delete str3;delete str2;int x[3];int* y = new int[3];for (int i=3; i=1; i–){y[i-1] = i*i;x[i-1] = y[i-1]*y[i-1];}delete [] y;2614 Complexity Code Writing [ / 9 ]For each of the problems below, write a function void complexity(int n) that satisfies the big-O runningtime. Assume that the input is size n. You should not use anything that requires a #include statement.You should write no more than 7 lines of code per box (including the function prototype).O(1):void complexity(int n){sample solution: 1 line(s) of code}O(n2):void complexity(int n){sample solution: 5 line(s) of code}O(log n)For this one, do not use any loops, do not use math functions such as log() or log2():void complexity(int n){sample solution: 4 line(s) of code}请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“