09數(shù)據(jù)結(jié)構(gòu)與算法試題

2009級(jí)(2010學(xué)年秋季學(xué)期《SE211數(shù)據(jù)結(jié)構(gòu)與算法》期末試題(B卷(考試形式： 考試時(shí)間:2小時(shí)考試作弊不授予學(xué)士學(xué)位 123456789111111I、Selection(withonlyoneIndatastructure,whichofthefollowingstructureofdataisnotrelatedtocomputers（與所使storage B)physicalC)logical D)physicalandstorageThecomputeralgorithmrefersto(sortingschedulingFinitesequencesofoperationsforproblemWhenwetalkaboutthedataincomputermemory,()isakindofstructurewhosephysicaladdressandlogicaladdressarethesameandcontiguous(物理地址與邏輯地址相同并且是storagelogicalcontiguousstoragelinkedstorageGivenastackswiththeinputsequence:1,2,...,n,andtheoutputsequence:p1,p2,…,pn,ifp1=n，thenpi=(). Supposethereisatwo-dimensionarraya[1..60,1..70]with60rowsand70columns,whosemainorderisthecolumnorder(以列序?yàn)橹餍?.Ifthebaseaddressis10000andeachelementoccupiestwostorageunit,thenthestorageaddressofa[32,58]is().(無(wú)第0行第0列元素) D)Noneof LetAbean×nsymmetricmatrix（對(duì)稱矩陣）Inordertosavememoryitslowertriangularis（下三角）storedinaone-dimensionalarrayB[1..n(n+1)/2]byrow.Thesubscriptposition(下標(biāo))kofanyelementaij(i≥j)inlowertriangularis（對(duì)下三角部分中任一元素aij(i≥j)在一維數(shù)組B的下標(biāo)位置k值是）() C)i(i+1)/2+j-1GiventwostringsAandB,theoperationtosearchthefirstpositionofBinAiscalled( B)patternmatchingC)substring D)stringlengthThepost-orderandthein-ordersequencesofabinarytreearedabecanddebac.Thepreorderis(). Useanadjacencytable(鄰接表)torepresentandirectedgraphincludingnverticesandedges,thetimecomplexityofdeletingalledgesassociatedwithavertexis( Howmanyminimumspanningtreesdoesanundirectedgraphhas?(morethanoneoronlymaybenotDeterminingwhetherthereisaloopinadirectedgraph,wecanusetopologysortingaswellas()searchingmethodforthecriticalpath(求關(guān)鍵路徑方法breadth-firsttraversaldepth-firsttraversalUsingthebreadth-firstalgorithmtotraversethegraphrepresentedbyanadjacencytable,weshouldusethedatastructurenamed()toimplementit. Usingthedepth-firstalgorithmtotraversethegraphrepresentedbyanadjacencytable,weshouldusethedatastructurenamed()toimplementit. Ifthereexistsamappingrelationshipbetweenthememoryaddressofanodeandthekeyword(結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系),wecalledthestorage第3頁(yè)/第3頁(yè)/5scatter(Hash)storagelinkedstorageindexstorage Whichkindofsortingalgorithmweused?(Selection B)shell C)merge D)quick BlankThetimecomplexity “i=1;while(i<=n) Thetimecomplexityofaccessanynodeinthecontiguouslist(順序表)is ,sowecalledthecontiguouslistthe datastructure.Ifthereexistacompletebinarytree（完全二叉樹(shù)）including768nodes,thenthenumberoftheleafnodeis Ifthereexistak-waytree（K叉樹(shù)）includingnnodes,themaximumpossibledepth ,theminimumdepthis arebothcommonlyusedstoragestructureforgraphs.Totraverseagraph,weusuallyusethefollowingtwomethods: Inordertomergetwoorderedsequenceswithlengthmintoaneworderedsequence,weneedatleast timesofkeycomparing,andatmost timesofkeycomparing.SupposeadirectedgraphGincludingasetofvertex{v1,v2,v3,v4,v5},andasetof{<v1,v2>,<v2,v4>,<v3,v5>,<v1,v3>,<v1,v5>,<v2,v3>,<v3,v4>,<v4,v5>},thenodewhichhasthegreatestin-degree(入度)is .Thenodewhichhasthegreatestout-degree(出度)is,theresultoftopologicalsortingofGis QuestionsandAnswersGivenanemptybinarytree,pleaseinserte,b,d,f,a,g,cinsequence,bytheerconstructingabinarysearchtree.(9%)AssumingthemessageusedforcommunicationiscomposedofonlyC1~C8letters（用于通C1～C8字母組成）thefrequencyofeachletterappearinginthemessageis0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.DesigntheHuffmancodingforthese8letters，andrepresentitwithanotherequallengthbinaryencodingmethodfrom0to7（試80～7的二進(jìn)制等長(zhǎng)編碼方案表示）.Inthisexample,comparetheadvantagesanddisadvantagesofthesetwomethods.(9%)GivenagraphG,seefigure1.TrytofindouttheMinimumspanningtree（最小生成樹(shù)）,anddrawthelogicalstructuralgraph（邏輯結(jié)構(gòu)圖）.ShowtheStorageforgraphG,withtwodifferentrepresentations(hint:useadjacencymatrixandadjacencytable).Inthefollowingsequenceofkeys,insertthekeys,intheordershown,tobuildthemintoanAVLtree.Pleasedrawtheillustrationfiguresforthewholeprocedure.(9%) Reverse(逆轉(zhuǎn)List:DesignanalgorithmtoreservealistLYouaregivenTheheadofL:Linklist*Thedeclarationoflist-node:template<classEntry>structLinklist{Entrydata;Linklist*next;Declarationofprotofunction:voidreverse(LinklistNode:DonotcreatenewnodeforthereversedlistwhenHint:TheillustrationfiguresforthewholeprocedureisasWriteafunctionvoidselectionSort(intA[],intn)toimplementaselectionsortalgorithm.ThearrayA[]containstheintegerstosort,andndenotesthesizeofA[] Writeanon-recursive（非遞歸）algorithmtotraverseabinarytreebypre-order（前序）Thedeclarationofbinarytreeandtreenodearegivenasfollowing:template<classclass{