Final Review - INFS 519 Fall 2011

Here are a handful of questions which are similar to those on the actual final.

class BinNode<T> {
  BinNode left;
  BinNode right;
  T data;

  public BinNode(T data) {
    this.data = data;
  }

  // More stuff below
}

class BinTree<T> {
  BinNode<T> root;

  public BinTree() {
    root = null;
  }

}

• 1. Write a recursive function that finds the minimum value in a binary tree, using the BinNode and BinTree classes above.
  

• 2. In open-address hashing, how can double hashing be used to avoid clustering?
  

• 3. When representing a complete binary tree as an array, what is the formula to find the left child of the node at index i? (You can derive it if you know how a complete binary tree is stored in an array.)
  

• 4. Compare and contrast merge sort, quicksort, and heapsort.
  

• 5. Mark which nodes are visited during a breadth-first traversal of the depicted graph beginning at node A, including the numeric order. For example, the start node, A, would be numbered with 1 since it's the first node visited in the traversal. Please feel free to mark up the included Figure 1 or sketch your own copy. Please show your answer with a copy of the graph.
  

• 6. Add the integer 17 to the B-tree in Figure 2. Please draw the resulting B-tree after adding the new value and fixing any excessively sized nodes.
  

  

  Figure 1. A directed graph

  

  Figure 2. A B-tree with min = 1, max = min * 2 = 2

Validate XHTML 1.0