數(shù)據(jù)結(jié)構(gòu)例題解析

SingleChoice(10points)(a)Forthefollowingprogramfragmenttherunningtime(Big-Oh)is.i=0;s=0;while(s<(5*n*n+2)){i++;s=s+i;}21/23O(n)b.O(n 2) c.O(n 1/2)d.O(n 3)(c)Whichisnon-lineardatastructure .queue c.tree d.sequencelist(b)Theworst-timeforremovinganelementfromasequencelist(Big-Oh)is.23O(1)b.O(n) c.O(n)d.O(n)(d)Inacircularqueuewecandistinguish(區(qū)分)emptyqueuesfromfullqueuesby.a.usingagapinthearrayincrementingqueuepositionsby2insteadof1acountofthenumberofelementsd.aandc(b)Arecursivefunctioncancauseaninfinitesequenceoffunctioncallsif.a.theproblemsizeishalvedateachsteptheterminationconditionismissingnousefulincrementalcomputationisdoneineachsteptheproblemsizeispositive6．(c)Thefullbinarytreewithheight4has nodes.a.15 b.16(b)Searchinginanunsortedlistcanbemadefasterbyusing .a.binarysearchasentinel(哨兵)attheendofthelistlinkedlisttostoretheelementsaandc(b)Supposethereare3edgesinanundirectedgraphG,IfwerepresentgraphGwithaadjacencymatrix,Howmany “1”sarethereinthematrix?TOC\o"1-5"\h\za.3 b.6 c.1 d.9(d)ConstructaHuffmantreebyfourleafwhoseweightsare9,2,5,7respectively.Theweightedpathlength is .a.29 b.37 c.46Considerthefollowingweightedgraph.ConsiderDijkstra'salgorithmonthisgraphtofindtheshortestpathswi thsasastartingvertex.Whicharethefirstfourverticesextractedfromthepriorityqueuebythealgorithm(listedintheordertheyareextracted)?a.s,y,t,xb.s,y,x,zc.s,t,y,xd.s,y,x,tFig.1Hereisanarrayoftenintegers:5389170264Supposewepartitionthisarrayusingquicksort'spartitionfunctionandusing5forthepivot.Whichshowsthearrayafterpartitionfinishes:a.5342107968b.034215796831024589673102458976NoneoftheaboveFillinBlank(10points)Forthefollowingprogramfragmenttherunningtime(Big-Oh)isO(n2).for(inti=0;i<n;i++)for(intj=0;j<=i;j++)s;Westorea4×4symmetricmatrixAintoanarrayBwithrowmajororder,Storethelowertriangleonly.theindexofelementa[2][3]inBis6.3．Wecanuse3vectortypetostorevalueandofnon-zeroelementsinasparsematrix.A stack isalistwhereremovalandadditionoccuratthesameend.FrequentlyknownaLIFO(Last-In-First-Out)structure.T(n)=2T(n/2)+cn,T(n)=O(logn)T(n)=T(n-1)+cn,T(n)=O( n )Thereisabinarytreewhoseelementsarecharacters.Preorderlistofthebinarytreeis“ABECDFGH”IJandinorderlistofthebinarytreeis “EBCDAFHIG”J.PostordertraversalsequenceofthebinarytreeisEDCBIHJGFA.7．Thereare (n+1)/2leafnodesinafullbinarytreewithnnodes.8．Whentheinputhasbeensorted,therunningtimeofinsertionsort(Big-Oh)isO(n).9．Wesortthesequence(43，02，80，48，26，57，15，73，21，24，66)withshellsortforincrement3,theresultis (1502212426574366804873)10、Inacircularqueue,“front”and“rear”arethefrontpointerandrearpointerrespectively. Queuesizeis“maxsize”.Wheninsertanelementinthequeue,rear=__(rear+1)%maxsize__11.A B樹 isanexampleofasearchtreewhichismultiway(allowsmorethantwochildren).Atreeinwhicheverynodeisnosmallerthanitschildrenistermed 大頂堆 .ApplicationofAlgorithms (35points)GshowninFig2isadirectedgraph,pleasedescribeGwithadjacencymatrixandwritetheordersofbreadthfirsttraversalanddepthfirsttraversal.ABCDEA01010B00110C00001D00001E00000Dft:ABCEDBft:ABDCE2．Thesequenceofinputkeysisshownbelow:19 ，1，23，14，55，20，84，27，68，11，10，17Afixedtablesizeof19andahashfunctionH(key)=key%13，withlinearprobing(線性探測),fillthetablebelowandcomputetheaveragelengthofsuccessfulsearch.Showtheresultsofinserting53,17,78,09,45,65,87each,oneatatime,inainitiallyemptymaxheap(大根堆)writethesequenceofpreorder,postordertraversalsandaddinorderthreadsinthetree.Fig.3BuildaHuffmantreeanddetermineHuffmancodewhentheprobabilitydistribution(概率分布)overthe8alphabets(c1,c2,c3,c4,c5,c6,c7,c8)is,,,,,,,GraphGshowninFig4isadirectedgraph,pleasedescribeGwithadjacencylistandwritetopologicalordering.Fig.4Fillinblankofalgorithms. (15)1．HereissinglesourceshortestpathalgorithmDijkstra.Fillinblankofthealgorithm.classGraph{ #include<stack>Usingnamespacestd;intmatching(string&exp){Writeefficientfunctions(andgivetheirBig-Ohrunningtimes)thattakeapointertoabinarytreerootTandcompute:–ThenumberofleavesofTtypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;amethodcalledmaximumDegreeofanundirectedhgraphthatreturnsthemaximumdegreeofanyvertexinthegraph.Thegraphisstoredwithadjacencymatrix.Writethedefinitionofthegraph.implementthefunction.Analyzespacecomplexityandtimecomplexityofyourfunction.3.Writeafunctionwithlinkedlistthatinsertsanumberintoasortedlinkedlist.Firstly,youshouldwriteafunctioncreatesalistthatlikethis:L={3,5,8,12,32,48}andtheninsert25intothislist.答案解析0-0，僅供參考，若有不同意見請聯(lián)系☆ _☆選擇題：1-5:ACBDB6-11:CBBDDE1、知識點：復(fù)雜度分析，必考思路：復(fù)雜度主要計算算法的步數(shù)，可以看出，當(dāng)前循環(huán)執(zhí)行的步數(shù)與i的值是相等的，所以可列1+2+..+i=(5*n*n+2)，復(fù)雜度的計算忽略常數(shù),(1+i)*i/2=(5*n*n+2),i~O(n)2、知識點：non-linear與linear的區(qū)別3、知識點：復(fù)雜度分析+線性序列思路：很顯然，當(dāng)元素在sequencelist的末尾的時候，removing元素復(fù)雜度最高O(n)4、知識點：循環(huán)隊列(circularqueue)，重點思路：主要區(qū)分循環(huán)隊列判斷空與滿的條件。主要有三個方法count計數(shù)，判斷當(dāng)前隊列的元素與maxsize的大小vis標(biāo)志，比如可以一開始設(shè)vis=0,滿時設(shè)置vis=1就是題目中說的gap( 重點)front代表頭指針,rear代表尾指針循環(huán)隊列空時：front==rear; 滿時：front==(rear+1)%maxsize5、知識點：遞歸的定義,terminationmissing，終止條件缺失則可能無限調(diào)用。6、知識點：完全二叉樹(completebinarytree)與滿二叉樹(fullbinarytree)的區(qū)別思路：學(xué)院PPT上有如下定義depthofanode:numberofancestorsheightofatree:maximumdepthofanynode并且有結(jié)點計算公式：2h+1-1(其中h為樹的高度，與某XX百度定義樹的高度不一樣，且照學(xué)院教材來做==)所以ans:24+1-1=317、知識點：查找思路：有疑問的題...單純來說二分查找(binarysearch)的速度O(logN)是比較快的，可是題目僅僅要求Searchinginanunsortedlist, 只進(jìn)行一次查找，那我們用二分還要先進(jìn)行排序O(NlogN)+O(logN)的復(fù)雜度是不如選項b的。sentinel( 哨兵...)的概念可見ppt講插入排序的地方，貌似能加快查找速度吧...8、知識點：圖的鄰接矩陣存儲思路：注意題目所問，無向圖(undirectedgraph),每條邊都是要存儲兩遍的9、知識點：哈夫曼樹(Huffmantree)思路：離散上學(xué)過的。。。weightedpathlength=權(quán)值路徑長度所以ans=9*1+7*2+5*3+2*3=44(自己構(gòu)造哈夫曼樹》?！?10、知識點：Dijkstra/最短路,重點11、知識點：快排,重點10、11兩題是重點，限文字難于描述清楚，請自主學(xué)習(xí) %>_<%注意10題在priority_queue里進(jìn)行更新時一開始肯定加入s、y結(jié)點，而后x結(jié)點會因為松弛操作從而距離變?yōu)?+3=4<5(t結(jié)點)，所以x結(jié)點會比t結(jié)點先壓入隊列。二、填空題21、O(n2)2、 6 數(shù)組元素存儲地址的計算。注意題目中規(guī)定存儲下三角矩陣 lowertriangleonly3、 location 在稀疏矩陣中sparsematrix，如果對每個元素都進(jìn)行存儲的話空間復(fù)雜度為O(N2)，因為好多位置沒有值所以這會造成空間的極大浪費。可以用題目所說的，

只存儲有值元素的值與位置(即i,j下標(biāo))。4、 stack棧(stack)與隊列(queue)的區(qū)別，重點5、題目有問題。正確問法應(yīng)該是這樣：T(n)=2T(n/2)+cn,T(n)=O(T(n)=2T(n/2)+cn,T(n)=O( T(n)=T(n-1)+cn,T(n)=O( 時間復(fù)雜度計算。對題目有點疑問，故此題答案不確定。cn中的n是下標(biāo)還cn相乘。)對于T(n)=2T(n/2)+cn對于T(n/2)又會轉(zhuǎn)化為程度在遞減。可以自T(16)->T(8)->T(4)->T(2)->T(1),logn )n )(不清楚這是按遞歸還遞推進(jìn)行計算得出，還有T(n)都會轉(zhuǎn)化為2*T(n/2)+cn,2的指數(shù)次冪的那計算過程為T(n)=T(n-1)+cn，可以這樣想，每次計算T(n/4)的計算，如此計算下去，其實就是按己舉個例子，所以計比如計算T(16)，算次數(shù)為log16=4,類似的復(fù)雜度可以計算。6、 樹的前、中、后序遍歷，重點首先要明白前、中、后序遍歷是根據(jù)根的位置決定的，比如前序遍歷就是 (根左右)，中序遍歷為(左根右) 首先你得能很熟練的寫出一棵樹的前、中、后序遍歷(preorder、inorder、postorder)，然后可以進(jìn)行一下分析，對于前序遍歷 ABECDFGHI，J中序遍歷EBCDAFHIG，J由前序遍歷可知根結(jié)點肯定為A，那么從中序遍歷里面可以以A為中點進(jìn)行分割，左邊的部分必定屬于左子樹，右邊的部分肯定屬于右子樹，然后進(jìn)行一步步分割，自己多嘗試一下就ok了構(gòu)造樹如下：所以后序遍歷為:EDCBIHJGFAps:已知前序遍歷和后序遍歷，不能確定唯一的中序遍