CSC 241- Exam 3        Name:

1. Describe the general strategy for the two O(n log n) sorting algorithms (quickSort and mergeSort).

2. Identify the characteristics of a binary search tree.

3. Consider the following Binary Search Tree:

                                    root_
                                     67
                                   /    \
                                  /      \
                                43        76
                               /  \      /  \
                             12    55  70    90

Also, consider the following declaration of treeNode:

   class treeNode {
       Keyed element_;
       treeNode left_;
       treeNode right_;
       treeNode (Keyed k, treeNode l, treeNode r) {
         left_=l;
         right_=r;
         element_=k;
       }
    }

a. Insert a 75 into the above tree. No Code, simply redraw the tree with 75.

b. What is in root_.right_.right_.element_?

c. Delete 43 from the original tree shown above. Redraw the complete tree with your changes.

d. Write the method that returns the element with the largest key in a BST.

  public elementType largest (treeNode root) {         
    if (root == null) return null;






  }

e. Write a recursive method that would print all elements of a tree in the ascending order of their keys.

  public void print (treeNode root) {         
    if (root == null) return;

4.How would you print all elements in a hash table?

5.Remember that Tree is a class that implements the interface Set. Here is the definition of Set:

public interface Set {
  public void add(elementType e) throws duplicateException;
  public void remove(String k) throws notFoundException;
  public elementType find (String k);
  public int size();
  public void dump();
  public Object[] toArray();
}

Consider the following wordAndMeaning class that implements the elementType interface:

public class wordAndMeaning implements elementType {
   String word_;
   String meaning_;
   String key() {return word;}
   String stringView() {return "key= " + word_ + " Name= " + meaning_;}
   wordAndMeaning (){}
}

try {
  System.out.println("Enter word: ");
  String word=istream.readLine();
  System.out.println("Enter new Meaning: ");
  String meaning=istream.readLine();
  wordAndMeaning w_and_m = new wordAndMeaning();
  .
  .
  .
}
catch(..)