Data Structures

Data Structures and Algorithms Name:

1. (5 points) For the set of {1, 4, 5, 16, 17, 21} of keys, draw binary search trees of heights 2, 3, 4, 5, and 6.

2. (5 points) Use the Binary Search Tree class to Write the TREE-PREDECESSOR pro- cedure.

3. (5 points) Show that there are at most d n 2h+1

e nodes of height h in any n-element heap.

4. (5 points) Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6n−1 is divisible by 5

5. (5 points) Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

(a) (2.5 points) f(n) + g(n) = Θ(min(f(n), g(n)).

(b) (2.5 points) f(n) + O(f(n)) = Θ(f(n)).

6. (5 points) Use the following tree to answer the questions:

39

27

18

9

10

21

19

29

28 36

45

40 54

59

65

60

(a) (2.5 points) Write the a pseudocode to find key 36 successor.

(b) (2.5 points) Write the pseudocode to find the minimum key in the previous tree.