作業(yè)單元考核第一章緒論(上)（a）計算（a）計算--作業(yè)（b）計算模型--作業(yè)（c）大O記號--作業(yè)第一章緒論(下)（d）算法分析--作業(yè)（e）迭代與遞歸--作業(yè)（xc）動態(tài)規(guī)劃--作業(yè)本章測驗--作業(yè)第二章向量(上)第二章向量(下)（d3）有序向量：Fibonacci查找--作業(yè)（d4）有序向量：二分查找（改進(jìn)）--作業(yè)第二章向量(下)--（d5）有序向量：插值查找（e）起泡排序--作業(yè)（f）歸并排序--作業(yè)本章測驗--作業(yè)第三章列表（a）接口與實現(xiàn)--作業(yè)（b）無序列表--作業(yè)（c）有序列表--作業(yè)（d）選擇排序--作業(yè)（e）插入排序--作業(yè)本章測驗--作業(yè)第四章棧與隊列（a）棧接口與實現(xiàn)--作業(yè)第四章棧與隊列--（c1）棧應(yīng)用：進(jìn)制轉(zhuǎn)換（c2）棧應(yīng)用：括號匹配--作業(yè)第四章棧與隊列--（c3）棧應(yīng)用：棧混洗（c4）棧應(yīng)用：中綴表達(dá)式求值--作業(yè)第四章棧與隊列--（c5）棧應(yīng)用：逆波蘭表達(dá)式第四章棧與隊列--本章測驗第五章二叉樹（a）樹--作業(yè)第五章二叉樹--（b）樹的表示（c）二叉樹--作業(yè)（d）二叉樹實現(xiàn)--作業(yè)（e1）先序遍歷--作業(yè)第五章二叉樹--（e2）中序遍歷第五章二叉樹--（e4）層次遍歷（e5）重構(gòu)--作業(yè)本章測驗--作業(yè)第六章圖（a）概述--作業(yè)（b1）鄰接矩陣--作業(yè)（c）廣度優(yōu)先搜索--作業(yè)（d）深度優(yōu)先搜索--作業(yè)第六章圖--本章測驗第一章緒論(上)單選題

(1分)ForcomputingtheHailstonesequence(a.k.a.3n+1problem),the

Hailstone(n)

program視頻中提到的Hailstone問題（又名3n+1問題）中Hailstone(n)的計算程序是Awon'tterminateforanyvalueofn.對于所有的n都是無窮的Bwon'tterminateforsomevaluesofn(butwillterminateotherwise).對于部分n是無窮的CWedon'tknowifittermiatesforanyvalueofn.不能確定是否存在n，使程序無法終止Dalwaysterminateforanyvalueofn.對于所有的n都是有窮的

正確答案：C單選題

(1分)Whatistheforemostcriterionfora"goodalgorithm"?判斷一個算法是否是一個“好算法”，最重要的一條性質(zhì)是Acorrectness正確Brobustness健壯Creadability可讀Defficiency效率

正確答案：D單選題

(1分)WhichofthefollowingisNOTacomponentofaTuringmachine?以下哪項不是圖靈機(jī)的組成要件？AAtapeoffinitelength有限長的紙帶BAfinitealphabet有限的字母表CAfinitesetofstates有限種狀態(tài)DAheadforreadingandwriting讀寫頭

正確答案：A單選題

(1分)Trueoffalse:TheRAMmodelisequippedwithafiniteamountofstorage,whichdiffersfromtheTuringmachine.判斷正誤：RAM模型與圖靈機(jī)模型的區(qū)別在于圖靈機(jī)的存儲空間無限，而RAM的存儲空間有限。ATrue對BFalse錯

正確答案：B單選題

(1分)Whichoneofthefollowingisequivalentto

O(n3)

inthesenseofbig-O?(misnotaconstant)在大O記號的意義下，以下哪一項與

O(n3)

相等？(m不是常數(shù))AO(3n)BO(n3+2000n2+1000n)CO(n3+m)DO(2000n3+n4)

正確答案：B第一章緒論(下)

單選題

(1分)Whichofthefollowingequationsiswrong?下列對應(yīng)關(guān)系中錯誤的是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)

正確答案：D

單選題

(1分)x=n;y=1;while(x>=(y?1)?(y?1))y++;Thecomplexityoftheprogramaboveis以上程序的時間復(fù)雜度為AO(logn)BO(n)CO(nlogn)DO(n2)

