雨课堂学堂在线学堂云《Data Structures and Algorithm Design Part I（清华）》单元测试考核答案

第1题ForcomputingtheHailstonesequence(a.k.a.3n+1problem),theHailstone(n)program视频中提到的Hailstone问题（又名3n+1问题）中Hailstone(n)的计算程序是Awon'tterminateforanyvalueofn.对于所有的n都是无穷的Bwon'tterminateforsomevaluesofn(butwillterminateotherwise).对于部分n是无穷的CWedon'tknowifittermiatesforanyvalueofn.不能确定是否存在n，使程序无法终止Dalwaysterminateforanyvalueofn.对于所有的n都是有穷的第2题Whatistheforemostcriterionfora"goodalgorithm"?判断一个算法是否是一个“好算法”，最重要的一条性质是Acorrectness正确Brobustness健壮Creadability可读Defficiency效率第1题WhichofthefollowingisNOTacomponentofaTuringmachine?以下哪项不是图灵机的组成要件？AAtapeoffinitelength有限长的纸带BAfinitealphabet有限的字母表CAfinitesetofstates有限种状态DAheadforreadingandwriting读写头第2题Trueoffalse:TheRAMmodelisequippedwithafiniteamountofstorage,whichdiffersfromtheTuringmachine.判断正误：RAM模型与图灵机模型的区别在于图灵机的存储空间无限，而RAM的存储空间有限。ATrue对BFalse错C.Big_o--Homework第1题WhichoneofthefollowingisequivalenttoO(n3)inthesenseofbig-O?(misnotaconstant)在大O记号的意义下，以下哪一项与O(n3)相等？(m不是常数)AO(3n)BO(n3+2000n2+1000n)CO(n3+m)DO(2000n3+n4)D.Algorithm_analysis--Homework第1题Whichofthefollowingequationsiswrong?下列对应关系中错误的是A12+22+32+...+n2=O(n3)B1+2+4+...+2n=O(2n)Clog1+log2+log3+...+logn=O(nlogn)D1+1/2+1/3+...+1/n=O(nlogn)第2题x=n;y=1;while(x>=(y−1)∗(y−1))y++;Thecomplexityoftheprogramaboveis以上程序的时间复杂度为AO(logn)BO(n)CO(nlogn)DO(n2)第3题Trueorfalse:Inbubblesort,thesizeoftheproblemisreducedtokafterkroundsofsweep&swap.判断：经过k轮扫描交换后，起泡排序程序会将问题规模缩减至k。ATrue对BFalse错E.Iteration+Recursion--Homework第1题Trueorfalse:Toapplydecrease-and-conquer,wedividetheoriginalproblemintotwodegeneratedsub-problems,solvethem,andmergetheirsolutions.判断：减而治之的思想是：将问题划分为两个平凡的子问题，分别求解子问题，来得到原问题的解。ATrue对BFalse错第2题LiLeiandHanMeimeihavedifferentopinionsregardingthelineartimecomplexityinthevideolecture.对于视频中线性递归的时间复杂度，A、B两位同学有不同的看法。LiLeiaggreestothevideo,thecomplexityisO(n)becausethereareninstanceseachrequiringO(1)executiontime.A同学赞同视频中的算法，由于单个递归实例需要O（1）时间完成，共有n个实例，所以整个算法的复杂度是O（n）。However,HanMeimeibelievesthetimeforsum（A,n)tobeO(n)insteadofO(1),sinceit'sstillexecutingevenwhencallingsum(A,n-1),leadingtoatotaltimecomplexityof（n+n−1+...+3+2+1=O（n2.Youagreewith但B同学认为，当sum（A,n）函数中调用sum(A,n-1)时，sum(A,n)仍在执行，因此sum（A,n）的完成时间不是O(1)而是O（n），依此计算，整个算法的复杂度应该为（）。n+n−1+...+3+2+1=O（n2）。请问哪位同学对了？ALiLeiA同学BHanMeimeiB同学第3题Inthevideolectureweseeacommentinthecode:"Twobasecasesarerequired".Whatdoesitreferto?视频里代码注释中“需要两个递归基”的含义是AWeneedtwofunctionshandlingdifferentcases(whennisevenorodd).问题需要按照“n为奇数”、“n为偶数”两种情况分别设计两个函数BThesequenceofrecursivecalllsisterminatedwhentheproblemsizeisreducedtoeither0or1.在问题规模缩减为0或1时，停止递归CTheprogramreturnstothemainfunctionwhentheproblemsizeisreducedtoeither0or1.在问题规模缩减为0或1时，返回main函数（或递归函数被调用的函数）DTwosub-instancesaregeneratedfromeveryinstanceoftherecursivecalls.递归函数在执行过程中将每次创建两个递归实例第4题判断：用分而治之的思想来解决长度为n的数组的求和问题（n足够大），递归实例的数目会比用减而治之的方法少。A对B错F.Dynamic_Programming--Homework第1题Thenaivewayofcomputingfib(n)recursivelyleadstoatimecomplexityof直接用定义以递归的方式计算fib(n)的时间复杂度是：AΘ(n2)BO(2n)CΘ(2n)DO(n)第2题Witharegularcomputer,computingfib(100)naivelyusingrecursionwouldcost(noneedtoconsideroverflow).以现在普通计算机的速度，直接用定义以递归的方式计算fib(100)需要多少时间（不考虑溢出）:Alessthananhour一小时之内Baboutaday大约一天Ctenyears十年Dmuchlongerthanyourlifetime.这辈子看不到啦第3题Forthestaircaseprobleminthevideolecture,howmanydifferentwayscangetyoufromthefirststeptotheeighth.对于视频中的上台阶问题（从第一层开始），上到第8层共有多少种不同的走法：A21B13C17D34第4题Thetimeandspacecomplexitiesforcomputingfib(n)withdynamicprogrammingare用动态规划计算fib(n)的时间、空间复杂度分别为AΘ(n2),Θ(n2)BΘ(n2),Θ(n)CΘ(n),Θ(n)DΘ(n),Θ(1)第5题ThelengthoftheLCSbetween"program"and"algorithm"isprogram和algorithm的LCS长度为:A1B2C3D4第6题LCS(x,y)isdefinedtobethelengthoftheLCSbetweenstringsxandy.LCS("program","algorithm")=LCS(x,y)表示字符串x,y最长公共子序列长度，则LCS（“program”,“algorithm”）=ALCS（“progra”,“algorith”）+1BLCS（“progra”,“algorithm”）CLCS（“program”,“algorith”）Dmax{LCS（“progra”,“algorithm”）,LCS（“program”,“algorith”）}第7题CheckouttheDemointhevideolecture(thedownloadlinkisontherightsideofthe"Course"page,orin01-f-6).Whichtoolwasusedtowritethedemo?下载并使用视频中的Demo（下载链接在“课程信息”右侧，01-f-6里也有），它是用什么做的？AVisualBasicBVC++CXwindowDMSExcel第8题ComputingtheLCSusingdynamicprogrammingleadstoatimecomplexityof(mandnarethelengthsoftheinputstrings)用动态规划求解输入序列长度分别为m,n的LCS问题，时间复杂度为：AΘ(mn)BΘ(nlog2⁡(m))CΘ(m+n)DΘ(n2)Homework第1题Givennon-negativefunctionsf(n),g(h)andh(n),whichofthefollowingstatementsaboutO,Θ,Ωiscorrect?设函数f(n),g(n),h(n)非负，以下关于O,Θ,Ω记号的命题，正确的有：AIff(n)=O(h(n))andg(n)=O(h(n)),thenf(n)=g(n)已知f(n)=O(h(n))且g(n)=O(h(n))，则f(n)=g(n)BΘ(n)+Θ(n)>Θ(n)CΘ(n)+Θ(n/2)+Θ(n/4)+…+Θ(1)=Θ(n2)Diff(n)=O(h(n))andf(n)=Ω(h(n)),thenf(n)=Θ(h(n))已知f(n)=O(h(n))且f(n)=Ω(h(n))，则f(n)=Θ(h(n))第2题Whichofthefollowingfunctionsgrowsfastestasymptotically?下列函数渐进增长速度最快的是：An2/3Bnlog2⁡(n)Clog2⁡(log2⁡(n))Dlog22⁡n第3题Giventhefollowingthreefunctions:以下是三个函数：Theirtimecomplexitiesare:它们的时间复杂度分别为：AΘ(n),Θ(n2),Θ(n)BΘ(nlog2⁡(n)),Θ(nlog2⁡(n)),Θ(n)CΘ(n),Θ(n2),Θ(nlog2⁡(n))DΘ(n2),Θ(n),Θ(nlog2⁡(n))第4题ThefollowingrecursivefunctionisforreversingarrayA[lo,hi]以下递归函数实现数组A[lo,hi]的倒置：Whatisthetimecomplexityofreverse(A,0,n-1),forreversinganarrayoflengthn?调用reverse(A,0,n-1)以倒置长度为n的数组，算法的时间复杂度为：AΘ(n)BΘ(nlog2⁡(n))CΘ(n2)DΘ(log2⁡(n))第5题V={11,23,19,7,17,5,3,13,2,29}WhensortingVusingbubblesort,whatisthevalueofV[8]aftertworoundsofsweep&swap?对V进行起泡排序，两趟扫描交换后V[8]=A17B19C23D29A.Interface+Implementation--Homework第1题Whichofthefollowingoptionsiscorrect:下列说法中正确的是：ATheabstractdatatypeisanadvanceddatatypeprovidedbyC++forimplementingdatastructures.抽象数据类型是C++提供的一种高级的数据类型，用于实现数据结构。BTheabstractdatatypedetermineshowdataisstored.抽象数据类型决定了数据的存储方式。CThesameabstractdatatypemaybeimplementedusingmultipledatastructures.同一个抽象数据类型可能用多种数据结构实现。DDatastructureisanabstractdatatype.数据结构即抽象数据类型。第2题Onaninitiallyemptyvector,what'stheresultofexecutinginsert(0,2),insert(1,6),put(0,1),remove(1)andinsert(0,7):在一个初始为空的向量上依次执行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的结果是：A{6,2,7}B2,6,0,7}C{7,1}D{2,1,7}第3题Thefollowingcodeisavariantofthevectorcopycodewiththesamesemantics.Thespaceshouldbefilledwith:以下代码是向量复制代码的一个变体且语义与其相同，空格处应填入的内容为：A--hiBhi--C++loDlo++B.extendable_vector--Homework第1题Onanemptyvectorwithaninitialmaximumcapacityof10,theloadfactorafterexecutinginsert(0,2),insert(1,6),put(0,1),remove(1)andinsert(0,7)is:在一个初始最大容量为10的空向量上依次执行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的装填因子是：A10%B20%C30%D40%第2题Isitpossibletoreplace:是否可以将视频里向量扩容代码中的：for(inti=0;i<_size;i++)_elem[i]=oldElem[i];inthevectorexpansioncodeinthevideowith:替代为：memcpy(_elem,oldElem,_size*sizeof(T));P.S.ThisquestioninvolvestherelevantknowledgeofC++P.S.本题涉及C++的相关知识AYes,theyareequivalentandtherewillbenoproblem.是，二者是等价的，不会有任何问题。BNo,becausetherangeofelementalintervalsforthetwocopiesisdifferent.否，因为二者复制的元素区间范围不同。CNo,becausetheirefficiencyaredifferent.否，因为二者的效率不同。DNo,becausewhetherthelattercanachievethepurposeisrelatedtoelementtypeT.否，因为后者能否达到目的与元素类型T有关。第3题Usingtheexpansionstrategyofappendingfixedmemoryspaceeachtime,theamortizedtimecomplexityofinsertingelementofvectorofsizenis:采用每次追加固定内存空间的扩容策略，规模为n的向量插入元素的分摊时间复杂度为：AΘ(nlog2n)BΘ(n)CΘ(log2n)DΘ(1)第4题Byusingtwoexpansionstrategies,oneforeachadditionalfixedmemoryspaceandonefordoubleupmemoryspace,theamortizedtimecomplexityofinsertingelementsofvectorofsizenis:分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，规模为n的向量插入元素的分摊时间复杂度分别为：AΘ(n),Θ(1)BΘ(n),Θ(n)CΘ(1),Θ(1)DΘ(n),Θ(log2n)第5题Withregardtotheaveragecomplexityandtheamortizedcomplexity,whichofthefollowingstatementiswrong:关于平均复杂度和分摊复杂度，下列说法中错误的是：AThesequenceofoperationsconsideredbytheamortizedcomplexitymustberealisticandfeasible分摊复杂度所考量的一串操作序列一定是真实可行的BTheaveragecomplexitydependsontheassumptionoftheprobabilityofoccurrenceofeachoperation,whiletheamortizedcomplexityisnot平均复杂度依赖于对各操作出现概率的假设，而分摊复杂度则不是如此CAmortizedcomplexityresultsinlowerthanaveragecomplexity分摊复杂度得到的结果比平均复杂度低DTheconclusionofΘ(1)inthedoubleupexpansionstrategyreferstotheamortizedcomplexity加倍扩容策略中Θ(1)的结论是指分摊复杂度C.unsorted_Vector--Homework第1题WhatisthemeaningofthereturnvalueofT&Vector<T>::operator[](Rankr){return_elem[r];}?T&Vector<T>::operator[](Rankr){return_elem[r];}中的返回值T&是什么意义？AThisisapointeroftypeTbecauseitismoreefficient这是类型T的指针，使用它是因为效率更高BThisisareferencetotypeTbecauseitismoreefficient这是类型T的引用，使用它是因为效率更高CThisisapointeroftypeTbecauseitsreturnvaluecanbeusedasanleftvalue这是类型T的指针，使用它是因为返回值可以作为左值DThisisareferencetothetypeTbecauseitsreturnvaluecanbeusedasanleftvalue这是类型T的引用，使用它是因为返回值可以作为左值第2题WhathappensiftheFORloopintheinsert()functionchangestothefollowingform？for(inti=r;i<_size;i++)_elem[i+1]=_elem[i];ANoproblem,justchangeitfromfronttoback没有问题，只是改为从前向后移动罢了BOverwriteallelementsintheoriginalvectorwithrankgreaterthanr会覆盖原向量中秩大于r的所有元素COverwriteallelementsintheoriginalvectorwithranklessthanr会覆盖原向量中秩小于r的所有元素DWillcausevectorexpansionfailure会引起向量扩容失败第3题Whythesuffixofthedeletedelementismovedfromfronttobackintheintervaldeletionalgorithmremove(lo,hi)?为什么区间删除算法remove(lo,hi)中要从前向后移动被删除元素的后缀？AThisisacustomarypractice,whichinturnisalsofeasible这是一个约定俗成的习惯，反过来也可行BOtherwiseitmaycoversomeelements否则可能会覆盖部分元素COtherwiseitmayfailtodeleteallelementswithintheinterval[lo,hi)否则可能未能删除区间[lo,hi)内所有的元素DOtherwiseitmayleadtoinefficiency否则可能导致效率低下第4题Forthededuplicate()algorithm,theworst-casetimecomplexityforthevectorscalenis:对于deduplicate()算法，向量规模为n时的最坏时间复杂度为：AΘ(n2)BΘ(nlog2n)CΘ(n)DΘ(1)第5题AsafunctionobjectclassXXX,whichofthefollowingmemberfunctionsmustbeexplicitlydefined:作为一个函数对象的类XXX，它必须显式定义以下哪个成员函数：AXXX()B~XXX()Coperator[]()Doperator()()D1.Sorted_Vector.uniquify--Homework第1题Thereturnvalueofthedisordered()algorithmis:disordered()算法的返回值是：AReverseordernumber逆序数BThenumberofadjacentinversion相邻逆序对个数CTheboolvalueofwhetherit'sordered表示是否有序的bool值DTheintvalueofwhetherit'sordered表示是否有序的int值第2题Repeatingelementsinanorderedvector有序向量中的重复元素ASameastheunorderedvector与无序向量相同BMostofthemisadjacentdistribution,onlyaverysmallpartspreadinotherlocations大部分紧邻分布，只有极小部分散布在其它位置CAllofthemareadjacentdistribution必定全部紧邻分布DAllofthemaretimedistribution全部相间分布第3题Forvectorsofsizen,theworst-casetimecomplexityoftheinefficientversionofuniquify()is:对于规模为n的向量，低效版uniquify()的最坏时间复杂度为：AΘ(n2)BΘ(nlog2n)CΘ(n)DΘ(1)第4题Whydoesn'tthealgorithmneedtocallremove()todeleteanelement?为什么该算法中不需要调用remove()进行元素删除？AThereisnoduplicateelement本来就没有重复元素BDuplicateelementsareignoreddirectly重复元素被直接忽略了CDuplicateelementsaremovedtotheendofthevector重复元素被移到了向量末尾DDuplicateelementshavebeenmodifiedtobenon-repeatingelements重复元素修改成了不重复的元素第5题Forvectorsofsizen,theworst-casetimecomplexityoftheefficientversionofuniquify()is:对于规模为n的向量，高效版uniquify()的最坏时间复杂度为：AΘ(n2)BΘ(nlog2n)CΘ(n)DΘ(1)D2.Sorted_Vector.binary_search--Homework第1题Foravectorofsizen,thereturnvalueoffind()onasearchfailureis:对于规模为n的向量，查找失败时find()的返回值是：A-1B0CnDnan第2题InserttheelementeintheorderedvectorVandkeepitinorder,whichofthefollowingcodeiscorrect:在有序向量V中插入元素e并使之保持有序，下列代码正确的是:AV.put(V.search(e),e);BV.insert(V.search(e),e);CV.put(V.search(e)+1,e);DV.insert(V.search(e)+1,e);第3题Inbinsearch(e,lo,hi)versionA,ifV[mi]<e,thenthenextsearchrangeis:在binsearch(e,lo,hi)版本A中，若V[mi]<e，则下一步的查找范围是：AV(mi,hi)BV[mi,hi]CV(mi,hi]DV[lo,hi)第4题WhichofthefollowingexpressionsisequivalenttoRankmi=(lo+hi)>>1?(loandhiarenon-negative)Rankmi=(lo+hi)>>1等效于下列哪个表达式?（lo和hi非负）ARankmi=(lo+hi)\2BRankmi=(lo+hi)%2CRankmi=(lo+hi)/2DRankmi=(double)(lo+hi)/2第5题V={2,3,5,7,11,13,17}.HowmanycomparisonsV.search(16,0,7)needtomake?V={2,3,5,7,11,13,17}。V.search(16,0,7)需要进行多少次比较？A4B5C6D7第6题V1={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}V2={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}Thesearchlengthofsearching43inV1isx,thenthesearchlengthofsearching14inV2is:在V1中查找43的查找长度是x，则在V2中查找14的查找长度为：AxBx+1C2*xDx/2D3.Sorted_Vector.fibonaccian_search--Homework第1题WhatisthedifferencebetweenthefibSearch()algorithmandbinSearch()algorithm?fibSearch()算法与binSearch()有什么区别？ATheirreturnvalueisdifferent二者的返回值不同BTheformerisarecursivealgorithm,andthelatterisaniterativealgorithm前者是递归算法，后者是迭代算法CTherearedifferentwaystochoosetheaxispointmi二者选取轴点mi的方式不同DTheformer'sasymptotictimecomplexityislowerthanthelatter,sotheformerismoreefficient前者的渐进时间复杂度低于后者，故前者效率更高第2题V={1,2,3,4,5,6,7},usingFibonaccitofindelement1inV,theelementselectedasthepivotpointmiis:V={1,2,3,4,5,6,7}，在V中用Fibonacci查找元素1，被选取为轴点mi的元素依次是：A4,3,2,1B4,2,1C5,2,1D5,3,2,1第3题WhyisthesearchprocessforbinSearch()versionAnotbalanced?为什么说binSearch()版本A的查找过程并不平衡?ABecausetheleftandrightbrancheshavedifferentsubvectorsizes因为向左、向右两个分支的子向量规模不同BBecausethenumberofcomparisonsrequiredfortheleftandrightbranchesisnotequal因为向左、向右两个分支所需要的比较次数不相等CBecausetheFibonaccisearchismorebalancedthanthebinarysearch因为Fibonacci查找比二分查找更平衡DBecausetheprobabilitythatthekeyisintheleftsubvectorisgreaterthantheprobabilitythatitisintheright因为关键码位于左子向量中的概率比位于右侧的概率大D4.Sorted_Vector.binary_search_optimized--Homework第1题Foravectorofsizen,theoptimaltimecomplexityforbinarysearchversionsAandBis:对于规模为n的向量，二分查找版本A和B的最优时间复杂度分别为：AΘ(n2),Θ(n)BΘ(nlog2n),Θ(n)CΘ(log2n),Θ(log2n)DΘ(1),Θ(log2n)第2题Forthesearch()interface,whatwearegoingtoreturnwhenthereismorethanonetargetelementinthevector:对于search()接口，我们约定当向量中存在多个目标元素时返回其中：ARankmaximun秩最大者BRankminimum秩最小者CRankintermediate秩中间者DRandomlyreturnoneofthem随机返回其中一个即可第3题ForbinarysearchversionC,whatisthenextsearchrangewhene<V[mi]isnotestablished:对于二分查找版本C，当e<V[mi]不成立时下一步的查找范围是：AV[lo,mi)BV[mi,hi)CV[mi,hi]DV(mi,hi)第4题ForbinarysearchversionC,whenthelengthofthesearchintervalisreducedto0,V[lo]is:对于二分查找版本C，当查找区间的长度缩小为0时，V[lo]是：A、max{0≤r<n|V[r]<e}B、max{0≤r<n|V[r]≤e}C、min{0≤r<n|e<V[r]}D、min{0≤r<n|e≤V[r]}ABCDD5.Sorted_Verpolation_search--Homework第1题Ifthedistributionofelementsinan(ordered)vectorsatisfiesanindependentuniformdistribution(beforesorting),theaveragetimecomplexityoftheinterpolationsearchis:如果（有序）向量中元素的分布满足独立均匀分布（排序前），插值查找的平均时间复杂度为：AO(n)BO(logn)CO(loglogn)DO(1)第2题Searchingforsearchelements7withinterpolationinthevectorV={2,3,5,7,11,13,17,19,23}在向量V={2,3,5,7,11,13,17,19,23}中用插值查找搜索元素7Guessthepivotpointmi猜测的轴点mi____正确答案：:1E.Bubblesort--Homework第1题V={7,2,3,11,17,5,19,13}AftertwoscanexchangeofV,V[6]=V={7,2,3,11,17,5,19,13}，对V进行两次扫描交换后V[6]=A11B13C17D19第2题Whichsituationwilltheimprovedblisteringorderwillendprematurely?经改进的起泡排序在什么情况下会提前结束？ACompletealln-1scans完成全部n-1趟扫描交换BThenumberofscanconversionscompleted=Thenumberofscanswitchingparametersfortheactualelementexchange+1完成的扫描交换趟数=实际发生元素交换的扫描交换趟数+1CThenumberofscanconversionscompleted=Thenumberofscanswitchingsthatactuallytookplaceforelementexchange完成的扫描交换趟数=实际发生元素交换的扫描交换趟数DComplete(n-1)/2scanexchange完成(n-1)/2趟扫描交换第3题TrythefollowingalgorithmtosortV={19,17,23}:试用以下算法对V={19,17,23}排序：1.Sortbyunitsatfirst1.先按个位排序2.Onthebasisofthepreviousstep,sortagainbytens2.在上一步基础上，再按十位排序Isthisalgorithmcorrect?这个算法的是否正确？ACertainlycorrect一定正确BCertainlyincorrect一定不正确CIfthesortingalgorithmusedinstep2isstable,thencorrect若第2步用的排序算法是稳定的，则正确DIfthesortingalgorithmusedinstep1isstable,thencorrect若第1步用的排序算法是稳定的，则正确F.Mergesort-Homework第1题WhatisthesolutiontotherecurrenceformulaT(n)=2T(n2)+O(n)?WhichoftheO(n)itemsrepresent?归并排序时间复杂度的递推公式T(n)=2T(n2)+O(n)的解是什么？其中O(n)项代表什么？AO(n),timeformergingtwosortedsubvectorsO(n),归并两个已排序子向量的时间BO(nlog2n),thetimeforsortingtwosub-vectorsseparatelyO(nlog2n),对两个子向量分别进行排序的时间CO(n2),thetimeforsortingtwosub-vectorsseparatelyO(n2),对两个子向量分别进行排序的时间DO(nlog2n),timeformergingtwosortedsubvectorsO(nlog2n),归并两个已排序子向量的时间第2题Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:对{2,5,7}和{3,11,13}进行二路归并，执行的元素比较依次是：A2and3,5and3,5and11,7and112与3、5与3、5与11、7与11B2and5,5and3,11and13,5and72与5、5与3、11与13、5与7C2and3,2and11,7and11,13and72与3、2与11、7与11、13与7D2and3,5and11,7and132与3、5与11、7与13第3题Forvectorsofsizen,theoptimalandworst-casetimecomplexityformergesortingis:对于规模为n的向量，归并排序的最优、最坏时间复杂度分别为：AΘ(n),Θ(nlog2n)BΘ(nlog2n),Θ(nlog2n)CΘ(nlog2n),Θ(n2)DΘ(n),Θ(n2)Homework第1题Byusingtwoexpansionstrategies,oneforeachadditionalfixedmemoryspaceandonefordoubleupmemoryspace,theamortizedtimecomplexityofinsertinganelementofvectorofsizenis:分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，在规模为n的向量中插入一个元素的分摊时间复杂度为：AO(n),O(1)BO(n),O(n)CO(1),O(1)DO(n),O(log2(n))第2题InserttheelementeintheorderedvectorVandkeepitinorder,whichofthefollowingcodeiscorrect:在有序向量V中插入元素e并使之保持有序，下列代码正确的是:AV.put(V.search(e),e);BV.insert(V.search(e),e);CV.put(V.search(e)+1,e);DV.insert(V.search(e)+1,e);第3题Thebinarysearchfor"versionC"isextractedasfollows:二分查找“版本C”摘录如下：ThevectorV={2,3,5,7,11,13,17,19}isusedtofindthetargetelement16inV.Theelementsthathavebeencomparedwiththetargetelementinthewholeprocessare:向量V={2,3,5,7,11,13,17,19}，在V中使用它查找目标元素16，整个过程中与目标元素发生过比较的元素依次为：A11,17,13B7,3,17C13,11,17D5,7,11第4题Thebinarysearchfor"versionC"isextractedasfollows:二分查找“版本C”摘录如下：WhentherearemultipleelementstobesearchedinthearrayA,thereturnvalueofthefunction:当数组A中有多个待查找元素e时，函数的返回值为：AReturntheelementwhoserankissmallest返回秩最小者BReturntheelementwhoserankisbiggest返回秩最大者CReturntheelementwhoserankisinthemiddle返回秩位于正中间者DRandomlyreturnoneofthem随机返回其中一个第5题Thefollowingfunctionisarecursiveversionofthebinarysearch:以下函数是二分查找的递归版：Foravectorofsizen,thetimeandspacecomplexityoftherecursiveversionandtheiteratedversionlearnedinclassare:对于规模为n的向量，该递归版的时间、空间复杂度和课堂上所学的迭代版的时间、空间复杂度分别是：AO(n),O(nlog2(n)),O(n),O(1)B，O(nlog2(n)),O(nlog2(n)),O(nlog2(n))，O(nlog2(n))CO(log2(n)),O(1),O(log2(n)),O(1)DO(log2(n)),O(log2(n)),O(log2(n)),O(1)第6题ThevectorV={1,2,3,4,5,6,7},usestheFibonaccisearchtofindthetargetelement1inV,theelementsselectedasthepivotmiare:向量V={1,2,3,4,5,6,7}，在V中用斐波那契查找查找目标元素1，被选取为轴点mi的元素依次是：A4,3,2,1B4,2,1C5,2,1D5,3,2,1第7题Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:对{2,5,7}和{3,11,13}进行二路归并，执行的元素比较依次是：A2and3,5and3,5and11,7and112与3、5与3、5与11、7与11B2and5,5and3,11and13,5and72与5、5与3、11与13、5与7C2and3,2and11,7and11,13and72与3、2与11、7与11、13与7D2and3,5and11,7and132与3、5与11、7与13第8题Inanyscanningexchangeofbubblingordering,ifthelastexchangeistoswapelementsX>YforY<X,then:在起泡排序的任何一趟扫描交换过程中，若最后一次交换是将元素X>Y交换为Y<X，则此后：AXandYmusthavebeeninplaceX和Y必然都已经就位BXmustbeinplacewhileYisnotnecessarilyX必然就位，而Y未必CYmustbeinplacewhileXisnotnecessarilyX未必就位，而Y必然DNeitherXnorYarenecessarilyinplaceX和Y都未必已经就位第9题Onaninitiallyemptyvector,what'stheanswerafterexecuting:insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)在一个初始为空的向量上依次执行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的结果是：A{1,2,7}B{2,1,0,7}C{7,1}D{2,1,7}第10题Thefollowingcodeimplementsintervaldeletionofvectorsbycontinuouslydeletingindividualelements:以下代码通过不断删除单个元素实现向量的区间删除：Theoverloadedfunctionremove(Rankr)completestheoperationofdeletingasingleelement,anditstimecomplexityisproportionaltothenumberofsucceedingelementsofthedeletedelement.Forvectorsofsizen,theworst-casecomplexityofthisintervaldeletionalgorithmis:其中重载函数remove(Rankr)完成删除单个元素的操作，其时间复杂度正比于被删除元素的后继个数。对于规模为n的向量，该区间删除算法的最坏时间复杂度为：AO(n)BO(nlog2(n))CO(n2)DO(log2(n))A.interface+Implementation--Homework第1题Whichofthefollowingoptionsaboutrankoflistnodeisincorrect下列关于列表的秩的说法中不正确的是AThephysicaladdressofalistnodecanbedeterminedbyitsrank列表节点的秩与物理地址有明确的对应关系BThecostofmaintainingrankoflistnodeishigh列表的秩具有很高的维护成本CInalist,thecostofrank-basedaccessishigh在列表中循秩访问的成本较高DInalist,location-basedaccessisfasterthanrank-basedaccess在列表中循位置访问会比循秩访问更快第2题Whichofthefollowingoptionsaboutdefinedinterfaceisincorrect?下列关于我们定义的接口的描述中，哪一条是错误的？AForthenodesinthelist,wecantaketheirpredecessorandsuccessorrespectivelybycallingthepred()andsucc()interfaces.对于列表中的节点，我们可以通过调用pred()和succ()接口分别取其前驱和后继。BOneoftheimportantdifferencesbetweenfind(e)andsearch(e)inlistinterfaceisthatfind(e)issuitableforalllists,andsearch(e)isappliedtoorderedlists.对于列表接口中的find(e)与search(e)，其中一个重要区别在于find普适于所有列表，而search适用于有序列表。CIfthelengthofthe'visiblelist'partisn,theranksofthe'head',first,last,and'trail'nodesare-1,0,n,n+1respectively.如果一个列表的visiblelist部分长度为n，则头、首、末、尾节点的秩分别为-1,0,n,n+1DInconstructingthelist,weneedtoconstructsentrynodesfirst.在构造列表时，我们需要首先构造哨兵节点。B.Unsorted_list--Homewrok第1题IfyouchangeinsertAsPred()tothefollowingfunction,theresultis:若将insertAsPred()改为以下函数，其结果是：ACaninsertnodesnormally.能正常插入节点BCannotinsertnode,originallistremainsunchanged.不能插入节点，原列表仍然保持不变CCannotinsertnode,thestructureoftheoriginallistisdestroyed.不能插入节点，原列表的结构被破坏DCaninsertanoderelatedtothestructureofthelistatthetime.能否插入节点与当时列表的结构有关第2题Wecanconsiderspeedingupcall-by-rankby:Ifr>n2,thenwecancontinuetoaccesspred()fromthetailandeventuallymovebackwardstofindthenodewithrankr.我们可以考虑通过如下方式加快循秩访问的速度：如果r>n2，则我们可以从尾部哨兵开始不断访问pred()，最终从后向前地找到秩为r的节点。Whatkindofargumentiswrongaboutthisoptimization?关于这种优化，哪种说法是错误的？AFromtheperspectiveofexpectation,ifrisanequalprobabilitydistributionin[0,n),thenumberofvisitstothelistelementcanbereducedbyhalfduringthecall-by-rank.从期望的角度看，r在[0,n)中是等概率分布的话，那么在循秩访问的过程中，对列表元素的访问次数可以节约一半。BTheslowestaccesstimeoforiginmethodwasmostlyseenatr≈n,whiletheslowestaccesstimeafterimprovementwasgenerallyseenatr≈n/2.原有方法访问最慢的情形大致出现在r≈n时，而改进后的方法访问最慢的情形大致出现在r≈n/2时。CWhentheaccesstothelistisconcentratedattheendofthelist,theeffectofthisoptimizationstrategyismostpronounced.当对于列表的访问集中在列表尾部时，这种优化策略的效果最明显。DThroughthisoptimization,wecanmakethecall-by-ranktimecomplexitybetterthanO(n).通过这样的优化，我们可以使循秩访问时间复杂度优于O(n)。C.Sorted_list--Homewrok第1题Theprocessoforderedlistuniquealgorithmis:有序列表唯一化算法的过程是：AKeeponlythefirstelementofeachintervalofequalelements.只保留每个相等元素区间的第一个元素BEachtimeanelementisencountered,findbackwardanddeletethesameone.每遇到一个元素，向后查找并删除与之雷同者CEverytimeanelementisencountered,lookaheadanddeletethesameone.每遇到一个元素，向前查找并删除与之雷同者DCheck(n¦2)pairsofdifferentelements.Foreachpairofelements,iftheyareidentical,arbitrarilydeleteoneofthem.检查(n¦2)个不同的元素对，对于每一对元素，若雷同则任意删除其一第2题CanabinarysearchbeusedinanorderedlisttoreducethetimecomplexitytoΘ(log2n)?能否在有序列表中用二分查找使得时间复杂度降为Θ(log2n)？AYes能BNo,becausetheamortizedtimecomplexityoflistexpansionisnotΘ(1)不能，因为列表扩容的分摊复杂度不是Θ(1)CNo,becausethelistcannotbeefficientlyaccessedbyrank不能，因为列表不能高效地循秩访问DYes,becausethetimecomplexityofthelistdeletenodeisΘ(1)能，因为列表删除节点的时间复杂度为Θ(1)D.Selectionsort--Homework第1题V={11,5,7,13,2,3},sortingVbyselectionsort,thelargestelementselectedastheunsortedsubvectorisV={11,5,7,13,2,3}，对V进行选择排序，被选为未排序子向量中最大的元素依次为：A11,5,7,2,3B13,7,11,2,5C13,11,7,5,3D2,11,13,5,7第2题InordertoensurethestabilityoftheselectSort()algorithm,themeasureswetakeare为了保证selectSort()算法的稳定性，我们采取的措施是：AInselectMax(),amongthemultipleequallargestelements,theselectionpositionisthelastoneselectMax()中对于多个相等的最大元素，选取其中位置最靠后者BInselectMax(),amongthemultipleequallargestelements,theselectionpositionisthefirstoneselectMax()中对于多个相等的最大元素，选取其中位置最靠前者CFirstcalldeduplicate()toremoveallduplicateelements.先调用deduplicate()删除所有重复元素DRegardlessofimplementationdetails,thealgorithmisinherentlystable无论实现细节如何，该算法本来就是稳定的第3题Foravectororlistofsizen,theworst-casetimecomplexityforselectingsortingandbubblesortingis.对于规模为n的向量或列表，选择排序和冒泡排序的最坏时间复杂度为：AΘ(nlog2n),Θ(n2)BΘ(nlog2n),Θ(nlog2n)CΘ(n2),Θ(n2)DΘ(n2),Θ(nlog2n)E.Insertionsort--Homework第1题TheaverageandworsttimecomplexityofinsertionSort()isinsertionSort()的平均、最坏时间复杂度分别为：AΘ(n),Θ(n2)BΘ(n2),Θ(n2)CΘ(nlog2⁡(n)),Θ(n2)DΘ(nlog2⁡(n)),Θ(nlog2⁡(n))第2题Themaximumnumberofreversedpairscontainedinasequenceofnelementsisn个元素的序列所含逆序对的个数最大是：An!Bn!/2C(n(n-1))/2Dn第3题ForaOrderedsubsequenceintheinsertionprocessorder(supposeitslengthtok)对于插入过程排序中的已排序子序列（设其长度为k）：ATheelementsarethesmallestkelementsintheentiresequence其中的元素是整个序列中最小的k个元素BTheelementsarethelargestkelementsintheentiresequence其中的元素是整个序列中最大的k个元素CTheelementsarethekelementsatthefrontoftheoriginalsequence其中的元素是原序列中位于前方的k个元素DTheelementsarethekelementsinthebackoftheoriginalsequence其中的元素是原序列中位于后方的k个元素第4题Afterastepofinsertionsorting,thefollowingsub-sequenceV={2,7,13,5,3}isobtained,andthe3elementsaresorted.Afteranotheriteration,theresultis:在插入排序的某一步后得到如下子序列V={2,7,13,5,3}，此时已排序部分有3个元素。经过又一轮迭代后的结果是：A{2,3,7,13,5}B{2,7,13,3,5}C{2,5,7,13,3}D{3,2,7,13,5}Homework第1题About