Ch10算法导论第三版第十章答案英6736

Chapter10

MichelleBodnar,AndrewLohr

April12,2016

Exercise10.1-1

4

41

413

41

418

41

Exercise10.1-2

WewillcallthestacksTandR.Initially,setT.top=0andR.top=n+1.

Essentially,stackTusesthefirstpartofthearrayandstackRusesthelast

partofthearray.InstackT,thetopistherightmostelementofT.InstackR,

thetopistheleftmostelementofR.

Algorithm1PUSH(S,x)

1:ifS==Tthen

ifT.top+1==R.topthen

error“overflow”

else

2:

3:

4:

T.top=T.top+1

T[T.top]=x

5:

6:

endif

8:endif

9:ifS==Rthen

7:

ifR.top−1==T.topthen

error“overflow”

else

10:

11:

12:

R.top=R.top−1

T[T.top]=x

13:

14:

endif

15:

16:endif

1

Algorithm2POP(S)

ifS==Tthen

ifT.top==0then

error“underflow”

else

T.top=T.top−1.

returnT[T.top+1]

endif

endif

ifS==Rthen

ifR.top==n+1then

error“underflow”

else

R.top=R.top+1.

returnR[R.top−1]

endif

endif

Exercise10.1-3

4

41

413

13

138

38

Exercise10.1-4

Algorithm3ENQUEUE

ifQ.head==Q.tail+1,orQ.head==1andQ.tail==Q.lengththen

error“overflow”

endif

Q[Q.tail]=x

ifQ.tail==Q.lengththen

Q.tail=1

else

Q.tail=Q.head+1

endif

Exercise10.1-5

Asintheexamplecodegiveninthesection,wewillneglecttocheckfor

overflowandunderflowerrors.

2

Algorithm4DEQUEUE

ifQ.tail==Q.headthen

error“underflow”

endif

x=Q[Q.head]

ifQ.head==Q.lengththen

Q.head=1

else

Q.head=Q.head+1

endif

returnx

Algorithm5HEAD-ENQUEUE(Q,x)

Q[Q.head]=x

ifQ.head==1then

Q.head=Q.length

else

Q.head=Q.head−1

endif

Algorithm6TAIL-ENQUEUE(Q,x)

Q[Q.tail]=x

ifQ.tail==Q.lengththen

Q.tail=1

else

Q.tail=Q.tail+1

endif

Algorithm7HEAD-DEQUEUE(Q,x)

x=Q[Q.head]

ifQ.head==Q.lengththen

Q.head=1

else

Q.head=Q.head+1

endif

Algorithm8TAIL-DEQUEUE(Q,x)

x=Q[Q.tail]

ifQ.tail==1then

Q.tail=Q.length

else

Q.tail=Q.tail−1

endif

3

Exercise10.1-6

Theoperationenqueuewillbethesameaspushinganelementontostack

1.ThisoperationisO(1).Todequeue,wepopanelementfromstack2.Ifstack

2isempty,foreachelementinstack1wepopitoff,thenpushitontostack2.

Finally,popthetopitemfromstack2.ThisoperationisO(n)intheworstcase.

Exercise10.1-7

Thefollowingisawayofimplementingastackusingtwoqueues,wherepop

takeslineartime,andpushtakesconstanttime.Thefirstoftheseways,consists

ofjustenqueueingeachelementasyoupushit.Then,todoapop,youdequque

eachelementfromoneofthequeuesandplaceitintheother,butstopping

justbeforethelastelement.Then,returnthesingleelementleftintheoriginal

queue.

Exercise10.2-1

Toinsertanelementinconstanttime,justaddittotheheadbymakingit

pointtotheoldheadandhaveitbethehead.Todeleteanelement,itneeds

lineartimebecausethereisnowaytogetapointertothepreviouselementin

thelistwithoutstartingattheheadandscanningalong.

Exercise10.2-2

ThePUSH(L,x)operationisexactlythesameasLIST-INSERT(L,x).The

POPoperationsetsxequaltoL.head,callsLIST-DELETE(L,L.head),then

returnsx.

Exercise10.2-3

Inadditiontothehead,alsokeepapointertothelastelementinthelinked

list.Toenqueue,inserttheelementafterthelastelementofthelist,andsetit

