=========================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