1. Tree problems. (a) [10 points] Traverse the following binary tree using the

1. Tree problems.
(a) [10 points] Traverse the following binary tree using the four traversal algo
rithms: Preorder traversal, inorder traversal, postorder traversal, and level
order (or breadth-first) traversal.
(b) [10 points] Draw the binary search tree that results from the following op
erations in that order into an initially empty binary search tree: insert 70,
insert 40, insert 30, insert 80, insert 50, insert 20, delete 50, insert 90, insert
10, delete 70, insert 70. You are only required to show the final tree.
(c) [10 points] Draw the (2, 4) tree that results from the following operations in
that order into an initially empty tree: insert 70, insert 40, insert 30, insert
80, insert 50, insert 20, insert 90, insert 10, insert 70, insert 100, insert 60.
You are only required to show the final tree
2. Heap problems.
(a) [5 points] Draw the min-heap (tree representation) that results from the fol
lowing operations in that order into an initially empty min heap: insert 30,
insert 40, insert 10, deletemin, insert 20, insert 30, deletemin, insert 40, in
sert 20, insert 70, insert 50, deletemin, insert 60, insert 20. You should not
insert duplicate elements into the heap. You are only required to show the
f
inal tree.
1
(b) [10 points] Givenanarray, designanefficientalgorithm ISMINHEAP(A[1 n])
to check if the array represents a min-heap.
(c) [10 points] Given an array of integers A[1 n], design an efficient algorithm
COMPUTELARGESTELEMENTS(A[1 n],k)tocomputethek largestelements
of the array using a heap?
(d) [10 points] Given a minheapandakeyk,designanefficientalgorithm COM
PUTESMALLESTELEMENTSGIVENKEY(A[1 n], k)tocompute all the entries
in the heap having keys less than or equal to k. Your algorithm should run in
time proportional to the number of entries returned, and should not modify
the heap.
3. Hash table problems.
(a) [10 points] Given an array A[1 n] and a sum s, design an efficient algo
rithm EXISTSPAIR(A[1 n] s) that uses a hash table to find and return a
pair (A[i]A[j]) such that i j, that adds to sum s, i.e., A[i] + A[j] = s. If there
is no such pair, return null.
(b) Draw the 11-entry hash table that results from using the hash function H(i) =
(3 i+7) mod 11, to hash the keys 12441388239411392016and5, assum
ing collisions are handled by:
(a) [5 points] Chaining
(b) [5 points] Linear probing
(c) [5 points] Quadratic probing
4. Graph problems.
Consider the following graph. Assume that the traversals are considered in al
phabetical order and all adjacency lists are given in alphabetical order. Starting
from vertex m, showtheordering of vertices produced by the following algorithms.
(a) [5 points] Depth-first search
(b) [5 points] Breadth-first search