雨课堂学堂在线学堂云《Data Structures and Algorithms（西安邮电）》单元测试考核答案

第1题1Inthedatastructure,thedatastructurecanbelogicallydividedinto().AdynamicstructureandstaticBcompactstructureandnon-compactstructureClinearandnonlinearstructureDinternalstructureandexternalstructure第2题2Inthedatastructure,fromthestoragestructurecanbedividedinto().AdynamicstructureandstaticBsequentialstructureandlinkedstructureCcompactstructureandnon-compactstructureDlinearandnonlinearstructures第3题3Thetimecomplexityofthealgorithmdependson().AthescaleoftheproblemBinitialstateofdatatobeprocessedCthescaleoftheproblemandtheinitialstateofthedatatobeprocessedDNocorrectanswer第4题4ThetimecomplexityofanalgorithmisO(n^2),indicatingthatthealgorithm's().Aexecutiontimeisproportionalton^2Bscaleoftheproblemisn^2Cexecutiontimeisequalton^2Dscaleoftheproblemisproportionalton^2第5题5Inthefollowingprogramsegment,thefrequencyoftheassignmentstatementforxis().FORi:=1TOnDOFORj:=1TOnDOx:=x+1;AO(2n)BO(n)CO(n^2)DO(log2n)第6题6Whendesigningcontinuousstorage,theaddressofthestorageunit().AmustbecontinuousBmustnotbecontinuousCnotnecessarilycontinuousDPartiallycontinuous,partiallydiscontinuous第7题7Theimportantcriterionforevaluatingtheperformanceofanalgorithmis().AalgorithmcorrectnessBalgorithmiseasytodebugCalgorithmtimecomplexityDalgorithmiseasytounderstand第8题8Ifyouneedtouseformalparameterstodirectlyaccessandmodifytheactualparametervalues,youshoulddescribetheformalparametersas()parameters.AvalueparameterBrealaddressCpointerDaddressparameters第9题9Foragivennelements,thereare()kindsoflogicalstructuresthatcanbeconstructed.A3B4C5D6第10题10Inthefollowingprogramsegment,thesentencefrequencyofx=x+1;is().for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;AO(2n)BO(n)CO(n^2)DO(log2n)第11题11Thetimecomplexityofthefollowingfunctionsum(n)is().sum(intn){intsum=0;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p*=j;sum+=p;}return(sum);}AO(2n)BO(n)CO(n^2)DO(log2n)第12题12Thereisthefollowingrecursivefunctionfact(n),whosetimecomplexityis().intfact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}AO(2n)BO(n)CO(n^2)DO(log2n)第13题13Afterthefollowingstatementsegmentisexecuted,thevalueofiis()intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A2B4C8DInfiniterecursion第1题1.Whichofthefollowingistheadvantageofsequentialstoragestructure().AA.highstoragedensityBB.easytoinsertCC.easytodeleteDD.Itcanbeeasilyusedforstoragerepresentationofvariouslogicalstructures第2题2.Theerrorinthefollowingdescriptionofthelineartableis().AA.Thelineartableusessequentialstorage,whichiseasytoinsertionanddeletion.BB.Thelineartableusessequentialstorage,andmustoccupyacontinuousstorageunit.CC.Thelineartableuseslinkedstorage,whichdoesnotneedtooccupyacontinuousstorageunit.DD.Thelineartableuseslinkedstorage,whichiseasytoinsertanddelete.第3题3.Ifthemostcommonoperationofalineartableistoaccessanyelementwithspecifiedsequencenumberandinsertanddeleteattheendoftheoperation,the()storagemethodisthemosttime-savingAA.sequencetableBB.doublylinkedlistCC.doublylinkedcircularlistwithaheadnodeDD.singlylinkedcircularlist第4题4.Iftheaddressofthefirstelementinasequencetableisbase(indexstartsfrom1),andeachnodeaccountsforMunits,thentheaddressoftheithnodeis()AA.Base+(i-1)×mBB.Base+(i+1)×mCC.Base+i×mDD.Base-i×m第5题5.Themostcommonoperationinalineartableistoinsertanelementafterthelastelementanddeletethefirstelement,so()storageisthemosttime-savingoperation.AA.singlylinkedcircularlistwithonlyatailpointerBB.singlylinkedlsitCC.singlylinkedcircularlistwithonlyaheadpointerDD.doublylinkedlist第6题6.Themostcommonoperationforsettingalinkedlististoinsertanodeattheendanddeletethetailnode,so()isthemosttime-savingoption.AA.doublylinkedcircularlistwithaheadnodeBB.singlylinkedlistCC.singlylinkedcircularlistwithatailpointerDD.singlylinkedcircularlist第7题7.Thepointerinthestaticlinkedlistrepresents().AA.theaddressofthenextelementBB.memoryaddressCC.arraysubscriptDD.addressoftheleftchildandtherightchild第8题8.Ifthelineartablewithlengthnusesthesequentialstoragestructure,thetimecomplexityofthealgorithmofinsertinganewelementinitsithpositionis().AA.O(n)BB.O(0)CC.O(1)

