09数据结构与算法试题

2009级(2010学年秋季学期《SE211数据结构与算法》期末试题(B卷(考试形式： 考试时间:2小时考试作弊不授予学士学位 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(以列序为主序).Ifthebaseaddressis10000andeachelementoccupiestwostorageunit,thenthestorageaddressofa[32,58]is().(无第0行第0列元素) D)Noneof LetAbean×nsymmetricmatrix（对称矩阵）Inordertosavememoryitslowertriangularis（下三角）storedinaone-dimensionalarrayB[1..n(n+1)/2]byrow.Thesubscriptposition(下标)kofanyelementaij(i≥j)inlowertriangularis（对下三角部分中任一元素aij(i≥j)在一维数组B的下标位置k值是）() C)i(i+1)/2+j-1GiventwostringsAandB,theoperationtosearchthefirstpositionofBinAiscalled( B)patternmatchingC)substring D)stringlengthThepost-orderandthein-ordersequencesofabinarytreearedabecanddebac.Thepreorderis(). Useanadjacencytable(邻接表)torepresentandirectedgraphincludingnverticesandedges,thetimecomplexityofdeletingalledgesassociatedwithavertexis( Howmanyminimumspanningtreesdoesanundirectedgraphhas?(morethanoneoronlymaybenotDeterminingwhetherthereisaloopinadirectedgraph,wecanusetopologysortingaswellas()searchingmethodforthecriticalpath(求关键路径方法breadth-firsttraversaldepth-firsttraversalUsingthebreadth-firstalgorithmtotraversethegraphrepresentedbyanadjacencytable,weshouldusethedatastructurenamed()toimplementit. Usingthedepth-firstalgorithmtotraversethegraphrepresentedbyanadjacencytable,weshouldusethedatastructurenamed()toimplementit. Ifthereexistsamappingrelationshipbetweenthememoryaddressofanodeandthekeyword(结点的存储地址与其关键字之间存在某种映射关系),wecalledthestorage第3页/第3页/5scatter(Hash)storagelinkedstorageindexstorage Whichkindofsortingalgorithmweused?(Selection B)shell C)merge D)quick BlankThetimecomplexity “i=1;while(i<=n) Thetimecomplexityofaccessanynodeinthecontiguouslist(顺序表)is ,sowecalledthecontiguouslistthe datastructure.Ifthereexistacompletebinarytree（完全二叉树）including768nodes,thenthenumberoftheleafnodeis Ifthereexistak-waytree（K叉树）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的二进制等长编码方案表示）.Inthisexample,comparetheadvantagesanddisadvantagesofthesetwomethods.(9%)GivenagraphG,seefigure1.TrytofindouttheMinimumspanningtree（最小生成树）,anddrawthelogicalstructuralgraph（逻辑结构图）.ShowtheStorageforgraphG,withtwodifferentrepresentations(hint:useadjacencymatrixandadjacencytable).Inthefollowingsequenceofkeys,insertthekeys,intheordershown,tobuildthemintoanAVLtree.Pleasedrawtheillustrationfiguresforthewholeprocedure.(9%) Reverse(逆转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{