Data Structures & Algorithms

Exam 2

Sample 1, 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(){}; 
      BinaryTree<T>& SwapChildren();
   private:
      BinaryTreeNode<T> *root;  // pointer to root
};
```
The new member SwapChildren swaps the left and right children of every node in a binary tree. It returns *this.

(a)
[8] Write C++ code for the SwapChildren 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);
   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 Insert member function.
(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 <= 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