DD.O(n^2)第9题9.Forthesequencetable,thetimecomplexityofaccessinganddeletingnodesare().AA.O(1)

O(n)BB.O(n)

O(n)CC.O(n)

O(1)DD.O(1)

O(1)第10题10.InsertthenodewhosepointerisSafterthenodewhosepointerisPinthesinglylinkedlist.Thecorrectoperationis().AA.s->next=p->next;p->next=s;BB.p->next=s;s->next=p->next;CC.p->next=s;p->next=s->next;DD.p->next=s->next;p->next=s;第11题11.Forasinglylinkedlistwiththeheadnodeandheadpointerishead,Theconditionforjudgingthatthetableisemptyis()AA.s->next=p->next;p->next=s;BB.p->next=s;s->next=p->next;CC.p->next=s;p->next=s->next;DD.p->next=s->next;p->next=s;第12题12.Mergetwoorderedtableswithnelementsintooneorderedtable,andtheminimumnumberofcomparisonis().AA.n

BB.2n-1CC.2nDD.n-1第13题13.Ifthemostcommonoperationofatableistoinsertanodeafterthelastnodeordeletethelastnode.Then,thestoragemethodof()isadoptedtosavetheoperationtime.AA.doublylinkedcircularlistwithaheadnodeBB.singlylinkedlsitCC.doublylinkedlistDD.singlylinkedcircularlist第14题14.ThecharacteristicofthetailnodePofthelinkedcircularlistHis().AA.P->next=HBB.P->next=H->next

CC.P=HDD.P=H->next第15题15.Twopointers,PandQ,pointtotwoelementsofthesinglylinkedlistrespectively.TheconditionthattheelementPreferstoistheprecursoroftheelementQreferstois().AAP->next==QBBP->next==Q->nextCCQ->next==PDDP==Q第16题16.Inadoublylinkedlist,theoperationtodeleteanodeafterthenodepis().AA.p->next=p->next->next;p->next->next->prior=p;BB.p->next->prior=p;p->next=p->next->next;

CC.p->next=p->next->next;p->next->prior=p;DD.p->next->next=p->next;p->next->prior=p;第17题17.Whenalineartableisstoredin()mode,itcannotaccessallothernodesfromanynodeinthetable.AA.singlylinkedlsitBB.doublylinkedlistCC.singlylinkedcircularlistDD.doublylinkedcircularlist第18题18.Foralineartablerequiresnotonlytobeabletoinsertanddeletequickly,butalsorequiresthatthestoragestructurecanreflectthelogicalrelationshipbetweendata,youshoulduse().AA.sequentialstoragestructureBB.linkedstoragestructureCC.hashstoragestructureDD.alloftheaboveisoktest3第1题Bothstacksandqueuesare().AALinearstructurewithrestrictedaccesspointsBBSequentiallystoredlinearstructureCCNon-linearstructureoflinkedstorageDDNon-linearstructurewithrestrictedaccesspoints第2题Accordingtotheorderofsixelements6,5,4,3,2,1pushintothestack,whichofthefollowingisnotalegalsequence().AA543612BB453216CC346521DD234156第3题SettheinitialstateofstackSandqueueQtobeempty.Elementse1,e2,e3,e4,e5,ande6pushintothestackSinsequence.Whenanelementispopped,itpushintothequeueQimmediately,ifthepopsequenceof6elementsise2,e4,e3,e6,e5,e1,thenthecapacityofstackSshouldbeatleast().AA3BB6CC4DD2第4题Designanalgorithmtojudgewhetherthebracketsinthediscriminantexpressionmatchtheoccurrence,andthedatastructureusing()isthebest.AAstackBBSequencelistCCQueueDDLinkedlist第5题Thesuffixexpressionoftheexpressiona*(b+c)-dis().AAabc+*d-

