川大软件数据结构选择题库

川大软件数据结构选择题库Chapter1DataStructuresandAlgorithms:Instructor'sCDquestions1.Theprimarypurposeofmostcomputerprogramsisa)toperformamathematicalcalculation.*b)tostoreandretrieveinformation.c)tosortacollectionofrecords.d)alloftheabove.e)noneoftheabove.2.Anintegerisa*a)simpletypeb)aggregatetypec)compositetyped)aandbe)noneoftheabove3.Apayrollrecordsisaa)simpletypeb)aggregatetypec)compositetype*d)aandbe)noneoftheabove4.WhichofthefollowingshouldNOTbeviewedasanADT?a)listb)integerc)array*d)noneoftheabove5.Amathematicalfunctionismostlikea*a)Problemb)Algorithmc)Program6.AnalgorithmmustbeordoallofthefollowingEXCEPT:a)correctb)composedofconcretesteps*c)ambiguousd)composedofafinitenumberofstepse)terminate7.Asolutionisefficientifa.itsolvesaproblemwithintherequireresourceconstraints.b.itsolvesaproblemwithinhumanreactiontime.c.itsolvesaproblemfasterthanotherknownsolutions.d.aandb.*e.aandc.f.bandc.8.Anarrayisa)Acontiguousblockofmemorylocationswhereeachmemorylocationstoresafixed-lengthdataitem.b)AnADTcomposedofahomogeneouscollectionofdataitems,eachdataitemidentifiedbyaparticularnumber.c)asetofintegervalues.*d)aandb.e)aandc.f)bandc.9.Orderthefollowingstepstoselectingadatastructuretosolveaproblem.(1)Determinethebasicoperationstobesupported.(2)Quantifytheresourceconstraintsforeachoperation.(3)Selectthedatastructurethatbestmeetstheserequirements.(4)Analyzetheproblemtodeterminetheresourceconstraintsthatanysolutionmustmeet.a)(1,2,3,4)b)(2,3,1,4)c)(2,1,3,4)*d)(1,2,4,3)e)(1,4,3,2)10.Searchingforallthoserecordsinadatabasewithkeyvaluebetween10and100isknownas:a)Anexactmatchquery.*b)Arangequery.c)Asequentialsearch.d)Abinarysearch.Chapter2MathematicalPreliminaries:Instructor'sCDquestions1.Asethasthefollowingproperties:a)Mayhaveduplicates,elementhaveaposition.b)Mayhaveduplicates,elementsdonothaveaposition.c)Maynothaveduplicates,elementshaveaposition.*d)Maynothaveduplicates,elementsdonothaveaposition.2.Asequencehasthefollowingproperties:*a)Mayhaveduplicates,elementhaveaposition.b)Mayhaveduplicates,elementsdonothaveaposition.c)Maynothaveduplicates,elementshaveaposition.d)Maynothaveduplicates,elementsdonothaveaposition.3.ForsetP,thenotation|P|indicates*a)ThenumberofelementsinP.b)TheinverseofP.c)ThepowersetofP.d)Noneoftheabove.4.AssumethatPcontainsnelements.ThenumberofsetsinthepowersetofPisa)nb)n^2*c)2^nd)2^n-1e)2^n+15.Ifasequencehasnvalues,thenthenumberofpermutationsforthatsequencewillbea)nb)n^2c)n^2-1d)2^n*e)n!6.IfRisabinaryrelationoversetS,thenRisreflexiveif*a)aRaforallainS.b)wheneveraRb,thenbRa,foralla,binS.c)wheneveraRbandbRa,thena=b,foralla,binS.d)wheneveraRbandaRc,thenaRc,foralla,b,cinS.7.IfRisabinaryrelationoversetS,thenRistransitiveifa)aRaforallainS.b)wheneveraRb,thenbRa,foralla,binS.c)wheneveraRbandbRa,thena=b,foralla,binS.*d)wheneveraRbandaRc,thenaRc,foralla,b,cinS.8.RisanequivalencerelationonsetSifitis*a)reflexive,symmetric,transitive.b)reflexive,antisymmetric,transitive.c)symmetric,transitive.d)antisymmetric,transitive.e)irreflexive,symmetric,transitive.f)irreflexive,antisymmetric,transitive.9.Forthepowersetofintegers,thesubsetoperationdefines*a)apartialorder.b)atotalorder.c)atransitiveorder.d)noneoftheabove.10.lognmisequaltoa)n+m*b)logn+logmc)mlognd)logn-logm11.Aclose-formsolutionisa)ananalysisforaprogram.*b)anequationthatdirectlycomputesthevalueofasummation.c)acompletesolutionforaproblem.12.Mathematicalinductionismostlikea)iteration.*b)recursion.c)branching.d)divideandconquer.13.Arecurrencerelationisoftenusedtomodelprogramswitha)forloops.b)branchcontrollike"if"statements.*c)recursivecalls.d)functioncalls.14.Whichofthefollowingisnotagoodprooftechnique.a)proofbycontradiction.*b)proofbyexample.c)proofbymathematicalinduction.15.Wecanusemathematicalinductionto:a)Findaclosed-formsolutionforasummation.*b)Verifyaproposedclosed-formsolutionforasummation.c)Bothfindandverifyaclosed-formsolutionforasummation.Chapter3AlgorithmAnalysis:Instructor'sCDquestions1.Agrowthrateappliesto:a)thetimetakenbyanalgorithmintheaveragecase.b)thetimetakenbyanalgorithmastheinputsizegrows.c)thespacetakenbyanalgorithmintheaveragecase.d)thespacetakenbyanalgorithmastheinputsizegrows.e)anyresourceyouwishtomeasureforanalgorithmintheaveragecase.*f)anyresourceyouwishtomeasureforanalgorithmastheinputsizegrows.2.Pickthegrowthratethatcorrespondstothemostefficientalgorithmasngetslarge:a)5n*b)20lognc)2n^2d)2^n3.Pickthegrowthratethatcorrespondstothemostefficientalgorithmwhenn=4.a)5nb)20lognc)2n^2*d)2^n4.Pickthequadraticgrowthrate.a)5nb)20logn*c)2n^2d)2^n5.Asymptoticanalysisrefersto:a)Thecostofanalgorithminitsbest,worst,oraveragecase.*b)Thegrowthincostofanalgorithmastheinputsizegrowstowardsinfinity.c)Thesizeofadatastructure.d)Thecostofanalgorithmforsmallinputsizes6.Foranairtrafficcontrolsystem,themostimportantmetricis:a)Thebest-caseupperbound.b)Theaverage-caseupperbound.*c)Theworst-caseupperbound.d)Thebest-caselowerbound.e)Theaverage-caselowerbound.f)Theworst-caselowerbound.7.Whenwewishtodescribetheupperboundforaproblemweuse:*a)Theupperboundofthebestalgorithmweknow.b)Thelowerboundofthebestalgorithmweknow.c)Wecan'ttalkabouttheupperboundofaproblembecausetherecanalwaysbeanarbitrarilyslowalgorithm.8.Whenwedescribethelowerboundforaproblemweuse:a)Theupperboundforthebestalgorithmweknow.b)thelowerboundforthebestalgorithmweknow.c)Thesmallestupperboundthatwecanproveforthebestalgorithmthatcouldpossiblyexist.*d)Thegreatestlowerboundthatwecanproveforthebestalgorithmthatcouldpossiblyexist.9.Whentheupperandlowerboundsforanalgorithmarethesame,weuse:a)big-Ohnotation.b)big-Omeganotation.*c)Thetanotation.d)asymptoticanalysis.e)Averagecaseanalysis.f)Worstcaseanalysis.10.Whenperformingasymptoticanalysis,wecanignoreconstantsandlowordertermsbecause:*a)Wearemeasuringthegrowthrateastheinputsizegetslarge.b)Weareonlyinterestedinsmallinputsizes.c)Wearestudyingtheworstcasebehavior.d)Weonlyneedanapproximation.11.Thebestcaseforanalgorithmrefersto:a)Thesmallestpossibleinputsize.*b)Thespecificinputinstanceofagivensizethatgivesthelowestcost.c)Thelargestpossibleinputsizethatmeetstherequiredgrowthrate.d)Thespecificinputinstanceofagivensizethatgivesthegreatestcost.12.Foranyalgorithm:*a)Theupperandlowerboundsalwaysmeet,butwemightnotknowwhattheyare.b)Theupperandlowerboundsmightormightnotmeet.c)Wecanalwaysdeterminetheupperbound,butmightnotbeabletodeterminethelowerbound.d)Wecanalwaysdeterminethelowerbound,butmightnotbeabletodeterminetheupperbound.13.IfanalgorithmisTheta(f(n))intheaveragecase,thenitis:a)Omega(f(n))inthebestcase.*b)Omega(f(n))intheworstcase.c)O(f(n))intheworstcase.14.Forthepurposeofperformingalgorithmanalysis,animportantpropertyofabasicoperationisthat:a)Itbefast.b)Itbeslowenoughtomeasure.c)Itscostdoesdependonthevalueofitsoperands.*d)Itscostdoesnotdependonthevalueofitsoperands.15.Forsequentialsearch,a)Thebest,average,andworstcasesareasymptoticallythesame.*b)Thebestcaseisasymptoticallybetterthantheaverageandworstcases.c)Thebestandaveragecasesareasymptoticallybetterthantheworstcase.d)Thebestcaseisasymptoticallybetterthantheaveragecase,andtheaveragecaseisasymptoticallybetterthantheworstcase.Chapter4Lists,StacksandQueues:Instructor'sCDquestions1.Anorderedlistisoneinwhich:a)Theelementvaluesareinsortedorder.*b)Eachelementapositionwithinthelist.2.Anorderedlistismostlikea:a)set.b)bag.*c)sequence.3.Ascomparedtothelinkedlistimplementationforlists,thearray-basedlistimplementationrequires:a)Morespaceb)Lessspace*c)Moreorlessspacedependingonhowmanyelementsareinthelist.4.HereisaseriesofC++statementsusingthelistADTinthebook.L1.append(10);L1.append(20);L1.append(15);Ifthesestatementsareappliedtoanemptylist,theresultwilllooklike:a)<102015>*b)<|102015>c)<102015|>d)<152010>e)<|152010>f)<152010|>5.Whencomparingthearray-basedandlinkedimplementations,thearray-basedimplementationhas:*a)fasterdirectaccesstoelementsbyposition,butslowerinsert/deletefromthecurrentposition.b)slowerdirectaccesstoelementsbyposition,butfasterinsert/deletefromthecurrentposition.c)bothfasterdirectaccesstoelementsbyposition,andfasterinsert/deletefromthecurrentposition.d)bothslowerdirectaccesstoelementsbyposition,andslowerinsert/deletefromthecurrentposition.6.Foralistoflengthn,thelinked-listimplementation'sprevfunctionrequiresworst-casetime:a)O(1).b)O(logn).*c)O(n).d)O(n^2).7.Findingtheelementinanarray-basedlistwithagivenkeyvaluerequiresworstcasetime:a)O(1).b)O(logn).*c)O(n).d)O(n^2).8.Inthelinked-listimplementationpresentedinthebook,aheadernodeisused:*a)Tosimplifyspecialcases.b)Becausetheinsertanddeleteroutineswon'tworkcorrectlywithoutit.c)Becausetherewouldbenootherwaytomakethecurrentpointerindicatethefirstelementonthelist.9.Whenapointerrequires4bytesandadataelementrequires4bytes,thelinkedlistimplementationrequireslessspacethanthearray-basedlistimplementationwhenthearraywouldbe:a)lessthan1/4full.b)lessthan1/3full.*c)lessthanhalffull.d)lessthan2/3full.e)lessthan3/4fullf)never.10.Whenapointerrequires4bytesandadataelementrequires12bytes,thelinkedlistimplementationrequireslessspacethanthearray-basedlistimplementationwhenthearraywouldbe:*a)lessthan1/4full.b)lessthan1/3full.c)lessthanhalffull.d)lessthan2/3full.e)lessthan3/4fullf)never.11.Whenwesaythatalistimplementationenforceshomogeneity,wemeanthat:a)Alllistelementshavethesamesize.*b)Alllistelementshavethesametype.c)Alllistelementsappearinsortorder.12.Whencomparingthedoublyandsinglylinkedlistimplementations,wefindthatthedoublylinkedlistimplementation*a)Savestimeonsomeoperationsattheexpenseofadditionalspace.b)Savesneithertimenorspace,butiseasiertoimplement.c)Savesneithertimenorspace,andisalsohardertoimplement.13.WeuseacomparatorfunctionintheDictionaryclassADT:a)tosimplifyimplementation.*b)toincreasetheopportunityforcodereuse.c)toimproveasymptoticefficiencyofsomefunctions.14.Alloperationsonastackcanbeimplementedinconstanttimeexcept:a)Pushb)Popc)Theimplementor'schoiceofpushorpop(theycannotbothbeimplementedinconstanttime).*d)Noneoftheabove.15.Recursionisgenerallyimplementedusinga)Asortedlist.*b)Astack.c)Aqueue.Chapter5BinaryTrees:Instructor'sCDquestions1.Theheightofabinarytreeis:a)Theheightofthedeepestnode.b)Thedepthofthedeepestnode.*c)Onemorethanthedepthofthedeepestnode.2.Afullbinarytreeisoneinwhich:*a)Everyinternalnodehastwonon-emptychildren.b)allofthelevels,exceptpossiblythebottomlevel,arefilled.3.Therelationshipbetweenafullandacompletebinarytreeis:a)Everycompletebinarytreeisfull.b)Everyfullbinarytreeiscomplete.*c)Noneoftheabove.4.TheFullBinaryTreeTheoremstatesthat:*a)Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternalnodes.b)Thenumberofleavesinanon-emptyfullbinarytreeisonelessthanthenumberofinternalnodes.c)Thenumberofleavesinanon-emptyfullbinarytreeisonehalfofthenumberofinternalnodes.d)Thenumberofinternalnodesinanon-emptyfullbinarytreeisonehalfofthenumberofleaves.5.ThecorrecttraversaltouseonaBSTtovisitthenodesinsortedorderis:a)Preordertraversal.*b)Inordertraversal.c)Postordertraversal.6.Wheneverynodeofafullbinarytreestoresa4-bytedatafield,two4-bytechildpointers,anda4-byteparentpointer,theoverheadfractionisapproximately:a)onequarter.b)onethird.c)onehalf.d)twothirds.*e)threequarters.f)noneoftheabove.7.Wheneverynodeofafullbinarytreestoresan8-bytedatafieldandtwo4-bytechildpointers,theoverheadfractionisapproximately:a)onequarter.b)onethird.*c)onehalf.d)twothirds.e)threequarters.f)noneoftheabove.8.Wheneverynodeofafullbinarytreestoresa4-bytedatafieldandtheinternalnodesstoretwo4-bytechildpointers,theoverheadfractionisapproximately:a)onequarter.b)onethird.*c)onehalf.d)twothirds.e)threequarters.f)noneoftheabove.9.Ifanodeisatpositionrinthearrayimplementationforacompletebinarytree,thenitsparentisat:*a)(r-1)/2ifr>0b)2r+1if(2r+1)<nc)2r+2if(2r+2)<nd)r-1ifrisevene)r+1ifrisodd.10.Ifanodeisatpositionrinthearrayimplementationforacompletebinarytree,thenitsrightchildisat:a)(r-1)/2ifr>0b)2r+1if(2r+1)<n*c)2r+2if(2r+2)<nd)r-1ifrisevene)r+1ifrisodd.11.AssumeaBSTisimplementedsothatallnodesintheleftsubtreeofagivennodehavevalueslessthanthatnode,andallnodesintherightsubtreehavevaluesgreaterthanorequaltothatnode.Whenimplementingthedeleteroutine,wemustselectasitsreplacement:a)Thegreatestvaluefromtheleftsubtree.*b)Theleastvaluefromtherightsubtree.c)Eitheroftheabove.12.Whichofthefollowingisatruestatement:a)InaBST,theleftchildofanynodeislessthantherightchild,andinaheap,theleftchildofanynodeislessthantherightchild.*b)InaBST,theleftchildofanynodeislessthantherightchild,butinaheap,theleftchildofanynodecouldbelessthanorgreaterthantherightchild.c)InaBST,theleftchildofanynodecouldbelessorgreaterthantherightchild,butinaheap,theleftchildofanynodemustbelessthantherightchild.d)InbothaBSTandaheap,theleftchildofanynodecouldbeeitherlessthanorgreaterthantherightchild.13.WhenimplementingheapsandBSTs,whichisthebestanswer?a)ThetimetobuildaBSTofnnodesisO(nlogn),andthetimetobuildaheapofnnodesisO(nlogn).b)ThetimetobuildaBSTofnnodesisO(n),andthetimetobuildaheapofnnodesisO(nlogn).*c)ThetimetobuildaBSTofnnodesisO(nlogn),andthetimetobuildaheapofnnodesisO(n).d)ThetimetobuildaBSTofnnodesisO(n),andthetimetobuildaheapofnnodesisO(n).14.TheHuffmancodingtreeworksbestwhenthefrequenciesforlettersarea)Roughlythesameforallletters.*b)Skewedsothatthereisagreatdifferenceinrelativefrequenciesforvariousletters.15.Huffmancodingprovidestheoptimalcodingwhen:a)ThemessagesareinEnglish.b)Themessagesarebinarynumbers.*c)Thefrequencyofoccurrenceforaletterisindependentofitscontextwithinthemessage.d)Never.Chapter6BinaryTrees:Instructor'sCDquestions1.TheprimaryADTaccessfunctionsusedtotraverseageneraltreeare:a)leftchildandrightsiblingb)leftchildandrightchild*c)leftmostchildandrightsiblingd)leftmostchildandnextchild2.Thetreetraversalthatmakestheleastsenseforageneraltreeis:a)preordertraversal*b)inordertraversalc)postordertraversal3.TheprimaryaccessfunctionusedtonavigatethegeneraltreewhenperformingUNION/FINDis:a)leftchildb)leftmostchildc)rightchildd)rightsibling*e)parent4.Whenusingtheweightedunionruleformergingdisjointsets,themaximumdepthforanynodeinatreeofsizenwillbe:a)nearlyconstant*b)lognc)nd)nlogne)n^25.Weusetheparentpointerrepresentationforgeneraltreestosolvewhichproblem?a)Shortestpathsb)Generaltreetraversal*c)Equivalenceclassesd)Exact-matchquery6.Whenusingpathcompressionalongwiththeweightedunionruleformergingdisjointsets,theaveragecostforanyUNIONorFINDoperationinatreeofsizenwillbe:*a)nearlyconstantb)lognc)nd)nlogn7.Themostspaceefficientrepresentationforgeneraltreeswilltypicallybe:a)Listofchildren*b)Left-child/rightsiblingc)AK-arytree.8.Theeasiestwaytorepresentageneraltreeisto:a)converttoalist.*b)converttoabinarytree.c)converttoagraph.9.AsKgetsbigger,theratioofinternalnodestoleafnodes:*a)Getssmaller.b)Staysthesame.c)Getsbigger.d)Cannotbedetermined,sinceitdependsontheparticularconfigurationofthetree.10.Asequentialtreerepresentationisbestusedfor:*a)Archivingthetreetodisk.b)Useindynamicin-memoryapplications.c)Encryptionalgorithms.d)Itisneverbetterthanadynamicrepresentation.Chapter7InternalSorting:Instructor'sCDquestions1.Asortingalgorithmisstableifit:a)Worksforallinputs.*b)Doesnotchangetherelativeorderingofrecordswithidenticalkeyvalues.c)Alwayssortsinthesameamountoftime(withinaconstantfactor)foragiveninputsize.2.Whichsortingalgorithmdoesnothaveanypracticaluse?a)Insertionsort.*b)Bubblesort.c)Quicksort.d)RadixSort.e)aandb.3.Whensortingnrecords,Insertionsorthasbest-casecost:a)O(logn).c)O(nlogn).d)O(n^2)e)O(n!)f)Noneoftheabove.4.Whensortingnrecords,Insertionsorthasworst-casecost:a)O(logn).b)O(n).c)O(nlogn).*d)O(n^2)e)O(n!)f)Noneoftheabove.5.Whensortingnrecords,Quicksorthasworst-casecost:a)O(logn).b)O(n).c)O(nlogn).*d)O(n^2)e)O(n!)f)Noneoftheabove.6.Whensortingnrecords,Quicksorthasaverage-casecost:a)O(logn).b)O(n).*c)O(nlogn).d)O(n^2)e)O(n!)f)Noneoftheabove.7.Whensortingnrecords,Mergesorthasworst-casecost:a)O(logn).b)O(n).*c)O(nlogn).d)O(n^2)e)O(n!)f)Noneoftheabove.8.Whensortingnrecords,Radixsorthasworst-casecost:a)O(logn).b)O(n).c)O(nlogn).d)O(n^2)e)O(n!)*f)Noneoftheabove.9.Whensortingnrecordswithdistinctkeys,Radixsorthasalowerboundof:a)Omega(logn).b)Omega(n).*c)Omega(nlogn).d)Omega(n^2)e)Omega(n!)f)Noneoftheabove.10.Anysortthatcanonlyswapadjacentrecordsasanaveragecaselowerboundof:a)Omega(logn).b)Omega(n).c)Omega(nlogn).*d)Omega(n^2)e)Omega(n!)f)Noneoftheabove.11.Thenumberofpermutationsofsizenis:a)O(logn).b)O(n).c)O(nlogn).d)O(n^2)*e)O(n!)f)Noneoftheabove.12.Whensortingnrecords,Selectionsortwillperformhowmanyswapsintheworstcase?a)O(logn).*b)O(n).c)O(nlogn).d)O(n^2)e)O(n!)f)Noneoftheabove.13.Shellsorttakesadvantageofthebest-casebehaviorofwhichsort?*a)Insertionsortb)Bubblesortc)Selectionsortd)Shellsorte)Quicksortf)Radixsort14.Apoorresultfromwhichstepcausestheworst-casebehaviorforQuicksort?*a)Selectingthepivotb)Partitioningthelistc)Therecursivecall15.Intheworstcase,theverybestthatasortingalgorithmcandowhensortingnrecordsis:a)O(logn).b)O(n).*c)O(nlogn).d)O(n^2)e)O(n!)f)Noneoftheabove.Chapter8FileProcessingandExternalSorting:Instructor'sCDquestions1.Ascomparedtothetimerequiredtoaccessoneunitofdatafrommainmemory,accessingoneunitofdatafromdiskis:a)10timesfaster.b)1000timesfaster.c)1,000,000timefaster.d)10timesslower.e)1000timesslower.*f)1,000,000timesslower.2.Themosteffectivewaytoreducethetimerequiredbyadisk-basedprogramisto:a)Improvethebasicoperations.*b)Minimizethenumberofdiskaccesses.c)Eliminatetherecursivecalls.d)Reducemainmemoryuse.3.ThebasicunitofI/Owhenaccessingadiskdriveis:a)Abyte.*b)Asector.c)Acluster.d)Atrack.e)Anextent.4.ThebasicunitfordiskallocationunderDOSorWindowsis:a)Abyte.b)Asector.*c)Acluster.d)Atrack.e)Anextent.5.Themosttime-consumingpartofarandomaccesstodiskisusually:*a)Theseek.b)Therotationaldelay.c