浙江大学《数据结构基础》课程期末考试试卷A

浙江大学2012-20学年秋学期《数据结构基础》课程期末考试试卷（A）课程号，开课学院计算机科学与技术考试试卷卷、B卷（请在选定项上打V）考试形式J闭、开卷（请在选定项上打J）允许带—无—入场考试日期2012年H月15日，考试时间:120分钟诚信考试，沉着应考，杜绝违纪考生姓名学号所属院系AnswerSheet

①rool=S[rool1@trail-lead;

③―S[trail]=root;PartIII44TNo.Example:212No.Example:1111VIV3V4V5V2VIV3V2V4V5c{VlV3V5};{V2};{V4}37bN.Canonlyconsistoftwoskewedsubtrees.

4.Inincreasingorder.YesifsalwaystruesinceifsfromaBST.PartIV15typedefstructTreeNode*Tree;structTreeNode{TreeChild;intkey;TreeSibling;；intCounter[MAX_LEVEL];/*Counter[i]storesthenumberofleavesonthei-thlevel.*//*Therootisonthelevel

0.*/voidCount_LeavesTreeT—Level=0;VisitTslevel;VisitTreeTint*levelif!T-ChildCounter[*level]++;else{level++;VisitT-Childlevel;*level--;IfT-SiblingVisitT-Siblinglevel;NOTE:Pleasewriteyouranswersontheanswersheet.注意请将答案填写在答题纸上Pleaseselecttheanswerforthefollowingproblems.20pointsWhichoneofthefollowingstatementsistrueasNgrowsa.ForanyXXNgrowsfasterthanN\logN2growsfasterthan\I-NlogN2growsfasterthanlogN2Ngrowsfasterthanyl-NlogN2WhatisthetimecomplexityofthefollowingfunctionthatcomputesXNlongintPowlongintXunsignedintN{ifN==0return1;ifN==1returnX;ifIsEvenN/*IsEvenNreturns1ifNisevenor0othervzise*/returnPowXzN/2*PowXN/2;elsereturnPowX*XN/2*X;a.ONb.OlogNc.ONlogNd.0SupposethatNintegersarepushedintoandpoppedoutofastack.Theinputsequenceis12Nandtheoutputsequenceispip2•••，Pn.IfP2=2thenpii2mustbeLa.ib.i+2c.N-id.cannotbedeterminedWhatisthemajordifferenceamonglistsstacksandqueuesListsusepointersandstacksandqueuesusearraysStacksandqueuesarelistswithinsertion/deletionconstraintsListsandqueuescanbeimplementedusingcircularlylinkedlistsbutstackscannotStacksandqueuesarelinearstructureswhilelistsarenotForanin-orderthreadedbinarytreeifthepre-orderandinordertraversalsequencesareABCDEFandCBAEDFrespectivelywhichpairnodeszrightlinksareboththreadsa.AandBb.BandDc.CandDd.BandEIfNkeysarehashedintothesameslotthentofindtheseNkeystheminimumnumberofprobeswithlinearprobingisLa.N-lb.Nc.NN+l/2d.N+lIfanundirectedgraphwithNverticesandEedgesisrepresentedbyanadjacencymatrix.Howmanyzeroelementsarethereinthematrixa.Eb.2Ec.N2-Ed.N2-2EIfadirectedgraphisstoredbyanupper-triangularadjacencymatrix--thatisalltheelementsbelowthemaindiagonalarezero.ThenitstopologicalorderLa.existsandmustbeuniqueb.existsbutmaynotbeuniquec.doesnotexistd.cannotbedeterminedSortasequenceofnineintegers{4837921065}byinsertionsort.When2ismovedtothefirstpositionthenumber8mustbeatpositionstartfrom1La.4b.5c.6d.7LetTbeatreeofNnodescreatedbyunion-by-heightwithoutpathcompressionthenthedepthofthetreeisa.N/2b.OlogNc.ON2d.01Giventhefunctiondescriptionsofthefollowingtwopseudo-codeprogramspleasefillintheblanklines.21pointsisasimplesortingalgorithm.Supposewehaveawanttosorttheminascendingorder.Bubblethelistfromtheheadtothetailandswapsiftheyareinthewrongorder.Pleasecompletetoimplementbubblesort.12pointsstructnodeintvalue;structnode*next;/*someotherfields*/structnodeBubbleSortstructnode*h/*histheheadpointerofthelistwithadummyheadnode*/structnode*p*q;intflag_swap;if!h-nextreturnh;do{flag_swap-0;p=h;whilep-next-next{if

①{flag_swap++;q-p-next;elsep=p-next;}}whileflag_swap0;returnh;2ThefunctionistoperformFindasaUnion/Findoperationwithpathcompression.9pointsSetTypeFindElementTypeXDisjSetSElementTyperoottraillead;forroot=X;S[root]0;

①fortrail=X;trail!=root;

②{lead=Strail];returnroot;Pleasewriteordrawyouranswersforthefollowingproblemsontheanswersheet.44pointsAsortingalgorithmisstableifforanykeysKi=KjforijzthecorrespondingrecordsRiprecedesRjinthesortedlist.IsHeapSortstablePleasegiveaproofifyouranswerisYES”elsepleaseprovideacounterexample.4pointsIsQuickSortstablePleasegiveaproofifyouranswerisYES〃，elsepleaseprovideacounterexample.4pointsGiventheadjacencylistrepresentationofadirectedgraph.SupposeVIisalwaysthefirstvertexbeingvisited.Pleaselistthedepth-firstsearchsequence;5pointsthebreath-firstsearchsequence;5pointsandthestronglyconnectedcomponents.3pointsAbinarysearchtreeissaidtobeoftypeA“ifallthekeysalongthepathfromtheroottoanyleafnodeareinsortedordereitherascendingordescending.Givenfourkeys{1234}pleasedrawallthepossiblebinarysearchtreesoftypeA.4pointsIngeneralgivenNkeys{12N}howmanydifferentbinarysearchtreesoftypeAcanbeconstructed3pointsGivenahashtableofsize13andthehashfunctionHkey=keymod

13.Assumethatquadraticprobingisusedtosolvecollisions.Pleasefillinthehashtablewithinputnumbers{2153166292428}.4pointsGiveneightkeys{128}.Pleasedothefollowing:constructacompletebinarytreewhichisalsoabinarysearchtree;5pointsandconstructamin-heapoutofthearraywhichstoresthecompletebinarytreeobtainedfroma.UseBuildHeapwithasequenceofpercolate-down7s.4pointsObservethekeysoneachlevelofthemin-heapobtainedfromb.IsthereapatternoforderingIsthistrueformoregeneralcases3pointsGivenatreerepresentedbyleft-child-right-siblingstructurepleasedescribeanalgorithmthatcountsthenumberofleafnodesoneverylevel.15points题序—*=四总分得分评卷人Part

1201.d

2.a

3.d

4.b

5.d

6.c

7.d

8.a

9.b

10.bPartII

211.

①、-〉next-〉valuep・next・next・value

②p-nex=q-next;orp・next-next.

③q-next=p・next-next

④p・next-nex=q;•10123456789101112H[i]2153286162429。