BBbc+a*d-CCab*c+d-

DDdabc+*-

第6题Whenrecursiveproceduresorfunctioncalls,adatastructureof()isneededtoprocessparametersandreturnaddresses.AAStack

BBQueueCC

MultidimensionalArraysDDLinearlist第7题Ifanarrayofsize6isusedtoimplementacircularqueue,andthecurrentvaluesofrearandfrontare0and3respectively,whenoneelementisdeletedfromthequeueandtwomoreelementsareadded,thevalueofrearandfrontis().AA4and2BB1and5CC2and4DD5and1第8题Thecircularqueuewiththemaximumcapacityofn,thetailpointerofthequeueisrear,andtheheadpointerofthequeueisfront,theconditionforqueueemptyis().AArear=frontBB(rear+1)MODn=frontCCrear+1=frontDD(rear-l)MODn=front第9题AssumingthattheelementsofthecircularqueuearestoredinthearrayA[m],andtheheadandtailpointersarefrontandrearrespectively,thenumberofelementsinthecurrentqueueis().AA(rear-front+m)%mBBrear-front+1CC(front-rear+m)%mDD(rear-front+1)%m第10题Theoutputofthefollowingprogramis().int

f(int

x)

{

return

(x>0)?x*f(x-1):2;

}

voidmain()

{int

i

;i=f(f(1));printf("%d",i);

}

AA4BB2

CC8DDunlimitedrecursion第11题Theinputsequenceofastackis12345,thenthefollowingsequencecannotbetheoutputsequenceofthestackis().AA54132BB23415CC23145DD15432第12题Theinputsequenceofastackis1,2,3,...,n,ifthefirstelementoftheoutputsequenceisi,thentheoutputelementj(1<=j<=n)is().AAi-j+1BBi-j-1

CCj-i+1DDUncertain第13题InDoublelinkedlists(nodesinclude:data,prior,next),whendeletingthenodepointedtobythepointerp，theoperationis（).AAp->prior->next=p->next;p->next->prior=p->prior;BBp->prior=p->prior->prior;p->prior->next=p;

CCp->next->prior=p;p->next=p->next->next;

DDp->next=p->prior->prior;p->prior=p->next->next;第14题SupposethatthesequenceofnelementsPUSHthestackisp1,p2,p3,...,pn,andtheoutputsequenceis1,2,3,...,n,ifp3=1,thenthevalueofp1is().AAThevaluemaybe2BBThevaluemustbe2CCThevaluecannotbe2DDThevaluecannotbe3第15题Theinputsequenceofastackis1,2,3,...,n,andthefirstelementoftheoutputsequenceisn,thenthei-thoutputelementis().AAn-i+1BBn-1CCiDDAnyelementispossible第16题ExistinginfixexpressionE=((100-4)/3+3*(36-7))*2.WhichofthefollowingistheequivalentpostfixexpressionofE?（Thereisonlyonecorrectanswer）AA、((1004–)3/3(367–)*+)2*BB、*+/–10043*3–3672CC、1004–3/3367–*+2*DD、*(+/(–1004)3*3(–367))2test4第1题1Whichofthefollowingstatementsaboutstringisincorrect().ANullstringisastringofspaces.BStringisafinitesequenceofcharacters.CPatternmatchingisanimportantoperationofstring.DStringcanusenotonlysequentialstorage,butalsolinkedstorage.第2题2Stringisaspeciallinearlist,itsparticularityisreflectedin().AdataelementischaractersBsequentialstorageClinkedstorageDlogicalstructureislinearstructure第3题3IfthestringS='software',thenumberofitsprefixtruesubstringsis().A7B10C9D8第4题4Thelengthofthestringis().AthenumberofcharactersinthestringBthenumberofdifferentlettersinastringCthenumberofdifferentcharactersinastringDthenumberofnonspacecharactersinastring第5题5Thenecessaryandsufficientconditionfortwostringstobeequalisthat().Athelengthofthetwostringsisequalandthecharactersinthecorrespondingpositionsareequal.Bthecharactersinthecorrespondingpositionsinthetwostringsareequal.Cthetwostringsarestoredinthesameform.Dthelengthoftwostringsisequal.第6题6Therearetwostringspandq,whereqisasubstringofp.thealgorithmforfindingthefirstpositionofqinpiscalled().ApatternmatchingBsubstringCconcatenatedstringDthelengthofstring第7题7KnownstringS='aaab',itsnextfunctionvalueis().A0123B1123C1231D1211第8题8Thenextfunctionvalueofthepatternstring'ababaabaa'is().A011234223456B012345678999C012121111212D0123012322345第9题9Thereturnvalueofthefunctionstrcmp('stcabuc','stbabuc')is().A1B-1C2第10题10Patternstringt='abcaabbcabcabdab',thenextfunctionvalueofthepatternstringis().A01112231123456712B01112211123456712C01102131011021701D01110013101100701第11题11Ifthenullstringisasubstringofanystring,thenumberofsubstringsofstringS='Computer'is().A37B9C36D8第12题12StrIndex（‘DATASTRUCTURE'，‘STR'）=（）.A5B3C4D6第13题13Ifthelengthofmainbodystringisnandthelengthofpatternstringism,thetimecomplexityofKMPalgorithmforpatternmatchingis().AO(m+n)

