581325-0 Data Structures, 2nd intermediate exam April 11 2001/AW

1. The AVL-tree is initially empty. The keys 21, 23, 165, 203, 204 and 546 are inserted to the tree. Draw a picture of the AVL-tree after these insertions.

   Then the keys 15, 14, 22, 12 and 9 are inserted. Draw a picture of the AVL-tree after these new insertions.

   Finally the AVL-tree is considered as a normal binary search tree; The keys 203 and 21 are deleted by the remove-operation. Draw a picture of the tree after these deletions. (There are two ways to implement the remove; here we use the principle of "the maximum of left subtree".)

   Is the tree anymore an AVL-tree after these deletions? If not, when and how did the AVL-feature disappeared?

                                                                 (6 points)
   
   
   
   
   

2. 1. Describe a so-called hash function. What is it and how does it work? On what grounds may it be evaluated? Give examples of good and bad hash functions.

   2. The interface Hashable is specified as follows.

        public interface Hashable {
          public int hash(int sizeOfArray);
        }
      

      In open addressing, a linear probing is used. Program the following method.

      • public void insert(Hashable value)
        inserts the value to the hash table; if it was already found, nothing changes.

      Describe the details of the hashing as much as is needed to understand the implementation of the operation.

                                                                 (6 points)
   
   
   
   
   
   

3. The elements of a binary heap are Comparable objects:

     public interface Comparable {
       public int compareTo(Object anOther);
     }
   

   The heap is implemented in sequential order to an array. Program the following operations of the heap.

   1. public boolean insert(Comparable element)
      inserts the object given as parameter to the heap; the method returns true if the addition is possible, and false if the heap is full.
   2. public Comparable deleteMin()
      returns a reference to the smallest element in the heap and deletes it from the heap.
   3. public static void makeToHeap(Comparable[] array)
      arranges any Comparable array given as parameter into a minimum heap in time O(n).
   Describe the details of the heap implementation as much as is needed to understand the implementations of the operations.

                                                                 (8 points)
   
   
   
   

4. 1. Describe in detail the implementation of graph as adjacency matrix and adjacency list.

   2. Program a method that prints the number of edges going from and coming to the vertices in a graph represented as an adjacency matrix.

                                                                 (5 points)