EE 3011 Data Structure and Programming, Fall 2018

Final Exam Problem Sheet

January 7, 2019

The paper is double-sided, 5 pages, consisting of 13 questions. Total 104 points.

1. (10 pts) Multiple Options

Choose the best possible answer(s). No explanation needed.
(1) What is the worst-case height of an AVL tree with n items? (choose the tightest bound)
√
A. O(n) B. O(2n ) C. O(log n) D. O(n log n) E. O( n)
(2) What is the worst-case height of a splay tree with n items? (choose the tightest bound)
√
A. O(n) B. O(2n ) C. O(log n) D. O(n log n) E. O( n)
(3) What is the worst-case time complexity of quick sort? (choose the tightest bound)
A. O(2n ) B. O(n) C. O(n2 ) D. O(n log n) E. O(n log∗ n)
(4) What is the worst-case time complexity of insertion sort? (choose the tightest bound)
√
A. O(n) B. O(n2 ) C. O( n) D. O(n log n) E. O(n log∗ n)
(5) What is the worst-case time complexity of finding the maximum key in a binary search tree (BST) with
n nodes? (choose the tightest bound)
A. O(1) B. O(log n) C. O(log∗ n) D. O(n) E. O(n log n)
(6) Consider disjoint set union/find algorithms with weighted union and path compression. What is the
worst-case complexity of one find operation? (choose the tightest bound)
A. O(n) B. O(log n) C. O(log∗ n) D. O(1) E. O(log log n)
(7) What is the worst-case time complexity of building a binary heap bottom-up from n unsorted numbers?
Assume the n numbers are given in batch. (choose the tightest bound)
√
A. O(n) B. O(n2 ) C. O( n) D. O(n log n) E. O(n log∗ n)
(8) Let x be a non-root node in a Fibonacci heap. If x has degree 21, at least how many children of x should
have degree ≥ 14?
A. 5 B. 6 C. 7 D. 8 E. 9
(9) What is the maximum possible degree of a root in a Fibonacci heap with n = 100 nodes?
A. 7 B. 8 C. 9 D. 10 E. 11
(10) Which of the following statement(s) is (are) true?
A. Every subtree of a BST is also a BST.
B. Every subtree of an AVL tree is also an AVL tree.
C. Every subtree of a red-black tree is also a red-black tree. (without changing the node color)
D. A binary heap is a BST.
E. A binary heap is an AVL tree.

1
2. (19 pts) Time complexity tables
(a) (13 pts) Fill in Table 1 with the amortized worst-case time complexities in big-Oh notation (in terms
of n, the size of the priority queue) of the various operations performed on various priority queues. No
explanation needed.

Binary Heap Binomial Heap Fibonacci Heap Leftist Heap Skew Heap
insert
find-min
delete-min
union
decrease-key

Table 1: Complexity of priority queue operations in Problem 2a.

(b) (6 pts) Fill in Table 2 with the amortized worst-case time complexities in big-Oh notation (in terms of
n, the size of the tree) of the various operations performed on various trees. No explanation needed.

Binary Search Tree Red-Black Tree Splay Tree AVL Tree

insert
search
delete

Table 2: Complexity of tree operations in Problem 2b.

3. (8 pts) AVL tree

(a) (5 pts) Start with an empty AVL tree and perform the following sequence of insertions: 1, 2, 3, 4, 5, 6,
7, 8, 9, 10. Show all the intermediate trees.
(b) (3 pts) Following the previous question, illustrate the result after deleting the key 4. Show all the
intermediate trees.
4. (6 pts) Splay tree

(a) (3 pts) After inserting the key 4 into the splay tree shown in Figure 1, what is the resulting tree? Show
all the intermediate trees. Please use the top-down splay and split operation.
(b) (3 pts) After deleting the key 5 from the splay tree shown in Figure 1, what is the resulting tree? Show
all the intermediate trees. Please use the bottom-up splay.

3
2 6
1 5 8
9

Figure 1: The initial splay tree in Problem 4.

5. (4 pts) 2-4 tree

(a) (2 pts) What is the minimum and maximum number of nodes in a 2-4 tree of height h? Assume that
a tree with only one node is of height 1.
(b) (2 pts) What is the minimum and maximum number of items (a.k.a., keys) in a 2-4 tree of height h?
Assume that a tree with only one node is of height 1.

