University of Florida
COP 5536
COP5536 Advanced Data Structures
Exam 2
Closed Book Duration: 60 mins
Prof. Sartaj Sahni
PLEASE READ THE FOLLOWING INSTRUCTIONS CAREFULLY
1. For all problems, use only the algorithms discussed in class/text.
2. Write your answers directly on the exam question sheet. You may use scrap paper
(supplied by your proctor) for wo
...[Show More]
COP5536 Advanced Data Structures
Exam 2
Closed Book Duration: 60 mins
Prof. Sartaj Sahni
PLEASE READ THE FOLLOWING INSTRUCTIONS CAREFULLY
1. For all problems, use only the algorithms discussed in class/text.
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.
Last name: First name: UFID:
Page 1 of 8
Problem 1 (12)
(a) (6)Drawn below is a min Fibonacci heap (The ChildCut field is shown in parentheses):
3(min) -----------------15
/
|
| 6(T) |
|
\
|
4(F) / \
|
5 (T)
|
\
|
(T)8 7(F) 12(T) 7(T)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(T)10
|
11(F)
|
|
|
|
|
/ |
|
|
|
|
|
|
|
(F)11 17(T)
|
13(T)
|
|
|
|
|
|
|
|
|
|
|
|
20(T)
|
|
|
|
|
|
Perform a DecreaseKey operation by changing 17 to 4.
[Show Less]