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).
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)
.
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;
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.
What is the big-O running time of the worst case for inserting N values in an open-addressed hash table of size 2N?
Overview | Schedule | Resources | Assignments | Home |
DePauw University,
Computer Science Department,
Spring 2008
Maintained by Brian Howard
(bhoward@depauw.edu
).
Last updated