tobethenewlastelement.Todequeue,deletethefirstelementofthelistand

returnit.

Exercise10.2-4

FirstletL.nil.key=k.ThenrunLIST-SEARCH’asusual,butremovethe

checkthatx=L.nil.

Exercise10.2-5

Toinsert,justdolistinsertbeforethecurrenthead,inconstanttime.To

search,startatthehead,checkiftheelementisthecurrentnodebeingin-

spected,checkthenextelement,andsoonuntilattheendofthelistoryou

4

foundtheelement.Thiscantakelineartimeintheworstcase.Todelete,again

lineartimeisusedbecausethereisnowaytogettotheelementimmediately

beforethecurrentelementwithoutstartingattheheadandgoingalongthelist.

Exercise10.2-6

LetL1beadoublylinkedlistcontainingtheelementsofS1andL2bea

doublylinkedlistcontainingtheelementsofS2.WeimplementUNIONasfol-

lows:SetL.nil.prev.next=L.nil.nextandL.nil.next.prev=L.nil.prev

1

2

2

1

sothatthelastelementofL1isfollowedbythefirstelementofL2.Thenset

L.nil.prev=L.nil.prevandL.nil.prev.next=L.nil,sothatL.nilisthe

1

2

2

1

1

sentinelforthedoublylinkedlistcontainingalltheelementsofL1andL2.

Exercise10.2-7

Algorithm9REVERSE(L)

a=L.head.next

b=L.head

whilea=NILdo

tmp=a.next

a.next=b

b=a

a=tmp

endwhile

L.head=b

Exercise10.2-8

WewillstorethepointervalueforL.headseparately,forconvenience.In

general,AXOR(AXORC)=C,soonceweknowonepointer’struevalue

wecanrecoveralltheothers(namelyL.head)byapplyingthisrule.Assuming

thereareatleasttwoelementsinthelist,thefirstelementwillcontainexactly

theaddressofthesecond.

Algorithm10LISTnp-SEARCH(L,k)

p=NIL

x=L.head

whilex=NILandx.key=kdo

temp=x

x=pXORx.np

p=temp

endwhile

Toreversethelist,wesimplyneedtomaketheheadbethe“last”ele-

5

Algorithm11LISTnp-INSERT(L,x)

x.np=L.head

L.nil.np=xXOR(L.nil.npXORL.head)

L.head=x

Algorithm12LISTnp-Delete(L,x)

L.nil.np=L.nil.npXORL.headXORL.head.np

L.head.np.np=L.head.np.npXORL.head

mentbeforeL.nilinsteadofthefirstoneafterthis.Thisisdonebysetting

L.head=L.nil.npXORL.head.

Exercise10.3-1

AmultiplearrayversioncouldbeL=2,

/34567/

124819511

/23456

AsinglearrayversioncouldbeL=4,

127/410481371916105191311/16

Exercise10.3-2

Algorithm13Allocate-Object()

iffree==NILthen

error“outofspace”

else

x=free

free=A[x+1]

endif

Exercise10.3-3

Allocateobjectjustreturnstheindexofsomecellsthatit’sguaranteedto

notgiveoutagainuntilthey’vebeenfreed.Theprevattributeisnotmodified

becauseonlythenextattributeisusedbythememorymanager,it’suptothe

codethatcallsallocatetousetheprevandkeyattributesasitseesfit.

Exercise10.3-4

ForALLOCATE-OBJECT,wewillkeeptrackofthenextavailablespotin

thearray,anditwillalwaysbeonegreaterthanthenumberofelementsbeing

stored.ForFREE-OBJECT(x),whenaspaceisfreed,wewilldecrementthe

6

Algorithm14Free-Object(x)

A[x+1]=free

free=x

positionofeachelementinapositiongreaterthanthatofxby1andupdate

pointersaccordingly.Thistakeslineartime.

Exercise10.3-5

SeethealgorithmCOMPACTIFY−LIST(L,F)

Exercise10.4-1

18

12

10

7

4

5

2

21

Notethatindices8and2inthearraydonotappear,and,infactdonot

representavalidtree.

Exercise10.4-2

SeethealgorithmPRINT-TREE.

Exercise10.4-3