正確答案：B單選題

(1分)Thenaivewayofcomputingfib(n)recursivelyleadstoatimecomplexityof直接用定義以遞歸的方式計算fib(n)的時間復(fù)雜度是：AΘ(n2)BO(2n)CΘ(2n)DO(n)

正確答案：B單選題

(1分)Witharegularcomputer,computingfib(100)naivelyusingrecursionwouldcost(noneedtoconsideroverflow).以現(xiàn)在普通計算機(jī)的速度，直接用定義以遞歸的方式計算fib(100)需要多少時間（不考慮溢出）:Alessthananhour一小時之內(nèi)Baboutaday大約一天Ctenyears十年Dmuchlongerthanyourlifetime.這輩子看不到啦

正確答案：D單選題

(1分)Forthestaircaseprobleminthevideolecture,howmanydifferentwayscangetyoufromthefirststeptotheeighth.對于視頻中的上臺階問題（從第一層開始），上到第8層共有多少種不同的走法：A21B13C17D34

正確答案：A單選題

(1分)Givennon-negativefunctionsf(n),g(h)andh(n),whichofthefollowingstatementsabout

O,Θ,Ω

iscorrect?

設(shè)函數(shù)f(n),g(n),h(n)非負(fù)，以下關(guān)于O,Θ,Ω記號的命題，正確的有：AIf

f(n)=O(h(n))

and

g(n)=O(h(n)),then

f(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)Dif

f(n)=O(h(n))

and

f(n)=Ω(h(n)),then

f(n)=Θ(h(n))

已知f(n)=O(h(n))且f(n)=Ω(h(n))，則f(n)=Θ(h(n))

正確答案：D單選題

(1分)Whichofthefollowingfunctionsgrowsfastestasymptotically?

下列函數(shù)漸進(jìn)增長速度最快的是：An2/3Bnlog2?(n)Clog2?(log2?(n))Dlog22?n

正確答案：B單選題

(1分)Giventhefollowingthreefunctions:以下是三個函數(shù)：Theirtimecomplexitiesare:它們的時間復(fù)雜度分別為：AΘ(n),Θ(n2),Θ(n)BΘ(nlog2?(n)),Θ(nlog2?(n)),Θ(n)CΘ(n),Θ(n2),Θ(nlog2?(n))DΘ(n2),Θ(n),Θ(nlog2?(n))

正確答案：C單選題

(1分)ThefollowingrecursivefunctionisforreversingarrayA[lo,hi]

以下遞歸函數(shù)實現(xiàn)數(shù)組A[lo,hi]的倒置：Whatisthetimecomplexityofreverse(A,0,n-1),forreversinganarrayoflengthn?

調(diào)用reverse(A,0,n-1)以倒置長度為n的數(shù)組，算法的時間復(fù)雜度為：AΘ(n)BΘ(nlog2?(n))CΘ(n2)DΘ(log2?(n))

正確答案：A單選題

(1分)V={11,23,19,7,17,5,3,13,2,29}WhensortingVusingbubblesort,whatisthevalueofV[8]aftertworoundsofsweep&swap?對V進(jìn)行起泡排序，兩趟掃描交換后V[8]=A17B19C23D29

正確答案：C第二章向量(上)

單選題

(1分)Whichofthefollowingoptionsiscorrect:下列說法中正確的是：ATheabstractdatatypeisanadvanceddatatypeprovidedbyC++forimplementingdatastructures.抽象數(shù)據(jù)類型是C++提供的一種高級的數(shù)據(jù)類型，用于實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。BTheabstractdatatypedetermineshowdataisstored.抽象數(shù)據(jù)類型決定了數(shù)據(jù)的存儲方式。CThesameabstractdatatypemaybeimplementedusingmultipledatastructures.同一個抽象數(shù)據(jù)類型可能用多種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。DDatastructureisanabstractdatatype.數(shù)據(jù)結(jié)構(gòu)即抽象數(shù)據(jù)類型。

正確答案：C

單選題

(1分)Onaninitiallyemptyvector,what'stheresultofexecutinginsert(0,2),insert(1,6),put(0,1),remove(1)andinsert(0,7):在一個初始為空的向量上依次執(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}

正確答案：C

單選題

(1分)Thefollowingcodeisavariantofthevectorcopycodewiththesamesemantics.Thespaceshouldbefilledwith:以下代碼是向量復(fù)制代碼的一個變體且語義與其相同，空格處應(yīng)填入的內(nèi)容為：A--hiBhi--C++loDlo++