BO(m*n)CO(m)DO(n)第14题14StrIndex(‘IndexofString’,1,‘Str’）=（）.A10B9C8D7第15题15ThereturnvalueofSubStr('IlikeUniversity',8,3)is().AUni

BikeCverDers第16题16Therearetwostringspandq,qisp’ssubstring.Thealgorithmtosearchthefirsttimeqappearedinpiscalled()ASeekingsubstringBConcatenationCMatchingDSeekinglength第17题17Whichofthefollowingstatementsiscorrect?A“Emptystring”isblankstring.BEmptystringisasubstringofarbitrarystring.CStringonlycanbestoredinsequentialmethodandcannotbestoredinlinkedmethod.DInC++standards,charS[M]canrepresentuptoastringoflengthM.第18题18IfthestringS1='ABCDEFG',S2='9898',S3='###',S4='012345',executeconcat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,'8'),length(S2)))Notesubstr(S,i,j)istheoperationtotakestringS’sjcharactersfromsubscripti.Subscripthereisstartingfrom0.（Thereisonlyonecorrectanswer）AABC###G0123BABCD###2345CABCD###1234DABC###G2345第19题19Whichofthefollowingdescriptionsaboutstringisincorrect?AStringisafinitesequenceofcharacters.BPatternmatchingisanimportantoperation.CStringisalinearlistwhosedataobjectsandoperationsbothspecialDEmptystringisastringconsistingofspaces.test5第1题1ThereisasymmetricmatrixAoforder10,usingacompressedstoragemethod,withrow-majororder,a11isthefirstelement,itsstorageaddressis1,eachelementoccupiesanaddressspace,thentheaddressofa85is().A33B13C18D40第2题2ThereisanarrayA[i,j],thelengthofeachelementis3bytes,thevalueofiis1to8,thevalueofjis1to10.ThefirstaddressofthearrayisBA,withrow-majororder,theaddressofelementA[5,8]is().ABA+141BBA+180CBA+222DBA+225第3题3Assumingthatthetwo-dimensionalarrayA[1...100,1...100]isstoredinrow-majororder,andeachelementoccupies2storageunits,andthebaseaddressis10,thenLOC[5,5]=().A808B818C1010D1020第4题4Eachelementofthetwo-dimensionalarrayAisastringof6characters,therowsubscriptirangesfrom0to8,andthecolumnsubscriptjrangesfrom1to10,sostoringArequiresatleast()bytes.A90B180C240D540第5题5Eachelementofthetwo-dimensionalarrayAisastringof6characters,therowsubscriptirangesfrom0to8,andthecolumnsubscriptjrangesfrom1to10,thenthe8thcolumnofAandthe5throwoccupy()bytes.A54B108C114D150第6题6Eachelementofthetwo-dimensionalarrayAisastringof6characters,therowsubscriptirangesfrom0to8,andthecolumnsubscriptjrangesfrom1to10,ThentheaddressofelementA[8,5]withrow-majororderisthesameaselement()withcolumn-majororder.AA[3,10]BA[8,5]CA[5,8]DA[0,9]第7题7LetAbean-ordersymmetricmatrix,itselementsofthelowertriangle(includingallelementsonthemaindiagonal)arestoredinrow-majororderintheone-dimensionalarrayB[1...(n+1)/2].Ifthevalueofaij((1≤i≤j≤n))isstoredinB[k],thenthecalculationformulaofkis().Aj(j-1)/2+iBi(i-1)/2+jCi(i+1)/2+jDj(j+1)/2+i第8题8LetAbean-ordersymmetricmatrix,itselementsoftheuppertriangle(includingallelementsonthemaindiagonal)arestoredincolumn-majororderintheone-dimensionalarrayB[1...(n+1)/2].Ifthevalueofaij(1≤i≤j≤n)isstoredinB[k],thenthecalculationformulaofkis().Aj(j-1)/2+iBi(i-1)/2+jCj(j-1)/2+i-1Di(i-1)/2+j-1第9题9Letthetwo-dimensionalarrayA[1...m,1...n]bestoredinthearrayB[1...m*n]byrow-majororder,thenthesubscriptoftheelementA[i,j]inarrayBis().A(i-1)n+j-1B(i-1)n+jCi(j-1)Dj*m+i-1第10题10Thereisasparsematrixof100*90,andthereare10non-zeroelements(inttype).Assumingthattheinttypeoccupies2bytes,thenumberofbytesrequiredtostorethematrixwithatriplesequencetableis().A66B60C18000D33第11题11Thepurposeofcompressedstorageofsparsematrixis().AtosavestoragespaceBfacilitatingmatrixoperationsCeasyinputandoutputDreducingthetimecomplexityofoperations第12题12ThenumberofelementsinarrayA[0...4,-1...-3,5...7]is().A45B55C36D16第13题13EachelementofthearrayA[0...5,0...6]occupies5bytes,anditisstoredincolumn-majororderinmemorywhitastartingaddressof1000,thentheaddressofelementA[5,5]is().A1175B1180C1205D1210第14题14Intriplesequencetableofsparsematrix,eachtriplerepresents().Atherownumber,columnnumberanddatavalueofnon-zeroelementsinthematrixBthedatavalueofnon-zeroelementsinthematrixCtherowandcolumnnumbersofelementsinthematrixDtherownumber,columnnumberanddatavalueofelementsinthematrix第15题15Aftercompressingandstoringthefollowingmatrix,itis()thatlosestherandomaccessfunction.AsparsematrixBsymmetricmatrixCtriangularmatrixDtridiagonalmatrixtest6第1题1Themostsuitablestructureforatreeis().AStructurewithbranchesandhierarchicalrelationshipsbetweenelementsBOrderedstructurebetweenelementCDisorderedstructurebetweenelementsDUnconnectedstructure第2题2Assumingthatthenumberofnodesofabinarytreeis18,itsheightisatleast().A4

