CSCI 3300
Spring 2010
Exercises for Quiz 5

Some of these questions use the following type Cell, which is the same as the Cell type used in class.

    struct Cell
    {
      Cell* next;
      int   item;

      Cell(int i, Cell* n)
      {
        item = i;
        next = n;
      }
    };

Some of these problems use the following type, Node.

    struct Node
    {
      int   item;
      Node* left;
      Node* right;

      Node(int i, Node* L, Node* R)
      {
        item  = i;
        left  = L;
        right = R;
      }
    };

1. Write a definition of function isPrefix(A,B), which returns true if list A is a prefix of list B. Every list is a prefix of itself.

   Answer

2. Write a definition of function getPrefix(L, n), which returns a list of the first n members of list L. It must not modify list L. If n is greater than the length of L, then getPrefix(L, n) should return list L. In that case, the returned list can share the cells of L.

   Answer

3. Write a definition of function compare(A, B) that takes two lists A and B (type Cell*) and returns 0 if list A is equal to list B (meaning that the two lists contain exactly the same numbers, in the same order), returns -1 if list A is lexicographically less than list B, and returns 1 if list B is lexicographically less than list A. We say that list A is lexicographically less than list B if one of the following is true.

   1. A is empty but B is not.
   2. Both A and B are nonempty and A's head is less than B's head.
   3. Both A and B are nonempty and A's head is equal to B's head and A's tail is lexicographically less than B's tail.
   When you think in terms of strings instead of lists of integers, lexicographic order is just dictionary order, with the proviso that, if word w is a proper prefix of word t, then w comes before t.

   Answer

4. If you insert 26 into the following binary search tree by the basic insertion algorithm, what tree do you get?

   

   Answer

5. If you insert 27 into the following binary search tree by the basic insertion algorithm, what tree do you get?

   

   Answer

6. Write a function that writes all of the numbers in a binary search tree in ascending order on the standard output, one number per line. The function takes a parameter of type const Node*, pointing to the tree, and has a void return type.

   Answer

7. Assume that function insert(x, t) is available to you, where insert(x, t) inserts x into binary search tree t, modifying t.

   Write a definition of function insertAll(L, t), which takes a linked list L (type Cell*) and a binary search tree t (type Node*&) and inserts all members of list s into tree t.

   Answer