Exercise10.4-4

SeethealgorithmPRINT-TREE.

Exercise10.4-5

SeethealgorithmINORDER-PRINT’(T)

Exercise10.4-6

Ourtwopointerswillbeleftandright.Foranodex,x.leftwillpointto

theleftmostchildofxandx.rightwillpointtothesiblingofximmediatelyto

itsright,ifithasone,andtheparentofxotherwise.Ourbooleanvalueb,stored

atx,willbesuchthatb=depth(x)mod2.Toreachtheparentofanode,

simplykeepfollowingthe“right”pointersuntiltheparityofthebooleanvalue

changes.Tofindallthechildrenofanode,startbyfindingx.left,thenfollow

7

Algorithm15COMPACTIFY-LIST(L,F)

ifn=mthen

return

endif

e=max{max

{|key[i]|},maxi∈L{|key[i]|}}

increaseeveryelementofkey[1..m]by2e

i∈[m]

foreveryelementofL,ifitskeyisgreaterthane,reduceitby2e

f=1

whilekey[f]<edo

f++

endwhile

a=L.head

ifa>mthen

next[prev[f]]=next[f]

prev[next[f]]=prev[f]

next[f]=next[a]

key[f]=key[a]

prev[f]=prev[a]

FREE−OBJECT(a)

f++

whilekey[f]<edo

f++

endwhile

endif

whilea=L.headdo

ifa>mthen

next[prev[f]]=next[f]

prev[next[f]]=prev[f]

next[f]=next[a]

key[f]=key[a]

prev[f]=prev[a]

FREE−OBJECT(a)

f++

whilekey[f]<edo

f++

endwhile

endif

endwhile

8

Algorithm16PRINT-TREE(T.root)

ifT.root==NILthen

return

else

PrintT.root.key

PRINT-TREE(T.root.left)

PRINT-TREE(T.root.right)

endif

Algorithm17INORDER-PRINT(T)

letSbeanemptystack

push(S,T)

whileSisnotemptydo

U=pop(S)

ifU=NILthen

printU.key

push(S,U.left)

push(S,U.right)

endif

endwhile

Algorithm18PRINT-TREE(T.root)

ifT.root==NILthen

return

else

PrintT.root.key

x=T.root.left−child

whilex=NILdo

PRINT-TREE(x)

x=x.right−sibling

endwhile

endif

9

Algorithm19INORDER-PRINT’(T)

a=T.left

prev=T

whilea=Tdo

ifprev=a.leftthen

printa.key

prev=a

a=a.right

elseifprev=a.rightthen

prev=a

a=a.p

elseifprev=a.pthen

prev=a

a=a.left

endif

endwhile

printT.key

a=T.right

whilea=Tdo

ifprev=a.leftthen

printa.key

prev=a

a=a.right

elseifprev=a.rightthen

prev=a

a=a.p

elseifprev=a.pthen

prev=a

a=a.left

endif

endwhile

10

the“right”pointersuntiltheparityofthebooleanvaluechanges,ignoringthis

lastnodesinceitwillbex.

Problem10-1

Foreach,weassumesortedmeanssortedinascendingorder

unsorted,singlesorted,singleunsorted,doublesorted,double

SEARCH(L,k)

INSERT(L,x)

DELETE(L,x)

SUCCESSOR(L,x)

PREDECESSOR(L,x)

MINIMUM(L,x)

MAXIMUM(L,x)

n

1

n

1

n

1

1

n

1

1

1

1

1

1

n

n

n

n

n

n

1

n

n

n

n

n

1

n

Problem10-2

Inallthreecases,MAKE-HEAPsimplycreatesanewlistL,setsL.head=

NIL,andreturnsLinconstanttime.Assumelistsaredoublylinked.Torealize

alinkedlistasaheap,weimaginetheusualarrayimplementationofabinary

heap,wherethechildrenoftheithelementare2iand2i+1.

a.Toinsert,weperformalinearscantoseewheretoinsertanelementsuch

thatthelistremainssorted.Thistakeslineartime.Thefirstelementinthe

lististheminimumelement,andwecanfinditinconstanttime.Extract-min

returnsthefirstelementofthelist,thendeletesit.Unionperformsamerge

