数据结构与算法分析(Java语言描述)习题答案(第三版).docx
- 文档编号:18939006
- 上传时间:2024-03-02
- 格式:DOCX
- 页数:127
- 大小:1.52MB
数据结构与算法分析(Java语言描述)习题答案(第三版).docx
《数据结构与算法分析(Java语言描述)习题答案(第三版).docx》由会员分享,可在线阅读,更多相关《数据结构与算法分析(Java语言描述)习题答案(第三版).docx(127页珍藏版)》请在冰点文库上搜索。
CHAPTER1
Introduction
1.4Thegeneralwaytodothisistowriteaprocedurewithheading
voidprocessFile(StringfileName);
whichopensfileName,doeswhateverprocessingisneeded,andthenclosesit.Ifalineoftheform
#includeSomeFile
isdetected,thenthecall
processFile(SomeFile);
ismaderecursively.Self-referentialincludescanbedetectedbykeepingalistoffilesforwhichacallto
processFilehasnotyetterminated,andcheckingthislistbeforemakinganewcalltoprocessFile.
1.5publicstaticintones(intn)
{
if(n<2)returnn;
returnn%2+ones(n/2);
}
1.7(a)Theproofisbyinduction.Thetheoremisclearlytruefor0 (b)Let2X=A.ThenAB=(2X)B=2XB.ThuslogAB=XB.SinceX=logA,thetheoremisproved. 1.8(a)Thesumis4/3andfollowsdirectlyfromtheformula. (b) S=1+2+3+ Subtractingthefirstequationfromthesecondgives .4S=1+2+3+ . 4 42 4 42 43 3S=1+1+2+ 4 42 .Bypart(a),3S=4/3soS=4/9. (c) S=1+4+9+ Subtractingthefirstequationfromthesecondgives .4S=1+4+9+16+ . 4 42 43 4 42 43 ¥ ¥ . 3S=1+3+5+7+ Rewriting,weget3S=2åi+å1.Thus3S=2(4/9)+4/3=20/9.ThusS= i i 4 42 43 i=04 i=04 20/27. ¥ 4i (d)LetSN=åiN.Followthesamemethodasinparts(a)–(c)toobtainaformulaforSNintermsofSN–1, i=0 SN–2,...,S0andsolvetherecurrence.Solvingtherecurrenceisverydifficult. N N êëN/2-1úû 1.9 å1=å1- å1»lnN-lnN/2»ln2. i i i i=êëN/2úû i=1 i=1 1.10 24=16º1(mod5).(24)25º125(mod5).Thus2100º1(mod5). 1.11 (a)Proofisbyinduction.ThestatementisclearlytrueforN=1andN=2.AssumetrueforN=1,2,...,k. k+1 k Then åFi=åFi+Fk+1.Bytheinductionhypothesis,thevalueofthesumontherightisFk+2–2+Fk+1= i=1 i=1 Fk+3–2,wherethelatterequalityfollowsfromthedefinitionoftheFibonaccinumbers.ThisprovestheclaimforN=k+1,andhenceforallN. (b)Asinthetext,theproofisbyinduction.Observethatf+1=f2.Thisimpliesthatf–1+f–2=1.ForN=1andN=2,thestatementistrue.AssumetheclaimistrueforN=1,2,...,k. Fk+1=Fk+Fk-1 bythedefinition,andwecanusetheinductivehypothesisontheright-handside,obtaining Fk+1 Fk+1<(f-1+f-2)fk+1 andprovingthetheorem. (c)Seeanyoftheadvancedmathreferencesattheendofthechapter.Thederivationinvolvestheuseofgeneratingfunctions. N N N 1.12 (a)å(2i-1)=2åi-å1=N(N+1)–N=N2. i=1 i=1 i=1 (b)Theeasiestwaytoprovethisisbyinduction.ThecaseN=1istrivial.Otherwise, N+1 N åi3=(N+1)3+åi3 i=1 =(N+1)3 i=1 +N2(N+1)2 4 = 2éN2 ù (N+1)ê4+(N+1)ú ë û = 2éN2+4N+4ù (N+1)ê 4 ú ë û =(N+1)2(N+2)222 é(N+1)(N+2)ù2 =êë 2 úû å éN+1ù2 =ê iú ëi=1û CHAPTER2 AlgorithmAnalysis N 2.12/N,37, ,N,NloglogN,NlogN,Nlog(N2),Nlog2N,N1.5,N2,N2logN,N3,2N/2,2N. NlogNandNlog(N2)growatthesamerate. 2.2(a)True. (b)False.AcounterexampleisT1(N)=2N,T2(N)=N,andf(N)=N. (c)False.AcounterexampleisT1(N)=N2,T2(N)=N,andf(N)=N2. (d)False.Thesamecounterexampleasinpart(c)applies. logN 2.3WeclaimthatNlogNistheslowergrowingfunction.Toseethis,supposeotherwise.Then,Ne wouldgrowslowerthanlogN.Takinglogsofbothsides,wefindthat,underthisassumption, e/logNlogN growsslowerthanloglogN.Butthefirstexpressionsimplifiestoe logN.IfL=logN, L thenweareclaimingthate growsslowerthanlogL,orequivalently,thate2Lgrowsslowerthanlog2L.Butweknowthatlog2L=o(L),sotheoriginalassumptionisfalse,provingtheclaim. 2.4Clearly,logk1N=o(logk2N)ifk1 lim N®¥ logiNN =limi N®¥ logi-1NN Thesecondlimitiszerobytheinductivehypothesis,provingtheclaim. 2.5Letf(N)=1whenNiseven,andNwhenNisodd.Likewise,letg(N)=1whenNisodd,andNwhenNiseven.Thentheratiof(N)/g(N)oscillatesbetween0andinf. 2.6 (a)22N (b)O(loglogD) 2.7Foralltheseprograms,thefollowinganalysiswillagreewithasimulation: (I)TherunningtimeisO(N). (II)TherunningtimeisO(N2). (III)TherunningtimeisO(N3). (IV)TherunningtimeisO(N2). (V)jcanbeaslargeasi2,whichcouldbeaslargeasN2.kcanbeaslargeasj,whichisN2.TherunningtimeisthusproportionaltoN×N2×N2,whichisO(N5). (VI)TheifstatementisexecutedatmostN3times,bypreviousarguments,butitistrueonlyO(N2)times(becauseitistrueexactlyitimesforeachi).ThustheinnermostloopisonlyexecutedO(N2)times.Eachtimethrough,ittakesO(j2)=O(N2)time,foratotalofO(N4).Thisisanexamplewheremultiplyingloopsizescanoccasionallygiveanoverestimate. 2.8(a)Itshouldbeclearthatallalgorithmsgenerateonlylegalpermutations.Thefirsttwoalgorithmshaveteststoguaranteenoduplicates;thethirdalgorithmworksbyshufflinganarraythatinitiallyhasnoduplicates,sononecanoccur.Itisalsoclearthatthefirsttwoalgorithmsarecompletelyrandom,andthateachpermutationisequallylikely.Thethirdalgorithm,duetoR.Floyd,isnotasobvious;thecorrectnesscanbeprovedbyinduction.SeeJ.Bentley,“ProgrammingPearls,”CommunicationsoftheACM30(1987),754–757.Notethatifthesecondlineofalgorithm3isreplacedwiththestatement swapReferences(a[i],a[randint(0,n–1)]); thennotallpermutationsareequallylikely.Toseethis,noticethatforN=3,thereare27equallylikelywaysofperformingthethreeswaps,dependingonthethreerandomintegers.Sincethereareonly6permutations,and6doesnotevenlydivide27,eachpermutationcannotpossiblybeequallyrepresented. (b)Forthefirstalgorithm,thetimetodecideifarandomnumbertobeplacedina[i]hasnotbeenusedearlierisO(i).TheexpectednumberofrandomnumbersthatneedtobetriedisN/(N–i).Thisisobtainedasfollows: ioftheNnumberswouldbeduplicates.Thustheprobabilityofsuccessis(N–i)/N.ThustheexpectednumberofindependenttrialsisN/(N–i).Thetimeboundisthus N-1Ni N-1N2 N-i N-i N-i < < N-1 1 2 2N1 2 å i=0 å i=0 Nå i=0 å =O(N j j=1 logN) Thesecondalgorithmsavesafactorofiforeachrandomnumber,andthusreducesthetimeboundto O(NlogN)onaverage.Thethirdalgorithmisclearlylinear. (c,d)Therunningtimesshouldagreewiththeprecedinganalysisifthemachinehasenoughmemory.Ifnot,thethirdalgorithmwillnotseemlinearbecauseofadrasticincreaseforlargeN. (e)Theworst-caserunningtimeofalgorithmsIandIIcannotbeboundedbecausethereisalwaysafiniteprobabilitythattheprogramwillnotterminatebysomegiventimeT.Thealgorithmdoes,however,terminatewithprobability1.Theworst-caserunningtimeofthethirdalgorithmislinear—itsrunningtimedoesnotdependonthesequenceofrandomnumbers. 2.9Algorithm1at10,000isabout38minutesandat100,000isabout26days.Algorithms1–4at1millionareapproximately: 72years,4hours,0.7seconds,and0.03secondsrespectively.Thesecalculationsassumeamachinewithenoughmemorytoholdtheentirearray. 2.10 (a)O(N) (b)O(N2) (c)Theanswerdependsonhowmanydigitspastthedecimalpointarecomputed.EachdigitcostsO(N). 2.11(a)Fivetimesaslong,or2.5ms. (b)Slightlymorethanfivetimesaslong. (c)25timesaslong,or12.5ms. (d)125timesaslong,or62.5ms. 2.12(a)12000timesaslargeaproblem,orinputsize1,200,000. (b)inputsizeofapproximately425,000. 12000 (c)timesaslargeaproblem,orinputsize10,954. (d)120001/3timesaslargeaproblem,orinputsize2,289. 2.13 (a)O(N2). (b)O(NlogN). 2.15 UseavariationofbinarysearchtogetanO(logN)solution(assumingthearrayisreread). N. 2.20(a)TesttoseeifNisanoddnumber(or2)andisnotdivisibleby3,5,7, (b)O(N),assumingthatalldivisionscountforoneunitoftime. (c)B=O(logN). (d)O(2B/2). (e)Ifa20-bitnumbercanbetestedintimeT,thena40-bitnumberwouldrequireaboutT2time. (f)Bisthebettermeasurebecauseitmoreaccuratelyrepresentsthesizeoftheinput. 2.21TherunningtimeisproportionaltoNtimesthesumofthereciprocalsoftheprimeslessthanN.ThisisO(N loglogN).SeeKnuth,Volume2. 2.22 ComputeX2,X4,X8,X10,X20,X40,X60,andX62. 2.23Maintainanarraythatcanbefilledinaforloop.ThearraywillcontainX,X2,X4,upto X2êëlogNúû.Thebinary representationofN(whichcanbeobtainedbytestingevenoroddandthendividingby2,untilallbitsareexamined)canbeusedtomultiplytheappropriateentriesofthearray. 2.24ForN=0orN=1,thenumberofmultipliesiszero.Ifb(N)i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 分析 Java 语言 描述 习题 答案 第三