Final W08 Solutions

PIC 10B Final Exam KEY Winter 2008 Prof. Todd Wittman 1.) [2 points] List 2 important differences between heaps and binary search trees. i. Ordering is different. Trees put smaller values to left of parent, larger values to right. Heaps require parent is smaller than both children. ii. The shape of a heap is fixed; the levels are filled top to bottom, left to right. Trees can have any shape, depending on order the values are inserted. iii. Heaps can only access the element at the top (root). Trees can insert, erase, or find any node in the tree. 2.) [2 points] The Heap class we built did not contain a destructor or copy constructor. Explain why this was not necessary. The Big 4 are only necessary for dynamic memory. Heap has a vector as a private variable, so we get destructor, copy constructor, and operator= automatically. 3.) [2 points] On travel websites such as Priceline, the cheapest airline ticket is reported to the customer. Once that ticket is purchased, it is removed from the database and the next cheapest is shown to the next customer. What data structure would be best for managing this data and why? A heap is best since it will return the minimum price ticket in O(logN) time. 4.) [2 points] Darth Vader is enrolled in PIC 10B and he noticed something rather odd in his HW9 write-up. When he placed all the words in the English language into his hash table, he got tens of thousands of collisions even when he set the number of buckets very large. Explain to Darth why there are so many collisions on this data set. The hash function just adds up the integer values of the chars in the word. So order does not matter and anagrams like "dog" and "god" always map to the same bucket. 5.) [2 points] What is a friend function? A friend function is a non-member function that has access to the private variables of a class. 6.) [14 points] Write the single-line of C++ code that accomplishes the following task. a.) Create a hash table H with M buckets storing student records of type R, sorted based on the student's name. HashTable H(M); b.) Look up (but do not remove) the minimum value in a heap H and store it in a pre-existing variable v. v = H.peek(); c.) Look up (but do not remove) the minimum value in a tree T and store it in a pre-existing variable v. v = T.findMinimum(T.getRoot())->getValue(); d.) Erase the last element in a linked list L. L.erase(L.end()); e.) Erase the record with key "YODA" in a hash table H. H.erase(H.find("YODA")); f.) Print out the number of nodes in a linked list L. cout << L.size(); g.) Erase the parent of the node containing the string "Vader" in a tree T. T.erase(T.parent(T.find("Vader"))); 7.) [8 points] Show how to sort the list of numbers: 14, 3, 8, 10, 2, 4, 9, 7 a.) Insertion Sort Insert 3 before 14 3, 14, 8, 10, 2, 4, 9, 7 Insert 8 before 14 3, 8, 14, 10, 2, 4, 9, 7 Insert 10 before 14 3, 8, 10, 14, 2, 4, 9, 7 Insert 2 before 3 2, 3, 8, 10, 14, 4, 9, 7 Insert 4 before 8 2, 3, 4, 8, 10, 14, 9, 7 Insert 9 before 10 2, 3, 4, 8, 9, 10, 14, 7 Insert 7 before 8 2, 3, 4, 7, 8, 9, 10, 14 b.) Quick Sort using the right end as the pivot 14 3 8 10 2 4 9 7 3 2 4 7 14 8 10 9 3 2 4 7 8 9 14 10 2 3 4 7 8 9 10 14 1 8.) [3 points] Draw the binary tree that results when the following values are inserted in order. 6, 8, 3, 2, 9, 1 6 3 8 2 9 1 9.) [3 points] Draw the heap that results when the following values are inserted in order. 5, 8, 2, 3, 10 2 3 5 8 10 10.) [6 points] Given the binary tree T below. a.) What are the leaves of the tree? 3, 10, 16 b.) What is the depth of the 9 node? 2 c.) Write the pre-order traversal of the tree. 8, 5, 3, 12, 9, 10, 20, 16 d.) Draw the tree that results after the command: T.erase(T.getRoot()); 9 5 12 3 10 20 16 11.) [2 points] Given the heap H below. Draw the heap that results after the command: int x = H.leave(); 12.) [8 points] Write a member function for the HashTable class that returns the number of records in the largest bucket. (You may write your function from HW9.) template int HashTable::largestBucket( ) { int largest = 0; for (int i=0; i largest) largest = table[i].size(); return largest; } 2 13.) [8 points] Overload the output push << for the Heap class so that the command cout << myHeap; would print all the values in the heap myHeap, sorted from smallest to largest and separated by a blank space. When the function is complete, the heap should remain the same. Write the function as a non-member non-friend function. (Hint: create a second temporary heap.) template ostream& Heap::operator<< (ostream& out, const Heap& right) { Heap tempHeap = *this; while (!tempHeap.isEmpty()) out << tempHeap.leave() << " "; return out; } 14.) [14 points] Write a member function for the LinkedList class called isInList that takes an Iterator as input and a value as input. The function searches forward from the Iterator's position and returns TRUE if the given value is in the list, FALSE if that value is not in the list. An example usage is shown below. a.) Write a non-recursive version of the isInList function. template bool LinkedList::isInList (Iterator iter, T value) { while (iter.position != NULL) { if (iter.get() == value) return true; iter.forward(); } return false; } b.) Write a recursive version of the isInList function. Your answer should contain no loops. template bool LinkedList::isInList (Iterator iter, T value) { if (iter.position == NULL) return false; if (iter.get() == value) return true; iter.forward(); return isInList(iter, value); } 15.) [8 points] Write a copy constructor for the LinkedList class. template LinkedList::LinkedList (const LinkedList& right) { Iterator left_iter = begin(); Iterator right_iter = right.end(); while (right_iter.position != NULL) { insert(left_iter, right_iter.get()); left_iter.backward(); right_iter.backward(); } } 3 16.) [8 points] Write a member function for the LinkedList class that removes all duplicate values from the list. When the function is done, only the first occurrence of each value should remain. Recall that the erase function moves the Iterator to the next node in the list after it deletes a node. template void LinkedList::removeDuplicates( ) { Iterator iter1 = begin(); Iterator iter2; while (iter1.position != NULL) { iter2 = iter1; iter2.forward(); while (iter2.position != NULL) { if (iter2.get() == iter1.get()) erase(iter2); else iter2.forward(); } iter1.forward(); } return; } 17.) [8 points] Suppose we have a templated class Empire whose private variables consist of a dynamic array list and an integer size that tracks the number of elements in the array. Write the assignment operator= function for the Empire class. Empire& Empire::operator= (const Empire& right) { if (this != &right) { delete[] list; size = right.size; list = new T[size]; for (int i=0; i