Data Structures & Algorithms

Exam 2

Sample 2, 50 Minutes

An abbreviated version of the class BinaryTree of the text is given below.
```
template <class T>
class BinaryTreeNode {
   friend BinaryTree<T>;
   private:
      T data;
      BinaryTreeNode<T> *LeftChild,  // left subtree
                        *RightChild; // right subtree
};
template<class T>
class BinaryTree {
   public:
      BinaryTree() {root = 0;};
      ~BinaryTree(){}; 
      T DeepestElement();
   private:
      BinaryTreeNode<T> *root;  // pointer to root
};
```
The new member DeepestElement returns any one of the elements at the maximum level of the binary tree.

(a)
[8] Write C++ code for the DeepestElement member function. You may define and implement new private member functions as needed. You may not create or delete any nodes or invoke any binary tree functions not defined in this problem unless you provide code for these functions.
(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.


template<class T>
class MinHeap {
   public:
      MinHeap(int MinHeapSize = 10);
      ~MinHeap() {delete [] heap;}
      MinHeap<T>& Insert(const T& x);
      MinHeap<T>& DeleteMin(T& x);
      MinHeap<T>& ChangeMin(const T& x);
   private:
      T *heap;          // 1D array
      int CurrentSize,  // number currently in heap
          MaxSize;      // capacity of heap[]
};

template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{// Min heap constructor.
   MaxSize = MinHeapSize;
   heap = new T[MaxSize+1];
   CurrentSize = 0;
}

(a): [8] Write C++ code for the ChangeMin member function. This function replaces the current min element with x and restructures the min heap as necessary. You may not invoke either Insert or DeleteMin.
(b): [2] What is time complexity of your code as a function of CurrentSize?

(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 <= 7 and U _n <= 12 ?

(b)
[3] Suppose you start with a collection of n singleton sets and perform unions using the weighting rule. Prove that you never create a tree whose height exceeds floor(log ₂ n) + 1.

(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 preorder, the output is ADBCJGFEHI. Draw the binary tree showing the data in each node and the pointers between nodes.

Solutions