University of Florida
COP 5536
COP 5536
Advanced Data Structures
Exam 2
CLOSED BOOK
60 Minutes
PLEASE READ THE FOLLOWING INSTRUCTIONS CAREFULLY
1. For all problems, use only the algorithms discussed in class.
2. Write your answers directly on the exam question sheet. You may use
scrap paper (supplied by your proctor) for work, but these will not be gra
...[Show More]
COP 5536
Advanced Data Structures
Exam 2
CLOSED BOOK
60 Minutes
PLEASE READ THE FOLLOWING INSTRUCTIONS CAREFULLY
1. For all problems, use only the algorithms discussed in class.
2. Write your answers directly on the exam question sheet. You may use
scrap paper (supplied by your proctor) for work, but these will not be graded.
3. All answers will be graded on correctness, efficiency, clarity, elegance and
other normal criteria that determine quality.
4. You may use only a pen or a pencil. No calculators allowed.
Note. The points assigned to each question are provided in parentheses.
_______________
Page 2 of 8
1. (15)
(a) [8 points] For the min Fibonacci heap shown below, perform a DecreaseKey
operation by changing 19 to 2. Draw the resulting min Fibonacci heap, clearly label
ChildCut values. (The ChildCut field is shown in parentheses; ChildCut is undefined for
the root.)
min
(b) [7 points] Perform a DeleteMin operation on the resulting Fibonacci heap of (a),
clearly label ChildCut values.
Page 3 of 8
Page 4 of 8
2. (10):
a) [5 points] With an initially empty two-‐pass min pairing heap, insert the following
keys in sequence: 9,7,6,8,1,2,3,4 and 5 (show each step).
b) [5 points] Perform DeleteMin on the resulting tree of part a (use the two-‐pass
scheme and show each step)
Solution:
Basic rule: tree with larger root becomes the left-most subtree
Step1: remove node 1.
Step2(1st pass): we meld from left to right; if the number of subtrees is odd, meld
remaining original subtree with newly generated ones.
Step3(2nd pass): start from right most, meld all.
Page 5 of 8
3. (10) Consider the following AVL tree.
40
/ \
80
(a) [5 points] Delete key 30, show each step and specify each rotation type.
(b) [5 points] Start with the original AVL tree (i.e., the tree before the deletion key 30)
and insert 77 and 81 in this order. Show each step and specify each rotation type.
Powered by TCPDF (www.tcpdf.org)
[Show Less]