COM 301

Midterm Exam

1. Develop an algorithm that can be used to determine whether a Stack object S has exactly one element.

2. Develop an algorithm that adds the value val to a queue object Q. The queue is represented using an array data of size s. The algorithm should assume that the queue is not full. The most recently added item is at index r (rear), and the least recently added item is at index f (front). If the queue is empty, r = f = -1.

3. Develop an algorithm that removes the least recently added item from a queue Q. The queue is represented using an array of size s. The algorithm assumes that the queue is not empty. The most recently added item is at index r (rear), and the least recently added item is at index f (front). If the queue is empty, r = f = -1.

4. Develop an algorithm that computes the degree of each vertex in a graph. The graph is represented using adjacency lists A; A[i] is a reference to the first node in a linked list of nodes representing the vertices adjacent to vertex i. The next field in each node, except the last, references the next node in the list. The next field of the last node is null. The vertices are 1, 2, . . . .’

5. Develop a recursive algorithm that returns the number of nodes in a binary tree with root r.

6. Develop an algorithm that inserts the value val into a binary search tree with root.  If the tree is empty, root = null. The algorithm returns the root of the tree containing the added item. You should assume that “new node” creates a new node with data field data and reference fields left (for left child) and right (for right child).

7. Show each AVL tree created from each of the following insertion:  3, 2, 1, 4, 5,6,7,16,15,14

8. Show the AVL tree created by the following array {20,30,80,40,10,60,50,70}

9. Given the following Splay tree, show the resulting tree after removing the node labeled “6”.

10. Given the following B-tree of order 5, show the resulting trees after each of the following operations: (a) Insert 12 (b) Insert 53.

11. Prove that if n keys are uniformly distributed in m buckets, the number of comparisons in an unsuccessful search is given by n/m.

12. Show the heap built from this array {150  80  40  30 10  70 110  100  20  90 60  50 120 140 130}. Then fix the heap to become a priority queue tree.