2016华南理工大学数据结构试卷A及答案

«Da«DataStructure?A试卷题号一二三四五六七八九十一总分得分评卷人考前须知：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3.测试形式：闭卷；4.本试卷共十大题,总分值100分,测试时间120分钟.1.Selectthecorrectchoice.(20scores,each2scores)诚信应考,测试作弊将带来严重后果!华南理工大学期末测试⑴AnalgorithmmustbeordoallofthefollowingEXCEPT:(B)(A)Partiallycorrect(B)Ambiguous(C)terminate(D)ConcretestepsPickthegrowthratethatcorrespondstothemostefficientgrowingalgorithmasngetslarger:(B)(A)4n3(B)5n2logn(C)3n!(D)2nIfadataelementrequires12bytesandapointerrequires4bytes,thenalinkedlistrepresentationwillbemorespaceefficientthanastandardarrayrepresentationwhenthefractionofnon-nullelementsislessthanabout:(B)(A)1/3(B)3/4(C)3/5(D)2/3Whichistherealizationofadatatypeasasoftwarecomponent:(A)(A)Anabstractdatatype(B)Arealdatatype(C)Atype(D)AdatastructureThemosteffectivewaytoreducethetimerequiredbyadisk-basedprogramisto:(B)(A)ImprovethebasicI/Ooperations.(B)Minimizethenumberofdiskaccesses.(C)Eliminatetherecursivecalls.(D)Reducemainmemoryuse.Inthehashfunction,collisionrefersto(B).Twoelementshavethesamekeyvalue.Differentkeysaremappedtothesamepositionofhashtable.Tworecordshavethesamerequiringnumber.Dataelementsaretoomuch.GivenanarrayasA[m][n].SupposedthatA[0][0]islocatedat644(io)andA[4][4]isstoredat676i.).(彳0)“meansthatthenumberispresentedindecimals.ThentheelementA[2][2](io)isatposition:(B)(A)692(B)660(C)650(D)708Whichstatementisnotcorrectamongthefollowingfour:(A)Thenumberofemptysub-treesinanon-emptybinarytreeisonelessthanthenumberofnodesinthetree.TheMergesortisastablesortingalgorithm.Therootofabinarytreetransferredfromageneraltreehasonlyleftchild.Asectoristhesmallestunitofallocationforarecord,soallrecordsoccupyamultipleofthesectorsize.(9)Treeindexingmethodsaremeanttoovercomewhatdeficiencyinhashing?(D)(A)Inabilitytohandlerangequeries.(B)Inabilitytomaximumqueries(C)Inabilitytohandlequeriesinkeyorder(D)Allofabove.(10)Assumethatwehaveeightrecords,withkeyvaluesAtoH,andthattheyareinitiallyplacedinalphabeticalorder.Now,considertheresultofapplyingthefollowingaccesspattern:FDFGEGFADFGEifthelistisorganizedbythetransposeheuristic,thenthefinallistwillbe(B).(A)AFCDHGEB(B)ABFDGECH(C)ABFGDCEH(D)AHFDGECBFilltheblankwithcorrectC++codes:(16scores)Givenanarraystoringintegersorderedbyvalue,modifythebinarysearchroutinestoreturnthepositionofthefirstintegerwiththeleastvaluegreaterthanKwhenKitselfdoesnotappearinthearray.ReturnERRORifthegreatestvalueinthearrayislessthanK:(10scores)//Returnpositionoflestelement>=Kintnewbinary(intarray[],intn,intK){intl=-1;intr=n;//landrbeyondarrayboundswhile(l+1!=r){//Stopwhenlandrmeet_inti=(l+r)/2一；//Checkmiddleofremainingsubarrayif(K<array[i])r=i;//Inlefthalfif(K==array[i])returni;//Founditif(K>array[i])l=i//Inrighthalf}——//KisnotinarrayorthegreatestvalueislessthanKifK<array[n-1]orr!=nthenreturnr;//thefirstintegerwiththeleastvaluegreaterthanK//whenKitselfdoesnotappearinthearrayelsereturnERROR;//thegreatestvalueinthearrayislessthanK}⑵Theheightoftheshortesttreeandthetallesttreewithbothnnodesisrespectively