正確答案：A單選題

(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的引用，使用它是因為返回值可以作為左值

正確答案：D單選題

(1分)WhathappensiftheFORloopintheinsert()functionchangestothefollowingform？for(inti=r;i<_size;i++)_elem[i+1]=_elem[i];ANoproblem,justchangeitfromfronttoback沒有問題，只是改為從前向后移動罷了BOverwriteallelementsintheoriginalvectorwithrankgreaterthanr會覆蓋原向量中秩大于r的所有元素COverwriteallelementsintheoriginalvectorwithranklessthanr會覆蓋原向量中秩小于r的所有元素DWillcausevectorexpansionfailure會引起向量擴(kuò)容失敗

正確答案：B單選題

(1分)Whythesuffixofthedeletedelementismovedfromfronttobackintheintervaldeletionalgorithmremove(lo,hi)?為什么區(qū)間刪除算法remove(lo,hi)中要從前向后移動被刪除元素的后綴？AThisisacustomarypractice,whichinturnisalsofeasible這是一個約定俗成的習(xí)慣，反過來也可行BOtherwiseitmaycoversomeelements否則可能會覆蓋部分元素COtherwiseitmayfailtodeleteallelementswithintheinterval[lo,hi)否則可能未能刪除區(qū)間[lo,hi)內(nèi)所有的元素DOtherwiseitmayleadtoinefficiency否則可能導(dǎo)致效率低下

正確答案：B單選題

(1分)Forthededuplicate()algorithm,theworst-casetimecomplexityforthevectorscalenis:對于deduplicate()算法，向量規(guī)模為n時的最壞時間復(fù)雜度為：AΘ(n2)BΘ(nlog2n)CΘ(n)DΘ(1)

正確答案：A單選題

(1分)Foravectorofsizen,thereturnvalueoffind()onasearchfailureis:對于規(guī)模為n的向量，查找失敗時find()的返回值是：A-1B0CnDnan

正確答案：A單選題

(1分)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);

正確答案：D單選題

(1分)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)

正確答案：A單選題

(1分)WhichofthefollowingexpressionsisequivalenttoRankmi=(lo+hi)>>1?(loandhiarenon-negative)Rankmi=(lo+hi)>>1等效于下列哪個表達(dá)式?（lo和hi非負(fù)）ARankmi=(lo+hi)\2BRankmi=(lo+hi)%2CRankmi=(lo+hi)/2DRankmi=(double)(lo+hi)/2

正確答案：C單選題

(1分)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)行多少次比較？A4B5C6D7

正確答案：B單選題

(1分)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/2

正確答案：A第二章向量(下)單選題

(1分)WhatisthedifferencebetweenthefibSearch()algorithmandbinSearch()algorithm?fibSearch()算法與binSearch()有什么區(qū)別？ATheirreturnvalueisdifferent二者的返回值不同BTheformerisarecursivealgorithm,andthelatterisaniterativealgorithm前者是遞歸算法，后者是迭代算法CTherearedifferentwaystochoosetheaxispointmi二者選取軸點mi的方式不同DTheformer'sasymptotictimecomplexityislowerthanthelatter,sotheformerismoreefficient前者的漸進(jìn)時間復(fù)雜度低于后者，故前者效率更高

正確答案：C單選題

(1分)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

正確答案：D

單選題

(1分)WhyisthesearchprocessforbinSearch()versionAnotbalanced?為什么說binSearch()版本A的查找過程并不平衡?ABecausetheleftandrightbrancheshavedifferentsubvectorsizes因為向左、向右兩個分支的子向量規(guī)模不同BBecausethenumberofcomparisonsrequiredfortheleftandrightbranchesisnotequal因為向左、向右兩個分支所需要的比較次數(shù)不相等CBecausetheFibonaccisearchismorebalancedthanthebinarysearch因為Fibonacci查找比二分查找更平衡DBecausetheprobabilitythatthekeyisintheleftsubvectorisgreaterthantheprobabilitythatitisintheright因為關(guān)鍵碼位于左子向量中的概率比位于右側(cè)的概率大

ABCD正確答案：B單選題

(1分)Foravectorofsizen,theoptimaltimecomplexityforbinarysearchversionsAandBis:對于規(guī)模為n的向量，二分查找版本A和B的最優(yōu)時間復(fù)雜度分別為：AΘ(n2),Θ(n)BΘ(nlog2n),Θ(n)CΘ(log2n),Θ(log2n)DΘ(1),Θ(log2n)

