第一章1、單選題ForcomputingtheHailstonesequence(a.k.a.3n+1problem),theHailstone(n)program視頻中提到的Hailstone問題（又名3n+1問題）中Hailstone(n)的計(jì)算程序是Awon'tterminateforanyvalueofn.對(duì)于所有的n都是無窮的Bwon'tterminateforsomevaluesofn(butwillterminateotherwise).對(duì)于部分n是無窮的CWedon'tknowifittermiatesforanyvalueofn.不能確定是否存在n，使程序無法終止Dalwaysterminateforanyvalueofn.對(duì)于所有的n都是有窮的C2、單選題Whatistheforemostcriterionfora"goodalgorithm"?判斷一個(gè)算法是否是一個(gè)“好算法”，最重要的一條性質(zhì)是Acorrectness正確Brobustness健壯Creadability可讀Defficiency效率D3、單選題WhichofthefollowingisNOTacomponentofaTuringmachine?以下哪項(xiàng)不是圖靈機(jī)的組成要件？AAtapeoffinitelength有限長(zhǎng)的紙帶BAfinitealphabet有限的字母表CAfinitesetofstates有限種狀態(tài)DAheadforreadingandwriting讀寫頭A4、單選題Trueoffalse:TheRAMmodelisequippedwithafiniteamountofstorage,whichdiffersfromtheTuringmachine.判斷正誤：RAM模型與圖靈機(jī)模型的區(qū)別在于圖靈機(jī)的存儲(chǔ)空間無限，而RAM的存儲(chǔ)空間有限。ATrue對(duì)BFalse錯(cuò)B5、O6、單選題Whichofthefollowingequationsiswrong?下列對(duì)應(yīng)關(guān)系中錯(cuò)誤的是1+17、單選題Thecomplexityoftheprogramaboveis以上程序的時(shí)間復(fù)雜度為8、單選題Trueorfalse:Inbubblesort,thesizeoftheproblemisreducedtokafterkroundsofsweep&swap.判斷：經(jīng)過k輪掃描交換后，起泡排序程序會(huì)將問題規(guī)模縮減至k。ATrue對(duì)BFalse錯(cuò)B9、單選題Trueorfalse:Toapplydecrease-and-conquer,wedividetheoriginalproblemintotwodegeneratedsub-problems,solvethem,andmergetheirsolutions.判斷：減而治之的思想是：將問題劃分為兩個(gè)平凡的子問題，分別求解子問題，來得到原問題的解。ATrue對(duì)BFalse錯(cuò)B10、LiLeiA同學(xué)11、單選題Inthevideolectureweseeacommentinthecode:"Twobasecasesarerequired".Whatdoesitreferto?視頻里代碼注釋中“需要兩個(gè)遞歸基”的含義是AWeneedtwofunctionshandlingdifferentcases(whennisevenorodd).問題需要按照“n為奇數(shù)”、“n為偶數(shù)”兩種情況分別設(shè)計(jì)兩個(gè)函數(shù)BThesequenceofrecursivecalllsisterminatedwhentheproblemsizeisreducedtoeither0or1.在問題規(guī)?？s減為0或1時(shí)，停止遞歸CTheprogramreturnstothemainfunctionwhentheproblemsizeisreducedtoeither0or1.在問題規(guī)?？s減為0或1時(shí)，返回main函數(shù)（或遞歸函數(shù)被調(diào)用的函數(shù)）DTwosub-instancesaregeneratedfromeveryinstanceoftherecursivecalls.遞歸函數(shù)在執(zhí)行過程中將每次創(chuàng)建兩個(gè)遞歸實(shí)例B12、單選題判斷：用分而治之的思想來解決長(zhǎng)度為n的數(shù)組的求和問題（n足夠大），遞歸實(shí)例的數(shù)目會(huì)比用減而治之的方法少。A對(duì)B錯(cuò)B13、單選題Thenaivewayofcomputingfib(n)recursivelyleadstoatimecomplexityof直接用定義以遞歸的方式計(jì)算fib(n)的時(shí)間復(fù)雜度是：O(2?)14、單選題Witharegularcomputer,computingfib(100)naivelyusingrecursionwouldcost(noneedtoconsideroverflow).以現(xiàn)在普通計(jì)算機(jī)的速度，直接用定義以遞歸的方式計(jì)算fib(100)需要多少時(shí)間（不考慮溢出）:Alessthananhour一小時(shí)之內(nèi)Baboutaday大約一天Ctenyears十Dmuchlongerthanyourlifetime.這輩子看不到啦D15、單選題Forthestaircaseprobleminthevideolecture,howmanydifferentwayscangetyoufromthefirststeptotheeighth.對(duì)于視頻中的上臺(tái)階問題（從第一層開始），上到第8層共有多少種不同的走法：A21B13C17D34A16、單選題Thetimeandspacecomplexitiesforcomputingfib(n)withdynamicprogrammingare用動(dòng)態(tài)規(guī)劃計(jì)算fib(n)的時(shí)間、空間復(fù)雜度分別為17、單選題ThelengthoftheLCSbetween"program"and"algorithm"isprogram和algorithm的LCS長(zhǎng)度為:A1B2C3D4C18、單選題LCS(x,y)isdefinedtobethelengthoftheLCSbetweenstringsxandy.LCS("program","algorithm")=LCS(x,y)表示字符串x,y最長(zhǎng)公共子序列長(zhǎng)度，則LCS（“program”,“algorithm”）=ALCS（“progra”,“algorith”）+1BLCS（“progra”,“algorithm”）CLCS（“program”,“algorith”）Dmax{LCS（“progra”,“algorithm”）,LCS（“program”,“algorith”）}A19、單選題CheckouttheDemointhevideolecture(thedownloadlinkisontherightsideofthe"Course"page,orin01-f-6).Whichtoolwasusedtowritethedemo?下載并使用視頻中的Demo（下載鏈接在“課程信息”右側(cè)，01-f-6里也有），它是用什么做的？AVisualBasicBVC++CXwindowDMSExcelD20、單選題ComputingtheLCSusingdynamicprogrammingleadstoatimecomplexityof(mandnarethelengthsoftheinputstrings)用動(dòng)態(tài)規(guī)劃求解輸入序列長(zhǎng)度分別為m,n的LCS問題，時(shí)間復(fù)雜度為：21、22、單選題Whichofthefollowingfunctionsgrowsfastestasymptotically?下列函數(shù)漸進(jìn)增長(zhǎng)速度最快的是：23、單選題Giventhefollowingthreefunctions:以下是三個(gè)函數(shù)：Theirtimecomplexitiesare:它們的時(shí)間復(fù)雜度分別為：24、單選題ThefollowingrecursivefunctionisforreversingarrayA[lo,hi]以下遞歸函數(shù)實(shí)現(xiàn)數(shù)組A[lo,hi]的倒置：Whatisthetimecomplexityofreverse(A,0,n-1),forreversinganarrayoflengthn?調(diào)用reverse(A,0,n-1)以倒置長(zhǎng)度為n的數(shù)組，算法的時(shí)間復(fù)雜度為：25、單選題V={11,23,19,7,17,5,3,13,2,29}WhensortingVusingbubblesort,whatisthevalueofV[8]aftertworoundsofsweep&swap?對(duì)V進(jìn)行起泡排序，兩趟掃描交換后V[8]=A17B19C23D29C第二章1、單選題Whichofthefollowingoptionsiscorrect:下列說法中正確的是：ATheabstractdatatypeisanadvanceddatatypeprovidedbyC++forimplementingdatastructures.抽象數(shù)據(jù)類型是C++提供的一種高級(jí)的數(shù)據(jù)類型，用于實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。BTheabstractdatatypedetermineshowdataisstored.抽象數(shù)據(jù)類型決定了數(shù)據(jù)的存儲(chǔ)方式。CThesameabstractdatatypemaybeimplementedusingmultipledatastructures.同一個(gè)抽象數(shù)據(jù)類型可能用多種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。DDatastructureisanabstractdatatype.數(shù)據(jù)結(jié)構(gòu)即抽象數(shù)據(jù)類型。C2、單選題Onaninitiallyemptyvector,what'stheresultofexecutinginsert(0,2),insert(1,6),put(0,1),remove(1)andinsert(0,7):在一個(gè)初始為空的向量上依次執(zhí)行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的結(jié)果是：A{6,2,7}B2,6,0,7}C{7,1}D{2,1,7}C3、單選題Thefollowingcodeisavariantofthevectorcopycodewiththesamesemantics.Thespaceshouldbefilledwith:以下代碼是向量復(fù)制代碼的一個(gè)變體且語義與其相同，空格處應(yīng)填入的內(nèi)容為：A--hiBhi--C++loDlo++A1、單選題Onanemptyvectorwithaninitialmaximumcapacityof10,theloadfactorafterexecutinginsert(0,2),insert(1,6),put(0,1),remove(1)andinsert(0,7)is:在一個(gè)初始最大容量為10的空向量上依次執(zhí)行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的裝填因子是：A10%B20%C30%D40%B2、單選題Isitpossibletoreplace:是否可以將視頻里向量擴(kuò)容代碼中的：for(inti=0;i<_size;i++)_elem[i]=oldElem[i];inthevectorexpansioncodeinthevideowith:替代為：memcpy(_elem,oldElem,_size*sizeof(T));P.S.ThisquestioninvolvestherelevantknowledgeofC++P.S.本題涉及C++的相關(guān)知識(shí)AYes,theyareequivalentandtherewillbenoproblem.是，二者是等價(jià)的，不會(huì)有任何問題。BNo,becausetherangeofelementalintervalsforthetwocopiesisdifferent.否，因?yàn)槎邚?fù)制的元素區(qū)間范圍不同。CNo,becausetheirefficiencyaredifferent.否，因?yàn)槎叩男什煌?。DNo,becausewhetherthelattercanachievethepurposeisrelatedtoelementtypeT.否，因?yàn)楹笳吣芊襁_(dá)到目的與元素類型T有關(guān)。D3、單選題Usingtheexpansionstrategyofappendingfixedmemoryspaceeachtime,theamortizedtimecomplexityofinsertingelementofvectorofsizenis:采用每次追加固定內(nèi)存空間的擴(kuò)容策略，規(guī)模為n的向量插入元素的分?jǐn)倳r(shí)間復(fù)雜度為：4、單選題Byusingtwoexpansionstrategies,oneforeachadditionalfixedmemoryspaceandonefordoubleupmemoryspace,theamortizedtimecomplexityofinsertingelementsofvectorofsizenis:分別采用每次追加固定內(nèi)存空間和每次內(nèi)存空間翻倍兩種擴(kuò)容策略，規(guī)模為n的向量插入元素的分?jǐn)倳r(shí)間復(fù)雜度分別為：5、單選題Withregardtotheaveragecomplexityandtheamortizedcomplexity,whichofthefollowingstatementiswrong:關(guān)于平均復(fù)雜度和分?jǐn)倧?fù)雜度，下列說法中錯(cuò)誤的是：AThesequenceofoperationsconsideredbytheamortizedcomplexitymustberealisticandfeasible分?jǐn)倧?fù)雜度所考量的一串操作序列一定是真實(shí)可行的BTheaveragecomplexitydependsontheassumptionoftheprobabilityofoccurrenceofeachoperation,whiletheamortizedcomplexityisnot平均復(fù)雜度依賴于對(duì)各操作出現(xiàn)概率的假設(shè)，而分?jǐn)倧?fù)雜度則不是如此CAmortizedcomplexityresultsinlowerthanaveragecomplexity分?jǐn)倧?fù)雜度得到的結(jié)果比平均復(fù)雜度低DTheconclusionofΘ(1)inthedoubleupexpansionstrategyreferstotheamortizedcomplexity加倍擴(kuò)容策略中Θ(1)的結(jié)論是指分?jǐn)倧?fù)雜度C1、單選題WhatisthemeaningofthereturnvalueofT&Vector<T>::operator[](Rankr){return_elem[r];}?T&Vector<T>::operator[](Rankr){return_elem[r];}中的返回值T&是什么意義？AThisisapointeroftypeTbecauseitismoreefficient這是類型T的指針，使用它是因?yàn)樾矢連ThisisareferencetotypeTbecauseitismoreefficient這是類型T的引用，使用它是因?yàn)樾矢逤ThisisapointeroftypeTbecauseitsreturnvaluecanbeusedasanleftvalue這是類型T的指針，使用它是因?yàn)榉祷刂悼梢宰鳛樽笾礑ThisisareferencetothetypeTbecauseitsreturnvaluecanbeusedasanleftvalue這是類型T的引用，使用它是因?yàn)榉祷刂悼梢宰鳛樽笾礑2、單選題WhathappensiftheFORloopintheinsert()functionchangestothefollowingform？for(inti=r;i<_size;i++)_elem[i+1]=_elem[i];ANoproblem,justchangeitfromfronttoback沒有問題，只是改為從前向后移動(dòng)罷了BOverwriteallelementsintheoriginalvectorwithrankgreaterthanr會(huì)覆蓋原向量中秩大于r的所有元素COverwriteallelementsintheoriginalvectorwithranklessthanr會(huì)覆蓋原向量中秩小于r的所有元素DWillcausevectorexpansionfailure會(huì)引起向量擴(kuò)容失敗B3、單選題Whythesuffixofthedeletedelementismovedfromfronttobackintheintervaldeletionalgorithmremove(lo,hi)?為什么區(qū)間刪除算法remove(lo,hi)中要從前向后移動(dòng)被刪除元素的后綴？AThisisacustomarypractice,whichinturnisalsofeasible這是一個(gè)約定俗成的習(xí)慣，反過來也可行BOtherwiseitmaycoversomeelements否則可能會(huì)覆蓋部分元素COtherwiseitmayfailtodeleteallelementswithintheinterval[lo,hi)否則可能未能刪除區(qū)間[lo,hi)內(nèi)所有的元素DOtherwiseitmayleadtoinefficiency否則可能導(dǎo)致效率低下B4、單選題Forthededuplicate()algorithm,theworst-casetimecomplexityforthevectorscalenis:對(duì)于deduplicate()算法，向量規(guī)模為n時(shí)的最壞時(shí)間復(fù)雜度為：5、單選題AsafunctionobjectclassXXX,whichofthefollowingmemberfunctionsmustbeexplicitlydefined:作為一個(gè)函數(shù)對(duì)象的類XXX，它必須顯式定義以下哪個(gè)成員函數(shù)：AXXX()B~XXX()Coperator[]()Doperator()()D1、單選題Thereturnvalueofthedisordered()algorithmis:disordered()算法的返回值是：AReverseordernumber逆序數(shù)BThenumberofadjacentinversion相鄰逆序?qū)€(gè)數(shù)CTheboolvalueofwhetherit'sordered表示是否有序的bool值DTheintvalueofwhetherit'sordered表示是否有序的int值B2、單選題Repeatingelementsinanorderedvector有序向量中的重復(fù)元素ASameastheunorderedvector與無序向量相同BMostofthemisadjacentdistribution,onlyaverysmallpartspreadinotherlocations大部分緊鄰分布，只有極小部分散布在其它位置CAllofthemareadjacentdistribution必定全部緊鄰分布DAllofthemaretimedistribution全部相間分布C3、單選題Forvectorsofsizen,theworst-casetimecomplexityoftheinefficientversionofuniquify()is:對(duì)于規(guī)模為n的向量，低效版uniquify()的最壞時(shí)間復(fù)雜度為：4、單選題Whydoesn'tthealgorithmneedtocallremove()todeleteanelement?為什么該算法中不需要調(diào)用remove()進(jìn)行元素刪除？AThereisnoduplicateelement本來就沒有重復(fù)元素BDuplicateelementsareignoreddirectly重復(fù)元素被直接忽略了CDuplicateelementsaremovedtotheendofthevector重復(fù)元素被移到了向量末尾DDuplicateelementshavebeenmodifiedtobenon-repeatingelements重復(fù)元素修改成了不重復(fù)的元素B5、單選題Forvectorsofsizen,theworst-casetimecomplexityoftheefficientversionofuniquify()is:對(duì)于規(guī)模為n的向量，高效版uniquify()的最壞時(shí)間復(fù)雜度為：1、單選題Foravectorofsizen,thereturnvalueoffind()onasearchfailureis:對(duì)于規(guī)模為n的向量，查找失敗時(shí)find()的返回值是：A-1B0CnDnanA2、單選題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);D3、單選題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)A4、單選題WhichofthefollowingexpressionsisequivalenttoRankmi=(lo+hi)>>1?(loandhiarenon-negative)Rankmi=(lo+hi)>>1等效于下列哪個(gè)表達(dá)式?（lo和hi非負(fù)）ARankmi=(lo+hi)\2BRankmi=(lo+hi)%2CRankmi=(lo+hi)/2DRankmi=(double)(lo+hi)/2C5、單選題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)需要進(jìn)行多少次比較？A4B5C6D7B6、單選題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的查找長(zhǎng)度是x，則在V2中查找14的查找長(zhǎng)度為：AxBx+1C2*xDx/2A1、單選題WhatisthedifferencebetweenthefibSearch()algorithmandbinSearch()algorithm?fibSearch()算法與binSearch()有什么區(qū)別？ATheirreturnvalueisdifferent二者的返回值不同BTheformerisarecursivealgorithm,andthelatterisaniterativealgorithm前者是遞歸算法，后者是迭代算法CTherearedifferentwaystochoosetheaxispointmi二者選取軸點(diǎn)mi的方式不同DTheformer'sasymptotictimecomplexityislowerthanthelatter,sotheformerismoreefficient前者的漸進(jìn)時(shí)間復(fù)雜度低于后者，故前者效率更高C2、單選題V={1,2,3,4,5,6,7},usingFibonaccitofindelement1inV,theelementselectedasthepivotpointmiis:V={1,2,3,4,5,6,7}，在V中用Fibonacci查找元素1，被選取為軸點(diǎn)mi的元素依次是：A4,3,2,1B4,2,1C5,2,1D5,3,2,1D3、單選題WhyisthesearchprocessforbinSearch()versionAnotbalanced?為什么說binSearch()版本A的查找過程并不平衡?ABecausetheleftandrightbrancheshavedifferentsubvectorsizes因?yàn)橄蜃?、向右兩個(gè)分支的子向量規(guī)模不同BBecausethenumberofcomparisonsrequiredfortheleftandrightbranchesisnotequal因?yàn)橄蜃?、向右兩個(gè)分支所需要的比較次數(shù)不相等CBecausetheFibonaccisearchismorebalancedthanthebinarysearch因?yàn)镕ibonacci查找比二分查找更平衡DBecausetheprobabilitythatthekeyisintheleftsubvectorisgreaterthantheprobabilitythatitisintheright因?yàn)殛P(guān)鍵碼位于左子向量中的概率比位于右側(cè)的概率大B1、單選題Foravectorofsizen,theoptimaltimecomplexityforbinarysearchversionsAandBis:對(duì)于規(guī)模為n的向量，二分查找版本A和B的最優(yōu)時(shí)間復(fù)雜度分別為：2、單選題Forthesearch()interface,whatwearegoingtoreturnwhenthereismorethanonetargetelementinthevector:對(duì)于search()接口，我們約定當(dāng)向量中存在多個(gè)目標(biāo)元素時(shí)返回其中：ARankmaximun秩最大者BRankminimum秩最小者CRankintermediate秩中間者DRandomlyreturnoneofthem隨機(jī)返回其中一個(gè)即可A3、單選題ForbinarysearchversionC,whatisthenextsearchrangewhene<V[mi]isnotestablished:對(duì)于二分查找版本C，當(dāng)e<V[mi]不成立時(shí)下一步的查找范圍是：AV[lo,mi)BV[mi,hi)CV[mi,hi]DV(mi,hi)D4、單選題ForbinarysearchversionC,whenthelengthofthesearchintervalisreducedto0,V[lo]is:對(duì)于二分查找版本C，當(dāng)查找區(qū)間的長(zhǎng)度縮小為0時(shí)，V[lo]是：1、單選題Ifthedistributionofelementsinan(ordered)vectorsatisfiesanindependentuniformdistribution(beforesorting),theaveragetimecomplexityoftheinterpolationsearchis:如果（有序）向量中元素的分布滿足獨(dú)立均勻分布（排序前），插值查找的平均時(shí)間復(fù)雜度為：AO(n)BO(logn)CO(loglogn)DO(1)C2、填空題Searchingforsearchelements7withinterpolationinthevectorV={2,3,5,7,11,13,17,19,23}在向量V={2,3,5,7,11,13,17,19,23}中用插值查找搜索元素7Guessthepivotpointmi猜測(cè)的軸點(diǎn)mi____11、單選題V={7,2,3,11,17,5,19,13}AftertwoscanexchangeofV,V[6]=V={7,2,3,11,17,5,19,13}，對(duì)V進(jìn)行兩次掃描交換后V[6]=A11B13C17D19C2、單選題Whichsituationwilltheimprovedblisteringorderwillendprematurely?經(jīng)改進(jìn)的起泡排序在什么情況下會(huì)提前結(jié)束？ACompletealln-1scans完成全部n-1趟掃描交換BThenumberofscanconversionscompleted=Thenumberofscanswitchingparametersfortheactualelementexchange+1完成的掃描交換趟數(shù)=實(shí)際發(fā)生元素交換的掃描交換趟數(shù)+1CThenumberofscanconversionscompleted=Thenumberofscanswitchingsthatactuallytookplaceforelementexchange完成的掃描交換趟數(shù)=實(shí)際發(fā)生元素交換的掃描交換趟數(shù)DComplete(n-1)/2scanexchange完成(n-1)/2趟掃描交換B3、單選題TrythefollowingalgorithmtosortV={19,17,23}:試用以下算法對(duì)V={19,17,23}排序：1.Sortbyunitsatfirst1.先按個(gè)位排序2.Onthebasisofthepreviousstep,sortagainbytens2.在上一步基礎(chǔ)上，再按十位排序Isthisalgorithmcorrect?這個(gè)算法的是否正確？ACertainlycorrect一定正確BCertainlyincorrect一定不正確CIfthesortingalgorithmusedinstep2isstable,thencorrect若第2步用的排序算法是穩(wěn)定的，則正確DIfthesortingalgorithmusedinstep1isstable,thencorrect若第1步用的排序算法是穩(wěn)定的，則正確C1、2、單選題Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:對(duì){2,5,7}和{3,11,13}進(jìn)行二路歸并，執(zhí)行的元素比較依次是：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與13A3、單選題Forvectorsofsizen,theoptimalandworst-casetimecomplexityformergesortingis:對(duì)于規(guī)模為n的向量，歸并排序的最優(yōu)、最壞時(shí)間復(fù)雜度分別為：1、單選題Byusingtwoexpansionstrategies,oneforeachadditionalfixedmemoryspaceandonefordoubleupmemoryspace,theamortizedtimecomplexityofinsertingelementsofvectorofsizenis:分別采用每次追加固定內(nèi)存空間和每次內(nèi)存空間翻倍兩種擴(kuò)容策略，規(guī)模為n的向量插入元素的分?jǐn)倳r(shí)間復(fù)雜度分別為：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);D3、單選題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中使用它查找目標(biāo)元素16，整個(gè)過程中與目標(biāo)元素發(fā)生過比較的元素依次為：A11,17,13B7,3,17C13,11,17D5,7,11A4、單選題Thebinarysearchfor"versionC"isextractedasfollows:二分查找“版本C”摘錄如下：WhentherearemultipleelementstobesearchedinthearrayA,thereturnvalueofthefunction:當(dāng)數(shù)組A中有多個(gè)待查找元素e時(shí)，函數(shù)的返回值為：AReturntheelementwhoserankissmallest返回秩最小者BReturntheelementwhoserankisbiggest返回秩最大者CReturntheelementwhoserankisinthemiddle返回秩位于正中間者DRandomlyreturnoneofthem隨機(jī)返回其中一個(gè)B5、單選題Thefollowingfunctionisarecursiveversionofthebinarysearch:以下函數(shù)是二分查找的遞歸版：Foravectorofsizen,thetimeandspacecomplexityoftherecursiveversionandtheiteratedversionlearnedinclassare:對(duì)于規(guī)模為n的向量，該遞歸版的時(shí)間、空間復(fù)雜度和課堂上所學(xué)的迭代版的時(shí)間、空間復(fù)雜度分別是：6、單選題ThevectorV={1,2,3,4,5,6,7},usestheFibonaccisearchtofindthetargetelement1inV,theelementsselectedasthepivotmiare:向量V={1,2,3,4,5,6,7}，在V中用斐波那契查找查找目標(biāo)元素1，被選取為軸點(diǎn)mi的元素依次是：A4,3,2,1B4,2,1C5,2,1D5,3,2,1D7、單選題Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:對(duì){2,5,7}和{3,11,13}進(jìn)行二路歸并，執(zhí)行的元素比較依次是：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與13A8、單選題Inanyscanningexchangeofbubblingordering,ifthelastexchangeistoswapelementsX>YforY<X,then:在起泡排序的任何一趟掃描交換過程中，若最后一次交換是將元素X>Y交換為Y<X，則此后：AXandYmusthavebeeninplaceX和Y必然都已經(jīng)就位BXmustbeinplacewhileYisnotnecessarilyX必然就位，而Y未必CYmustbeinplacewhileXisnotnecessarilyX未必就位，而Y必然DNeitherXnorYarenecessarilyinplaceX和Y都未必已經(jīng)就位B9、單選題Onaninitiallyemptyvector,what'stheanswerafterexecuting:insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)在一個(gè)初始為空的向量上依次執(zhí)行：insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)后的結(jié)果是：A{1,2,7}B{2,1,0,7}C{7,1}D{2,1,7}C10、單選題Thefollowingcodeimplementsintervaldeletionofvectorsbycontinuouslydeletingindividualelements:以下代碼通過不斷刪除單個(gè)元素實(shí)現(xiàn)向量的區(qū)間刪除：Theoverloadedfunctionremove(Rankr)completestheoperationofdeletingasingleelement,anditstimecomplexityisproportionaltothenumberofsucceedingelementsofthedeletedelement.Forvectorsofsizen,theworst-casecomplexityofthisintervaldeletionalgorithmis:其中重載函數(shù)remove(Rankr)完成刪除單個(gè)元素的操作，其時(shí)間復(fù)雜度正比于被刪除元素的后繼個(gè)數(shù)。對(duì)于規(guī)模為n的向量，該區(qū)間刪除算法的最壞時(shí)間復(fù)雜度為：第三章1、單選題Whichofthefollowingoptionsaboutrankoflistnodeisincorrect下列關(guān)于列表的秩的說法中不正確的是AThephysicaladdressofalistnodecanbedeterminedbyitsrank列表節(jié)點(diǎn)的秩與物理地址有明確的對(duì)應(yīng)關(guān)系BThecostofmaintainingrankoflistnodeishigh列表的秩具有很高的維護(hù)成本CInalist,thecostofrank-basedaccessishigh在列表中循秩訪問的成本較高DInalist,location-basedaccessisfasterthanrank-basedaccess在列表中循位置訪問會(huì)比循秩訪問更快A2、單選題Whichofthefollowingoptionsaboutdefinedinterfaceisincorrect?下列關(guān)于我們定義的接口的描述中，哪一條是錯(cuò)誤的？AForthenodesinthelist,wecantaketheirpredecessorandsuccessorrespectivelybycallingthepred()andsucc()interfaces.對(duì)于列表中的節(jié)點(diǎn)，我們可以通過調(diào)用pred()和succ()接口分別取其前驅(qū)和后繼。BOneoftheimportantdifferencesbetweenfind(e)andsearch(e)inlistinterfaceisthatfind(e)issuitableforalllists,andsearch(e)isappliedtoorderedlists.對(duì)于列表接口中的find(e)與search(e)，其中一個(gè)重要區(qū)別在于find普適于所有列表，而search適用于有序列表。CIfthelengthofthe'visiblelist'partisn,theranksofthe'head',first,last,and'trail'nodesare-1,0,n,n+1respectively.如果一個(gè)列表的visiblelist部分長(zhǎng)度為n，則頭、首、末、尾節(jié)點(diǎn)的秩分別為-1,0,n,n+1DInconstructingthelist,weneedtoconstructsentrynodesfirst.在構(gòu)造列表時(shí)，我們需要首先構(gòu)造哨兵節(jié)點(diǎn)。C1、單選題IfyouchangeinsertAsPred()tothefollowingfunction,theresultis:若將insertAsPred()改為以下函數(shù)，其結(jié)果是：ACaninsertnodesnormally.能正常插入節(jié)點(diǎn)BCannotinsertnode,originallistremainsunchanged.不能插入節(jié)點(diǎn)，原列表仍然保持不變CCannotinsertnode,thestructureoftheoriginallistisdestroyed.不能插入節(jié)點(diǎn)，原列表的結(jié)構(gòu)被破壞DCaninsertanoderelatedtothestructureofthelistatthetime.能否插入節(jié)點(diǎn)與當(dāng)時(shí)列表的結(jié)構(gòu)有關(guān)C2、Throughthisoptimization,wecanmakethecall-by-ranktimecomplexitybetterthanO(n).通過這樣的優(yōu)化，我們可以使循秩訪問時(shí)間復(fù)雜度優(yōu)于O(n)。1、單選題Theprocessoforderedlistuniquealgorithmis:有序列表唯一化算法的過程是：AKeeponlythefirstelementofeachintervalofequalelements.只保留每個(gè)相等元素區(qū)間的第一個(gè)元素BEachtimeanelementisencountered,findbackwardanddeletethesameone.每遇到一個(gè)元素，向后查找并刪除與之雷同者CEverytimeanelementisencountered,lookaheadanddeletethesameone.每遇到一個(gè)元素，向前查找并刪除與之雷同者DCheck(n|2)pairsofdifferentelements.Foreachpairofelements,iftheyareidentical,arbitrarilydeleteoneofthem.檢查(n|2)個(gè)不同的元素對(duì)，對(duì)于每一對(duì)元素，若雷同則任意刪除其一A2、No,becausethelistcannotbeefficientlyaccessedbyrank不能，因?yàn)榱斜聿荒芨咝У匮仍L問1、單選題V={11,5,7,13,2,3},sortingVbyselectionsort,thelargestelementselectedastheunsortedsubvectorisV={11,5,7,13,2,3}，對(duì)V進(jìn)行選擇排序，被選為未排序子向量中最大的元素依次為：A11,5,7,2,3B13,7,11,2,5C13,11,7,5,3D2,11,13,5,7C2、單選題InordertoensurethestabilityoftheselectSort()algorithm,themeasureswetakeare為了保證selectSort()算法的穩(wěn)定性，我們采取的措施是：AInselectMax(),amongthemultipleequallargestelements,theselectionpositionisthelastoneselectMax()中對(duì)于多個(gè)相等的最大元素，選取其中位置最靠后者BInselectMax(),amongthemultipleequallargestelements,theselectionpositionisthefirstoneselectMax()中對(duì)于多個(gè)相等的最大元素，選取其中位置最靠前者CFirstcalldeduplicate()toremoveallduplicateelements.先調(diào)用deduplicate()刪除所有重復(fù)元素DRegardlessofimplementationdetails,thealgorithmisinherentlystable無論實(shí)現(xiàn)細(xì)節(jié)如何，該算法本來就是穩(wěn)定的A3、單選題Foravectororlistofsizen,theworst-casetimecomplexityforselectingsortingandbubblesortingis.對(duì)于規(guī)模為n的向量或列表，選擇排序和冒泡排序的最壞時(shí)間復(fù)雜度為：1、單選題TheaverageandworsttimecomplexityofinsertionSort()isinsertionSort()的平均、最壞時(shí)間復(fù)雜度分別為：2、單選題Themaximumnumberofreversedpairscontainedinasequenceofnelementsisn個(gè)元素的序列所含逆序?qū)Φ膫€(gè)數(shù)最大是：An!Bn!/2C(n(n-1))/2DnC3、單選題ForaOrderedsubsequenceintheinsertionprocessorder(supposeitslengthtok)對(duì)于插入過程排序中的已排序子序列（設(shè)其長(zhǎng)度為k）：ATheelementsarethesmallestkelementsintheentiresequence其中的元素是整個(gè)序列中最小的k個(gè)元素BTheelementsarethelargestkelementsintheentiresequence其中的元素是整個(gè)序列中最大的k個(gè)元素CTheelementsarethekelementsatthefrontoftheoriginalsequence其中的元素是原序列中位于前方的k個(gè)元素DTheelementsarethekelementsinthebackoftheoriginalsequence其中的元素是原序列中位于后方的k個(gè)元素C4、1、單選題Aboutvectorandthefollowinglist,whichiswrong:下列關(guān)于向量和列表的說法錯(cuò)誤的是：2、單選題Inordertoinsertanewnodeinthelistasadirectprecursortop,therearefourrelatedstatements為了在列表中插入一個(gè)新節(jié)點(diǎn)node作為p的直接前驅(qū)，有四個(gè)相關(guān)的語句①p->pred->succ=node②node->pred=p->pred③node->succ=p④p->pred=nodeThecorrectexecutionorderoftheabovestatementis:上述語句執(zhí)行順序正確的是：A③②④①B③②①④C①④③②D④②③①B3、單選題Forabi-directionalandunidirectionallistofnnodes,theworst-casecomplexityoflocatinganodep'sdirectprecursoris:對(duì)于n個(gè)節(jié)點(diǎn)的雙向、單向列表，定位某節(jié)點(diǎn)p直接前驅(qū)的最壞時(shí)間復(fù)雜度分別為：4、單選題Thetimecomplexityoffindinganelementinanorderedlistis在有序列表中查找一個(gè)元素的時(shí)間復(fù)雜度是：5、單選題Selectingthelist{11,5,7,13,2,3}.EachtimetheelementsareselectedasthelargestelementintheunsortedsublistinselectMax()對(duì)列表{11,5,7,13,2,3}進(jìn)行選擇排序，每一次selectMax()被選為未排序子列表中最大者的元素依次為：A11,5,7,2,3B13,7,11,2,5C13,11,7,5,3D2,11,13,5,7C6、單選題WhichimplementationoftheselectSort()algorithmisstableselectSort()算法的哪種實(shí)現(xiàn)是穩(wěn)定的：AEachtimemovesthesmallestelementtothefront.Formultipleequalminimumelements,selecttheonewiththesmallestposition.每一趟將最小元素移到前方，對(duì)于多個(gè)相等的最小元素，選取其中位置最靠前者。BEachtimemovesthebiggestelementtothefront.Formultipleequalmaximumelements,selecttheonewiththesmallestposition.每一趟將最大元素移到后方，對(duì)于多個(gè)相等的最大元素，選取其中位置最靠前者。CEachtimemovesthesmallestelementtothefront.Formultipleequalminimumelements,selecttheonewiththelargestposition.每一趟將最小元素移到前方，對(duì)于多個(gè)相等的最小元素，選取其中位置最靠后者。DTheaboveimplementationsareallstable以上實(shí)現(xiàn)皆穩(wěn)定。A7、單選題Fororderedsubsequences(settheirlengthtok)duringinsertionsorting.對(duì)于插入排序過程中的已排序子序列（設(shè)其長(zhǎng)度為k）：ATheelementsarethesmallestkelementsintheentiresequence其中的元素是整個(gè)序列中最小的k個(gè)元素BTheelementsarethebiggestkelementsintheentiresequence其中的元素是整個(gè)序列中最大的k個(gè)元素CTheelementsarethekelementsatthefrontoftheoriginalsequence.其中的元素是原序列中位于前方的k個(gè)元素DTheelementsarethekelementsatthebackoftheoriginalsequence.其中的元素是原序列中位于后方的k個(gè)元素C8、單選題Thesequence{2,7,13,5,3,19,17}isobtainedafteroneinsertionintheinsertionorder,andthesortedportionhas3elements.After2iterations,theresultis插入排序中的某一次插入后得到序列{2,7,13,5,3,19,17}，此時(shí)已排序部分有3個(gè)元素。又經(jīng)過2趟迭代后的結(jié)果是：A{2,3,5,7,13,17,19}B{2,3,5,7,13,19,17}C{2,5,7,3,13,19,17}D{2,3,5,13,7,17,19}B9、單選題Thereversenumberofasequence??isdefinedasthetotalnumberofreversedpairsinthesequence,andthetotalnumberofelementcomparisonsperformedbytheinsertionsortinthelistofsizenis:一個(gè)序列的逆序數(shù)??定義為該序列中的逆序?qū)倲?shù)，規(guī)模為n的列表中插入排序進(jìn)行的元素比較總次數(shù)為:10、單選題Alistoflengthnisequallydividedinton/ksegments.Eachsegmenthasalengthofk.Thereisnoreverseorderforelementsbetweendifferentsegments.Theworst-casecomplexityforinsertionsortonthislistis:長(zhǎng)度為n的列表，被等分為n/k段，每段長(zhǎng)度為k，不同段之間的元素不存在逆序。對(duì)該列表進(jìn)行插入排序的最壞時(shí)間復(fù)雜度為：第四章1、單選題ThestackSisinitiallyempty.Afterthefollowingoperations,theelementsfromthetopofthestacktothebottomofthestackare:棧S初始為空，進(jìn)行以下操作后從棧頂?shù)綏５椎脑匾来螢椋篠.push(5);S.push(4);S.pop();S.push(2);S.pop();S.pop();S.push(1)A5,4,2,1B1,2,4,5C1D5,4C1、填空題ThebinarynumberofhexadecimalnumberAFis:16進(jìn)制數(shù)AF的二進(jìn)制為：____101011111、單選題Whenanopenparenthesisisscanned:當(dāng)掃描到一個(gè)左括號(hào)時(shí)：APopupstack出棧BEnterthestack進(jìn)棧CSkipthischaracter跳過該字符DEndthealgorithm算法結(jié)束B1、單選題Is{3,1,2,4}astackshuffleof{1,2,3,4}?{3,1,2,4}是否是{1,2,3,4}的?；煜矗緼Yes是BNo不是B2、填空題Howmanydifferentstackshufflesarethereforasequenceoflength4長(zhǎng)度為4的序列共有多少個(gè)不同的棧混洗？141、單選題Whendoestheactualcalculationhappen?什么時(shí)候進(jìn)行實(shí)際的運(yùn)算？AEachtimeanewnumberisencountered每遇到一個(gè)新的操作數(shù)BEachencountersanewoperator每遇到一個(gè)新的操作符CThecurrentoperatorhasahigherprioritythantheoperatoronthetopofthestack當(dāng)前的操作符比棧頂?shù)牟僮鞣麅?yōu)先級(jí)高DThecurrentoperatorhasalowerprioritythantheoperatoronthetopofthestack當(dāng)前的操作符比棧頂?shù)牟僮鞣麅?yōu)先級(jí)低D1、單選題WhenevaluatinganinversePolishexpression,whendoesanactualcalculationoccur?逆波蘭表達(dá)式的求值算法中，什么時(shí)候進(jìn)行一次實(shí)際的運(yùn)算？AEachtimeanewoperandisencountered每遇到一個(gè)新的操作數(shù)BEachencountersanewoperator每遇到一個(gè)新的操作符CThecurrentoperatorhasahigherprioritythanthetopofthestack當(dāng)前操作符優(yōu)先級(jí)高于棧頂DThecurrentoperatorhasalowerprioritythanthetopofthestack當(dāng)前操作符優(yōu)先級(jí)低于棧頂B2、填空題ReversePolishExpressionof15+逆波蘭表達(dá)式15+63、單選題在本節(jié)中，我們學(xué)過了如何將中綴表達(dá)式轉(zhuǎn)化為逆波蘭表達(dá)式，那么反過來，思考一下如何將逆波蘭表達(dá)式還原為中綴表達(dá)式呢？試將下列逆波蘭表達(dá)式還原為中綴表達(dá)式：1

2

+

3

4

^

*A(1-2)*3^4B(1+2)*3^4C(1+2)^3*4D(1+3)*2^4B1、單選題Thestackisinitiallyemptyandgoesthroughthefollowingoperationsinsequence:棧初始為空，依次經(jīng)過以下操作：push(5);push(8);pop();push(5);top();push(1);push(3);pop();pop();push(2);Atthispointfromthetopofthestacktothebottomofthestack:此時(shí)從棧頂?shù)綏５滓来螢椋篈2,5,5B2,3,1C5,5,2D1,3,2A2、單選題下Thefollowingisavector-basedimplementationofthequeue(fortheinterfaceandimplementationofvectorsrefertoChapter2):面是隊(duì)列的一種基于向量的實(shí)現(xiàn)(向量的接口和實(shí)現(xiàn)可參考第2章)：Forthisqueueofsizen,theworst-casecomplexityofenqueue()anddequeue()is:對(duì)于規(guī)模為n的該隊(duì)列，enqueue()和dequeue()的最壞時(shí)間復(fù)雜度分別為：3、單選題Thefollowingissomekindofda