Final Exam 3 15 09 PIC 10B Winter 2009 NAME ID NUMBER Check your TA s name Aleka Bobby Josh You have 3 hours to complete this exam You are not allowed to use any books notes calculators or electronic devices Write your answers carefully Incomplete unintelligible or illegible answers will receive little or no credit When you are asked to write a program it is not necessary to comment your code but you are expected to indent appropriately to make your code easier to follow There are a total of 100 points on this exam PAGE 1 SCORE POSSIBLE 6 2 8 3 8 4 12 5 10 6 16 7 10 8 10 9 10 10 10 TOTAL 100 1 1 2 points When we overloaded the input and output operators for our different classes we had to make them non member friend functions Why could we not write these functions as member functions 2 2 points Prof Wittman had an idea for mapping each of the records in his hash table to a random bucket He defined his hash function on M buckets to be int getHash int M return rand M Prof Wittman coded up this method created his hash table and printed out the results It seems to give a hash table with uniformly distributed records and few collisions Explain why this approach is a bad idea 3 2 points Write the output of the function below when called with fun 25 void fun int x if x 0 return fun x 10 cout x 2 4 8 points Show how to sort the list of numbers below using the indicated sorting algorithm Show all steps 6 15 8 2 10 4 1 a Insertion Sort b Quick Sort using the left end as the pivot 3 5 8 points The following values are inserted in order into a heap H of integers 13 9 4 2 8 a Draw the heap H that results b Draw the heap that results after the operation int x H leave c What is the value of the variable x in part b 4 6 12 points Write the single line of C code that performs the following task a Create a hash table H with 10 buckets storing objects of type Clown indexed by an integer b Print the data in the 4th block of a LinkedList L c Print the largest value in a Tree T d For a string valued tree T print the height of the subtree rooted at the node containing the value Vader e Remove the record in the HashTable H with key Yoda f Remove the data from the front of a Queue Q and put it into a Stack S 5 7 10 points The integer valued binary tree T is shown below a What is the height of this tree b What is the depth of the 35 node c What are the leaves of this tree d Write the pre order traversal of the tree e What is the output of the command below T printPostOrder cout T findMaximum T getRoot f Draw the tree that results after the root node is erased 6 8 8 points Overload the output push for the Stack class to print all the data elements each on a separate line You may assume that the templated data type that the list is storing can be printed You may also assume that your function was declared as a friend of the Stack class To receive full credit your function should run in O N time and should leave the original stack intact An example usage is shown below Stack string S S push YODA S push VADER S push LUKE cout S Hint Recall we named the pointer in the StackNode class down 9 8 points Overload the operator for the LinkedList class to define the piecewise addition of two linked lists You may assume the two lists being added have the same size store the same templated type T and that addition is defined for the type T Your function should run in O N time An example is shown below 7 10 10 points Write the copy constructor for the LinkedList class Your function should run in O N time 8 11 10 points Write a member function resize for the HashTable class that changes the number of buckets in the hash table All data in the original table should be preserved but possibly mapped to new locations by the hash function An example is shown below for a hash table storing objects of type Record indexed by a string 9 12 10 points Recall that the selection sort algorithm sorts a data set by repeatedly finding the minimum value and swapping it to the front of the list Write a function selection sort which performs selection sort on a templated vector Your answer should be self contained and should not require any other functions be written 10 13 10 points Suppose we have a templated class Yoda that has as its private variables a templated dynamic array called list and an integer size that tracks the number of elements in the array template typename T class Yoda public Yoda Possibly more functions private T list int size a Write the destructor for the Yoda class b Write the assignment operator for the Yoda class 11 LinkedList Stack Queue template typename T class LinkedList public LinkedList LinkedList int numNodes T defaultValue LinkedList void insert Iterator T iter T value void erase Iterator T iter T operator int index const T operator int index int size Iterator T begin Iterator T end private Node T first Node T last template typename T template typename T class Node class Iterator public public Node T value Iterator template typename T T get const friend class LinkedList void forward private void backward T data bool isNull template typename T Node T next Node T prev friend class LinkedList private Node T position template typename T template typename T class Stack class Queue public public Stack Queue bool isEmpty bool isEmpty Stack Queue void push T value void enter T value T pop T leave private T peek StackNode T top private QueueNode T front QueueNode T end 12 Tree Heap HashTable template typename T class Tree public Tree Tree TreeNode T getRoot const TreeNode T find T value TreeNode T parent TreeNode T child void insert T value void erase TreeNode T pos TreeNode T findMaximum TreeNode T rootNode TreeNode T findMinimum TreeNode T rootNode TreeNode T nextInOrder TreeNode T pos void printInOrder ostream out TreeNode T rootNode void printPostOrder ostream out TreeNode T rootNode void printPreOrder ostream out TreeNode T rootNode int size TreeNode T rootNode int height TreeNode T rootNode private TreeNode T root template typename T template typename T class TreeNode class Heap public public TreeNode T value Heap T getValue const bool isEmpty const template typename T void enter T value friend class Tree T leave private T peek const T data private TreeNode T left vector T v TreeNode T right void swap int i int j template typename T …