2
6. (9 pts) Hashing
Consider successively inserting 1, 14, 16, 21, 13, 26, 25, 38, 7, 10 and 2 into a hash table with 13 slots, where
every slot holds only one key. The hash function is h(k) = k mod 13. Illustrate the results of inserting these
keys using the following techniques.

(a) (3 pts) Separate chaining.

(b) (3 pts) Linear probing.
(c) (3 pts) Quadratic probing.
7. (10 pts) Red-black tree

(a) (5 pts) After inserting the key 16 into the red-black tree in Figure 2, what is the resulting red-black
tree? Use the top-down rules. Show all the intermediate trees and clearly specify colors of each node.
(b) (5 pts) After deleting the key 1 from the red-black tree in Figure 2, what is the resulting red-black tree?
Use the top-down rules. Show all the intermediate trees and clearly specify colors of each node.

2 10

1 4 8 12

3 5 7 9 11 14

13 15

Figure 2: The initial red-black tree in Problem 7. Dark nodes represent black nodes; light nodes represent red nodes.

8. (5 pts) AA tree
After inserting the key 5 into the AA tree in Figure 3, what is the resulting AA tree? How many skew and
split operations are performed? Show all steps that lead to your answer.

50 70

20 30 60 80

10 15 24 32 55 65 75 78 90

Figure 3: The initial AA tree in Problem 8.

3
 9. (6 pts) Binary heap
(a) (3 pts) Illustrate the result after inserting 15 into the binary heap in Figure 4.
(b) (3 pts) Illustrate the result after deleting the minimum from the binary heap in Figure 4.

10

11 24

12 38 56 33

55 45

Figure 4: The initial binary heap in Problem 9.

10. (6 pts) Fibonacci heap

(a) (3 pts) Illustrate the result after deleting minimum in the Fibonacci heap in Figure 5.
(b) (3 pts) Illustrate the result after decreasing 80 to 2 in the Fibonacci heap in Figure 5.

min 3 15 30

22 16 21 19 38 40

30 42 32 50

34 80 70

Figure 5: The initial Fibonacci heap in Problem 10.

11. (6 pts) Leftist heap

(a) (3 pts) After inserting 16 into the leftist heap in Figure 6, what is the resulting heap?
(b) (3 pts) After deleting the minimum element from the leftist heap in Figure 6, what is the resulting
heap?

7 5

9 8 6 10

13 12 11

14 15

Figure 6: A leftist heap.

4
 1 2

5 3 4 6

9 7 11 8 10

Figure 7: Two skew heaps.

12. (5 pts) Skew heap

Merge the two skew heaps in Figure 7 into a single skew heap.
13. (10 pts) Disjoint set

(a) (3 pts) After performing FIND(m) on the set in Figure 8(a) by applying path compression, what is
the resulting up-tree?
(b) (3 pts) A forest of up-trees can easily be stored in an array. Show the array which represents the forest
of up-trees in Figure 8(b). Use −1 to represent the parent index of a root.
(c) (4 pts) Given the sets {a}, {b}, {c}, {d}, {e}, {f }, and {g}, please successively perform the following
operations:


(1) UNION FIND(a), FIND(b)


(2) UNION FIND(c), FIND(d)


(3) UNION FIND(a), FIND(e)


(4) UNION FIND(f ), FIND(g)


(5) UNION FIND(e), FIND(b)


(6) UNION FIND(f ), FIND(c)


(7) UNION FIND(d), FIND(a)


(8) UNION FIND(b), FIND(e)
Show your procedure. Apply weighted union and path compression. Use an up-tree to represent a
set. Note that if x and y have the same rank when performing UNION(x, y), make x be the root of the
new up-tree.

a
a b e
g k
e
l c f g k
f
d
b d h i l
i c j

h j
m
0(a) 1(b) 2(c) 3(d) 4(e) 5(f) 6(g) 7(h) 8(i) 9(j) 10(k) 11(l)
n

(a) (b)

Figure 8: (a) The initial up-tree in Problem 13a. (b) The forest of up-trees in Problem 13b.