_2_orn(n<2)and__n_,supposethattheheightoftheone-nodetreeis1.A3-aryfulltreewithninternalnodeshas__3n+1_nodes.(6scores)Pleasecalculatethenumberofbinarytreesindifferentshapewith6nodesintotal,and6nodes?(4scores)2nodes:2shapes3nodes:rootwith1and2canbeallocatedtoleftandrightso1+2+2=54nodes:3canbeallocatedas0,3;1,2;2so5+5+2+2=145nodes:14+14+5+5+4=426nodes:32+32+14+14+5*2*2=132,C2nn/n+1AcertainbinarytreehasthepostorderenumerationasDCBEHJIGFAandtheinorderenumerationasBCDAEFGHIJ.Trytodrawthebinarytreeandgivethepostorderenumeration.(Theprocessofyoursolutionisrequired!!!)(6scores)preorderenumeration:ABCDFEGIHJ5.Designanalgorithmtotransferthescorereportfrom100-pointto5-point,thelevelEcorrespondingscore<60,6cH69beingD,70〜79beingC,80〜89asB,score>=90asA.Thedistributiontableisasfollowing.Pleasedescribeyouralgorithmusingadecisiontreeandgivethetotalpathlength.(6scores)Scorein100-point0-5960-6970-7980-8990-100Distributionrate5%10%45%35%5%solution:thedesignlogicistobuildaHuffmantreeTotallength:4*10%+10%*3+35%*2+45%=1.85,the0-false,1-trueasthelogicbranches.Recoveryageneraltreeasfollowingtransferredfromabinarytree.(4scores)TracebyhandtheexecutionofQuicksortalgorithmonthearray:inta[]={44,77,55,99,66,33,22,88,79}Thepivotis66inthefirstpass,thesecondis55and88,thethirdis33and77,thefouris22,andsoontillthealgorithmisfinished.(6scores)initial:44,77,55,99,66,33,22,88,79pass1:442255336699778879TOC\o"1-5"\h\zpass2:442233556679778899pass3:332244556677798899pass4:223344556677798899finalsortedarray:223344556677798899(a)Describesimplythemaintasksofthetwophasesofexternalsorting.(4scoresThetaskoffirstphaseistobreakthefilesintolargeinitialrunsbyreplacementselection;thesecondphaseistomergetherunstogethertoformasinglesortedrunfile.(b)Assumethatworkingmemoryis512KBbrokenintoblocksof4096bytes(thereisalsoadditionalspaceavailableforI/Obuffers,programvariables,etc.)Whatistheexpectedsizeforthelargestfilethatcanbemergedusingreplacementselectionfollowedbytwopassesofmulti-waymerge?Explainhowyougotyouranswer.(4scores)Sinceworkingmemoryis512KBandtheblocksizeis4KB,theworkingmemoryholds128blocks.Theexpectedrunlengthis1024KB,soasinglepassofmultiwaymergeformsrunsoflength1024KB*128=128MB.Thesecondpassthenformsarunaslargeas128MB*128=16GB.Assumeadiskdriveisconfiguredasfollows.Thetotalstorageisapproximately675Mdividedamong15surfaces.Eachsurfacehas612tracks;thereare144sectors/track,512byte/sector,and16sectors/cluster.Thediskturnsat7200rmp(8.33ms/r).Thetrack-to-trackseektimeis20ms,andtheaverageseektimeis80ms.Nowhowlongdoesittaketoreadallofthedataina380KBfileonthedisk?Assumethatthefile'sclustersarespreadrandomlyacrossthedisk.AseekmustbeperformedeachtimetheI/Oreadermovestoanewtrack.Showyourcalculations.(Theprocessofyoursolutionisrequired!!!)(6cores)Aclusterholds16*0.5K=8K.Thus,thefilerequires380/8=47.5clusters.Thetimetoreadaclusterisseektimetothecluster+latencytime+(interleaffactorxrotation

time).Averageseektimeisdefinedtobe80ms.Latencytimeis0.5*8.33,andclusterrotationtimeis47.5*(16/144)*8.33.Seektimeforthetotalfilereadtimeis47*(80+0.5*600/72+(16/144)*600/72)+(80+0.5*600/72+(8/144*600/72))=4083.98msUsingclosedhashing,withdoublehashingtoresolvecollisions,insertthefollowingkeysintoahashtableofelevenslots(theslotsarenumbered0through10).ThehashfunctionstobeusedareH1andH2,definedb