正確答案：D單選題

(1分)Forthesearch()interface,whatwearegoingtoreturnwhenthereismorethanonetargetelementinthevector:對于search()接口，我們約定當(dāng)向量中存在多個目標(biāo)元素時返回其中：ARankmaximun秩最大者BRankminimum秩最小者CRankintermediate秩中間者DRandomlyreturnoneofthem隨機(jī)返回其中一個即可

正確答案：A單選題

(1分)ForbinarysearchversionC,whatisthenextsearchrangewhene<V[mi]isnotestablished:對于二分查找版本C，當(dāng)e<V[mi]不成立時下一步的查找范圍是：AV[lo,mi)BV[mi,hi)CV[mi,hi]DV(mi,hi)

正確答案：D單選題(1分)ForbinarysearchversionC,whenthelengthofthesearchintervalisreducedto0,V[lo]is:對于二分查找版本C，當(dāng)查找區(qū)間的長度縮小為0時，V[lo]是：A、B、C、D、正確答案：C單選題

(1分)Ifthedistributionofelementsinan(ordered)vectorsatisfiesanindependentuniformdistribution(beforesorting),theaveragetimecomplexityoftheinterpolationsearchis:如果（有序）向量中元素的分布滿足獨立均勻分布（排序前），插值查找的平均時間復(fù)雜度為：AO(n)BO(logn)CO(loglogn)DO(1)

正確答案：C

填空題

(1分)Searchingforsearchelements7withinterpolationinthevectorV={2,3,5,7,11,13,17,19,23}

在向量V={2,3,5,7,11,13,17,19,23}中用插值查找搜索元素7Guessthepivotpointmi

猜測的軸點mi____

1正確答案:["1"]單選題

(1分)V={7,2,3,11,17,5,19,13}AftertwoscanexchangeofV,V[6]=V={7,2,3,11,17,5,19,13}，對V進(jìn)行兩次掃描交換后V[6]=A11B13C17D19

正確答案：C單選題

(1分)Whichsituationwilltheimprovedblisteringorderwillendprematurely?經(jīng)改進(jìn)的起泡排序在什么情況下會提前結(jié)束？ACompletealln-1scans完成全部n-1趟掃描交換BThenumberofscanconversionscompleted=Thenumberofscanswitchingparametersfortheactualelementexchange+1完成的掃描交換趟數(shù)=實際發(fā)生元素交換的掃描交換趟數(shù)+1CThenumberofscanconversionscompleted=Thenumberofscanswitchingsthatactuallytookplaceforelementexchange完成的掃描交換趟數(shù)=實際發(fā)生元素交換的掃描交換趟數(shù)DComplete(n-1)/2scanexchange完成(n-1)/2趟掃描交換

正確答案：B單選題

(1分)TrythefollowingalgorithmtosortV={19,17,23}:試用以下算法對V={19,17,23}排序：1.Sortbyunitsatfirst1.先按個位排序2.Onthebasisofthepreviousstep,sortagainbytens2.在上一步基礎(chǔ)上，再按十位排序Isthisalgorithmcorrect?這個算法的是否正確？ACertainlycorrect一定正確BCertainlyincorrect一定不正確CIfthesortingalgorithmusedinstep2isstable,thencorrect若第2步用的排序算法是穩(wěn)定的，則正確DIfthesortingalgorithmusedinstep1isstable,thencorrect若第1步用的排序算法是穩(wěn)定的，則正確

正確答案：C單選題

(1分)Whatisthesolutiontotherecurrenceformula

T(n)=2T(n2)+O(n)?Whichofthe

O(n)

itemsrepresent?歸并排序時間復(fù)雜度的遞推公式T(n)=2T(n2)+O(n)的解是什么？其中O(n)項代表什么？AO(n),timeformergingtwosortedsubvectors

O(n),歸并兩個已排序子向量的時間BO(nlog2n),thetimeforsortingtwosub-vectorsseparatelyO(nlog2n),對兩個子向量分別進(jìn)行排序的時間CO(n2),thetimeforsortingtwosub-vectorsseparatelyO(n2),對兩個子向量分別進(jìn)行排序的時間DO(nlog2n),timeformergingtwosortedsubvectorsO(nlog2n),歸并兩個已排序子向量的時間

正確答案：D單選題

