=========================preview======================
(COMP171)1999_spring_midterm_exam.pdf
Back to COMP171 Login to download
======================================================
THEHONGKONGUNIVERSITYOFSCIENCE&TECHNOLOGY
(c)Assumingthat\visitanode"means\outputthenode'slabel"givetheoutputfromthe DepartmentofComputerScience
reverseinordertraversalofthetreethatvisitsonlyinternalnodes.
COMP171:DataStructuresandAlgorithms
Spring1999

Midterm1Examination(Cream)
Synn.oveKekkonen-Moneta&DerickWood
Date:March17,1999. Time:19:30{21:30
Place:LTA,BandD(allocatedbytutorialsection) (d)Assumingthat\visitanode"means\outputthenode'slabel"givetheoutputfromthe
Thisisaclosedbookexamination.
bottom-uplevel-ordertraversalofthetreethatvisitsonlyexternalnodes.
Nocalculators. Eachquestiontellsyouhowmanymarksandhowmanypartsithas. Thisbooklethas9pagesincludingthecoverpage,pleasecheckit.
Studentname: StudentID:
Problem Yourmark Maximum Problem Yourmark Maximum
1 16 5 14
2 14 6 15
3 14 7 15
4 12
Subtotal 56 Subtotal 44

Yourtotalmarks:
1 3
1.(16marks)(4parts)Treesandtraversals
2.(14marks)(4parts)Prioritytreerepresentationofpriorityqueue
Answerthefollowingfourquestionsbasedonthetree:

Considermax-prioritytreesofsize5andassumethat\onedatamove"means\rewritinga node'scontent(orlabel)".
..
(a)Whatisthemaximumpossiblenumberofdatamovesfordeletemax().a
..
%e
%
%e
%e

..e..
%e
bc

....
(b)Giveanexampleofamax-prioritytreeofsize5thatrequiresthemaximumpossi-
..J .
B
blenumberofdatamovesfordeletemax().Drawtheprioritytreebeforeandafter
J
. .B
JB
deletemax().
..

...J..B

J...
de1f

......
.
B.
B.
B
.B.B.B
.B.B.B

.B
...B
.B

234g56
..
.J
.J.J.
..
.JJ.. hi

....
.
B.
B
.B.B
.B.B

(c)Whatistheminimumpossiblenumberofdatamovesfordeletemax().
.B
.B

78910 (d)Giveanexampleofamax-prioritytreeofsize5thatrequirestheminimumpossi-(a)Whatistheheightofthegiventree. blenumberofdatamovesfordeletemax().Drawtheprioritytreebeforeandafter
deletemax().
(b)Assumingthat\visitanode"means\outputthenode'slabel"givetheoutputfromthe
inordertraversalofthetreethatvisitsbothinternalandexternalnodes.

2 4