CPS 100, Fall 2002, Week #6

Answer the following questions and bring them to your recitation on Oct 21-23, 2002.

  1. Consider loading a stack and queue using the code below, this is the load code. tstack<int> t; tqueue<int> q; int k; for(k=0; k < 10; k++) { t.push(k); q.enqueue(k); }

    What is printed by the following after loading the stack using the load code.

    while (! s.isEmpty()) { cout << s.top() << endl; s.pop(); }

  2. What is printed by the following after loading the queue using the load code. while (! q.isEmpty()) { cout << q.front() << endl; q.dequeue(); }

  3. Consider the function popFromTo below. void popFromTo(stack<int>& from, stack<int>& to) { while (! from.isEmpty()) { to.push(from.top()); from.pop(); } } If stack s is loaded with 10 values using the load code, what are the contents of s after executing: stack<int> s2; popFromTo(s,s2); popFromTo(s2,s);

  4. What happens when the statement below executes? popFromTo(s,s);

  5. Write a function that returns the number of nodes with the info field set to "bug".

    Use the declaration for tree below in this problem and the next.

    struct TreeNode { string info; TreeNode * left, * right; TreeNode(const string& s, TreeNode * lptr, TreeNode * rptr) : info(s), left(lptr), right(rptr) { } };

    int BugCount(TreeNode * root) // post: return number of nodes in tree with info field set to "bug" { }

  6. Write a function that returns a copy of a tree. For every node in the tree passed as a paramter a new node should be constructed and linked into the tree being returned, the nodes should be in the same location relative to the right as in the original tree, i.e., the trees should be exact copies.

    TreeNode * copy(TreeNode * root) // post: return a copy of root { }


Susan H. Rodger
Last modified: Wed Oct 16 12:01:35 EDT 2002