浙江大学20072008学年秋季学期《数据结构基础》课程期末考试
浙江大学20072008学年秋季学期《数据结构基础》课程期末考试
浙江大学20072008学年秋季学期《数据结构基础》课程期末考试试卷开课学院：软件学院、计算机、竺可桢学院，考试形式：闭卷，允许带_无入场考试时间：_2007_年_11_月_17日所需时间：120分钟考生姓名：___学号：专业：____教师：
A
swerSheet
NOTEPleasewriteyoura
swerso
thea
swersheet注意：请将答案填写在答题纸上。IPleaseselectthea
swerforthefollowi
gproblems20poi
ts1Thetimecomplexityofthefollowi
gpieceofcodeis2poi
tsfori0iforjij0j2pri
tf“d
”jaO
bO
cO
log
dO
i2Supposethatthetimecomplexitiesoftwoprogramsaregive
byT1NOfNa
dT2NOfNWhichofthefollowi
gequatio
sistrue2poi
tsaT1NT2NOfNbT1NT2NofNcT1NT2NO1dT1NOT2N3Give
a
emptystackSa
da
emptyqueueQAlistofcharactersarepushed
1
f浙江大学20072008学年秋季学期《数据结构基础》课程期末考试
i
toSi
theorderofabcdefa
deverycharacterthatispoppedfromSwillbei
sertedi
toQimmediatelyIftheoutputofQisbdcfeathemi
imumcapacityofSmustbe2poi
tsa6b5c4d34Supposethatthesizeofahashtableis11a
dthehashfu
ctio
isHkeykey11Thefollowi
g4eleme
tshavebee
i
sertedi
tothetableasAddr143Addr385Addr616Addr869Whe
ope
addressi
gwithquadraticprobi
gisusedtosolvecollisio
stheaddressoftheeleme
twithkey49willbe2poi
tsa4b7c8d105Forabi
arytreegive
thepostordertraversalseque
ceFDEBGCAa
dthei
ordertraversalseque
ceFDBEACGthecorrespo
di
gpreordertraversalseque
ceis2poi
tsaABDFEGCbABDEFCGcABDFECGdABCDEFG6I
sert101211465815397411132i
toa
i
itiallyemptybi
arymi
heapo
eatatimeafterperformi
gthreeDeleteMi
operatio
sthelasteleme
toftheheapis2poi
tsa10b11c8d57LetTbeatreecreatedbyu
io
bysizewithN
odesthe
theheightofTca
be2poi
tsaatmostlog2N1batleastlog2N1
2
f浙江大学20072008学年秋季学期《数据结构基础》课程期末考试
caslargeasNda
ythi
gthatisgreatertha
18Give
aweighteda
dco
ectedu
directedgraphGthereisaremi
imumspa
i
gtreesofG2poi
tsao
lyo
ebo
eormorecmoretha
o
edzeroormore9Tofi
dtheshortestpathbetwee
apairofgive
verticesmethodca
beused2poi
tsaKruskalbDijkstracHashi
gdCriticalPath10Amo
gthefollowi
gsorti
galgorithmshastheaverageru
timeONlogNwithONextraspaces2poi
tsaQuicksortbHeapsortr