1、誠信應(yīng)考，考試作弊將帶來嚴(yán)重后果!(1) Pickthegrowthratethatcorrespondstothemostinefficientalgorithmasngetslarge:(C)(A)2n3(B)2n2logn(C)n!(D)2nAnalgorithmmustbeordoallofthefollowingEXCEPT:(B)(A)Partiallycorrect(B)Ambiguous(C)Canstop(D)Concretesteps(3)Ifadataelementrequires6bytesandapointerrequires2bytes,thenalinkedlis

2、trepresentationwillbemorespaceefficientthanastandardarrayrepresentationwhenthefractionofnon-nullelementsislessthanabout:(B)(A)1/4(B)3/4(C)4/7(D)2/3(4)Whichstatementisnotcorrectamongthefollowingfour:(C)(A)TheQuick-sortisanunstablesortingalgorithm.(B)Thenumberofemptysub-treesinanon-emptyfullbinarytree

3、isonemorethanthenumberofnodesinthetree.(C)Thebestcaseformyalgorithmisnbecominglargerandlargerbecausethatisthemostquickly.(D)Aclusteristhesmallestunitofallocationforafile,soallfilesoccupyamultipleoftheclustersize.(5)Whichofthefollowingisatruestatement:(C)(A)Ageneraltreecanbetransferredtoabinarytreewi

4、ththeroothavingbothleftchildandrightchild.(B)InaBST,thenodecanbeenumeratedsortedbyapreordertraversaltotheBST.(C)InaBST,theleftchildofanynodeislessthantherightchild,butinaheap,theleftchildofanynodecouldbelessthanorgreaterthantherightchild.(D)Aheapmustbefullbinarytree.(6)Thegoldenruleofadisk-basedprog

5、ramdesignisto:(B)(A)ImprovethebasicI/Ooperations.(B)MinimizethenumberofdiskDataStructureA 試卷第 1 頁共 5 頁華南理工大學(xué)期末考試DataStructure試卷A題號一二三四五六七八九十總分:得分評卷人)二題-答-院不-學(xué)內(nèi)線封密(注意事項(xiàng)：1.考前請將密封線內(nèi)填寫清楚；2.所有答案請答在答題紙上；3.考試形式：閉卷；4.本試卷共十大題，滿分100分，考試時(shí)間120分鐘。1.Selectthecorrectchoice.(20scores,each2scores)accesses.(C)Elimina

6、tetherecursivecalls.(D)Reducemainmemoryuse.(7)GivenanarrayasAmn.SupposedthatA00islocatedat644(10)andA22isstoredat676(IO),andeveryelementoccupiesonespace沁)meansthatthenumberispresentedindecimals.Thentheelement11(IO)isatposition:(D)(A)692(B)695(C)650(D)660(8)Ifthereis1MBworkingmemory,4KBblocks,andyiel

7、d128blocksforworkingmemory.Bythemulti-waymergeinexternalsorting,theaveragerunsizeandthesortedsizeinonepassofmulti-waymergeonaverageareseparately(C)?(A)1MB,128MB(B)2MB,512MB(C)2MB,256MB(D)1MB,256MB(9)Inthefollowingsortingalgorithms,whichisthebestonetofindthefirst10biggestelementsinthe1000unsortedelem

8、ents?(B)(A)Quick-sort(B)Heapsort(C)Insertionsort(D)Replacementselection(10)Assumethatwehaveeightrecords,withkeyvaluesAtoH,andthattheyareinitiallyplacedinalphabeticalorder.Now,considertheresultofapplyingthefollowingaccesspattern:FDFGEGFADFGEifthelistisorganizedbytheMove-to-frontheuristic,thenthefinal

9、listwillbe(B).(A)FGDEABCH(B)EGFDABCH(C)ABFDGECH(D)EGFACBDH2. FilltheblankwithcorrectC+codes:(16scores)(1)Givenanarraystoringintegersorderedbydistinctvaluewithoutduplicate,modifythebinarysearchroutinestoreturnthepositionoftheintegerwiththegreatestvaluelessthanKwhenKitselfdoesnotappearinthearray.Retur

10、nERRORifthelestvalueinthearrayisgreaterthanK:(10scores)/ReturnpositionofgreatestelementKintnewbinary(intarray,intn,intK)intl=-1;intr=n;/landrbeyondarrayboundswhile(l+1!=r)/Stopwhenlandrmeetinti=(l+r)/2;/Lookatmiddleofsubarrayif(Karrayi)l=i/Inrighthalf)/KisnotinarrayorthegreatestvalueislessthanKifKar