(1分)Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:對{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與13

正確答案：A單選題

(1分)Forvectorsofsizen,theoptimalandworst-casetimecomplexityformergesortingis:對于規(guī)模為n的向量，歸并排序的最優(yōu)、最壞時間復(fù)雜度分別為：AΘ(n),Θ(nlog2n)BΘ(nlog2n),Θ(nlog2n)CΘ(nlog2n),Θ(n2)DΘ(n),Θ(n2)

正確答案：B單選題

(1分)Byusingtwoexpansionstrategies,oneforeachadditionalfixedmemoryspaceandonefordoubleupmemoryspace,theamortizedtimecomplexityofinsertinganelementofvectorofsizenis:分別采用每次追加固定內(nèi)存空間和每次內(nèi)存空間翻倍兩種擴(kuò)容策略，在規(guī)模為n的向量中插入一個元素的分?jǐn)倳r間復(fù)雜度為：AO(n),O(1)BO(n),O(n)CO(1),O(1)DO(n),O(log2(n))

正確答案：A單選題

(1分)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);

正確答案：D單選題

(1分)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，整個過程中與目標(biāo)元素發(fā)生過比較的元素依次為：A11,17,13B7,3,17C13,11,17D5,7,11

正確答案：A單選題

(1分)Thebinarysearchfor"versionC"isextractedasfollows:二分查找“版本C”摘錄如下：WhentherearemultipleelementstobesearchedinthearrayA,thereturnvalueofthefunction:當(dāng)數(shù)組A中有多個待查找元素e時，函數(shù)的返回值為：AReturntheelementwhoserankissmallest返回秩最小者BReturntheelementwhoserankisbiggest返回秩最大者CReturntheelementwhoserankisinthemiddle返回秩位于正中間者DRandomlyreturnoneofthem隨機(jī)返回其中一個

正確答案：B單選題

(1分)Thefollowingfunctionisarecursiveversionofthebinarysearch:以下函數(shù)是二分查找的遞歸版：Foravectorofsizen,thetimeandspacecomplexityoftherecursiveversionandtheiteratedversionlearnedinclassare:對于規(guī)模為n的向量，該遞歸版的時間、空間復(fù)雜度和課堂上所學(xué)的迭代版的時間、空間復(fù)雜度分別是：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)

正確答案：D單選題

(1分)ThevectorV={1,2,3,4,5,6,7},usestheFibonaccisearchtofindthetargetelement1inV,theelementsselectedasthepivotmiare:向量V={1,2,3,4,5,6,7}，在V中用斐波那契查找查找目標(biāo)元素1，被選取為軸點mi的元素依次是：A4,3,2,1B4,2,1C5,2,1D5,3,2,1

正確答案：D單選題

