还剩4页未读,继续阅读
文本内容:
浙江大学2012-20学年秋学期《数据结构基础》课程期末考试试卷(A)课程号,开课学院计算机科学与技术考试试卷卷、B卷(请在选定项上打V)考试形式J闭、开卷(请在选定项上打J),允许带—无—入场考试日期2012年H月15日,考试时间:120分钟诚信考试,沉着应考,杜绝违纪考生姓名学号所属院系—*=题序四总分得分评卷人Answer SheetPart
1201.d
2.a
3.d
4.b
5.d
6.c
7.d
8.a
9.b
10.bPart II
211.
①、-〉next-〉valuep・next・next・value_______________
②p-nex=q-next;or p・next-next.
③q-next=p・next-next________________________________
④p・next-nex=q;_______________________________________
2.
①rool=S[rool1@trail-lead;
③―S[trail]=root;_____________________________________Part III44Ta No.Example:2,1,2b No.Example:1,1,1,1a VI,V3,V4,V5,V2b VI,V3,V2,V4,V5c{Vl,V3,V5};{V2};{V4}37b N.Can onlyconsist oftwo skewedsubtrees.
4.•
101234567891011125.a bH[i]2153286162429c Inincreasing order.Yes ifsalways truesince ifsfrom aBST.Part IV15typedef struct TreeNode*Tree;structTreeNode{Tree Child;int key;Tree Sibling;;int Counter[MAX_LEVEL];/*Counter[i]stores the number ofleaves on the i-th level.*//*The rootison thelevel
0.*/void Count_Leaves Tree T—Level=0;Visit T,slevel;VisitTreeT,int*levelif!T-ChildCounter[*level]++;else{level++;VisitT-Child,level;*level--;If T-SiblingVisit T-Sibling,level;NOTE:Please writeyour answerson the answer sheet.注意请将答案填写在答题纸上I.Please selecttheanswerfor the following problems.20pointsX,XN1Which oneof the following statementsis trueas Ngrows a.For anyN\grows faster thanN2\I-Nb.log grows faster thanN2N2c.log growsfasterthan logN yl-N N2d.growsfasterthanlog2What isthe timecomplexity of thefollowingfunction thatcomputes XNlong int PowlongintX,unsigned intN{if N==0return1;if N==1return X;if IsEven N/*IsEvenNreturns1if Nis even,or0othervzise*/return PowXzN/2*Pow X,N/2;else returnPowX*X,N/2*X;a.ON b.OlogN c.ONlogN d.03Suppose thatN integersare pushedinto andpopped outof astack.The inputsequence is1,2,N and the outputsequenceispi,p2,•••,PN.If P2=2,then pii2must beLa.i b.i+2c.N-i d.cannot bedetermined4What isthe majordifference amonglists,stacks,and queuesa.Lists usepointers,and stacksand queuesuse arraysb.Stacks andqueues arelists withinsertion/deletion constraintsc.Lists andqueues can be implementedusing circularlylinked lists,but stackscannotd.Stacks andqueues arelinear structureswhile listsare not5For anin-order threadedbinary tree,if thepre-order andinorder traversalsequencesare ABCDEFand CBAEDFrespectively,which pairnodesz rightlinks areboththreadsa.A andB b.B andD c.C andD d.B andE6If N keys arehashed into the sameslot,then tofind theseNkeys,the minimumnumber of probeswith linearprobing isLa.N-l b.N c.NN+l/2d.N+l7If anundirected graphwith Nvertices andE edgesis representedby an adjacencymatrix.How manyzero elementsare therein thematrixa.E b.2E c.N2-E d.N2-2E8If a directed graph is storedbyanupper-triangular adjacencymatrix--thatis,all theelements belowthe maindiagonal arezero.Then itstopological orderLa.exists andmust beunique b.exists butmay notbe uniquec.does notexist d.cannot bedetermined9Sort asequence ofnine integers{4,8,3,7,9,2,10,6,5}by insertionsort.When2is movedtothe first position,thenumber8must be at positionstartfrom1La.4b.5c.6d.710Let Tbeatree ofN nodescreated byunion-by-height withoutpath compression,then the depth of the treeisa.N/2b.OlogN c.ON2d.01II.Given thefunction descriptionsofthefollowing twopseudo-code programs,please fill in theblank lines.21points1Bubble sortof isa simplesorting algorithm.Suppose wehave awant tolistintegersand sortthem inascending order.Bubble the list from thesortrepeatedly scanshead tothe tail,and swapsif theyare inthe wrongorder.twoadjacent numbersPlease completeto implementbubble sort.12points thefollowingprogramstruct nodeint value;struct node*next;/*some otherfields*/struct nodeBubbleSort struct node*h/*histhe headpointer ofthelistwith adummy headnode*/structnode*p,*q;int flag_swap;if!h-next return h;do{flag_swap-0;p=h;while p-next-next{if
①__{flag_swap++;q-p-next;else p=p-next;}}while flag_swap0;returnh;2The functionis toperform Findas aUnion/Find operationwith pathcompression.9pointsSetType FindElementType X,DisjSet SElementType root,trail,lead;
①forroot=X;S[root]0;
②fortrail=X;trail!=root;{lead=S trail];return root;III.Please writeor drawyour answersfor thefollowing problemsontheanswer sheet.44points1A sortingalgorithm isstable iffor anykeys Ki=Kj forij zthecorresponding recordsRi precedesRj inthe sortedlist.a IsHeap Sortstable Pleasegive aproof ifyour answeris YES”,elseplease providea counterexample.4points〃,b IsQuick Sortstable Pleasegive aproof ifyour answeris YESelseplease providea counterexample.4points2Given theadjacency listrepresentation ofadirectedgraph.Suppose VIis alwaysthefirstvertex beingvisited.Please listathedepth-first searchsequence;5pointsb thebreath-first searchsequence;5points andcthe stronglyconnected components.3points3A binary search treeis saidto beof type A“if all the keysalong thepathfromtheroot toany leafnode arein sortedorder eitherascendingor descending.a Givenfour keys{1,2,3,4},please drawallthepossible binarysearchtrees oftype A.4pointsb Ingeneral,given Nkeys{1,2,N},how manydifferent binarysearch treesoftypeAcanbeconstructed3pointsH key=key4Given ahash tableof size13andthe hash functionmod
13.Assume thatquadratic probingis usedto solvecollisions.Please3,fillinthehashtable withinput numbers{2,15,16,6,29,24,28}.4points2,5Given eightkeys{1,8}.Please dothefollowing:a construct a completebinary treewhich isalso abinarysearchtree;5points andbconstructamin-heap outofthearray whichstores thecomplete binarytreeobtained froma.Use BuildHeapwith asequence ofpercolate-down7s.4pointsc Observethe keyson eachlevel ofthe min-heap obtainedfrom b.Isthere apattern ofordering Isthis truefor moregeneral cases3pointsIV.Given atree representedby left-child-right-sibling structure,please describeanalgorithm thatcounts thenumberofleaf nodeson everylevel.15points。