B5

C6

D18第3题3Therelativepositionoftheleafnodeofanybinarytreeinitspreorder,inorder,andpostordersequence().ADefinitelynotchangedBMustchangeCSometimeschangesDUnconfirmed第4题4TheconditionforjudgingthatanodePinthethreadedbinary-treehasaleftchildis().Ap->LTag==0Bp!=NULLCp->lchild!=NULL

Dp->LTag==1第5题5Supposethereare4treesintheforestT,andthenumberofnodesisn1,n2,n3,n4respectively,thenwhentheforestTisconvertedintoabinarytree,thereare()nodesontherightsubtreeoftherootnode.An1-1Bn1Cn1+n2+n3Dn2+n3+n4第6题6ConstructaHuffmantreefrom4leafnodeswithweightsof9,2,5and7,thentheweightedpathlengthofthetreeis().A23B37C44D46第7题7LetTbeaHuffmantreewith8leafnodes,thenthehighestheightofTcanbe()A4B6C8D10第8题8Whichofthefollowingisaprefixcode?()A{0,1101,1110,1100,1111}B{0,1,01,010,110}C{00,01,10,11,101}D{01,00,10,001,110,101}第9题9Thepostfixexpressionofthearithmeticexpressiona+b*(c+d/e)is().Aabcde/+*+Bab+cde/*Cabcde/*++Dabcde*/++第10题10SupposethedegreeoftreeTis4,wherethenumberofnodeswithdegrees1,2,3and4are4,2,1,1,respectively,thenthenumberofleavesinTis().A5B6C7D8第11题11AHuffmantreehasatotalof215nodes,andHuffmancodingcangetatotalof()differentcodewords.A107B108C214D215第12题12AbinarytreewithNnodesisstoredinabinarylinkedlist,andthereare()nullpointerfields.AN+1BNCN-1DUnconfirmed第13题13ThetotalnumberofnodesinthebinarytreewithdepthK().A≤2^k-1B<2^k-1C=2^k-1D≤2^k第14题14AHuffmantreeconstructedwiththedataset{4,5,6,7,10,12,18}astheleafnodeweights,anditsweightedpathlengthis().A155B160C165D170第15题15Atreewith3degreeshas2nodeswith1degree,3nodeswith2degreesand4nodeswith3degrees,soithas()leafnodes.A12B10C11D13第16题16ItisknownthattheinfixformofanarithmeticexpressionisA+B*C-D/E,thesuffixformisABC*+DE/-,anditsprefixformis().A=-+A*BC/DEB-A+B*C/DEC-A+B*CD/ED-+*ABC/DE第17题17Ifanundirectedgraphwithnnodesandkedgesisaforest(n>k),thentheremustbe()treesintheforest.An-kBkCnDn+k第18题18AandBaretwonodesonabinarytree.Inthein-ordertraversal,theconditionforAbeforeBis().AAistotheleftofBBAistotherightofB

