计算机组成原理

ISingleChoice(10 )Forthefollowingprogramfragmenttherunningtime(Big-Oh)is i=0;s=while(s<(5*n*n+ s=s+}a. b. c. d. )Whichisnon-lineardata a. c. d.sequence )Theworst-timeforremovinganelementfromasequence (Big-Oh) a. b. c. d. )Inacircularqueuewecandistinguish(区分)emptyqueuesfromfullqueues usingagapintheincrementingqueuepositionsby2insteadof1c.keeacountofthenumberofelementsd.aand )Arecursivefunctioncancauseaninfinitesequenceoffunctioncalls theproblemsizeishalvedateachtheterminationconditionisnousefulincrementalcomputationisdoneineachtheproblemsizeis )Thefullbinarytreewithheight4 a. b. )Searchinginanunsortedlistcanbemadefasterby binaryasentinel（哨兵）attheendofthelinkedlisttostoretheaand ）Supposethereare3edgesinanundirectedgraphG, IfwerepresentgraphGwithaadjacencymatrix,Howmany“1”sarethereinthematrix?a. b. c. d. )ConstructaHuffmantreebyfourleafwhoseweightsare9,2,5,7respectively.Theweightedpathlengthis a. b. c. ConsiderthefollowingweightedConsiderDijkstra’salgorithmonthisgraphtofindtheshortestpathswithsasastartingvertex.Whicharethefirstfourverticesextractedfromthepriorityqueuebythealgorithm(listedintheordertheyareextracted)?a.s,y,t, b.s,y,x, c.s,t,y, d.s,y,x,Fig.Hereisanarrayoftenintegers:5389170264Supposewepartitionthisarrayusingquicksort'spartitionfunctionandusing5forthepivot.Whichshowsthearrayafterpartitionfinishes:534210796034215796310245896310245897NoneoftheFillinBlank(10Forthefollowingprogramfragmenttherunningtime(Big-Oh)is for(inti=0;i<n;i++)for(intj=0;j<=i; //sWestorea4×4symmetricmatrixAintoanarrayBwithrowmajororder,Storethelowertriangleonly.theindexofelementa[2][3]inBis Wecanuse3vectortypetostorevalueand ofnon-zeroelementsinasparsematrix. isalistwhereremovalandadditionoccuratthesameend.FrequentlyknownaLIFO(Last-In-First-Out)structure.T(n)=2T(n/2)+ T(n)=T(n- T(n)= Thereisabinarytreewhoseelementsarecharacters.Preorderlistofthebinarytreeis“ABECDFGHIJ”andinorderlistofthebinarytreeis“EBCDAFHIGJ”.Postordertraversalsequenceofthebinarytreeis There leafnodesinafullbinarytreewithn8．Whentheinputhasbeensorted,therunningtimeofinsertionsort(Big-Oh) 9．Wesortthesequence（43，02，80，48，26，57，15，73，21，24，66）withssortincrement3,theresultis _sizeis“maxsize”.Wheninsertanelementinthequeue,rear= 11.A isanexampleofasearchtreewhichismultiway(allowsmorethantwochildren).12.Atreeinwhicheverynodeisnosmallerthanitschildrenis ApplicationofAlgorithms（35GraphGshowninFig2isadirectedgraph,pleasedescribeGwithadjacencymatrixandwritetheordersofbreadthfirsttraversalanddepthfirsttraversal.BBCAEDThesequenceofinputkeysisshownbelow:Afixedtablesizeof19andahashfunctionH(key)=key%13，withlinearprobing(线性探测),fillthetablebelowandcomputetheaveragelengthofsuccessfulsearch.Showtheresultsofinserting53,17,78,09,45,65,87each,oneatatime,inainitiallyemptymaxwritethesequenceofpreorder,postordertraversalsandaddinorderthreadsintheAABCDEFFig.BuildaHuffmantreeand determineHuffmancodewhentheprobabilitydistribution(概率分布)overthe8alphabets(c1,c2,c3,c4,c5,c6,c7,c8)is(0.05,0.25,0.03,0.06,0.10,0.11,GraphGshowninFig4isadirectedgraph,pleasedescribeGwithadjacencylistandwritetopologicalordering.Fig.Fillinblankofalgorithms.1．HereissinglesourceshortestpathalgorithmDijkstraFillinblankofthealgorithm.classGraph{ floatfloatdist[NumVertices];//最短路径长度数组intpath[NumVertices]; intS[NumVertices]; voidShortestPath(int, int);intchoose(int);voidGraph::ShortestPath(int intv//n个顶点的带权有向图中,Edge[i][j]给出。建立一个数组dist[j],0j<n,//vj的最短路径长度,path[j],0j<n,for(inti=0;i<n;i++)dist[i] //distS[i]=if(i!=v&&dist[i]<MAXNUM)path[i]=v;elsepath[i]=-1; //path数组初始化}S[v] dist[v] //顶点v//选择当前不在集合S中具有最短路径的顶点ufor(i=0;i< ;i++){floatmin=MAXNUM; intu=v;for(intj=0;j<n;j++)if(!S[j] {u= min=dist[j];S[u]=1; //将顶点u加入集合Sfor(intw=0;w<n;w++) if(!S[w]&&Edge[u][w]<MAXNUM {dist[w] path[w]= }（圆括号）andnumbers.PleaseFillinblank.#include<stack>Usingnamespaceintmatching(string&exp)//expisapointertoastringtocheckintstate=1,i=0;chare;stack<char>s;while(i<exp.length()&&state)switch(exp[i]){case;case')':if ) i++;state=0; //anerroroccursi++; //endofif return returnProgrammingWriteefficientfunctions(andgivetheirBig-Ohrunningtimes)thattakeapointertoabinarytreerootTandcompute:–ThenumberofleavesofTtypedefstructBiTNode struct }BiTNode,WriteamethodcalledumDegreeofanundirectedhgraphthatreturnstheumdegreeofanyvertexinthegraph.Thegraphisstoredwithadjacencymatrix.Writethedefinitiono