581325-0 Data Structures, 2nd intermediate exam April 9 2003/AW
Write at the top of each paper the name of the course, the exam date,
your name, social security number and your signature.
Write each answer on a separate paper!
The AVL-tree is initially empty. The keys
33, 63, 23, 40, 38, 57
are inserted to the tree.
Draw a picture of the AVL-tree after these insertions.
Then the keys
1, 2, 3, 4
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 key
2
is deleted by the remove-operation.
Draw a picture of the tree after these deletions,
when remove is implemented using the principle
"the maximum of left subtree"
when remove is implemented using the principle
"the minimum of right subtree".
Is the tree anymore an AVL-tree after these deletions? If not,
when and how did the AVL-feature disappeared?
(8 points)
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.
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.
public Comparable deleteMin()
returns a reference to the smallest element in the heap and deletes it
from the heap.
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)
Describe in detail the implementation of graph as adjacency
matrix and adjacency list.
Program a method that prints the number of edges going from and
coming
to the vertices in a graph represented as an adjacency matrix.
Program a method that prints the number of edges going from and
coming
to the vertices in a graph represented as an adjacency list.