PIC 10B Practice Final Exam KEY 1 TRUE or FALSE If the answer is false briefly explain why the statement is false a Every key in a hash table must be unique TRUE b Every key in a hash table must map to a unique hash index FALSE This is how we get collisions c Hash table performance decreases as the number of buckets increases FALSE Performance generally increases with number of buckets d Hash table searches are linear in the number of records FALSE With no collisions searches are O 1 In general a hash table search is O K where K is the maximum number of records in one bucket e Searching a binary tree is at worst O logN FALSE A binary tree search is O h where h is the tree height A poorly built tree is at worst O N height So the worst case search is O N O logN is the cost of a search in the average case f In a binary tree the depth of the root node is 1 FALSE The depth of the root node is 0 g A string is a primitive data type FALSE A string is a STL class defined in the string library h The Big 4 functions must be defined for every class FALSE The Big 4 are never necessary although they are highly recommended for classes using dynamic memory The default constructor is always a nice thing to have for any class but it is not absolutely necessary i A binary tree can be recovered from its in order traversal FALSE A binary tree can be recovered from its pre order traversal but different trees will result in the same in order traversal as long as they contain the same values j A function that changes the private variables of a class must be written as a member function FALSE A non member friend function can change the private variables k If the declaration of the class Clown contains the line friend class Yoda written in its declaration then member functions of the Clown class can access the private variables of the Yoda class FALSE The member of functions of Yoda can access the private variables of Clown not the other way around Friendship is granted not taken 2 Using Big O Notation fill in the running time and memory requirement of the sorting algorithms when sorting N elements When referring to memory we are asking how many blocks are required in addition to the N blocks used to store the original list of elements Best Case Average Case Worst Case Memory Insertion Sort O N O N2 O N2 O 1 Quick Sort O NlogN O NlogN O N2 O 1 Merge Sort O NlogN O NlogN O NlogN O N Selection Sort O N2 O N2 O N2 O 1 3 When writing the operator definition for a class explain what it means to check for self assignment Why is this important In an assignment A B we include the statement if this right to check if the left side A is the same as the right side B already That is not just the values but the actual memory address is identical This is important to check so that we don t make unnecessary changes In some cases like with the dynamic array in our Matrix class omitting this check might result in a run time error by accidentally deleting the array before we copy it 4 A hash function should map keys to an index in the range 0 M 1 where M is the number of buckets Since the mapping should be as uniform as possible to avoid collisions Prof Wittman decides to use a uniform random distribution index rand M Explain what is wrong with Prof Wittman s hash function This hash function would assign a record say Luke Skywalker to a random bucket in the range 0 M 1 But then when we tried to search for the record with the key Luke Skywalker we would know which bucket to look in because the record was put in a random spot A hash function cannot be based on random numbers The hash function must be reproducible for us to do searches 5 In our HashTable class which of the Big 4 functions did we write Explain why these functions were or were not written We didn t write any of the Big 4 for the HashTable class We didn t create a default constructor because the size of the hash table should depend on the specified number of buckets M We don t need the other 3 copy constructor assignment operator destructor because our HashTable was built out of vectors so these 3 functions will be created automatically for us 6 Write the single line of C code to accomplish the following tasks a Create a hash table H storing objects of class Clown indexed by the Clown s integer ID number HashTable Clown int H M M is number of buckets b Print out the record in a hash table H whose key is the string Yoda cout H find Yoda Remember find returns a pointer not the actual record c Erase the record in the hash table H whose key is the string Luke H erase H find Luke d Sort a list of integers in the vector V using merge sort merge sort V 0 V size 1 e Print out the post order traversal of a binary tree T T printPostOrder cout T getRoot f Erase the parent of the node containing the string Vader in a binary tree T T erase T parent T find Vader 7 Given the recursive function yoda below determine what is printed out when yoda 74 5 is called and when yoda 74 7 is called void yoda int n int b if n b yoda n b b cout n b It s a trick In both cases it never makes the recursive call because the original n b So it prints 74 5 4 for the first function and 74 7 4 for the second function yoda 74 5 4 yoda 74 7 4 For practice you should see what it prints when we send yoda 5 74 8 A record class contains a string and an integer A hash table is built from this class using the integer as the key and the division method as the hash function Draw the hash table that results when the following records are inserted in the order given into a hash table with M 6 buckets 15 21 24 11 32 33 5 Luke Yoda Leia Vader Lando Han Chewbacca 9 Show how each of the methods sorts the list of integers below by writing out the vector at each step of the sorting algorithm 15 20 3 9 25 30 2 5 a Selection Sort Better if you draw arrows to show the swaps Original 15 20 3 9 25 30 2 5 Swap 2 5 2 20 3 9 25 30 15 5 Swap 20 3 2 3 20 9 25 30 15 5 …