Practice Exam 1 - 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.

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

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); 
}

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

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

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.

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.

Write a similar function that takes a 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;
}

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

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:

    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?

3 times -- once each for a and b at the end of main, and once for x (which was passed a copy of a) at the end of f.

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;

be inserted
be not inserted
not inserted
or inserted
to inserted
to not inserted
be not or to

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

Insert 42:

Insert 37:

   42
  /
37

Insert 4:

     42         37
    /          /  \
  37     ==>  4    42
 /
4

Insert 28:

Insert 17:

   37               37
  /  \             /  \
 4    42         17    42
  \       ==>   /  \
   28          4    28
  /
17

Insert 33:

     37               28
    /  \             /  \
  17    42         17    37
 /  \       ==>   /     /  \
4    28          4    33    42
       \
        33