CSCI-1200 Data StructuresTest 2 — Practice ProblemsNote: This packet contains selected practice problems from Test 2 from three previous years.Your test will contain approximately one third to one half as many problems (totalling ∼100 pts).1 Linked Tube Repair [ / 33 ]Alyssa P. Hacker is working on a modified linked list that is both twodimensionaland circular. A small sample with height=3 and circumference=4is shown below. Each templated Node has pointers to its 4 neighbors. Thetop and bottom edges of the tube structure have NULL pointers. But the leftand right edges wrap around, like a circularly linked list. This cylindrical tubestructure may have any number of nodes for its height and its circumference.template <class T>class Node {public:// REPRESENTATIONT value;Node<T> *up;Node<T> *down;Node<T> *left;Node<T> *right;}; 1.1 Tube repair Diagram [ / 4 ]First Alyssa wants to tackle the challenge of repairing a hole in the structure. Assume a single Node ismissing from the structure, and we have a pointer n to the Node immediately to the left of the hole. Modifythe diagram below to show all of the necessary edits for a call to repair(n,7);nup:1.2 Thinking about Tube repair Complexity [ / 3 ]The repair function should have constant running time in most cases. Describe an example structure witha single missing Node that can be repaired, but not in constant time. Write 2-3 concise and well-writtensentences. You may want to complete the implementation on the next page before answering.11.3 Tube repair Implementation [ / 13 ]Now, implement repair, which takes 2 arguments: a pointer to the Node immediately to the left of thehole and the value to be stored in the hole. You may assume a single Node is missing from the structure.sample solution: 26 line(s) of code21.4 Non-Iterative destroy tube Implementation [ / 13 ]Now write destroy_tube (and any necessary helper functions) to clean up the heap memory associatedwith this structure. The function should take a single argument, a pointer to any Node in the structure.You may assume the structure has no holes or other errors. You cannot use a for or while loop.sample solution: 17 line(s) of code32 Rehashing the Vec Assignment Operator [ / 15 ]Complete the Vec assignment operator implementation below, while minimizing wasted heap memory.Assume the allocator is most efficient when all heap allocations are powers of two (1, 2, 4, 8, 16, etc.)1 template <class T>2 Vec<T>& Vec<T>::operator=(const Vec<T>& v) {3 if (this != &v) {4 delete ;5 m_size = ;6 m_alloc = ;7 m_data = ;8 for (int i = 0; i < ; ++i) {9 m_data[i] = ;10 }11 }12 return *this;13 }Add code below to perform a simple test of the assignment operator:Vec<double> v; v.push_back(3.14159); v.push_back(6.02); v.push_back(2.71828);Is line 12 necessary? Continue your testing code above with a test that would break if line 12 was omitted.What is the purpose of line 3? Write code for a test that would break if lines 3 and 10 were omitted.43 Essay Revision: Embellishment [ / 14 ]Write a function embellish that modifies its single argument, sentence (an STL list of STL strings),adding the word “very” in front of “pretty” and adding “with a wet nose” after “grey puppy”. Forexample:the pretty kitty sat next to a grey puppy in a pretty gardenShould become:the very pretty kitty sat next to a grey puppy with a wet nose in a very pretty gardensample solution: 20 line(s) of codeIf there are w words in the input sentence, what is the worst case Big O Notation for this function? If weswitched each STL list to STL vector in the above function, what is the Big O Notation?STL list: STL vector:54 Essay Revision: Redundant Phrases [ / 15 ]Complete redundant, which takes a sentence and 2 phrases and replaces all occurrences of the first phrasewith the second, shorter phrase. For example “pouring down rain” is replaced with “pouring rain”:it is pouring down rain so take an umbrella → it is pouring rain so take an umbrellaOr we can just eliminate the word “that” (the replacement phrase is empty):I knew that there would be late nights when I decided that CS was the career for me→ I knew there would be late nights when I decided CS was the career for metypedef std::list<std::string> words;void redundant( sentence, phrase, replace) {sample solution: 19 line(s) of code}65 Don’t Ignore Compilation Warnings! [ / 15 ]Write a useful but buggy segment of code (or function) that will compile with no errors but will producethe indicated compilation warning. Put a star next to the line of code that will trigger the warning.Write a concise and well-written sentence describing the intended vs. actual (buggy) behavior of the code.warning: comparison of integers of different signs: 'int' and 'unsigned int'warning: control reaches / may reach end of non-void functionwarning: variable is uninitialized when used here / in this functionwarning: returning reference to local temporary object / reference to stack memoryassociated with a local variable returned7warning: expression result unused / expression has no effectwarning: unused variable / unused parameter6 Cyber Insecurity [ / 5 ]Ben Bitdiddle wrote the following code fragment to manage his personal information.1 std::ifstream istr("my_information.txt");2 std::string s;3 std::vector<std::string> data;4 while (istr >> s) { data.push_back(s); }5 std::vector<std::string>::iterator password = data.begin()+4;6 data.push_back("credit_card:");7 data.push_back("1234-5678-8765-4321");8 data[4] = "qwerty";9 std::cout << "my password is: " << *password << std::endl;my information.txtname: Ben Bitdiddlepassword: pa$$wordSSN: 123-45-6789Write “True” in the box next to each true statement. Leave the boxes next to the false statements empty.Lines 2 & 3 will produce an “uninitialized read” error when run under gdb or lldb.Line 5 is not a valid way to initialize an iterator.Ben’s credit card information is not saved back to the file.This program might behave differently if re-run on this computer or another computer.A memory debugger might detect an “unaddressable access of freed memory” error on Line 9.If we move lines 6 & 7 after line 9, this code fragment will run without memory errors.This code contains memory leaks that can be detected by Dr. Memory or Valgrind.These password choices disqualify Ben from any job in computer security.87 Boxy Storage Solutions [ / 25 ]Eva Lu Ator is working on her capstone project to manage physical storage facilities. She’s mapped outthe overall design and started implementation of the two classes.class Box {public:Box(int w, int d, int h) :width(w), depth(d), height(h) {}int width;int depth;int height;};BwidthdepthheightACStorage storage(4,3,2);assert (storage.available_space() == 24);Box *a = new Box(2,2,2);assert (storage.add(a,0,0,0));Box *b = new Box(3,2,1);assert (!storage.add(b,2,0,0));delete b;Box *b_rotated = new Box(2,3,1);assert (storage.add(b_rotated,2,0,0));Box *c = new Box(1,1,1);assert (storage.add(c,2,0,1));assert (storage.available_space() == 9);class Storage {public:Storage(int w, int d, int h);// FILL IN FOR PART 1bool add(Box *b, int w, int d, int h);int available_space();private:void remove(Box *b, int w, int d, int h);Box **data;int width;int depth;int height;};bool Storage::add (Box *b, int w, int d, int h) {for (int i = w; i < w+b->width; i++) {if (i >= width) return false;for (int j = d; j < d+b->depth; j++) {if (j >= depth) return false;for (int k = h; k < h+b->height; k++) {if (k >= height) return false;if (datai[k] != NULL) return false;}}}for (int i = w; i < w+b->width; i++) {for (int j = d; j < d+b->depth; j++) {for (int k = h; k < h+b->height; k++) {datai[k] = b;}}}return true;}97.1 Missing functions from Storage Class Declaration [ / 5 ]Her friend Ben Bitdiddle doesn’t remember much from Data Structures, but he reminds her that classeswith dynamically-allocated memory need a few key functions. Fill in the missing prototypes for PART 1.7.2 Storage Destructor [ / 20 ]Eva explains to Ben that the private remove member function will be useful in implementing the destructor.First write the remove member function:sample solution: 10 line(s) of codeNow write the Storage class destructor:sample solution: 14 line(s) of code108 Transpose Linked Grid [ / 27 ]Louis B. Reasoner is working on a new member function for our Homework 5 Linked Grid named transpose.This function should mirror or flip the elements along the diagonal. Here’s a sample grid with integer dataand how it prints before and after a call to transpose:grid.print();std::cout << std::endl;grid.transpose();grid.print();1 2 3 48 7 6 59 10 11 121 8 92 7 103 6 114 5 12template <class T>class Node {public:// REPRESENTATIONT value;Node<T> *up;Node<T> *down;Node<T> *left;Node<T> *right;}; 8.1 Diagram [ / 7 ]First neatly modify the diagram of this smaller grid below to show all of the necessary edits that must beperformed by a call to transpose().:upper_leftup:down:right:value::leftup:down:right:value::leftup:down:right:value::leftup:down:right:value::leftup:down:right:value::leftup:down:right:value::leftheight:upper_right:width::lower_left lower_left:Grid<int>NULLNULL NULL NULLNULLNULLNULL NULL NULLNULL4 5 61 2 33 28.2 Complexity Analysis [ / 5 ]What is the Big ’O’ Notation for the running time of the transpose() member function? Assume the gridwidth is w and the height is h. Write 1-2 concise and well-written sentences justifying your answer. Youprobably want to complete the implementation on the next page before answering.118.3 Implementation [ / 15 ]Louis has suggested that we first implement a helper non-member function named swap, which will makethe implementation of transpose more concise.sample solution: 5 line(s) of codeNow implement transpose, as it would appear outside of the Grid class declaration.sample solution: 16 line(s) of code129 Organizing Words [ / 30 ]Alyssa P. Hacker is working on a program to clean up a dataset of words. The task is to write a functionnamed organize_words that takes in an STL vector of STL lists of words (STL strings). The functionshould organize the words into groups by word length, and ensure that the words are sorted within eachgroup. Many or most of the words will already be in the right place. That is, they will already be in theslot of the vector that matches the length of the word. And the neighboring words in each slot/list willalready be mostly alphabetized.For example, given the data shown on the left, your implementation should move the four misplaced wordsto produce the data shown on the right.01 diamond23 gem malachite4 jade opal rock ruby5 geode pearl talc stone topaz6 garnet quartz gypsum7 amethyst azurite emerald8 fluorite sapphire90123 gem4 jade opal rock ruby talc5 geode pearl stone topaz6 garnet gypsum quartz7 azurite diamond emerald8 amethyst fluorite sapphire9 malachiteTo make the problem a little more “fun”, you are NOT ALLOWED to use:• the STL vector subscript/indexing operator, [ ], or .at(),• the STL sort function, or• any of the push or pop functions on vector or list.You may assume that the initial vector has at least as many slots as the longest word in the structure.9.1 Complexity Analysis - Big ’O’ Notation [ / 6 ]Once you’ve finished your implementation on the next pages, analyze the running time of your solution.Assume there are w total words in the whole structure, v slots in the vector, a maximum of m wordsper list, and x words are misplaced and need to be moved. Write 2-3 concise and well-written sentencesjustifying your answer.139.2 Helper Function Implementation [ / 12 ]Alyssa suggests writing a helper function named place that will place a word in the correct location in thestructure. Work within the provided framework below. Do not add any additional for or while loops.void place( ) {sample solution: 2 line(s) of codewhile ( ) {sample solution: 3 line(s) of codewhile ( ) {sample solution: 5 line(s) of code}sample solution: 5 line(s) of code}}149.3 Organize Implementation [ / 12 ]And now write the organize function, which calls the place function. Again, work within the providedframework below and do not add any additional for or while loops.void organize_words( ) {sample solution: 2 line(s) of codewhile ( ) {sample solution: 2 line(s) of codewhile ( ) {sample solution: 8 line(s) of code}sample solution: 2 line(s) of code}}1510 Merge-Spiration: Recursive Interval Computation [ / 15 ]Ben Bitdiddle was inspired by the recursive merge sort examplefrom Data Structures lecture and proposes it as a guide to computethe smallest interval that contains a collection of floating pointnumbers (e.g., the minimum and maximum). Implement Ben’s idea,a recursive function named compute interval that takes in an STLvector of floats and returns an Interval object.For example: 6.2 4.3 10.4 2.5 8.4 1.5 3.7 → [1.5, 10.4]class Interval {public:Interval(float i, float j): min(i), max(j) {}float min;float max;};sample solution: 12 line(s) of codeWithout resorting to personal insults, explain in two or three concise and well-written sentences why Ben’sidea isn’t going to result in significant performance improvements. Be technical.1611 How many DS students to change a lightbulb? [ / 38 ]In this problem you will complete the implementation of two new classes named Bulb and Lamp. We beginwith an example of how these classes are used.First, we create a new lamp that will hold 3 bulbs and make a note of the manufacturer’s recommendedbulb: a 60 watt bulb with an estimated lifetime of 300 hours from Phillips. Note that initially this lamphas no bulbs installed. We install one of manufacturer’s recommended bulbs and use the lamp (turn it“on”) for a total of 50 hours.Lamp floorlamp(Bulb(60,300,"Phillips"),3);bool success;success = floorlamp.install(); assert(success);floorlamp.On(50);assert (floorlamp.getTotalWattage() == 60);Next, we attempt to install 3 bulbs, another of the manufacturer’s recommended bulbs, and then two otherbrands of bulbs. The installation of the 3rd bulb made by Sylvania fails because there are no availablesockets slots in the lamp and no bulbs are burnt out and need replacement.success = floorlamp.install(); assert(success);success = floorlamp.install(Bulb(40,120,"GE")); assert(success);success = floorlamp.install(Bulb(120,500,"Sylvania")); assert(!success);We then use the lamp for another 100 hours. Once the wattage drops (due to a burnt out bulb), we againtry to install the Sylvania bulb and it is successful.floorlamp.On(100);assert (floorlamp.getTotalWattage() == 160);floorlamp.On(50);assert (floorlamp.getTotalWattage() == 120);success = floorlamp.install(Bulb(120,500,"Sylvania")); assert(success);assert (floorlamp.getTotalWattage() == 240);Finally, we create a duplicate lamp. Note that when we do this, we match the bulbs currently installed inthe original lamp, but the bulbs installed in the new lamp are brand new (and unused).Lamp another(floorlamp);assert (floorlamp.getTotalWattage() == another.getTotalWattage());for (int i = 0; i < 10; i++) {floorlamp.On(50);another.On(50);std::cout << "compare " << floorlamp.getTotalWattage() << " "<< another.getTotalWattage() << std::endl;}Which results in this output:compare 240 240compare 240 240compare 180 240compare 120 240compare 120 240compare 120 240compare 120 120compare 120 120compare 120 120compare 120 12011.1 Bulb Class Declaration [ / 14 ]The Bulb class is missing only one function. You will need to read the rest of the problem to determine what’smissing. Fill in the missing function – implement the function right here, within the class declaration.17class Bulb {public:// constructorsBulb(int w, int l, const std::string &b) :wattage(w),lifetime(l),hours_used(0),brand(b) {}sample solution: 2 line(s) of code// accessorsint getWattage() const { return wattage; }bool burntOut() const { return hours_used > lifetime; }const std::string& getBrand() const { return brand; }// modifiervoid On(int h) { hours_used += h; }private:// representationint wattage;int lifetime;int hours_used;std::string brand;};11.2 Lamp Class Declaration [ / 14 ]The Lamp class has a few more missing pieces. Read through the rest of the problem before attempting to fillthis in. Write the prototypes (not the implementation!) for the four missing functions. You will implementsome of these missing functions later. Also, fill in the member variables for the Lamp representation.Important: You may not use STL vector on this problem.class Lamp {public:// constructors, assignment operator, destructorsample solution: 4 line(s) of code18// accessorint getTotalWattage() const;// modifiersbool install(const Bulb &b = Bulb(0,0,""));void On(int h);private:// representationsample solution: 3 line(s) of code};Lamp Class ImplementationHere’s the implementation of one of the key member functions of the Lamp class.bool Lamp::install(const Bulb &b) {// first, let's figure out where to install the bulbint which = -1;for (int i = 0; i < max_bulbs; i++) {// check for an empty socketif (installed[i] == NULL) {which = i;break;}// or a socket that contains a burnt out bulbif (installed[i]->burntOut()) {which = i;delete installed[i];break;}}// return false if we cannot install this bulbif (which == -1) return false;if (b.getWattage() == 0) {// install the manufacturer's recommended bulb typeinstalled[which] = new Bulb(recommended);} else {// install the specified bulbinstalled[which] = new Bulb(b);}return true;}On the last two pages of this problem you will implement three important functions for the Lamp class, asthey would appear outside of the class declaration (in the lamp.cpp file) because their implementationsare > 1 line of code.1911.3 Lamp Constructor [ / 9 ]sample solution: 7 line(s) of code11.4 Lamp Destructor [ / 5 ]sample solution: 8 line(s) of code2011.5 Lamp Assignment Operator [ / 9 ]sample solution: 10 line(s) of code2112 Singly Linked List Subsequence Sum [ / 18 ]Write a recursive function named FindSumStart that takes the head Node of asingly-linked list storing positive numbers. The function should return a pointerto the Node that begins a subsequence of numbers that ends in the sum of thatsubsequence. For example, given this sequence: 5 1 4 2 3 9 6 7 the functionshould return a pointer to the Node storing 4, because 4 + 2 + 3 = 9.template <class T>class Node {public:Node(const T& v): value(v),next(NULL) {}T value;Node* next;};sample solution: 15 line(s) of codeAssuming the sequence has n numbers, what is the order notation for the running time of your function?2213 Reverse Splice [ / 20 ]Write a function named reverse_splice that takes in 3 arguments: an STL list named data and twoiterators i and j. The function should reverse the order of the data between those iterators. For example,if data initially stores this sequence: 1 2 3 4 5 6 7 8 9 and i refers to 3 and j refers to 7, then afterthe call reverse_splice(data,i,j), data will contain: 1 2 7 6 5 4 3 8 9 , i will refer to element 7,and j will refer to element 3. Your function should return true if the operation was successful, and false ifthe request is invalid. Note: Your function may only use a constant amount of additional memory.sample solution: 21 line(s) of code2314 Doubly Linked Factorization [ / 17 ]class Node {public:Node(int v) :value(v),next(NULL),prev(NULL) {}int value;Node* next;Node* prev;};Write a recursive function named Factor that takes in two arguments, pointers to the head and tail Nodesof a doubly linked list. This function should look for a non-prime number in the linked list structure, breakthe Node into two Nodes storing two of its factors, and then return true. If all elements are prime thefunction returns false. For example, if we start with a 3 element list containing 35 30 28 and repeatedlycall Factor:PrintNodes(head);while (Factor(head,tail)) { PrintNodes(head); }This is the output:35 30 285 7 30 285 7 2 15 285 7 2 3 5 285 7 2 3 5 2 145 7 2 3 5 2 2 75 7 2 3 5 2 2 7You may write a helper function. You do not need to write the PrintNodes function.
...