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, which represents a binary tree node
where each node is labeled with a value of type T
:
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
only 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); }
x
is declared as a stack<char>
?
x.push('h'); x.push('e'); x.push('l'); cout << x.top(); x.pop(); cout << x.top(); x.pop(); x.push('l'); x.push('o'); cout << x.top(); x.pop(); cout << x.top(); x.pop(); cout << x.top(); x.pop();
leolh
What would the output be from the same sequence if x
were
declared as a priority_queue<char>
(where characters later in
the alphabet have higher priority)?
lhole
Finally, what would the output be from the same sequence if x
were declared as a queue<char>
and the x.top()
operations
were replaced by x.front()
?
hello
int countBelow(const vector<int> &v, int n)
which will
return the number of items strictly less than n
found in the vector
v
. You should not assume anything about the ordering of the items
in the vector.
int countBelow(const vector<int> &v, int n) { int count = 0; for (int i = 0; i < v.size(); i++) { if (v[i] < n) count++; } return count; }Or, use the iterator version below, with the appropriate type changes.
list<int>
argument
instead of a vector<int>
.
int countBelow(const list<int> &v, int n) { int count = 0; for (list<int>::const_iterator it = v.begin(); it != v.end(); it++) { if (*it < n) count++; } return count; }
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 call tree that results from the function call
fibber(5)
.
5 / \ 4 3 / \ / 3 2 2 / 2
int a[N]
when N
is a million; instead, you can declare
a
to be an object of class test
, and the only space
required on the system stack will be for the data
pointer--the
million int
s will be allocated from the heap):
const int N = 1000000; class test { public: test() : data(new int[N]) { } test(const test& x); ~test(); test& operator=(const test& rhs); int& operator[](int i) { return data[i]; } const int& operator[](int i) const { return data[i]; } private: int *data; }; test::test(const test& x) : data(new int[N]) { for (int i = 0; i < N; i++) data[i] = x[i]; } test::~test() { // FINISH THIS:
delete[] data;
} test& test::operator=(const test& rhs) { // AND THIS:
for (int i = 0; i < N; i++) data[i] = rhs[i]; return *this;
}
What will be the output from the following program using this class?
void f(test x, test& y) { x[42] = 2 * y[42]; y = x; } int main() { test a; a[42] = 17; test b = a; f(a, b); cout << a[42] << " " << b[42] << endl; }
17 34
How many times will the test
destructor be called in the above
program?
a
and b
at the end of main
, and once for x
(which was passed
a copy of a
) at the end of f
.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
42
42 / 37
42 37 / / \ 37 ==> 4 42 / 4
37 / \ 4 42 \ 28
37 37 / \ / \ 4 42 17 42 \ ==> / \ 28 4 28 / 17
37 28 / \ / \ 17 42 17 37 / \ ==> / / \ 4 28 4 33 42 \ 33
Overview | Schedule | Resources | Assignments | Home |
DePauw University,
Computer Science Department,
Fall 2008
Maintained by Brian Howard
(bhoward@depauw.edu
).
Last updated