(1分)Thetwo-waymergerof{2,5,7}and{3,11,13}isperformedbycomparing:對{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與13

正確答案：A單選題

(1分)Inanyscanningexchangeofbubblingordering,ifthelastexchangeistoswapelementsX>YforY<X,then:在起泡排序的任何一趟掃描交換過程中，若最后一次交換是將元素X>Y交換為Y<X，則此后：AXandYmusthavebeeninplaceX和Y必然都已經(jīng)就位BXmustbeinplacewhileYisnotnecessarilyX必然就位，而Y未必CYmustbeinplacewhileXisnotnecessarilyX未必就位，而Y必然DNeitherXnorYarenecessarilyinplaceX和Y都未必已經(jīng)就位

正確答案：B單選題

(1分)Onaninitiallyemptyvector,what'stheanswerafterexecuting:insert(0,2),insert(1,6),put(0,1),remove(1),insert(0,7)在一個初始為空的向量上依次執(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}

正確答案：C單選題

(1分)Thefollowingcodeimplementsintervaldeletionofvectorsbycontinuouslydeletingindividualelements:以下代碼通過不斷刪除單個元素實現(xiàn)向量的區(qū)間刪除：Theoverloadedfunctionremove(Rankr)completestheoperationofdeletingasingleelement,anditstimecomplexityisproportionaltothenumberofsucceedingelementsofthedeletedelement.Forvectorsofsizen,theworst-casecomplexityofthisintervaldeletionalgorithmis:其中重載函數(shù)remove(Rankr)完成刪除單個元素的操作，其時間復(fù)雜度正比于被刪除元素的后繼個數(shù)。對于規(guī)模為n的向量，該區(qū)間刪除算法的最壞時間復(fù)雜度為：AO(n)BO(nlog2(n))CO(n2)DO(log2(n))

正確答案：C第三章列表單選題

(1分)Whichofthefollowingoptionsaboutrankoflistnodeisincorrect下列關(guān)于列表的秩的說法中不正確的是AThephysicaladdressofalistnodecanbedeterminedbyitsrank列表節(jié)點的秩與物理地址有明確的對應(yīng)關(guān)系BThecostofmaintainingrankoflistnodeishigh列表的秩具有很高的維護(hù)成本CInalist,thecostofrank-basedaccessishigh在列表中循秩訪問的成本較高DInalist,location-basedaccessisfasterthanrank-basedaccess在列表中循位置訪問會比循秩訪問更快

正確答案：A單選題

(1分)Whichofthefollowingoptionsaboutdefinedinterfaceisincorrect?下列關(guān)于我們定義的接口的描述中，哪一條是錯誤的？AForthenodesinthelist,wecantaketheirpredecessorandsuccessorrespectivelybycallingthepred()andsucc()interfaces.對于列表中的節(jié)點，我們可以通過調(diào)用pred()和succ()接口分別取其前驅(qū)和后繼。BOneoftheimportantdifferencesbetweenfind(e)andsearch(e)inlistinterfaceisthatfind(e)issuitableforalllists,andsearch(e)isappliedtoorderedlists.對于列表接口中的find(e)與search(e)，其中一個重要區(qū)別在于find普適于所有列表，而search適用于有序列表。CIfthelengthofthe'visiblelist'partisn,theranksofthe'head',first,last,and'trail'nodesare-1,0,n,n+1respectively.如果一個列表的visiblelist部分長度為n，則頭、首、末、尾節(jié)點的秩分別為-1,0,n,n+1DInconstructingthelist,weneedtoconstructsentrynodesfirst.在構(gòu)造列表時，我們需要首先構(gòu)造哨兵節(jié)點。

正確答案：C單選題

(1分)IfyouchangeinsertAsPred()tothefollowingfunction,theresultis:若將insertAsPred()改為以下函數(shù)，其結(jié)果是：ACaninsertnodesnormally.能正常插入節(jié)點BCannotinsertnode,originallistremainsunchanged.不能插入節(jié)點，原列表仍然保持不變CCannotinsertnode,thestructureoftheoriginallistisdestroyed.不能插入節(jié)點，原列表的結(jié)構(gòu)被破壞DCaninsertanoderelatedtothestructureofthelistatthetime.能否插入節(jié)點與當(dāng)時列表的結(jié)構(gòu)有關(guān)

正確答案：C單選題

(1分)Wecanconsiderspeedingupcall-by-rankby:If

r>n2,thenwecancontinuetoaccesspred()fromthetailandeventuallymovebackwardstofindthenodewithrankr.我們可以考慮通過如下方式加快循秩訪問的速度：如果r>n2，則我們可以從尾部哨兵開始不斷訪問pred()，最終從后向前地找到秩為r的節(jié)點。Whatkindofargumentiswrongaboutthisoptimization?關(guān)于這種優(yōu)化，哪種說法是錯誤的？AFromtheperspectiveofexpectation,ifrisanequalprobabilitydistributionin

[0,n),thenumberofvisitstothelistelementcanbereducedbyhalfduringthecall-by-rank.從期望的角度看，r在[0,n)中是等概率分布的話，那么在循秩訪問的過程中，對列表元素的訪問次數(shù)可以節(jié)約一半。BTheslowestaccesstimeoforiginmethodwasmostlyseenat

r≈n,whiletheslowestaccesstimeafterimprovementwasgenerallyseenat

r≈n/2.原有方法訪問最慢的情形大致出現(xiàn)在r≈n時，而改進(jìn)后的方法訪問最慢的情形大致出現(xiàn)在r≈n/2時。CWhentheaccesstothelistisconcentratedattheendofthelist,theeffectofthisoptimizationstrategyismostpronounced.當(dāng)對于列表的訪問集中在列表尾部時，這種優(yōu)化策略的效果最明顯。DThroughthisoptimization,wecanmakethecall-by-ranktimecomplexitybetterthanO(n).通過這樣的優(yōu)化，我們可以使循秩訪問時間復(fù)雜度優(yōu)于O(n)。

正確答案：D

單選題

(1分)Theprocessoforderedlistuniquealgorithmis:有序列表唯一化算法的過程是：AKeeponlythefirstelementofeachintervalofequalelements.只保留每個相等元素區(qū)間的第一個元素BEachtimeanelementisencountered,findbackwardanddeletethesameone.每遇到一個元素，向后查找并刪除與之雷同者CEverytimeanelementisencountered,lookaheadanddeletethesameone.每遇到一個元素，向前查找并刪除與之雷同者DCheck(n|2)pairsofdifferentelements.Foreachpairofelements,iftheyareidentical,arbitrarilydeleteoneofthem.檢查(n|2)個不同的元素對，對于每一對元素，若雷同則任意刪除其一

正確答案：A

單選題

(1分)Canabinarysearchbeusedinanorderedlisttoreducethetimecomplexityto

Θ(log2n)?能否在有序列表中用二分查找使得時間復(fù)雜度降為Θ(log2n)？AYes能BNo,becausetheamortizedtimecomplexityoflistexpansionisnot

Θ(1)不能，因為列表擴(kuò)容的分?jǐn)倧?fù)雜度不是Θ(1)CNo,becausethelistcannotbeefficientlyaccessedbyrank不能，因為列表不能高效地循秩訪問DYes,becausethetimecomplexityofthelistdeletenodeis

