Data Structure and Programming, Fall 2018
Midterm Exam
November 12, 2018
1. (15 pts) Use the master theory to find the Θ time complexity of T (n).
(a) (3 pts) T (n) = 8T (n/2) + 3n
(b) (3 pts) T (n) = 9T (n/3) + 2n2 log n
(c) (3 pts) T (n) = 2T (n/4) + 2n/2
(d) (3 pts) T (n) = 4T (n/2) + n/ log n
(e) (3 pts) T (n) = 6T (n/3) + n2 log n
2. (15 pts) Sort the following functions. Let f (n) ≻ g(n) and f (n) ∼ g(n) denote f (n) ∈ ω(g(n)) and
f (n) ∈ Θ(g(n)), respectively. No explanation needed.
(a) f1 (n) = nn
(b) f2 (n) = n!
(c) f3 (n) = n log n
√
(d) f4 (n) = n
(e) f5 (n) = n
(f) f6 (n) = log2 n
(g) f7 (n) = log n
(h) f8 (n) = n2n
(i) f9 (n) = 4n
(j) f10 (n) = log(n!)
(k) f11 (n) = ⌈log2 n⌉!
(l) f12 (n) = 2log4 n
(m) f13 (n) = log(log n)
(n) f14 (n) = 1000010000
(o) f15 (n) = (log n)n
3. (10 pts) Find the time complexity (in Θ notation) of the following operations. Assume all data
structures have size n.
(a) (2 pts) pop() for a stack.
(b) (2 pts) enqueue() for a queue.
(c) (2 pts) Deletion in a binary search tree.
(d) (2 pts) Insertion in an AVL tree.
(e) (2 pts) FindMax() for an AVL tree.
1
4. (15 pts) Prof. Wu designs an encoding algorithm on the string consisting of alphabets. According to
the algorithm, a,b,...,z are encoded into 1,2,...,26, respectively. Now, Prof. Wu wonders how many ways
an encoded string can be decoded into an alphabet string. For example, the encoded string “2141”
can be decoded to “bada”(“2,1,4,1”), “uda”(“21,4,1”), or “bna”(“2,14,1”). Thus, there are 3 ways to
decode “2141”. How many ways can we decode “12102121420”? Show your derivation in detail.
5. (15 pts) Consider the binary tree in Figure 1. Print the characters in the tree by
(a) (5 pts) Pre-order
(b) (5 pts) In-order
(c) (5 pts) Post-order
O E
G R L T
S K W A
N I
Figure 1: Binary tree
6. (15 pts) Show the result of building up an AVL tree by inserting 6, 8, 10, 1, 4, 2, 9, 5, 7, 3. Show your
derivation in detail.
7. (15 pts) Let x = (x1 , x2 , ..., xm ) and y = (y1 , y2 , ..., yn ) be two singly linked lists of integers. Assume
that in each list, the elements are in non-decreasing order (i.e., x1 ≤ x2 ≤ ... ≤ xm and y1 ≤ y2 ≤
... ≤ yn ). How can we merge the two lists into one list z = (z1 , z2 , ..., zm+n ) in non-decreasing order
without additional nodes? Assume that x = (29, 35, 42) and y = (15, 21, 41, 56, 75), show how the
pointers in x, y, z are updated in each step. Then, analyze the time complexity (in terms of m, n) of
your method. (Grade depends on the time complexity of your algorithm. Hint: Try to achieve linear
time complexity).
x.head
29 35 42
Null
y.head
15 21 41 56 75
Null
Figure 2: The singly linked lists x and y.
2
(1)
x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
z.tmp
(2) Null
x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
z.tmp Null
(3)
z.tmp x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
Null
(4) z.tmp x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
Null
(5) z.tmp x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
Null
(6)
z.tmp x.head
29 35 42
Null
y.head
z.head
15 21 41 56 75
Null
(7)
x.head
29 35 42 Null
y.head
z.head
15 21 41 56 75
z.tmp Null
Figure 3: The step-by-step procedure in Problem 7.
