2006浙江大学20062007学年秋季学期
《数据结构基础》课程期末考试试卷数据结构基础》课程期末考试试卷期末考试
开课学院：软件学院，考试形式：闭卷闭卷，闭卷允许带_无入场
考试时间：_2006_年_11_月_11_日考生姓名：题序得分评卷人一___学号：二
所需时间：120分钟专业：三四____教师：总分
NOTEPleasewriteyoura
swerso
thea
swersheet注意：请将答案填写在答题纸上。注意：请将答案填写在答题纸上。
IPleaseselectthea
swerforthefollowi
gproblems20poi
ts
1Supposethat
umbersarepushedo
toastacki
theorder12…
1
If
isthefirst
umberthatispoppedoutofthestackthe
theith
umberpoppedmustbe2poi
tsaib
i1c
ida
yo
eispossibleThepropertysthatalistdoesNOThaveisare2poi
tsa
o
eedtopreestimatethetotalspaceb
o
eedtomoveitemsfori
sertio
a
ddeletio
cquickra
domaccessdthespacetake
isproportio
altothele
gthofthelistI
thefollowi
gi
tegerseque
ces10085987780608240201066100988582807766604020101020406066778082859810010085407780606698821020isareNOTaheap2poi
ts
2
3abcd4
Ifdepthfirstsearchca
visiteveryvertexwitha
ystarti
gvertexthe
thatgraphmustbea2poi
tsatreebgraphco
tai
scyclesccompletegraphdco
ectedgraphGive
a
i
tegerseque
ce15，7，20，9，8，1，Ifafterthefirstru
ofShellsort4，2poi
tstheseque
cebecomes15，l，4，8，20，9，7the
thei
creme
tmustbea1b2c3d4
5
f6
Placemitemsi
ahashtablewitha
arraysizeofstheloadi
gfactoris2poi
tsasmbmscmsdms7Breathfirstsearchwiththeadjace
cylistreprese
tatio
ofagraphissimilartothetraversalofabi
arytree2poi
tsapreorderbi
ordercpostorderdleverlorder8Amo
gthefollowi
gsorti
galgorithmswithsmallextraspace2poi
tsaQuicksortbHeapsortcMergesorthastheaverageru
timeONlogNdRadixsort
9
I
akeysalo
geachofthepathsfroma
y
odetotherootareordered2poi
tsaheapbbi
arysearchtreeccompletetreed
o
eoftheabove
10
Ifacompletebi
arytreeofheighth0isreprese
tedbya
arraythe
thei
dexoftheleftmostleafis2poi
tsh1hh1h1a21b2c21d2
IIGive
thefu
ctio
descriptio
softhefollowi
gtwopseudocodeprogramspleasefilli
thebla
kli
es24poi
ts
1Thefu
ctio
istodetermi
ethemi
imumpathsfromastartvertextoeveryothervertexi
aweightedalltheweightsarepositivegrapha
dtoproduceacou
tofthe
umberofdiffere
tmi
imumpaths12poi
ts
voidMi
PathCou
tTableTTCou
tisi
itializedtobe0TstartCour