11、ray0(orl!=-1)/thelestvalueinthearrayisgreaterthanKwithlupdatedreturnl;/whenKitselfdoesnotappearinthearrayelsereturnERROR;/theintegerwiththelestvaluegreaterthanK(2)Thenumberofnodesinacompletebinarytreeasbigaspossiblewithheighthis2h-1(suppose1-nodetreeheightis1)(3scores)(3)Thenumberofdifferentshapesof

12、binarytreeswith6nodesi_132.(3scores)3. Acertainbinarytreehasthepost-orderenumerationasEDCBIHJGFAandthein-orderenumerationasEBDCAFIHGJ.Trytodrawthebinarytreeandgivethepostorderenumeration.(Theprocessofyoursolutionisrequired!)(6scores)AAABFBFCGCGEEJJIHHpreorderenumeration:ABECDFGHIJIareoftypeint(6scor

13、es)solution(n)solutionsolution(n)2422244545822223535itaStrucforthefollowingcodefragmentsintheaveragecase.Assumethat5.Showthemin-heapthatresultsfromrunningbuildheaponthefollowingvalues(2)sum=0;for(i=1;i=i;j-sum+;4.Determine8allvariablesstoredinanarray:4,2,5,8,3,6,10,1483sum=0;for(i=0;i5;i+)for(j=0;jn

14、;j+)sum+;DCIHGJsum=0;if(EVEN(n)for(i=0;in;i+)sum+;elsesum=sum+n;B:F4555 (6scores)2_(n)BDCFIHGJ-3re6.Designanalgorithmtotransferthescorereportfrom100-pointto5-point,thelevelEcorrespondingscore=90asA.Thedistributiontableisasfollowing.Pleasedescribeyouralgorithmusingadecisiontreeandgivethetotalpathleng

15、th.(9scores)Scorein100-point0-5960-6970-7980-8990-100Distributionrate5%10%45%35%5%solution:thedesignlogicistobuildaHuffmantreeTotallength:4*10%+10%*3+15%*3+35%*2+45%logicbranches.7. Assumeadiskdriveisconfiguredasfollows.Thetotalstorageisapproximately675Mdividedamong15surfaces.Eachsurfacehas612tracks

16、;thereare144sectors/track,512byte/sector,and16sectors/cluster.Theinterleavingfactoris3.Thediskturnsat7200rmp(8.3ms/r).Thetrack-to-trackseektimeis20ms,andtheaverageseektimeis80ms.Nowhowlongdoesittaketoreadallofthedataina360KBfileonthedisk?Assumethatthefilesclustersarespreadrandomlyacrossthedisk.Aseek

17、mustbeperformedeachtimetheI/Oreadermovestoanewtrack.Showyourcalculations.(Theprocessofyoursolutionisrequired!)(9scores)Solution:Aclusterholds16*0.5K=8K.Thus,thefilerequires360/8=45clusters.Thetimetoreadaclusterisseektimetothecluster+latencytime+(interleaffactorxrotationtime).Averageseektimeisdefined

18、tobe80ms.Latencytimeis0.5*8.3,andclusterrotationtimeis3*(16/144)*8.3.Seektimeforthetotalfilereadtimeis45*(80+0.5*8.3+3*(16/144)*8.3)=3911.258. Usingclosedhashing,withdoublehashingtoresolvecollisions,insertthefollowingkeysintoahashtableofelevenslots(theslotsarenumbered0through10).Thehashfunctionstobe

19、usedareH1andH2,definedbelow.Youshouldshowthehashtableafteralleightkeyshavebeeninserted.BesuretoindicatehowyouareusingH1andH2todothehashing.(Theprocessofyoursolutionisrequired!)H1(k)=3kmod11H2(k)=7kmod10+1Keys:22,41,53,46,30,13,1,67.(9scores)=2.25,the0-false,1-trueastheSolution:H1(22)=0,H1(41)=2,H1(53)=5,H1(46)=6,noconflictWhenH1(30)=2,H2(30)=1(2+1*1)%11=3,so30entersthe3rdslot;H1(13)=6,H2(13)=2(6+1*2)%11=8,so13entersthe8thslot;H1(1)=3,H2(1)=8(3+5*8)%11=10so1enters10(passby0,8,5,2);H1(67)=3,H2(67)=10(3+2*10)%11=1so67enter