Data Structures & Algorithms

Exam 2, Sample 1

75 Minutes

An abbreviated version of the classes BinaryTreeNode and LinkedBinaryTree of the text is given below.
```
public class BinaryTreeNode
{
   // package visible data members
   Object element;
   BinaryTreeNode leftChild;    // left subtree
   BinaryTreeNode rightChild;   // right subtree
}

public class LinkedBinaryTree
{
   // instance data member
   BinaryTreeNode root;  // root node

   public void swapChildren()
   {
      // code for this method comes here
   }
}
```
The method swapChildren swaps the left and right children of every node in the binary tree this.

(a)
[8] Write Java code for the method swapChildren. You may define and implement new private member methods as needed. You may not create or delete any nodes or invoke any binary tree methods not defined in this problem unless you provide code for these methods.
(b)
[2] What is time complexity of your code as a function of the number of nodes in the binary tree?

A condensed version of the class MinHeap is given below.


public class MinHeap
{
   // data members
   Comparable [] heap;   // array for complete binary tree
   int size;             // number of elements in heap

   // constructor
   /** create a heap with the given initial capacity */
   public MaxHeap(int initialCapacity)
   {
      if (initialCapacity < 1)
         throw new IllegalArgumentException
            ("initialCapacity must be >= 1");
      heap = new Comparable [initialCapacity + 1];
      size = 0;
   }
   
   /** put theElement into the heap */
   public void put(Comparable theElement)
   {
      // code for this method comes here
   }
}

(a): [8] Write Java code for the put method.
(b): [2] What is time complexity of your code as a function of size?

(a)
[3] The expected performance of chained hash tables is given by the equations:
S _n = 1 + alpha/2
U _n = (1 + alpha)/2
where alpha >= 1 is the loading density n/b, n is the number of elements in the table, and b is the number of buckets. Suppose that the hash function in use is division and that we expect to have at most 81 elements in the hash table. What divisor do you recommend using so that S _n <= 4 and U _n <= 2 ?

(b)
[3] Draw a tree that represents a set of elements. The depth of your tree should be at least 7. Show the tree that results following the operation find(e), where e is an element at level 7 and we are using path compaction.

(c)
[4] Suppose you have a binary tree whose data fields are single characters. When the data fields of the nodes are output in inorder, the output is ABCDEFGHIJ, and when they are output in postorder, the output is BDCAEHGJIF. Draw the binary tree showing the data in each node and the pointers between nodes.

Solutions