Practice Exam 2 - CSC 222: Data Structures and Algorithms, Spring 2008

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.

(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).

bool printSmallest(const node<int> *root)
{
    // Handle the base case of an empty tree:
    if (root == 0) return false;
    
    // Now check in the left child:
    if (printSmallest(root->left)) return true;
    
    // Not found to the left -- check root:
    if (test(root->nodeValue)) {
        cout << root->nodeValue;
        return true;
    }
    
    // Last chance -- try the right child:
    return printSmallest(root->right); 
}

(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).

(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;

be inserted
be not inserted
not inserted
or inserted
to inserted
to not inserted
be not or to

(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 distinct keys that will require the maximum amount of probing to insert in an initially empty table.

10, 20, 30, 40, 50 (or any sequence where all the keys have the same value mod 10)

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

In the worst case, each insertion will require a number of probes equal to the number of entries already in the table, plus one. Therefore, we need the sum 1 + 2 + 3 + ... + N, which is O(N²).

(4 points) Show the 2-3-4 tree that results from inserting the values 42, 19, 37, 65, 55, 49, and 51, in order.

     37,55
   /   |    \
  /    |     \
19  42,49,51  65

(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).

(3 points) Show the result of inserting the number 45 in the above red-black tree.

      49
     /  \
  37*    55*
 /  \   /  \
19  42 51  65
      \
       45*

The easiest way to see this is to work with the corresponding 2-3-4 tree, where the 49 had to split up into the root node:

    37,49,55
   /  |   \  \
19  42,45  51  65