ISingleChoice(10points)1.(a)Fortheis.i=0;s=0;following program fragment the running time(Big-Oh)while(s<(5*n*n+2)){i++;s=s+i;}2)1/2)3)a.O(n)b.O(nc.O(nd.O(n2.(c)Whichisnon-lineardatastructure_____.a.queuec.treed.sequencelist3.(b)Theworst-timeforremovinganelementfromasequencelist(Big-Oh)is.a.O(1)b.O(n)c.O(n2d.O(n3))4.(d)Inacircularqueuewecandistinguish(區分)emptyqueuesfromfullqueuesby.a.usingagapinthearrayb.incrementingqueuepositionsby2insteadof1acountofthenumberofelementsd.aandc(b)Arecursivefunctioncancauseaninfinitesequenceoffunctioncallsif .theproblemsizeishalvedateachsteptheterminationconditionismissingnousefulincrementalcomputationisdoneineachsteptheproblemsizeispositive6．(c)Thefullbinarytreewithheight4hasnodes.a.15b.167.(b)Searchinginanunsortedlistcanbemadefasterbyusing.binarysearchasentinel（哨兵）attheendofthelistlinkedlisttostoretheelementsaandc8.（b ）Supposethere are3edgesinanundirected graphG,IfGwithaadjacencymatrix,Howmany “1”sarethereinthematrixa.3 b.6 c.1 d.99.(d)ConstructaHuffmantreebyfourleafwhoseweightsare9,2,5,7respectively.Theweightedpathlength is___________.a.29 b.37 c.46

werepresent

graph10.Considerthefollowingweightedgraph.ConsiderDijkstra ’salgorithmonthisgraphtofindtheshortestpathswitasastarting vertex. Whicharethefirst four vertices extracted fromthequeuebythealgorithm(listedintheordertheyareextracted)a. s,y,t,x b. s, y,x,z c. s,t, y,x d. s,

hpriorityy,x,

stFig.1Hereisanarrayoftenintegers:5389170264Supposewepartitionthisarrayusingquicksort'spartitionfunctionandusing5forthepivot.Whichshowsthearrayafterpartitionfinishes:a.5342107968b.0342157968c.3102458967d.3102458976e.NoneoftheaboveIIFillinBlank(10points)1.Forthefollowingprogramfragmenttherunningtime(Big-Oh)is O(n2) .for(inti=0;i<n;i++)for(intj=0;j<=i;j++)s; Westorea4×4symmetricmatrixAintoanarrayBwithrowmajororder,Storethelowertriangleonly.theindexofelementa[2][3]inBis 6 .3．Wecanuse3vector typetostore valueand of non-zero elementsinasparsematrix.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_____)6.Thereis abinary tree whoseelements arecharacters. Preorder list ofthebinarytreeis “ABECDFGHIJ”andinorderlistofthebinarytreeis “EBCDAFHIGJ”.Postordertraversalsequenceofthebinarytreeis EDCBIHJGFA .7．Thereare (n+1)/2 leaf nodesinafull binary tree with nnodes.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).12.Atreeinwhicheverynodeisnosmallerthanitschildrenistermed_____大頂堆______.IIIApplicationofAlgorithms（35points）GshowninFig2isadirectedgraph,pleasedescribeGwithadjacencymatrixandwritetheordersofbreadthfirsttraversalanddepthfirsttraversal.B CA EDABCDEA01010B00110C00001D00001E00000Dft:ABCEDBft:ABDCE2．Thesequenceofinputkeysisshownbelow:19 ，1，23，14，55，20，84，27，68，11，10，17Afixedtablesizeof19andahashfunctionH(key)=key%13，withlinearprobing(線性探測),fillthetablebelowandcomputetheaveragelengthofsuccessfulsearch.3.Showtheresultsofinserting53,17,78,09,45,65,87each,oneatatime,inainitiallyemptymaxheap （大根堆）writethesequenceofpreorder,postordertraversalsandaddinorderthreadsinthetree.AB CD E FFig.3BuildaHuffmantreeanddetermineHuffmancodewhentheprobabilitydistribution(概率分布)overthe8alphabets(c1,c2,c3,c4,c5,c6,c7,c8)is,,,,,,,6.GraphGshowninFig4isadirectedgraph,pleasedescribeGwithadjacencylistandwritetopologicalordering.Fig.4IVFillinblankofalgorithms. （15）1．HereissinglesourceshortestpathalgorithmDijkstra.Fillinblankofthealgorithm.classGraph{ #include<stack>Usingnamespacestd;intmatching(string&exp){Write efficient functions (andgive their Big-Ohrunning times)that

take

apointertoabinarytreerootTandcompute:–ThenumberofleavesofTtypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;amethodcalledmaximumDegreeofanundirectedhgraphthatreturnsthemaximumdegreeofanyvertexinthegraph.Thegraphisstoredwithadjacencymatrix.Writethedefinitionofthegraph.implementthefunction.Analyzespacecomplexityandtimecomplexityofyourfunction.3.Writeafunctionwithlinkedlistthatinsertsanumberintoasortedlinked list. Firstly, youshouldwrite afunction creates alist that likethis:L={3,5,8,12,32,48}andtheninsert25intothislist.答案解析 0-0，僅供參考，若有不同意見請聯系☆ _☆選擇題：1-5:ACBDB6-11:CBBDDE1、知識點：復雜度分析，必考思路：復雜度主要計算算法的步數，可以看出，當前循環執行的步數與 i的值是相等的，所以可列1+2+..+i=(5*n*n+2) ，復雜度的計算忽略常數 ,(1+i)*i/2=(5*n*n+2),i~O(n)2、知識點：

non-linear

與

linear

的區別3、知識點：復雜度分析 +線性序列思路：很顯然，當元素在 sequencelist

的末尾的時候，

removing

元素復雜度最高

O(n)4、知識點：循環隊列

(circularqueue)

，重點思路：主要區分循環隊列判斷空與滿的條件。主要有三個方法count計數，判斷當前隊列的元素與

maxsize

的大小vis 標志，比如可以一開始設 vis=0,滿時設置 vis=1就是題目中說的 gap(.... 重點)front 代表頭指針,rear 代表尾指針循環隊列空時： front==rear; 滿時：front==(rear+1)%maxsize5、知識點：遞歸的定義 ,terminationmissing ，終止條件缺失則可能無限調用。6、知識點：完全二叉樹 (completebinarytree) 與滿二叉樹(fullbinarytree)

的區別思路：學院 PPT上有如下定義depthofanode:numberofancestorsheightofatree:maximumdepthofanynode并且有結點計算公式： 2h+1-1(其中不一樣，且照學院教材來做 ==)

h為樹的高度，與某

XX百度定義樹的高度所以ans:24+1-1=317、知識點：查找思路：有疑問的題...單純來說二分查找 (binary search)的速度O(logN)是比較快的，可是題目僅僅要求 Searching inanunsortedlist, 只進行一次查找 ，那我們用二分還要先進行排序 O(NlogN)+O(logN) 的復雜度是不如選項 b的。sentinel( 哨兵...) 的概念可見 ppt 講插入排序的地方，貌似能加快查找速度吧...8、知識點：圖的鄰接矩陣存儲思路：注意題目所問，無向圖 (undirectedgraph), 每條邊都是要存儲兩遍的9、知識點：哈夫曼樹 (Huffmantree)思路：離散上學過的。。。weightedpathlength= 權值 路徑長度所以ans=9*1+7*2+5*3+2*3=44( 自己構造哈夫曼樹》?！?10、知識點：Dijkstra/ 最短路,重點11、知識點：快排 ,重點10、11兩題是重點，限文字難于描述清楚，請自主學習 %>_<%注意10題在priority_queue 里進行更新時一開始肯定加入因 為松弛操作從而距離變為 1+3=4<5(t 結點)，所以x結點會比

s、y結點，而后 x結點會t結點先壓入隊列。二、填空題1、O(n2)2、6 數組元素存儲地址的計算。注意題目中規定存儲下三角矩陣 lowertriangleonly3、location 在稀疏矩陣中 sparsematrix，如果對每個元素都進行存儲的話空間復雜度為O(N2)，因為好多位置沒有值所以這會造成空間的極大浪費?？梢杂妙}目所說的，只存 儲有值元素的值與位置 (即i,j 下標)。4、stack 棧(stack) 與隊列(queue)的區別，重點5、題目有問題。正確問法應該是這樣：T(n)=2T(n/2)+cn,T(n)=T(n-1)+cn,

T(n)=O(____T(n)=O(_____

logn_____)n______)時間復雜度計算。對題目有點疑問，故此題答案不確定。 (不清楚這是按遞歸還遞推進行計算得出，還有cn中的n是下標還 cn相乘。)對于T(n)=2T(n/2)+cn ，可以這樣想，每次計算 T(n)都會轉化為 2*T(n/2)+cn,對于T(n/2) 又會轉化為 T(n/4)的計算，如此計算下去，其實就是按 2的指數次冪的程度在遞減?？?以自己舉個例子，比如計算 T(16) ，那計算過程為T(16)->T(8)->T(4)->T(2)->T(1), 所以計 算次數為 log16=4,類似 T(n)=T(n-1)+cn的復雜度可以計算。6、

樹的前、中、后序遍歷，重點首先要明白前、 中、后序遍歷是根據根的位置決定的，比如前序遍歷就是 (根左右)，中序遍歷為(左根右)....首先你得能很熟練的寫出一棵樹的前、 中、后序遍歷(preorder 、inorder 、postorder) ，然

后可以進行一下分析，對于前序遍歷 ABECDFGHIJ，中序遍歷 EBCDAFHIGJ，由前序遍歷可知根結點肯定為 A，那么從中序遍歷里面可以以 A為中點進行分割，左邊的部分必定屬于左子樹， 右邊的部分肯定屬于右子樹， 然后進行一步步分割， 自己多嘗試一下就ok了構造樹如下：所以后序遍歷為 :