..ISingleChoice(10points)1.(a)Forthefollowingprogramfragmenttherunningtime(Big-Oh)is.i=0;s=0;while(s<(5*n*n+2)){i++;s=s+i;}a.O(n)b.O(n2)c.O(n1/2)d.O(n3)2.(c)Whichisnon-lineardatastructure_____.a.queueb.stackc.treed.sequencelist3.(b)Theworst-timeforremovinganelementfromasequencelist(Big-Oh)is.a.O(1)b.O(n)c.O(n2)d.O(n3)4.(d)Inacircularqueuewecandistinguish(區(qū)分)emptyqueuesfromfullqueuesby.a.usingagapinthearrayb.incrementingqueuepositionsby2insteadof1c.keepingacountofthenumberofelementsd.aandc(b)Arecursivefunctioncancauseaninfinitesequenceoffunctioncallsif.theproblemsizeishalvedateachsteptheterminationconditionismissingnousefulincrementalputationisdoneineachsteptheproblemsizeispositive6．(c)Thefullbinarytreewithheight4hasnodes.a.15b.16c.31d.327.(b)Searchinginanunsortedlistcanbemadefasterbyusing.binarysearchasentinel〔哨兵〕attheendofthelistlinkedlisttostoretheelementsaandc8.〔b〕Supposethereare3edgesinanundirectedgraphG,IfwerepresentgraphGwithaadjacencymatrix,Howmany"1〞sarethereinthematrix"a.3b.6c.1d.99.(d)ConstructaHuffmantreebyfourleafwhoseweightsare9,2,5,7respectively.Theweightedpathlengthis___________.a.29b.37c.46d.4410.Considerthefollowingweightedgraph.ConsiderDijkstra’salgorithmonthisgraphtofindtheshortestpathswithsasastartingvertex.Whicharethefirstfourverticesextractedfromthepriorityqueuebythealgorithm(listedintheordertheyareextracted)"a.s,y,t,xb.s,y,x,zc.s,t,y,xd.s,y,x,tFig.111.Hereisanarrayoftenintegers:5389170264Supposewepartitionthisarrayusingquicksort'spartitionfunctionandusing5forthepivot.Whichshowsthearrayafterpartitionfinishes:a.5342107968b.0342157968c.3102458967d.3102458976e.NoneoftheaboveIIFillinBlank(10points)1.Forthefollowingprogramfragmenttherunningtime(Big-Oh)isO(n2).for(inti=0;i<n;i++)for(intj=0;j<=i;j++)s;//s為某種根本操作2.Westorea4×4symmetricmatrixAintoanarrayBwithrowmajororder,Storethelowertriangleonly.theindexofelementa[2][3]inBis6.3．Wecanuse3vectortypetostorevalueandofnon-zeroelementsinasparsematrix.4.A______stack______isalistwhereremovalandadditionoccuratthesameend.FrequentlyknownaLIFO(Last-In-First-Out)structure.T(n)=2T(n/2)+,T(n)=O(logn)T(n)=T(n-1)+,T(n)=O(_____n_____)6.Thereisabinarytreewhoseelementsarecharacters.Preorderlistofthebinarytreeis"ABECDFGHIJ〞andinorderlistofthebinarytreeis"EBCDAFHIGJ〞.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).12.Atreeinwhicheverynodeisnosmallerthanitschildrenistermed_____大頂堆______.IIIApplicationofAlgorithms〔35points〕1.GraphGshowninFig2isadirectedgraph,pleasedescribeGwithadjacencymatrixandwritetheordersofbreadthfirsttraversalanddepthfirsttraversal.Fig.2ABCDEA01010B00110C00001D00001E00000Dft:ABCEDBft:ABDCE2．Thesequenceofinputkeysisshownbelow:19，1，23，14，55，20，84，27，68，11，10，17Afixedtablesizeof19andahashfunctionH(key)=key%13，withlinearprobing(線性探測),fillthetablebelowandputetheaveragelengthofsuccessfulsearch.3.Showtheresultsofinserting53,17,78,09,45,65,87each,oneatatime,inainitiallyemptymaxheap〔大根堆〕4.writethesequenceofpreorder,postordertraversalsandaddinorderthreadsinthetree.Fig.35.BuildaHuffmantreeanddetermineHuffmancodewhentheprobabilitydistribution(概率分布)overthe8alphabets(c1,c2,c3,c4,c5,c6,c7,c8)is(0.05,0.25,0.03,0.06,0.10,0.11,0.36,0.046.GraphGshowninFig4isadirectedgraph,pleasedescribeGwithadjacencylistandwritetopologicalordering.Fig.4IVFillinblankofalgorithms.〔15〕HereissinglesourceshortestpathalgorithmDijkstra.Fillinblankofthealgorithm.classGraph{//圖的類定義private:floatEdge[NumVertices][NumVertices];floatdist[NumVertices]; //最短路徑長度數組 intpath[NumVertices]; //最短路徑數組 intS[NumVertices]; //最短路徑頂點集 public:voidShortestPath(int,int);intchoose(int);};voidGraph::ShortestPath(intn,intv){//在具有n個頂點的帶權有向圖中,各邊上權值由Edge[i][j]給出。建立一個數組:dist[j],0j<n,//保存從頂點v到頂點j的最短路徑長度,同時用數組path[j],0j<n,存放求到的最短路徑。for(inti=0;i<n;i++){dist[i]=Edge[v][i];//dist數組初始化S[i]=0; if(i!=v&&dist[i]<MAXNUM)path[i]=v;elsepath[i]=-1; //path數組初始化 }S[v]=1;dist[v]=0; //頂點v參加頂點集合//選擇當前不在集合S中具有最短路徑的頂點ufor(i=0;i<n;i++){ floatmin=MAXNUM;intu=v;for(intj=0;j<n;j++) if(!S[j]&&dist[j]<min) {u=j;min=dist[j];}S[u]=1; //將頂點u參加集合Sfor(intw=0;w<n;w++)//修改if(!S[w]&&Edge[u][w]<MAXNUM&&dis[w]>(min+Edge[u][w])){dist[w]=min+Edge[u][w];path[w]=u;}}}3．Considerthefollowingfunctiontobalancesymbolsstoredinstringexpthatincludesparentheses〔圓括號〕andnumbers.PleaseFillinblank.#include<stack>Usingnamespacestd;intmatching(string&exp){//expisapointertoastringtocheckintstate=1,i=0;chare;stack<char>s;while(i<exp.length()&&state)switch(exp[i]){case'(':s.push(exp[i]);i++;break;case')':if(!s.empty()&&s.front()==’(’){ s.pop();i++;}else state=0;//anerroroccursbreak;default:i++;break;}//endofwhileif(state&&s.empty())return1;elsereturn0;VProgramming〔30〕1.Writeefficientfunctions(andgivetheirBig-Ohrunningtimes)thattakeapointertoabinarytreerootTandpute:ThenumberofleavesofTtypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2.WriteamethodcalledmaximumDegreeofanundirectedhgraphthatreturnsthemaximumdegreeofanyvertexinthegraph.Thegraphisstoredwithadjacencymatrix.Writethedefinitionofthegraph.implementthefunction.Analyzespaceplexityandtimeplexityofyourfunction.3.Writeafunctionwithlinkedlistthatinsertsanumberintoasortedlinkedlist.Firstly,youshouldwriteafunctioncreatesalistthatlikethis:L={3,5,8,12,32,48}andtheninsert25intothislist.答案解析0-0，僅供參考，假設有不同意見請聯系QQ767954870☆_☆選擇題：1-5:ACBDB6-11:CBBDDE知識點：復雜度分析，必考思路：復雜度主要計算算法的步數，可以看出，當前循環(huán)執(zhí)行的步數與i的值是相等的，所以可列1+2+..+i=(5*n*n+2)，復雜度的計算忽略常數,(1+i)*i/2=(5*n*n+2),i~O(n)知識點：non-linear與linear的區(qū)別知識點：復雜度分析+線性序列思路：很顯然，當元素在sequencelist的末尾的時候，removing元素復雜度最高O(n)4、知識點：循環(huán)隊列(circularqueue)，重點思路：主要區(qū)分循環(huán)隊列判斷空與滿的條件。主要有三個方法count計數，判斷當前隊列的元素與maxsize的大小vis標志，比方可以一開場設vis=0,滿時設置vis=1就是題目中說的gap(....重點)front代表頭指針,rear代表尾指針循環(huán)隊列空時：front==rear;滿時：front==(rear+1)%maxsize知識點：遞歸的定義,terminationmissing，終止條件缺失那么可能無限調用。知識點：完全二叉樹(pletebinarytree)與滿二叉樹(fullbinarytree)的區(qū)別思路：學院PPT上有如下定義depthofanode:numberofancestorsheightofatree:maximumdepthofanynode并且有結點計算公式：2h+1-1(其中h為樹的高度，與某XX百度定義樹的高度 不一樣，且照學院教材來做==)所以ans:24+1-1=31知識點：查找思路：有疑問的題...單純來說二分查找(binarysearch)的速度O(logN)是比擬快的，可是題目僅僅要求 Searchinginanunsortedlist,只進展一次查找，那我們用二分還要先進展排序 O(NlogN)+O(logN)的復雜度是不如選項b的。sentinel(哨兵...)的概念可見ppt講插入排序的地方，貌似能加快查找速度吧...知識點：圖的鄰接矩陣存儲思路：注意題目所問，無向圖(undirectedgraph),每條邊都是要存儲兩遍的知識點：哈夫曼樹(Huffmantree)思路：離散上學過的。。。weightedpathlength=所以ans=9*1+7*2+5*3+2*3=44(自己構造哈夫曼樹"。")知識點：Dijkstra/最短路,重點知識點：快排,重點10、11兩題是重點，限文字難于描述清楚，請自主學習%>_<%注意10題在priority_queue里進展更新時一開場肯定參加s、y結點，而后x結點會因 為松弛操作從而距離變?yōu)?+3=4<5(t結點)，所以x結點會比t結點先壓入隊列。填空題O(n2)6數組元素存儲地址的計算。注意題目中規(guī)定存儲下三角矩陣lowertriangleonlylocation在稀疏矩陣中sparsematrix，如果對每個元素都進展存儲的話空間復雜度為 O(N2)，因為好多位置沒有值所以這會造成空間的極大浪費?？梢杂妙}目所說的，只存 儲有值元素的值與位置(即i,j下標)。stack棧(stack)與隊列(queue)的區(qū)別，重點題目有問題。正確問法應該是這樣：T(n)=2T(n/2)+,T(n)=O(____logn_____)T(n)=T(n-1)+,T(n)=O(_____n______)時間復雜度計算。對題目有點疑問，故此題答案不確定。(不清楚這是按遞歸還遞推進展計算得出，還有 中的n是下標還相乘。)對于T(n)=2T(n/2)+，可以這樣想，每次計算T(n)都會轉化為2*T(n/2)+,對于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)+的復雜度可以計算。樹的前、中、后序遍歷，重點首先要明白前、中、后序遍歷是根據根的位置決定的，比方前序遍歷就是(根左右)，中 序遍歷為(左根右)....首先你得能很熟練的寫出一棵樹的前、中、后序遍歷(preorder、inorder、postorder)，然 后可以進展一下分析，對于前序遍歷ABECDFGHIJ，中序遍歷EBCDAFHIGJ，由前序 遍歷可知根結點肯定為A，那么從中序遍歷里面可以以A為中點進展分割，左邊的部 分必定屬于左子樹，右邊的局部肯定屬于