Θ(1)能，因為列表刪除節(jié)點的時間復(fù)雜度為Θ(1)

正確答案：C單選題

(1分)V={11,5,7,13,2,3},sortingVbyselectionsort,thelargestelementselectedastheunsortedsubvectorisV={11,5,7,13,2,3}，對V進(jìn)行選擇排序，被選為未排序子向量中最大的元素依次為：A11,5,7,2,3B13,7,11,2,5C13,11,7,5,3D2,11,13,5,7

正確答案：C單選題

(1分)Aboutvectorandthefollowinglist,whichiswrong:下列關(guān)于向量和列表的說法錯誤的是：AVectorsusuallyoccupycontinuousspaceinmemory,butthelistisusuallynotthecase向量通常在內(nèi)存中占據(jù)連續(xù)的空間，列表則通常不是如此BFindinginorderedvectorsisprogressivelyfasterthanfindinginorderedlists在有序向量中查找漸進(jìn)地比在有序列表中查找快CThetimecomplexityofmergingsortinginvectoris

O(nlog2?(n)),andinlistis

Ω(n2)向量歸并排序的時間復(fù)雜度是O(nlog2?(n))，而列表為Ω(n2)DDeletingsinglenodeinListprogressivelyfasterthanthatinvectors.列表刪除單個節(jié)點漸進(jìn)地比向量刪除單個元素快

正確答案：C單選題

(1分)Inordertoinsertanewnodeinthelistasadirectprecursortop,therearefourrelatedstatements為了在列表中插入一個新節(jié)點node作為p的直接前驅(qū)，有四個相關(guān)的語句①p->pred->succ=node②node->pred=p->pred③node->succ=p④p->pred=nodeThecorrectexecutionorderoftheabovestatementis:上述語句執(zhí)行順序正確的是：A③②④①B③②①④C①④③②D④②③①

正確答案：B單選題

(1分)Forabi-directionalandunidirectionallistofnnodes,theworst-casecomplexityoflocatinganodep'sdirectprecursoris:對于n個節(jié)點的雙向、單向列表，定位某節(jié)點p直接前驅(qū)的最壞時間復(fù)雜度分別為：AO(1),O(1)BO(1),O(n)CO(n),O(1)DO(n),O(n)

正確答案：B單選題

(1分)Thetimecomplexityoffindinganelementinanorderedlistis在有序列表中查找一個元素的時間復(fù)雜度是：AΩ(nlog2?(n))BΩ(n)CO(log2?(n))DO(1)

正確答案：B單選題

