第一部分数据结构期末试卷

—二三四五六七八九十开课学院：计算机学院和软件学院 考试时间：2005年11—二三四五六七八九十Pleasefillinthetablewithyourbestchoices20points2points123456789Anundirectedgraphwithnverticeshasat ① ②n(n– ③n(n– ④ Givenaqueuethatisimplementedbyasinglelinkedlist,whichstatusis1->2->3,afteroperations“delete”and“insert(4)”,thestatusofthislistis：①4->1- ③is①OR ④neither①norTofindtheshortestpathbetweenapairofgiven methodcanbe① ② ③ ④CriticalInthedisjointsetproblem,ifUnionsareperformedbyheight,thenthedepthofanytreewithnnodesis ① ② ③O(log ④Givenasinglelinkedlist,wewoulddeletethenodefollowthenodeimpliedbyPpointer.whichoperationiscorrect?①p->next=p->next- ④p=p->next-Iftheinputisapresortedintegersequence,whichalgorithmisthebesttocomplete① ② ③ ④Insertion umnumberofnodesinabinarytreeofheightk①

– ② – ③

– ④

Givenaternarytree(三叉树)with5nodesofdegree1,3nodesofdegree2,2nodesofdegree3.Thenumberofleafnodesinthistreeis① ② ③ ④GivenaweightedandconnectedundirectedgraphG,thereis/are tree(s)ofG.①only ②oneor ③morethan ④zeroorWhichmethodthattheaveragesearchlengthisindependentofthenumberof①serial ②binary ③binarysearch ④二、Givenanintegersequence 、、 、、 、、 ,aftertheHeapsort’sinitialheapbuilding,thisintergersequence （7770000510三、Forthegraphgivenbytheadjacencymatrix5100404030300260(1)itsadjacencylistrepresentation(3(2)itsbiconnectedcomponents(6(3)theminimumcostspanningtree.(6 2,pleasegive: 四、Writepseudocodeforthedeletionofanynodeiinamin-heapH.Theresultingheapmustsatisfytheminheapdefinition.（8points）Deletion(PriorityQueueH,i)/*deleteelementH->Elements[i]五、Pleaseaccordingtothefollowingtravelresults,drawthe F:(7thepreorderbinarytravelofFisABCDEFGHIJKtheinorderbinarytravelofFisCBEFDGAJIKL六、Givenanintegersequence 、、 、、 、、 ,afterthefirstrunofthes sortingbyanincrement3,theintegersequenceis（7points）:七、Pleasecompletethefollowingprogramaccordingtothecorrespondingfunction(7pointsThefunctionis“union-by-size”inthedisjointsetproblem.voidSetUnion(DisjSetS,SetTypeRoot1,SetTypeRoot2){/*Root1andRoot2mustberootsif ;}else;S[Root2]=}}八、Aqueuecanbesimulatedbytwostacks,assumingthatthequeueandtwostacksareTheoperations‘push’and‘pop’onstack1areexpressedasP1(x)andO1.Theoperations‘push’and‘pop’onstack2areexpressedasP2(x)andO2.Theoperations‘enqueue’and‘dequeue’areexpressedasI(x)andD.ForexampletheoperationsequenceofqueueisI(x)、DcanbesimulatedbytheoperationsequenceofP1(x)、P2(O1)andO2.PleasegivethestackoperationsequencethatsimulatesthequeueoperationsequenceI(x)、I(y)andD.(7points)九、ThefollowingprogramisaDeleteoperationinabinarysearchtree.Pleasefillintheblanklinesofcode.(10points).SearchTreeDelete(ElementTypeX,SearchTreeT PositionTmpCell;if(T==NULL)elseif(X<T->Element)T->Left=Delete(X,T->Left);elseif(X>T->Element)T->Right=Delete(X,T->Right);if(T->Left&&T->Right)}elseTmpCell=if(T->Left==NULLelseif(T->Right==NULL(TmpCell}}十、pleasewriteaCprogramthatcountsthenumberofsimplepathswithlengthLbetweentwoverticesinagivenunweighteddirectedgraphG.TheinputisanadjacencymatrixforG,thetota