Overview | Schedule | Resources | Assignments | Home |
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.
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 int
s (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); }
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)
.
5 / \ 4 3 / \ / 3 2 2 / 2
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
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?
37,55 / | \ / | \ 19 42,49,51 65
37 / \ 19 55* / \ 49 65 / \ 42* 51*
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
Overview | Schedule | Resources | Assignments | Home |
DePauw University,
Computer Science Department,
Fall 2006
Maintained by Brian Howard
(bhoward@depauw.edu
).
Last updated