CAistheancestorofBDAisadescendantofB第19题19Afterconvertingatreeintoabinarytree,theshapeofthebinarytreeis().AOnlyBTherearemanyCTherearemany,butnoneoftherootnodeshaveleftchildrenDTherearemany,butnoneoftherootnodeshaverightchildren第20题20Whichofthefollowingstatementsiscorrect().AThereareatmosttwosubtreesinabinarytree,andthereareleftandrightsubtreesBAbinarytreeisanorderedtreeofdegree2CThereisnoleft-rightdistinctionwhenthenodehasonlyonechildinabinarytree.DTheremustbeanodeofdegree2inthebinarytree第21题21Therearealtogether()binarytreeswith7nodes,andtheyarenotsimilartoeachother.A429B428C427D426第22题22IntheHuffmantree,iftheencodinglengthisonlyallowedtobelessthanorequalto4,inadditiontothedeterminedencodingsoftwocharactersas0and10,atmost()characterscanbeencoded.A4B3C5D6第23题23Inthepreorder,inorderandpostordersequencesofthebinarytree,theorderofallleafnodesis().ANotthesameBExactlythesameCthesameinpreorderandinordersequence,butdifferentfromthatinpostordersequenceDthesameininorderandpostordersequence,butdifferentfromthatinperordersequenceEthesameininorderandpostordersequence,butdifferentfromthatinperordersequence第24题24Givenabinarytree,thepostordertraversalsequenceisEDBCA,andtheinordertraversalsequenceisBEDAC,thenthepreordertraversalsequenceis().ABAEDCBAEBDCCABDECDAEDBC第25题25Ifthereareonlynodeswithdegree0and2inthebinarytree,andifthereareXnodeswithdegree0,thenthenumberofnodesinthebinarytreeis().A2XB2X-1C2X+1DInsufficientconditionstocalculate第26题26Afullk-arytreewithdepthhhasatmost()leafnodes.Ak^(h-1)Bk^hC(k^(h-1)-1)/(k-1)D(k^h-1)/(k-1)第27题27Afullk-arytreewithdepthhhasatmost()nodes.Ak^(h-1)Bk^hC(k^(h-1)-1)/(k-1)D(k^h-1)/(k-1)第28题28IfaforesthasNverticesandKbranches（N>Kand2K>=N）,thentheforesthas()trees.AN-KBN-K+1CN-K/2DN-K/2+1第29题29AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenumberofnodesinT1,T2,T3aren1,n2,n3respectively.IfthebinarytreecorrespondingtoFisB,thereare()nodesintherightsubtreeofB.An2Bn3Cn1+n3Dn2+n3第30题30AssumethatFisaforest,madeupoftreeT1,T2,T3,andthenodenumbersofT1,T2,T3aren1,n2,n3respectively.IfthebinarytreecorrespondingtoFisB,thereare()nodesintheleftsubtreeofB.An2-1Bn3-1Cn1-1Dn2第31题31TransformatreeTintoabinarytreeB,Thenthepost-ordertraversalsequenceofTisthesameasthe()sequenceofB.ApreordertraversalBpostordertraversalCinordertraversalDleveltraversal第32题32Ifacomplete3-arytreeisstoredsequentiallyinaone-dimensionalarray(subscriptstartsfrom0).Thenwhichlevelisthenodewithsubscript121at?A4B5C6D7第33题33Ifacomplete3-arytreeisstoredsequentiallyinaone-dimensionalarray(subscriptstartsfrom0).Thenwhichlevelisthenodewithsubscript120at?A4B5C6D8第34题34Forthefollowingequivalenceclass,pleaseuse"weightedunionrule"andUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.4-06-28-49-43-59-55-21-27-1Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.A4464434444B4768831788C9225022205D4444643444test7第1题1.Anundirectedgraphwithnverticeshasatmost()edges.An(n-1)/2Bn(n-1)

