CSC 222: Data Structures and Algorithms, Fall 2006

Practice Exam 2

This exam is open-book and open-note. Please allow some time to check your work. If you need extra space, write on the back.

1. (5 points) Consider the tnode class template from the text (trimmed a little for space):

   template <typename T>
   class tnode {
   public:
       T nodeValue;
       tnode<T> *left, *right;
       
       tnode(const T& item, tnode<T> *lptr = 0, tnode<T> *rptr = 0) :
           nodeValue(item), left(lptr), right(rptr) { }
   };
   

   Suppose that root points to a binary search tree of ints (ordered by the usual < relation). Given a function test from int to bool, write an efficient function with the following prototype:

   bool printSmallest(const node<int> *root)
   

   which searches for the smallest value n in the tree such that test(n) is true. If such an n is found, it should print n to cout and return true; otherwise, it should return false and not print anything. For example, if test(n) returns true when n is even, and false otherwise, then printSmallest(root) should print the smallest even number (if any) in the tree pointed to by root (and return true if a number was printed).
2. (4 points) Consider the following C++ function:

   tnode<int> *fibber(int n)
   {
       if (n <= 1) return 0;
       tnode<int> *p = fibber(n - 1);
       tnode<int> *q = fibber(n - 2);
       return new tnode<int>(n, p, q);
   }
   

   Draw the tree that results from the function call fibber(5).
3. (4 points) What is the output of the following C++ code?

   multiset<string> m;
   m.insert("to"); m.insert("be"); m.insert("or");
   m.insert("not"); m.insert("to"); m.insert("be");
   
   set<string> s;
   multiset<string>::const_iterator it;
   for (it = m.begin(); it != m.end(); ++it) {
       cout << *it;
       pair<set<string>::iterator, bool> p = s.insert(*it);
       if (p.second) cout << " inserted" << endl;
       else cout << " not inserted" << endl;
   }
   
   set<string>::const_iterator sit;
   for (sit = s.begin(); sit != s.end(); ++sit) {
       cout << *sit << " ";
   }
   cout << endl;
   

4. (4 points) Suppose we have a hash table using linear probe open addressing where the key values are integers and the hash function is simply the identity function. Therefore, if the table has size m, the key k will hash to the index k mod m (that is, k % m). Let m = 10 and give an example of a sequence of five keys that will require the maximum amount of probing to insert in an initially empty table.

   What is the big-O running time of the worst case for inserting N values in an open-addressed hash table of size 2N?

5. (4 points) Show the 2-3-4 tree that results from inserting the values 42, 19, 37, 65, 55, 49, and 51, in order.
6. (2 points) Draw a red-black tree that corresponds to the result of the previous question (mark the red nodes with a star or some other special notation).
7. (3 points) Show the result of inserting the number 45 in the above red-black tree.

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated