试卷数据结构基础课程期末考试

浙江大学2008–2009学年秋季《数据结构基础》课程期末考试试卷 ，考试形式：闭卷，允许带无入场考试时间：2008年11月3日,所需时间：120分钟，任课教师考生 学号 专业—二三四AnswerPartIPartII1. 2. PartIIIi0i0123456789i01234567894.4.4.4.PartIVboolIs_BST_sequence(intK[],intN/*XisstoredatK[N-1]NOTE:Pleasewriteyouranswersontheanswer注意：请将答案填写在答题纸上。Pleaseselecttheanswerforthefollowingproblems.(20Toinsertanodepointedbysafterthenodepointedbypinalinkedlist,weshoulddothefollowing (2points) b.s->next=p->next;p-c.s->next=p->next; d.p->next=s;s-Pushnnumbersontoastackintheorder1,2,…,nandpoptheminsomeordersotoobtainanoutputsequencek1,k2,…,kn.Ifk1=n,thenkimustbe (2points)a. b.n- c.n- d.cannotbeIfthemostcommonlyusedoperationsaretoinsertanelementafterthelastelement,andtodeletethefirstelement,thenthedatastructureforstoringtheelementswhichgivesthefastestperformanceis(2points)asinglylinked b.adoublylinkedasinglylinkedcircularlistwithaheadasinglylinkedcircularlistwithatailTofindanumberfrom100sortednumbersbybinarysearch,umnumberofcomparisonsa. b. c. d.

(2Givenaquadtree(四叉树)with5nodesofdegree2,3nodesofdegree3,2nodesofdegree4.Thenumberofleafnodesinthistreeis (2points)a. b. c. d.Abinarytreewhichgivesexactlythesameorderunderpreorderandpostordertraversalsmustbe (2points)anybinary b.atreewithonlytheatreeofwhicheachnodehasonlytheleftatreeofwhicheachnodehasonlytherightGivenanintegersequence{261184531217109}.sortingmethodwhichtakesthemostextraspaceinsertion b. c.merge d.heap

(2Ifnkeysarehashedintothesameslot,thentoinsertthesenkeys,theminimumnumberofprobeswithlinearprobingis(2points)a.n-1b.nc.n+1d.Astronglyconnectedgraphwithnverticshasatleastedges(2points)a.n(n-1)b.n- c.nd.GivenaweightedgraphG.Amongthefollowingstatements,istrue.(2points)LetTbeaminimumspanningtreeofG.ThenthepathinTbetweenanypairofverticesmustbeashortestpathinG.LetPbeashortestpathfromvtou.IftheweightofeachedgeinGisincreasedby1,Premainsashortestpathfromvtou.Lettheweightstandsfortheflowcapacity.Ifthereisatleastonepathfromstot,thentherealwaysexistsanedgesuchthatincreasingthecapacityofthatedgewillincreasetheumflowofG.Noneofthe descriptionsof thefollowingtwo programs,pleasefillintheblanklines.(21points)ThefunctionistosortNelementsbyheapsort.(12#defineleftchild(i)(2*(i)+1voidPercDown(ElementTypeA[],inti,intN{intfor(Tmp=A[i];leftchild(i)<N;I=child{child=if( childif( A[i]=A[child];elsebreak;} }voidHeapsort(ElementTypeA[],intN{intfor(i=N/2;i>=0;i--)/*BuildHeap*/PercDown(A,i,N);for(i=N-1;i>0;i--)Swap(&A[0],&A[i] }}ThefunctionistomodifyDijkstra'salgorithmsothatifthereismorethanoneminimumpathfromvtow,apathwiththefewestnumberofedgesischosen.(9points)voidDijkstra(TableT{/*T[v].Countstoresthenumberofedgesonthepathfromthesourcetov,/*andisinitializedtobe0vertexv,w;for(;;)v=smallestunknowndistancevertex;if(v==NotAVertex)T[v].Known=for(eachwadjacenttov)if(!T[w].Known)if(T[v].Dist+Cvw<T[w].Dist{Decrease(T[w].DisttoT[v]+Cvw)T[w].Path=v; ;elseif((T[v].Dist+Cvw==T[w].Dist&& {T[w].Count=T[v].Count+ ;}}Pleasewriteordrawyouranswersforthefollowingproblemsontheanswersheet.(44points)Givenalistofintegers{5,2,1,3,6,4,7}.Pleasedrawtheresultsofthefollowing:(10points)insertthenumbersintoaninitiallyemptymax-heap;storethenumbersintoanarrayandadjustthearrayintomax-Pleasefillthearraywiththeresultsafterthefollowingunion/findoperations. Note:Assumeunion-by-size(iftwosetsareequal-sized,thefirstrootwillbetherootoftheresult) pression.S[i]isinitializedtobe-1forall0i9.(5points)Givenahashtableofsize13andthehashfunctionh(x)=xmod13.Pleasefillinthehashtablewithinputnumbers{21531662529}.Assumethatquadraticprobingisusedtosolvecollisions.(7points)GivenagraphGasshowninthefigure.Pleasethedepth-firstspanningtree(5points); theminimumspanningtree(5 Pleaselistthearticulationpoints(5 PleaseaddexactlytwoedgestoGhencemakeGabiconnectedgraph(4 Note:DFSstartsatvertex1,andifthereare thanonebranchestogo,verticesmustbevisited

4 increasingGivenanarrayofintegers{718082943}.Pleaseshowhowtheorderofthenumberschanges

duringeachstepofquicksortwithmedian-of-threeforselectingthepivotandacutoffof3forinsertionYouonlyhavetoshowthearrayaftereachpivotiscedatitsfinalposition.Thefinalresultmustbeanon-decreasingsequence.(3points)1423WhensearchforagivennumberXinabinarysearchtreeT,westartfromtherootandfollowapathdowntoX.ThenumbersalongthatpathformthesearchsequenceforX1423{1423}isasearchsequencefor3inthebinarysearchtreeshownbythefigure.Ontheotherhand,{2413}isNOTasearchsequencesinceaccordingtothedefinitionofabinarysearchtree,1mustnotbeint