Computer Science 3510
Summer 2001
Practice questions for midterm exam 2

This is a closed book test, but you may use one sheet of prepared notes.

  1. When doing object-oriented programming, you typically find that functions have one less parameter than do corresponding functions that are used in procedural (non-object-oriented) computing. For example, a procedural function to test whether a value x is present in a tree t has two parameters, x and t, but an object-oriented function has only one parameter, x. Explain why there is one less parameter.

  2. What is the purpose of a destructor for a class? What is the destructor for class River called? Under what circumstances is the destructor called?

  3. Does using classes and object-oriented programming usually make programs shorter than they would be using traditional methods?

  4. Object-oriented programming in C++ can be used to make it impossible to violate the abstraction of an abstract data type.

    1. What feature of C++ makes this possible?

    2. Programmers rarely deliberately sabotage their own work. Since programmers are not supposed to violate abstractions, why is it so important that a compiler prevent them from doing so? Can't programmers police themselves?

  5. Suppose that structure Polynomial is defined as follows. 
        struct Polynomial {
      int degree;
      double* coef;
      Polynomial(int n)
      {
        degree = n;
        coef = new double[d+1];
      }
    };
    Which of the following will create a polynomial with degree 5?
    1. Polynomial P(5);
    2. Polynomial(5) P;
    3. Polynomial P; Polynomial(5);
    4. Polynomial P; P(5);

  6. Suppose that structure Polynomial and variable P are defined as in the preceding problem. Which of the following will set the coefficient of P at index 1 to hold 3.5?
    1. P[1].coef = 3.5;
    2. P.coef[1] = 3.5;
    3. P.(*coef)[1] = 3.5;
    4. (*P).coef[1] = 3.5;

  7. Suppose that you insert 25 into the following tree using the algorithm that does rotations to keep the tree height-balanced. What is the resulting tree? 
                            81
                      /    \
                    20      100
                  /   \
               16      65

  8. Consider the following tree with integer keys. 
                          25
                    /    \
                  10      30
                        /    \
                      26      50

    1. Is this tree a binary search tree? That is, does it obey the ordering requirements?

    2. Ignoring the keys, is this tree height-balanced?

    3. If you were to use the standard (unbalanced) binary search tree insertion algorithm, show what this tree would look like after inserting 40.

    4. Is the tree height-balanced after inserting 40, without rebalancing?

  9. Suppose that you use the connection manager discussed in class to manage connections in a graph. Show how the superior array (called sup here) changes as each of the following operations are done. Use the algorithm that does not do either of the improvements -- the basic algorithm.

    In the diagram, the connect function is abbreviated c. So, for example c(2,4) indicates that we connect 2 and 4.

    i sup[i]
    1 1
    2 2
    3 3
    4 4
    5 5
    i sup[i]
    1 
    2 
    3 
    4 
    5 
    i sup[i]
    1 
    2 
    3 
    4 
    5 
    i sup[i]
    1 
    2 
    3 
    4 
    5 

  10. Using the type TreeNode shown, write a function called PrintEvens that prints the even numbers in a binary search tree in descending order, one number per line, skipping the odd numbers in the tree. (n is even if n%2 == 0.) For example, if t is the tree shown in problem 5, then PrintEvens(t) would print the numbers 100, 20 and 16, one per line, in that order. The function should not destroy the tree. 
          struct TreeNode {
        int key;
        TreeNode* left;
        TreeNode* right;
        TreeNode(TreeNode* l, int k, TreeNode* r)
        {
          left = l;
          key  = k;
          right = r;
        }
      };

  11. The binary search tree implementation that was discussed in class was nonpersistent; the insert operation, for example, changed the tree. It is possible to implement binary search trees in a persistent way also, so that they compute new trees from old ones.

    Using the type TreeNode of the previous problem, write a function removeMin(t) that returns the tree that would result from removing the smallest value from tree t, but that does not alter tree t. If t is empty, then removeMin(t) should return an empty tree. For example, if t is the tree 

                          81
                    /    \
                  20      100
                    \
                     65 
                   /    \
                 50      70
    then removeMin(t) should return the following tree, without altering tree t. 
                           81
                     /    \
                   65      100
                 /   \
               50     70
    Do not rebalance the tree. The new tree that you construct can share subtrees with t, as long as it does not change the subtrees. 
          TreeNode* removeMin(TreeNode* t)
      {