CSC 222: Data Structures and Algorithms, Fall 2008

Practice Exam 1

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.

1. Consider the following 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 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 only if a number was printed).
2. What is the output of the following sequence of operations if 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();
   

   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)?

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

3. Write a C++ function 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.
4. Write a similar function that takes a list<int> argument instead of a vector<int>.
5. 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 call tree that results from the function call fibber(5).
6. Fill in the two missing pieces of the following code so that it handles the dynamically-allocated storage correctly (the context here is that some systems limit the amount of space for stack-allocated variables, so you may not be able to declare a local variable such as 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 ints 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:
   
   
   }
   
   test& test::operator=(const test& rhs)
   {   // AND 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;
   }
   

   How many times will the test destructor be called in the above program?

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

8. Show the result after each step of inserting the numbers 42, 37, 4, 28, 17, and 33 into an initially empty AVL tree.

DePauw University, Computer Science Department, Fall 2008
Maintained by Brian Howard (bhoward@depauw.edu). Last updated