(1分)Selectingthelist{11,5,7,13,2,3}.EachtimetheelementsareselectedasthelargestelementintheunsortedsublistinselectMax()對列表{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,7

正確答案：C單選題

(1分)WhichimplementationoftheselectSort()algorithmisstableselectSort()算法的哪種實現(xiàn)是穩(wěn)定的：AEachtimemovesthesmallestelementtothefront.Formultipleequalminimumelements,selecttheonewiththesmallestposition.每一趟將最小元素移到前方，對于多個相等的最小元素，選取其中位置最靠前者。BEachtimemovesthebiggestelementtothefront.Formultipleequalmaximumelements,selecttheonewiththesmallestposition.每一趟將最大元素移到后方，對于多個相等的最大元素，選取其中位置最靠前者。CEachtimemovesthesmallestelementtothefront.Formultipleequalminimumelements,selecttheonewiththelargestposition.每一趟將最小元素移到前方，對于多個相等的最小元素，選取其中位置最靠后者。DTheaboveimplementationsareallstable以上實現(xiàn)皆穩(wěn)定。

正確答案：A單選題

(1分)Fororderedsubsequences(settheirlengthtok)duringinsertionsorting.對于插入排序過程中的已排序子序列（設(shè)其長度為k）：ATheelementsarethesmallestkelementsintheentiresequence其中的元素是整個序列中最小的k個元素BTheelementsarethebiggestkelementsintheentiresequence其中的元素是整個序列中最大的k個元素CTheelementsarethekelementsatthefrontoftheoriginalsequence.其中的元素是原序列中位于前方的k個元素DTheelementsarethekelementsatthebackoftheoriginalsequence.其中的元素是原序列中位于后方的k個元素

正確答案：C單選題

(1分)Thesequence{2,7,13,5,3,19,17}isobtainedafteroneinsertionintheinsertionorder,andthesortedportionhas3elements.After2iterations,theresultis插入排序中的某一次插入后得到序列{2,7,13,5,3,19,17}，此時已排序部分有3個元素。又經(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}

正確答案：B單選題

(1分)Thereversenumberofasequence

τ

isdefinedasthetotalnumberofreversedpairsinthesequence,andthetotalnumberofelementcomparisonsperformedbytheinsertionsortinthelistofsizenis:一個序列的逆序數(shù)τ定義為該序列中的逆序?qū)倲?shù)，規(guī)模為n的列表中插入排序進(jìn)行的元素比較總次數(shù)為:AO(n+τlog2?(τ))BO(n+τ)CO(n2+log2?(τ))DO(τ)

正確答案：B單選題

(1分)Alistoflengthnisequallydividedinton/ksegments.Eachsegmenthasalengthofk.Thereisnoreverseorderforelementsbetweendifferentsegments.Theworst-casecomplexityforinsertionsortonthislistis:長度為n的列表，被等分為n/k段，每段長度為k，不同段之間的元素不存在逆序。對該列表進(jìn)行插入排序的最壞時間復(fù)雜度為：AO(n2)BO(nk)CO(n2/k)DO(n2k)

正確答案：B第四章棧與隊列單選題

(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,4

正確答案：C填空題

(1分)ThebinarynumberofhexadecimalnumberAFis:

16進(jìn)制數(shù)AF的二進(jìn)制為：____

1正確答案:["10101111"]單選題

(1分)Whenanopenparenthesisisscanned:當(dāng)掃描到一個左括號時：APopupstack出棧BEnterthestack進(jìn)棧CSkipthischaracter跳過該字符DEndthealgorithm算法結(jié)束

ABCD正確答案：B單選題

(1分)Is{3,1,2,4}astackshuffleof{1,2,3,4}?{3,1,2,4}是否是{1,2,3,4}的?；煜矗緼Yes是BNo不是

正確答案：B

填空題

(1分)Howmanydifferentstackshufflesarethereforasequenceoflength4

長度為4的序列共有多少個不同的棧混洗？

____

1正確答案:["14"]單選題

(1分)Whendoestheactualcalculationhappen?什么時候進(jìn)行實際的運算？AEachtimeanewnumberisencountered每遇到一個新的操作數(shù)BEachencountersanewoperator每遇到一個新的操作符CThecurrentoperatorhasahigherprioritythantheoperatoronthetopofthestack當(dāng)前的操作符比棧頂?shù)牟僮鞣麅?yōu)先級高DThecurrentoperatorhasalowerprioritythantheoperatoronthetopofthestack當(dāng)前的操作符比棧頂?shù)牟僮鞣麅?yōu)先級低

正確答案：D單選題

(1分)WhenevaluatinganinversePolishexpression,whendoesanactualcalculationoccur?逆波蘭表達(dá)式的求值算法中，什么時候進(jìn)行一次實際的運算？AEachtimeanewoperandisencountered每遇到一個新的操作數(shù)BEachencountersanewoperator每遇到一個新的操作符CThecurrentoperatorhasahigherprioritythanthetopofthestack當(dāng)前操作符優(yōu)先級高于棧頂DThecurrentoperatorhasalowerprioritytha