Cn

D2n第2题2.Inadirectedgraphwithnvertices,atleastarcs()arerequiredtoconnectallvertices.AnBn-1Cn+1D2n第3题3.Inanundirectedgraph,thesumofdegreesofallverticesisequalto()timesthenumberofedges.A2

B1/2C1D4第4题4.Inadirectedgraph,thesumoftheindegreesofallverticesisequalto()timesthesumoftheoutdegreesofallvertices.A1B1/2C1D4第5题5.Foranundirectedgraphrepresentedbyanadjacencylistwithnverticesandeedges,thestoragespaceoccupiedis().An+2eBeC2eDn+e第6题6.Ifagraphwithnverticesformsaring,ithas()spanningtrees.AnBn-1Cn+1DUnclear第7题7.Theminimumspanningtreeofanyundirectedconnectednetwork().Ahaveoneormore

BonlyoneCmore

Dmaynotexist第8题8.Todeterminewhetherthereisaloopinadigraph,youcanuse().ADepth-firsttraversalalgorithmBThecriticalpathmethodCDijkstraDBreadth-firsttraversalalgorithm第9题9.AssumingthatgraphGhasnverticesandeedgesandadoptsadjacencytablestorage,thetimecomplexityofthetopologicalsortingalgorithmis().AO(n+e)BO(n)

CO(e)DO(n*e)第10题10.Thefollowingincorrectstatementis().AIfanykeyactivityiscompletedaheadoftime,thewholeprojectwillbecompletedaheadoftimeBKeyactivitiesnotcompletedontimewillaffectthecompletiontimeofthewholeprojectCAllkeyactivitiesarecompletedinadvance,thentheentireprojectiscompletedinadvanceDEarlycompletionofcertainkeyactivitieswillleadtoearlycompletionoftheentireproject第11题11.Thecriticalpathisintheeventnodenetworkis().AThelongestpathfromthesourcetothesinkBLongestloopCTheshortestpathfromthesourcetothesinkDShortestloop第12题12.GraphGisanon-connectedundirectedgraphwith28edgesintotal,sothegraphhasatleast()vertices.A9B8C10D11第13题13.Giventheadjacencymatrixrepresentationofagraph,themethodtodeleteallthestartingpointsfromthei-thvertexis().ASetalltheelementsonthei-throwofthematrixto0BSetalltheelementsonthei-thcolumnofthematrixto0CDeletethei-throwofthematrix,andmovethesubsequentrowsupDDeletethei-thcolumnofthematrix,andmovethesubsequentcolumnup第14题14.Depth-firsttraversalissimilartobinarytree().ATraversalBPreordertraversalCIn-ordertraversal

DPost-ordertraversal

第15题15.Breadth-firsttraversalissimilartobinarytree().APreordertraversalBIn-ordertraversal