operationbetweenthetwosortedlists,interleavingtheirentriessuchthat

theresultinglistissorted.Thistakestimelinearinthesumofthelengths

ofthetwolists.

b.Toinsertanelementxintotheheap,beginlinearlyscanningthelistuntil

thefirstinstanceofanelementywhichisstrictlylargerthanx.Ifnosuch

largerelementexists,simplyinsertxattheendofthelist.Ifydoesexist,

replaceytbyx.Thismaintainsthemin-heappropertybecausex≤yand

ywassmallerthaneachofitschildren,soxmustbeaswell.Moreover,x

islargerthanitsparentbecauseywasthefirstelementinthelisttoexceed

x.Nowinserty,startingthescanatthenodefollowingx.Sincewecheck

eachnodeatmostonce,thetimeislinearinthesizeofthelist.Togetthe

minimumelement,returnthekeyoftheheadofthelistinconstanttime.

Toextracttheminimumelement,wefirstcallMINIMUM.Next,we’llreplace

thekeyoftheheadofthelistbythekeyofthesecondsmallestelementy

inthelist.We’lltakethekeystoredattheendofthelistanduseitto

replacethekeyofy.Finally,we’lldeletethelastelementofthelist,andcall

MIN-HEAPIFYonthelist.Toimplementthiswithlinkedlists,weneedto

stepthroughthelisttogetfromelementitoelement2i.Weomitthisdetail

fromthecode,butwe’llconsideritforruntimeanalysis.Sincethevalueof

ionwhichMIN-HEAPIFYiscalledisalwaysincreasingandweneverneed

11

tostepthroughelementsmultipletimes,theruntimeislinearinthelength

ofthelist.

Algorithm20EXTRACT-MIN(L)

min=MINIMUM(L)

Linearlyscanforthesecondsmallestelement,locatedinpositioni.

L.head.key=L[i]

L[i].key=L[L.length].key

DELETE(L,L[L.length])

MIN-HEAPIFY(L[i],i)

returnmin

Algorithm21MIN-HEAPIFY(L[i],i)

1:l=L[2i].key

2:r=L[2i+1].key

3:p=L[i].key

4:smallest=i

5:ifL[2i]=NILandl<pthen

smallest=2i

6:

7:endif

8:ifL[2i+1]=NILandr<L[smallest]then

smallest=2i+1

9:

10:endif

11:ifsmallest=ithen

exchangeL[i]withL[smallest]

MIN-HEAPIFY(L[smallest],smallest)

12:

13:

14:endif

Unionisimplementedbelow,whereweassumeAandBarethetwolist

representationsofheapstobemerged.Theruntimeisagainlinearinthe

lengthsoftheliststobemerged.

c.Sincethealgorithmsinpartbdidn’tdependontheelementsbeingdistinct,

wecanusethesameones.

Problem10-3

a.Iftheoriginalversionofthealgorithmtakesonlytiterations,then,wehave

thatitwasonlyatmosttrandomskipsthoughthelisttogettothedesired

value,sinceeachiterationoftheoriginalwhileloopisapossiblerandom

jumpfollowedbyanormalstepthroughthelinkedlist.

b.Theforlooponlines2-7willgetrunexactlyttimes,eachofwhichisconstant

runtime.Afterthat,thewhilelooponlines8-9willberunexactlyXttimes.

So,thetotalruntimeisO(t+E[Xt]).

12

Algorithm22UNION(A,B)

1:ifA.head=NILthen

returnB

2:

3:endif

4:i=1

5:x=A.head

6:whileB.head=NILdo

ifB.head.key≤x.keythen

7:

InsertanodeattheendoflistBwithkeyx.key

8:

9:

x.key=B.head.key

Delete(B,B.head)

endifx=x.next

10:

11:

12:endwhile

13:returnA

c.UsingequationC.25,wehavethatE[Xt]=

Pr(Xt≥i).So,weneed

∞

i=1

toshowthatPr(Xt≥i)≤(1−i/n)t.ThiscanbeseenbecausehavingXt

beinggreaterthanimeansthateachrandomchoicewillresultinanelement

thatiseitheratleastistepsbeforethedesiredelement,orisafterthedesired

element.Therearen−isuchelements,outofthetotaln