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

《DataStructure》B试卷第1页共5页诚信应考,考试作弊将带来严重后果！华南理工大学期末考试《DataStructure》A试卷注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共十大题，满分100分，考试时间120分钟。题号一二三四五六七八九十十一总分得分评卷人1.Selectthecorrectchoice.(20scores,each2scores)(1)AnalgorithmmustbeordoallofthefollowingEXCEPT:(B)(A)Partiallycorrect(B)Ambiguous(C)terminate(D)Concretesteps(2)Pickthegrowthratethatcorrespondstothemostefficientgrowingalgorithmasngetslarger:(B)(A)4n3(B)5n2logn(C)3n!(D)2n(3)Ifadataelementrequires12bytesandapointerrequires4bytes,thenalinkedlistrepresentationwillbemorespaceefficientthanastandardarrayrepresentationwhenthefractionofnon-nullelementsislessthanabout:(B)(A)1/3(B)3/4(C)3/5(D)2/3(4)Whichistherealizationofadatatypeasasoftwarecomponent:(A)(A)Anabstractdatatype(B)Arealdatatype(C)Atype(D)Adatastructure(5)Themosteffectivewaytoreducethetimerequiredbyadisk-basedprogramisto:(B)(A)ImprovethebasicI/Ooperations.(B)Minimizethenumberofdiskaccesses.(C)Eliminatetherecursivecalls.(D)Reducemainmemoryuse.(6)Inthehashfunction,collisionrefersto(B).(A)Twoelementshavethesamekeyvalue.(B)Differentkeysaremappedtothesamepositionofhashtable.(C)Tworecordshavethesamerequiringnumber.(D)Dataelementsaretoomuch.(7)GivenanarrayasA[m][n].SupposedthatA[0][0]islocatedat644(10)andA[4][4]isstoredat676(10).“(10)”meansthatthenumberispresentedindecimals.ThentheelementA[2][2](10)isatposition:(B)(A)692(B)660(C)650(D)708_____________________…，A姓名学号学院专业座位号(密封线内不答题)……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………《DataStructure》B试卷第2页共5页(8)Whichstatementisnotcorrectamongthefollowingfour:(A)(A)Thenumberofemptysub-treesinanon-emptybinarytreeisonelessthanthenumberofnodesinthetree.(B)TheMergesortisastablesortingalgorithm.(C)Therootofabinarytreetransferredfromageneraltreehasonlyleftchild.(D)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)AHFDGECB2.FilltheblankwithcorrectC++codes:(16scores)(1)Givenanarraystoringintegersorderedbyvalue,modifythebinarysearchroutinestoreturnthepositionofthefirstintegerwiththeleastvaluegreaterthanKwhenKitselfdoesnotappearinthearray.ReturnERRORifthegreatestvalueinthearrayislessthanK:(10scores)//Returnpositionoflestelement=Kintnewbinary(intarray[],intn,intK){intl=-1;intr=n;//landrbeyondarrayboundswhile(l+1!=r){//Stopwhenlandrmeet___inti=（l+r）/2_____;//Checkmiddleofremainingsubarrayif(Karray[i])__r=i___;//Inlefthalfif(K==array[i])returni;//Founditif(Karray[i])___l=i___//Inrighthalf}//KisnotinarrayorthegreatestvalueislessthanKifKarray[n-1]orr!=nthenreturnr;//thefirstintegerwiththeleastvaluegreaterthanK//whenKitselfdoesnotappearinthearrayelsereturnERROR;//thegreatestvalueinthearrayislessthanK}(2)《DataStructure》B试卷第3页共5页Theheightoftheshortesttreeandthetallesttreewithbothnnodesisrespectively_2_orn(n2)and__n_,supposethattheheightoftheone-nodetreeis1.A3-aryfulltreewithninternalnodeshas__3n+1_nodes.(6scores)3.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+14.AcertainbinarytreehasthepostorderenumerationasDCBEHJIGFAandtheinorderenumerationasBCDAEFGHIJ.Trytodrawthebinarytreeandgivethepostorderenumeration.(Theprocessofyoursolutionisrequired!!!)(6scores)preorderenumeration:ABCDFEGIHJ5.Designanalgorithmtotransferthescorereportfrom100-pointto5-point,thelevelEcorrespondingscore60,60～69beingD,70～79beingC,80～89asB，score=90asA.Thedistributiontableisasfollowing.Pleasedescribeyouralgorithmusingadecisiontreeandgivethetotalpathlength.(6scores)Scorein100-point0-5960-6970-7980-8990-100Distributionrate5%10%45%35%5%solution:thedesignlogicistobuildaHuffmantreeBCDEFGHIJGJAABEFCDGHIJABFCDGIHJABFCDGIJHEEE10045%35%20%10%10%5%5%DDAEBC000111155%100%0《DataStructure》B试卷第4页共5页Totallength:4*10%+10%*3+35%*2+45%=1.85,the0-false,1-trueasthelogicbranches.6.Recoveryageneraltreeasfollowingtransferredfromabinarytree.(4scores)7.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:442255336699778879pass2:442233556679778899pass3:332244556677798899pass4:223344556677798899finalsortedarray:2233445566777988998.(a)Describesimplythemaintasksofthetwophasesofexternalsorting.(4scores)Thetaskoffirstphaseistobreakthefilesintolargeinitialrunsbyreplacementselection;thesecondphaseistomergetherunst