2第11章课件.docx
- 文档编号:15405106
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:34
- 大小:35.69KB
2第11章课件.docx
《2第11章课件.docx》由会员分享,可在线阅读,更多相关《2第11章课件.docx(34页珍藏版)》请在冰点文库上搜索。
2第11章课件
JavaSoftwareSolutions:
FoundationsofProgramDesign,6e(Lewis/Loftus)
Chapter11Recursion
Multiple-ChoiceQuestions
Forthequestionsbelow,usethefollowingrecursivemethod.
publicintquestion1_2(intx,inty)
{
if(x==y)return0;
elsereturnquestion1_2(x-1,y)+1;
}
1)Ifthemethodiscalledasquestion1_2(8,3),whatisreturned?
A)11
B)8
C)5
D)3
E)24
Answer:
C
Explanation:
C)Themethodcomputesx-yifx>y.Themethodworksasfollows:
eachtimethemethodiscalledrecursively,itsubtracts1fromxuntil(x==y)isbecomestrue,andadds1tothereturnvalue.So,1isaddedeachtimethemethodiscalled,andthemethodiscalledonceforeachintvaluebetweenxandy.
2)Callingthismethodwillresultininfiniterecursionifwhichconditionbelowisinitiallytrue?
A)(x==y)
B)(x!
=y)
C)(x>y)
D)(x E)(x==0&&y! =0) Answer: D Explanation: D)If(x 3)Thefollowingmethodshouldreturntrueiftheintparameterisevenandeitherpositiveor0,andfalseotherwise.Whichsetofcodeshouldyouusetoreplace...sothatthemethodworksappropriately? publicbooleanquestion3(intx){...} A)if(x==0)returntrue;elseif(x<0)returnfalse;elsereturnquestion3(x-1); B)if(x==0)returnfalse;elseif(x<0)returntrue;elsereturnquestion3(x-1); C)if(x==0)returntrue;elseif(x<0)returnfalse;elsereturnquestion3(x-2); D)if(x==0)returnfalse;elseif(x<0)returntrue;elsereturnquestion3(x-2); E)return(x==0); Answer: C Explanation: C)Themethodwillrecursivelycallitselfsubtracting2fromxuntilx==0orx<0.Ifx==0,thenitx-2*i==0(forsomeintvaluei)orx==2*i,soxmustbeeven.Otherwise,therecursionendswhenx<0,meaningthattheoriginalxwasoddorlessthan0. Forthequestionsbelow,refertothefollowingrecursivefactorialmethod. publicintfactorial(intx) { if(x>1)returnx*factorial(x-1); elsereturn1; } 4)Whatisreturnediffactorial(3)iscalled? A)0 B)1 C)3 D)6 E)9 Answer: D Explanation: D)Withfactorial(3),x>1,soitreturns3*factorial (2),withfactorial (2),x>1soitreturns2*factorial (1),withfactorial (1),1isreturned,sowehave3*2*1=6. 5)Whatisreturnediffactorial(0)iscalled? A)0 B)1 C)2 D)nothing,factorial(0)causesinfiniterecursion E)nothing,factorial(0)producesarun-timeerror Answer: B Explanation: B)Withfactorial(0),(x>1)isnottrue,sothebasecaseisexecutedand1isreturned.Therefore,eventhoughordinarily0*value=0,thefactorial(0)iscomputedas1. 6)Howmanytimesisthefactorialmethodinvokediforiginallycalledwithfactorial(5)? Includetheoriginalmethodcallinyourcounting. A)1 B)4 C)5 D)6 E)7 Answer: C Explanation: C)Themethodisfirstinvokedwithfactorial(5),whichinturnreturns5*factorial(4),sofactorialisinvokedagain,whichinturnreturns4*factorial(3),sofactorialisinvokedagain,whichinturnreturns3*factorial (2),sofactorialisinvokedagain,whichinturnreturns2*factorial (1),sofactorialisinvokedagain,andfinallyfactorial (1)invokesthebasecaseandreturns1.So,factorialwasinvoked5times. 7)Whatconditiondefinesthebasecaseforthismethod? A)(x>1) B)(x==1) C)(x==0) D)(x<=0) E)(x<=1) Answer: E Explanation: E)Theifconditionis(x>1)butthisistherecursivecase,sothebasecaseistheoppositecondition.Theoppositeof(x>1)is(x<=1). 8)Whatiswrongwiththefollowingrecursivesummethod? Themethodissupposedtosumupthevaluesbetween1andx(forinstance,sum(5)shouldbe5+4+3+2+1=15). publicintsum(intx) { if(x==0)return0; elsereturnsum(x-1)+x; } A)thebasecaseshouldreturn1insteadof0 B)therecursivecaseshouldreturnsum(x-1)+1;insteadofsum(x-1)+x; C)thebasecaseconditionshouldbe(x<=0)insteadof(x==0) D)therecursivecaseshouldreturnsum(x)+1; E)themethodshouldreturnabooleaninsteadofanint Answer: C Explanation: C)Themethoddoesnotappropriatelyhandleanegativeparameter,suchassum(-5).Theresultisinfiniterecursion.Wemightdefineanegativeparameterassomethingthatshouldreturn0,orallowanegativeparametertocomputeanegativesumasin: publicintsum(intx) { if(x==0)return0; elseif(x<0)return-1*sum(-x); elsereturnsum(x-1)+x; } 9)Whatdoesthefollowingmethodcompute? Assumethemethodiscalledinitiallywithi=0 publicintquestion9(Stringa,charb,inti) { if(i==a.length())return0; elseif(b==a.charAt(i))returnquestion9(a,b,i+1)+1; elsereturnquestion9(a,b,i+1); } A)thelengthofStringa B)thelengthofStringaconcatenatedwithcharb C)thenumberoftimescharbappearsinStringa D)returns1ifcharbappearsinStringaatleastonce,and0otherwise E)thecharwhichappearsatlocationiinStringa Answer: C Explanation: C)ThemethodcompareseachcharacterinStringawithcharbuntilireachesthelengthofStringa.1isaddedtothereturnvalueforeachmatch. 10)Whichofthefollowingrecursivemethodswouldexecuteapproximatelylog2ntimesforaninitialparametern? A)publicvoidlogcode(intn) { if(n>1)logcode(n-1); } B)publicvoidlogcode(intn) { if(n>2)logcode(n-2); } C)publicvoidlogcode(intn) { if(n>0)logcode(0); } D)publicvoidlogcode(intn) { if(n>1)logcode(n/2); } E)publicvoidlogcode(intn) { if(n>1)logcode(n-1/2); } Answer: D Explanation: D)Thismethodrecursivelycallsitselfwithnbeinghalfitsoriginalvalue.Ifnstartsat16,thesecondcallhasn=8,thethirdhasn=4,thefourthhasn=2,thefifthandfinalcallhasn=1.Ifnstartsat32,itaddsoneadditionalcall.Ifwedoublenagain,itonlyadds1morerecursivecall.Thisisalog2nbehavior. Forthequestionsbelow,assumethatint[]a={6,2,4,6,2,1,6,2,5}andconsiderthetworecursivemethodsbelowfooandbar. publicintfoo(int[]a,intb,intj) { if(j if(a[j]! =b)returnfoo(a,b,j+1); elsereturnfoo(a,b,j+1)+1; elsereturn0; } publicintbar(int[]a,intj) { if(j returna[I]+bar(a,j+1); elsereturn0; } 11)Whatistheresultofcallingfoo(a,2,0);? A)0 B)1 C)2 D)3 E)4 Answer: C Explanation: C)Themethodfoocountsthenumberofoccurrencesoftheintparameterinthesecondpositioninthearraystartingattheindexgivenasthethirdparameter.So,foo(a,2,0)findsthenumberof2sina.2appears3timesinarraya. 12)Whatistheresultofcallingfoo(a,3,0);? A)0 B)1 C)2 D)3 E)4 Answer: A Explanation: A)Themethodfoocountsthenumberofoccurrencesoftheintparameterinthesecondpositioninthearraystartingattheindexgivenasthethirdparameter.So,foo(a,3,0)findsthenumberof3sina.Therearenone. 13)Whatistheresultofcallingfoo(a,2,9);? A)0 B)1 C)2 D)3 E)4 Answer: A Explanation: A)Themethodfoocountsthenumberofoccurrencesoftheintparameterinthesecondpositioninthearraystartingattheindexgivenasthethirdparameter.So,foo(a,2,9)resultsinthebasecasebeingexecutedimmediatelybecause9==a.lengthandthebasecasereturns0. 14)Whatistheresultofcallingbar(a,0);? A)0 B)5 C)6 D)12 E)34 Answer: E Explanation: E)Thebarmethodrecursivelysumstheelementsofarrayastartingatthelocationofthesecondparameter.Sincethestartingpointislocation0,thiscallsumsallelementsofa(whichequals34). 15)Whatistheresultofbar(a,8);? A)0 B)5 C)6 D)12 E)34 Answer: B Explanation: B)Thebarmethodrecursivelysumstheelementsofarrayastartingatthelocationofthesecondparameter(8inthiscase).So,bar(a,8)sumsuponlythelastelementinthearray,5,andso5isreturned. 16)Whatdoesthefollowingrecursivemethoddetermine? publicbooleanquestion16(int[]a,int[]b,intj) { if(j==a.length)returnfalse; elseif(j==b.length)returntrue; elsereturnquestion16(a,b,j+1); } A)returnstrueifaandbareequalinsize,falseotherwise B)returnstrueifaislargerthanb,falseotherwise C)returnstrueifbislargerthana,falseotherwise D)returnstrueifaandbhavenoelements E)returnsthelengthofarraya+lengthofarrayb Answer: B Explanation: B)Themethodreturnstrueifthethirdparameter,j,isequaltothelengthofbbutnotequaltothelengthofa.Thus,themethodreturnstrueifthethirdparameterhasreachedthevalueindicatingtheendofarraybbutnottheendofarrayasothisistrueifaislargerthanb.Ifaandbareequallengthorifaisshorterthanb,falseisreturned. 17)Whyisthefollowingmethodonewhichhasinfiniterecursion? publicintinfiniteRecursion(intn) { if(n>0)returninfiniteRecursion(n)+1; elsereturn0; } A)Becausethereisnobasecase B)Becausethebasecasewillneverbetrue C)Becausetherecursivecalldoesnotmovetheparameterclosertothebasecase D)Becausetherecursivecallmovestheproblemfurtherawayfromthebasecase E)Noneoftheabove,thereisnoinfiniterecurs
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 11 课件