《数据结构与算法》课后答案

1.FilltheblankwithcorrectC++codes:

Givenanarraystoringintegersorderedbydistinctvaluewithoutduplicate,modifythebinary

searchroutinestoreturnthepositionoftheintegerwiththesmallestvaluegreaterthanKwhenK

itselfdoesnotappearinthearray.ReturnERRORifthegreatestvalueinthearrayislessthanK:

(12scores)

//Returnpositionofsmallestclement>=K

intnewbinary(intarray[],intn,intK){

intl=-l;

intr=n;//1andrbeyondarraybounds

while(1+1!=r){//Stopwhen1andrmeet

___inti=(1+r)/2;//Lookatmiddleofsubarray

if(K<array[i])_r=i—;//Inlefthalf

if(K==array[i])_returni__;//Foundit

if(K>array[i])___l=i___//Inrighthalf

)

//KisnotinarrayorthegreatestvalueislessthanK

ifK<=array[n-lJ(orr!=n)_//thegreatestvalueinthearrayisnotlessthanKwithr

updated

returnr;//whenKitselfdoesnotappearinthearray

elsereturnERROR;//theintegerwiththegreatestvaluelessthanK

(2)Theheightofacompletebinarytreewithknodesis」log?(k+l)|[1nodetree

hashight1)

(3)Thenumberofdifferentshapesofbinarytreeswith5nodesis_42_.

2.AcertainbinarytreehasthepreorderenumerationasABECDFGHIJandthe

inorderenumerationasEBDCAFIHGJ.Trytodrawthebinarytreeandgivethe

postorderenumeration.(Theprocessofyoursolutionisrequired!!!)

3.Determine@forthefollowingcodefragmentsintheaveragecase.Assumethat

allvariablesareoftypeint.

(1)sum=0;

for(i=0;i<5;i++)

for(j=0;j<n;j++)

sum++;solution:©___(n)

(2)sum=0;

for(i=l;i<=n;i++)

for(j=n;j>=i;j-)

sum++;solution:®_(n2)

(3)sum=0;

if(EVEN(n))

for(i=0;i<n;i++)

sum++;

else

sum=sum+n;solution:®___(n)

4.Tracebyhandtheexecutionofcreationabinarysearchtreewiththeinputsequence

as:{46,25,78,62,12,37,70,29}whichisemptytreeinitially.

Solution:BSTobtainedwithdatainsertedonebyone

46

2578

123762

2970

5.Designanalgorithmtotransferthescorereportfrom100-pointto5-point,thelevel

Ecorrespondingscore<60,60〜69beingD,70〜79beingC,80〜89asB,score>=90

asA.Thedistributiontableisasfollowing.Pleasedescribeyouralgorithmusinga

decisiontreeandgivethetotalpathlength.

Scorein100-point0-5960-6970-7980-8990-100

Distributionrate|5%10%45%25%15%

solution:

thedesignlogicistobuildaHuffmantree

Totallength:4+4+3+2+1=14,Averagelength:4*5%+10%*4+15%*3+25%*2+

45%=2.00,the0-false,1-trueasthelogicbranches.

6.Assumeadiskdriveisconfiguredasfollows.Thetotalstorageisapproximately

1.35Gdividedamong15surfaces.Eachsurfacehas612tracks;thereare144

sectors/track,1024byte/sector,and16sectors/cluster.Theinterleavingfactorisfour.

Thediskturnsat7200rmp(8.33ms/r).Thetrack-to-trackseektimeis20ms,andthe

averageseektimeis80ms.Nowhowlongdoesittaketoreadallofthedataina360

KBfileonthedisk?Assumethatthefile'sclustersarespreadrandomlyacrossthe

disk.AseekmustbeperformedeachtimetheI/Oreadermovestoanewtrack.Show

yourcalculations.(Theprocessofyoursolutionisrequired!!!)

Solution：

Thefirstquestionishowmanyclustersthefilerequires?

Aclusterholds16*1K=16K.Thus,thefilerequires360/16=22.5

clusters=22completeclusterand8k(8sectors)

Thetimetoreadaclusterisseektimetothe

cluster+latencytime+(interleaffactorXrotationtime).

Averageseektimeisdefinedtobe80ms.Latencytimeis0.5*8.33ms(60/7200q

8.33ms),andclusterrotationtimeis4*(16/144)*8.33.

Seektimeforthetotalfilereadtimeis

22*(80+0.5*8.33+4*(16/144)*8.33)+(80+0.5*8.33+4*(8/144)*8.33尸

2019.095ms

7.Usingclosedhashing,withdoublehashingtoresolvecollisions,insertthe

followingkeysintoahashtableofelevenslots(theslotsarenumbered0through10).

ThehashfunctionstobeusedareH1andH2,definedbelow.Youshouldshowthe

hashtableafteralleightkeyshavebeeninserted.Besuretoindicatehowyouare

usingHlandH2todothehashing.(Theprocessofyoursolutionisrequired!!!)

Hl(k)=3kmod11H2(k)=7kmod10+1

Keys:22,41,53,46,30,13,1,67.

Solution：

Hl(22)=0,Hl(41)=2,Hl(53)=5,Hl(46)=6,noconflict

WhenH1(30)=2,H2(30)=1(2+1*1)%11=3,so30entersthe3rdslot;

Hl(l3)=6,H2(l3)=2(6+1*2)%11=8,so13entersthe8thslot;

Hl(1)=3,H2(1)=8(3+5*8)%ll=10so1enters10(passby0,8,5,2);

H1(67)=3,H2(67)=10(3+2*10)%11=1so67entersl(passby2)

226741305346131

012345678910

8.Youaregivenaseriesofrecordswhosekeysareintegers.Therecordsarriveinthe

followingorder:C,S,D,T,A,M,P,I,B,W,N,G,U,R.Showthe2-3treethat

resultsfrominsertingtheserecords,(theprocessofyoursolutionisrequired!!!)

Solution：

9.

Thefollowinggraphisacommunicationnetw