Final Exam Study Guide Solutions

271 Final Exam Study Guide Answers

Dordal, Fall 2009

Here are a few suggested problems. They may involve the LCell (list cell) and TCell (Tree cell) declarations below:

class LCell<D> {
    private D data;
    private LCell<D> next;
    public LCell(D d, LCell<D> n) {data=d; next=n;}
    public D data() {return this.data;}
    public LCell<D> next() {return this.next;}
}

class TCell<D> {
    private D data;
    private TCell<D> left, right;
    public TCell(D d, LCell<D> l, LCell<D> r) {
        data=d; left = l; right = r;
    }
    public D data() {return this.data;}
    public TCell<D> left() {return this.left;}
    public TCell<D> right() {return this.right;}
}

1. Write a function to search a linked list of Strings, based on LCell<String>, for the string s. If the item is found, a pointer to that cell should be returned, otherwise null is returned.

    LCell<D> search(LCell<D> p, String s) {
          while (p!=null) {
                if (p.data().equals(s)) return p;
                p = p.next();
          }
          return null;
    }

There are other ways to organize this as well.

2. Write statements to create the LCell<String> list

       p -> [chicken] --> [turkey] --> [goose]

LCell<String> p = new LCell("goose", null);
                      p = new LCell("turkey", p);
                      p = new LCell("chicken", p);

Note the order.

3. Suppose we execute the following statements (all of p, q,r,s,t are LCell<String>)

    p = new LCell<String>("apple", null);
    p = new LCell<String>("pear", p);
    p = new LCell<String>("grape", p);

    r = new LCell<String>("fig", null);
    s = new LCell<String>("date", r);
    t = new LCell<String>("raisin", r);

Draw the lists pointed to by p, s, and t.

p --> [grape |-]---> [pear |-]---> [apple | X]

s --> [date |-]----
                         \
                           ---> [fig | X ]
                          /
t --> [raisin |-]--

r points to the fig cell.

4. Suppose the hash function used in creating a hash table of Strings is basedon the first letter:
    a --> 0
    b --> 1
    c --> 2
    d --> 3

Suppose hashTable = new LCell<D>[4] (an array of 4 pointers to LCells). Draw the table after the insertion of the following, in order:
    apple, banana, cherry, barley, artichoke, basil

0: --> artichoke --> apple
1: --> basil --> barley --> banana
2: --> cherry
3:

Later words are added to the front of their list.

5. Suppose we execute the following statements (all of p,q,r,s,t,u are TCell<String>):
    p = new TCell<String>("book", null, null);
    q = new TCell<String>("dog", null, null);
    r = new TCell<String>("cow", p, q);
    u = new TCell<String>("moo", null, null)
    t = new TCell<String>("pencil", u, null);
    s = new TCell<String>("frog", r, t);
Draw the tree. Which pointer represents the tree root? Is the tree an ordered tree?

                frog
              /     \
           cow        pencil
          /   \        /
        book dog    moo

Yes, it's an ordered tree.

6. Write statements as in #5 to create a tree of numbers:
          9
        /   \
       5     20
    / \   / \
     2 7 11   23

p = new TCell<Integer>(2, null, null);
q = new TCell<Integer>(7, null, null);
l = new TCell<Integer>(5, p, q);
// I'm reusing p and q now
p = new TCell<Integer>(11, null, null);
q = new TCell<Integer>(23, null, null);
r = new TCell<Integer(20, p, q);
root = new TCell<Integer>(9, l, r);

7. (a). In the tree above, rotate the node 5 to the root.

          5
        /   \
       2     9
            / \
           7   20
              / \
             11 23

(b). In the tree above, rotate the node 20 to the root.
          20
        /   \
       9     23
    / \    \
     5   11 23
    / \
   2   7

8. In the tree of problem 6, list the elements
    (a) following inorder traversal

    2 5 7 9 11 20 23

    (b) following postorder traversal

    2 7 5 11 23 20 9

    (c) following preorder traversal

9 5 2 7 20 11 23

    (d) following level-wise traversal

    9 5 20 2 7 11 23

9. In the following B-tree of degree 1 (so each node contains either 1 or 2 data values), insert the values 5, 6, and 7.

               [5]
              /   \
       [3]     [ 8]
         /   |     /    \
      [1]   [4]  [6,7] [9,10]

10. Consider the following tree; it was an AVL tree until we added 10:

       6
     /   \
    3     8
   /       \
2         9
             \
              10

(a). Which nodes have a "balance factor" (height of left subtree - height of right subtree) bigger than 1 (in absolute value)?

The only node with a balance factor >= 2 is 8.

(b). What is the result of doing rotations about those nodes?

       6
     /   \
    3     9
   /     / \
2     8   10

11. Suppose s is a stack, initially empty. We then execute the following:
    s.push(a)
    s.push(b)
    x = s.pop()
    s.push(c)
    s.push(d)
    y = s.pop()
    s.push(e)
What is on the stack, and what are the values of x and y?

x = b
y = d
s: a, c, e

12. Do problem 11 assuming that s is a queue instead of a stack, and that "push" represents "enqueue" and "pop" represents "dequeue".

x = a
y = b
s =c d e