算法設(shè)計(jì)與分析-青島大學(xué)中國(guó)大學(xué)mooc課后章節(jié)答案期末考試題庫(kù)2023年

算法設(shè)計(jì)與分析_青島大學(xué)中國(guó)大學(xué)mooc課后章節(jié)答案期末考試題庫(kù)2023年研究NPC問(wèn)題的意義，一旦一個(gè)NPC問(wèn)題找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法，那么所有的NPC問(wèn)題都找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法。

參考答案:

正確

NP問(wèn)題是確定性算法不能在多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問(wèn)題

參考答案:

錯(cuò)誤

下面哪個(gè)問(wèn)題不是NPC問(wèn)題

參考答案:

最小生成樹(shù)問(wèn)題

最優(yōu)分解問(wèn)題：一個(gè)正整數(shù)分解為若干互不相同的自然數(shù)的和，使其乘積最大。使用貪心算法求將22這個(gè)數(shù)最優(yōu)分解后，取得的最大乘積是多少？

參考答案:

1008

我國(guó)的貨幣單位是100元，50元，20元、10元、5元、2元、1元。有人到超市買了32元的商品，交給收銀員100元，問(wèn)收銀員最少需要幾張貨幣就能完成找零錢(qián)？

參考答案:

5

貪心算法是以自底向上的方式構(gòu)造問(wèn)題的最優(yōu)解

參考答案:

錯(cuò)誤

貪心算法中常包含排序算法，也就是排序是貪心算法的伴隨算法，有人這樣解釋其原因：貪心算法是根據(jù)貪心策略一步一步地選擇去構(gòu)造問(wèn)題的解，排序就是按照要選擇的順序排列好，選擇時(shí)只需按照排好的順序選擇就可以了。主要目的就是方便選擇。該說(shuō)法是否正確？

參考答案:

正確

n皇后問(wèn)題是可用回溯法解決的問(wèn)題。下面描述不正確的是？

參考答案:

兩種不同解空間樹(shù)的算法效率比較，排列樹(shù)的時(shí)間耗費(fèi)高于n叉樹(shù)

下面描述不正確的是？

參考答案:

當(dāng)解空間樹(shù)是子集樹(shù)時(shí)，約束函數(shù)對(duì)0分支剪枝，限界函數(shù)對(duì)1分支剪枝。

下面關(guān)于回溯法的描述中，不正確的是哪個(gè)?

參考答案:

回溯法，從解空間樹(shù)的根結(jié)點(diǎn)開(kāi)始，當(dāng)搜索至葉子結(jié)點(diǎn)時(shí)，就找到了問(wèn)題的解，算法結(jié)束。

分治法解決問(wèn)題分為三步走，即分、治、合。下面列出了幾種操作，請(qǐng)按分、治、合順序選擇正確的表述。（1）將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解，（2）將問(wèn)題分解為各自獨(dú)立的多個(gè)子問(wèn)題，（3）將多個(gè)子問(wèn)題合并為原問(wèn)題。（4）求各個(gè)子問(wèn)題的解，（5）將問(wèn)題分解為可重復(fù)的多個(gè)子問(wèn)題。

參考答案:

(2)(4)(1)

一個(gè)問(wèn)題，可能有多個(gè)最優(yōu)解，但是使用貪心算法最多只能找到一個(gè)最優(yōu)解。

參考答案:

正確

符號(hào)三角形問(wèn)題，其解空間樹(shù)是哪種？

參考答案:

n叉樹(shù)（這里n=2）

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，給定V中的一個(gè)頂點(diǎn)A，稱為源，求從源頂點(diǎn)A出發(fā)到其他各頂點(diǎn)的最短路徑長(zhǎng)度稱為單源最短路徑長(zhǎng)度問(wèn)題。關(guān)于單源最短路徑問(wèn)題的Dijkstra算法，下面哪些描述是正確的？

參考答案:

每次選擇加入S集合的頂點(diǎn)是從A頂點(diǎn)出發(fā)的最短路徑長(zhǎng)度已知的頂點(diǎn)，也就是V-S集合中最短特殊路徑長(zhǎng)度最小的頂點(diǎn)，通常算法中用dist[]數(shù)組記錄各頂點(diǎn)的最短特殊路徑長(zhǎng)度。_設(shè)定一個(gè)頂點(diǎn)集合S，初始時(shí)，S={A}，每次從V-S中選擇頂點(diǎn)加入S，直到全部加入，算法結(jié)束。_每次選擇一個(gè)頂點(diǎn)加入S集合后，都要檢查是否需要更新dist[]數(shù)組元素的值

哈夫曼編碼樹(shù)是用貪心算法解決的典型問(wèn)題，分析該算法，回答如下問(wèn)題，假定有n（n>1)個(gè)字符生成的編碼樹(shù)，問(wèn)編碼樹(shù)中的結(jié)點(diǎn)總數(shù)是多少？可能的最長(zhǎng)的字符編碼是多少位？

參考答案:

2n-1個(gè)結(jié)點(diǎn)

n-1位編碼

某中學(xué)有一個(gè)開(kāi)水房，只有一個(gè)供熱水龍頭，課間時(shí)，會(huì)有很多同學(xué)去排隊(duì)打開(kāi)水，同學(xué)們的水瓶大小不一，每個(gè)同學(xué)打水時(shí)都會(huì)將自己的水瓶裝滿。管理開(kāi)水房的師傅是個(gè)聰明人，他想到了一個(gè)排隊(duì)方案，也就是同學(xué)們按照他給出的排隊(duì)方法，可以使同學(xué)們的平均等待時(shí)間最短。你分析一下，給出這個(gè)排隊(duì)的方法，假定有n個(gè)人，第i個(gè)同學(xué)打水所需要的時(shí)間為ti，并給出平均等待時(shí)間的計(jì)算公式。（注意：第i個(gè)同學(xué)的等待時(shí)間包含前i-1個(gè)的打水時(shí)間和+自己打水的時(shí)間ti）

參考答案:

按照打水時(shí)間從小到大排隊(duì)，假定排隊(duì)后第i個(gè)人的打水時(shí)間是ti,

平均等待時(shí)間

T=∑(n-i+1)ti/n

1<=i<=n

一個(gè)n位的10進(jìn)制正整數(shù)，使得刪除k位（k

參考答案:

每次從整數(shù)中找包含最高位的從左至右的一個(gè)最長(zhǎng)的非遞減序列，將該序列的最后一位刪除

一個(gè)問(wèn)題，針對(duì)某個(gè)貪心策略，可通過(guò)找反例的方法快速判斷出其使用貪心算法不能構(gòu)造出最優(yōu)解。下面是關(guān)于0-1背包問(wèn)題，貪心策略是優(yōu)先選擇單位重量?jī)r(jià)值大的物品裝入背包，有二個(gè)同學(xué)分別找到一個(gè)反例，證明貪心算法不能構(gòu)造出0-1背包問(wèn)題的最優(yōu)解。（1）背包容量4，三個(gè)物品的重量和價(jià)值（wi，vi）:（2，4）,（2，3）,（2，2）（2）背包容量5，三個(gè)物品的重量和價(jià)值（wi，vi）:（1，2）,（2，3）,（4，4）分析判定哪個(gè)反例是對(duì)的，哪個(gè)反例是錯(cuò)的，從如下選項(xiàng)中找到你的答案。

參考答案:

（1）錯(cuò)（2）對(duì)

下面是一個(gè)布線問(wèn)題,S表示布線的起點(diǎn)，O表示布線的終點(diǎn)，假定布線只能垂直、或水平布線，從一個(gè)點(diǎn)按照上、下、左、右的優(yōu)先順序可往四個(gè)方向布線，“#"是障礙不能通過(guò)。已知從一個(gè)位置向其上、下、左、右四個(gè)相鄰位置布線的線路長(zhǎng)度為1。使用隊(duì)列式分支限界法解決該問(wèn)題，問(wèn)從S到O的最短布線長(zhǎng)度？###S##o#######

參考答案:

8

給定n個(gè)可能含有重復(fù)的元素存放于x[1:n]，輸出去掉重復(fù)的全排列，這里swap是實(shí)現(xiàn)兩個(gè)變量值的交換，下面是算法描述注意：紅色代碼部分【1】【2】【3】位置有代碼缺失。voidbacktrack(intt){if(t>n){for(inti=1;i<=n;i++)printf("%d",x[i]);printf("\n");}else{for(inti=t;i<=n;i++){intok=1;for(intj=【1】;j<【2】;j++)if(x[j]==x[i])｛【3】;break；｝if(ok){swap(x[t],x[i]);backtrack(t+1);swap(x[t],x[i]);}}}}上面的算法中，紅色代碼部分【1】【2】【3】位置代碼缺失，請(qǐng)從如下選項(xiàng)中找到合適的代碼。

參考答案:

【1】t，【2】

i，【3】

ok=0

0-1背包問(wèn)題的回溯算法，下面的解釋不正確的是

參考答案:

右（0）分支的剪枝：已裝入背包內(nèi)的物品價(jià)值和+剩余物品裝剩余背包容量所能獲得的最大價(jià)值（物品可分割，即用背包問(wèn)題的貪心算法求得的最大價(jià)值）>當(dāng)前最優(yōu)值bestp,就剪枝.

在隊(duì)列式分支限界法解決裝載問(wèn)題時(shí)，在隊(duì)列中加入一個(gè)-1標(biāo)志，該標(biāo)志所起的作用是表示其后的活結(jié)點(diǎn)在解空間樹(shù)中的層數(shù)比-1之前的活結(jié)點(diǎn)更深一層，或者說(shuō)是同層活結(jié)點(diǎn)的結(jié)束標(biāo)志。

參考答案:

正確

回溯法與分支限界法的空間復(fù)雜度是相同的，都是O(h(n)),h(n)是解空間樹(shù)的深度。

參考答案:

錯(cuò)誤

優(yōu)先隊(duì)列式分支限界法解決0-1背包問(wèn)題時(shí)，下面描述正確的是

參考答案:

左孩子結(jié)點(diǎn)的優(yōu)先級(jí)等于父結(jié)點(diǎn)的優(yōu)先級(jí)_右孩子結(jié)點(diǎn)相應(yīng)的背包內(nèi)物品的價(jià)值等于父結(jié)點(diǎn)相應(yīng)的背包內(nèi)的物品價(jià)值

閱讀該單元測(cè)試中關(guān)于0-1背包問(wèn)題的優(yōu)先隊(duì)列分支限界算法代碼，問(wèn)左分支的剪枝條件是什么？右分支的剪枝條件是什么？從代碼中找到命令行，使用原代碼回答問(wèn)題。

參考答案:

左分支：wt<=c,

右分支：up>bestp

下面是優(yōu)先隊(duì)列式分支限界算法解0-1背包問(wèn)題的部分主代碼，分析代碼將【】?jī)?nèi)的代碼補(bǔ)齊。TempleteTypepknap::MaxKnapsack(){//優(yōu)先隊(duì)列分支限界法，返回最大價(jià)值，最優(yōu)解bestxH=newMaxHeap>(1000);//定義最大堆的容量為1000bestx=newint[n+1];inti=1;E=0;cw=cp=0;Typepbestp=0;Typepup=Bound(1）；while(【1】){Typewwt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)【2】；AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(up>bestp)AddLiveNode(up,cp,cw,false,i+1);//從優(yōu)先隊(duì)列中取下一個(gè)擴(kuò)展節(jié)點(diǎn)HeapNodeN;H->DeleteMax(N);E=NNaNr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//構(gòu)造最優(yōu)解for（intj=n;j>0;j--）{bestx[j]=E->lchild;E=E->parent;}returncp;}

參考答案:

【1】i

在隊(duì)列式分支限界法中，葉子結(jié)點(diǎn)不加入隊(duì)列。而在優(yōu)先隊(duì)列式分支限界法中，葉子結(jié)點(diǎn)通常要加入到優(yōu)先隊(duì)列中。有下列2個(gè)解釋：（1）隊(duì)列式分支限界法，活結(jié)點(diǎn)在隊(duì)列中的順序是按照搜索解空間樹(shù)時(shí)擴(kuò)展出該結(jié)點(diǎn)的先后順序存放，每次從隊(duì)首取出一個(gè)活結(jié)點(diǎn)成為新的擴(kuò)展結(jié)點(diǎn)。擴(kuò)展結(jié)點(diǎn)擴(kuò)展出的兒子結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，會(huì)將該葉子結(jié)點(diǎn)的值同當(dāng)前最優(yōu)值比較，檢查更新最優(yōu)值，葉子結(jié)點(diǎn)并不進(jìn)入隊(duì)列，等隊(duì)列為空時(shí)，搜索結(jié)束，記錄的當(dāng)前最優(yōu)值就是問(wèn)題最優(yōu)值。（2）優(yōu)先隊(duì)列式分支限界法中，當(dāng)優(yōu)先級(jí)的定義是限界函數(shù)時(shí)，擴(kuò)展出的葉子結(jié)點(diǎn)進(jìn)入隊(duì)列，這種做法主要是為了讓搜索過(guò)程提前結(jié)束。也就是當(dāng)從優(yōu)先隊(duì)列中取出一個(gè)活結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，意味著現(xiàn)在優(yōu)先隊(duì)列中剩余的所有活結(jié)點(diǎn)其優(yōu)先級(jí)都不大于該葉子結(jié)點(diǎn)的優(yōu)先級(jí)，葉子結(jié)點(diǎn)的優(yōu)先級(jí)等于最優(yōu)值，算法結(jié)束，無(wú)論優(yōu)先隊(duì)列是否為空。根據(jù)其正確與否，給出答案

參考答案:

（1）正確，（2）正確

在隊(duì)列式分支限界法解決裝載問(wèn)題時(shí)，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時(shí)才去更新bestw，其目的是什么？

參考答案:

為了及早使右（0）分支剪枝函數(shù)生效。

分支限界法中，擴(kuò)展出的孩子結(jié)點(diǎn)在入隊(duì)時(shí)，存儲(chǔ)該孩子結(jié)點(diǎn)的父結(jié)點(diǎn)的地址和左孩子標(biāo)志。其目的是什么？

參考答案:

為了構(gòu)造最優(yōu)解

分支限界法與回溯法的不同點(diǎn)體現(xiàn)在哪些方面？（1）求解目標(biāo)不同，分支限界法可求最優(yōu)解或滿足條件的一個(gè)解，而回溯法可求最優(yōu)解或滿足條件的所有解（2）搜索方式不同，回溯法是以深度優(yōu)先狀態(tài)生成樹(shù)法搜索解空間樹(shù)，分支限界法則以廣度優(yōu)先或最小耗費(fèi)（最大效益）優(yōu)先的狀態(tài)生成樹(shù)法搜索解空間樹(shù)。（3）同一個(gè)問(wèn)題在使用回溯法或分支限界法時(shí)，該問(wèn)題的解空間樹(shù)的結(jié)構(gòu)不同（4）回溯法與分支限界法，構(gòu)造最優(yōu)解的方式不同。從上述選項(xiàng)中找出答案。

參考答案:

（1）（2）（4）

操場(chǎng)上擺放一行共4堆石頭，從左到右方向編號(hào)為1~4，各堆石子的數(shù)目分別為7,10,3,5，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過(guò)5次合并，最終合并為一堆。計(jì)算這6堆石子合并為一堆的最小得分

參考答案:

50

0-1背包問(wèn)題：給定n種物品和一背包，物品i的重量wi，價(jià)值vi，背包容量為c，如何選擇裝入背包中的物品，使得裝入背包中的物品總價(jià)值最大。設(shè)m[i][j]是前i個(gè)物品裝入背包容量為j的背包所能獲得的最大價(jià)值，下面是關(guān)于最優(yōu)值的遞歸定義，從中選出正確的關(guān)于最優(yōu)值m[i][j]的遞歸定義。

參考答案:

_

下面列出了算法的四個(gè)性質(zhì)，哪個(gè)性質(zhì)是程序不一定具備的？

參考答案:

有窮性

下面哪些內(nèi)容不是算法設(shè)計(jì)之前要完成的內(nèi)容?

參考答案:

使用何種計(jì)算機(jī)語(yǔ)言設(shè)計(jì)程序

下面哪個(gè)算法在最壞情況下的時(shí)間復(fù)雜性最低

參考答案:

歸并排序

分治法的時(shí)間復(fù)雜性分析，通常是通過(guò)分析得到一個(gè)關(guān)于時(shí)間復(fù)雜性T(n)的一個(gè)遞歸方程，然后解此方程可得T(n)的結(jié)果。T(n)的遞歸定義如下：【圖片】關(guān)于該定義中k，n/m,f(n)的解釋準(zhǔn)確的是

參考答案:

k是子問(wèn)題個(gè)數(shù)，n/m是子問(wèn)題的規(guī)模，f(n)是分解為子問(wèn)題的時(shí)間復(fù)雜性與合并子問(wèn)題的解的時(shí)間復(fù)雜性之和

已知斐波那契數(shù)列中第n個(gè)斐波那契數(shù)F(n)=F(n-1)+F(n-2),問(wèn)能不能使用分治策略求第n個(gè)斐波那契數(shù)，從下面選項(xiàng)中選取答案。

參考答案:

不能，因?yàn)樗粷M足分治法的第四個(gè)適應(yīng)條件（子問(wèn)題是相互獨(dú)立的，也就是沒(méi)有重復(fù)子問(wèn)題）

快速冪算法求【圖片】，其時(shí)間復(fù)雜性為O(logn)，a是實(shí)數(shù)，n為非負(fù)整數(shù)。下面是一同學(xué)用c語(yǔ)言編寫(xiě)的求【圖片】的代碼doubleexp2(doublea,intn){if(a==0)return0;if(n==0)return1;else{if(n%2)returna*exp2(a,n/2)*exp2(a,n/2);elsereturnexp2(a,n/2)*exp2(a,n/2);}}對(duì)該同學(xué)的算法評(píng)價(jià)正確的是？

參考答案:

運(yùn)行結(jié)果正確，時(shí)間復(fù)雜性為O(n)

快速排序和歸并排序是常用的排序算法，也都是采用分治法解決的問(wèn)題?？焖倥判虻臅r(shí)間復(fù)雜性為O(【圖片】),而歸并排序的時(shí)間復(fù)雜性為O(nlogn),究其原因，下面的解釋你認(rèn)為哪個(gè)正確？

參考答案:

因?yàn)闅w并排序把問(wèn)題劃分為兩個(gè)子問(wèn)題時(shí)其規(guī)模大致相等，是原來(lái)規(guī)模的n/2，而快速排序劃分為子問(wèn)題是使用partition()函數(shù)，劃分為子問(wèn)題時(shí)不能保證二個(gè)子問(wèn)題的規(guī)模大致相同，在極端狀況下，每次都只劃分為1個(gè)子問(wèn)題，其規(guī)模為原問(wèn)題規(guī)模n-1，因此快速排序在極端狀況下的時(shí)間復(fù)雜性的遞歸定義為T(mén)(n)=T(n-1)+O(n)

猜數(shù)游戲：隨機(jī)選擇一個(gè)0~100內(nèi)的整數(shù)，讓你猜。猜對(duì)了，你贏了，游戲結(jié)束。如果沒(méi)有猜對(duì)，會(huì)告訴你猜大了，還是猜小了。當(dāng)然，越早猜對(duì)越好。問(wèn)最少需要猜多少次，就能保證一定能猜對(duì)？

參考答案:

7

關(guān)于算法的正確性，下面哪些說(shuō)法是正確的？

參考答案:

若算法是正確的，則對(duì)于問(wèn)題的任何實(shí)例，算法都能得到正確的結(jié)果。_若算法是正確的，則算法一定能結(jié)束（運(yùn)行時(shí)間是有限的）_對(duì)于問(wèn)題的一個(gè)實(shí)例，如果算法不能獲得正確的結(jié)果，就證明算法是不正確的。

操場(chǎng)上擺放一行共n堆石頭，從左到右方向編號(hào)為1~n，石子的數(shù)目分別為p[1],……,p[n]，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過(guò)n-1次合并，最終合并為一堆。計(jì)算這n堆石子合并為一堆的最小得分。請(qǐng)根據(jù)題目要求，從如下選項(xiàng)中找出關(guān)于從第i堆到第j堆合并為一堆的最小得分m[i][j]的遞歸定義.

參考答案:

if（i

操場(chǎng)上擺放一行共n堆石頭，從左到右方向編號(hào)為1~n，石子的數(shù)目分別為p[1],……,p[n]，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過(guò)n-1次合并，最終合并為一堆。計(jì)算這n堆石子合并為一堆的最小得分。分析該問(wèn)題，從如下選項(xiàng)中找出用動(dòng)態(tài)規(guī)劃解決該問(wèn)題的時(shí)間復(fù)雜性和空間復(fù)雜性

參考答案:

T（n）=O（）

S(n)=O(

)

最長(zhǎng)公共子序列問(wèn)題：現(xiàn)有兩個(gè)字符序列X和Y,下面c矩陣和b矩陣是算法填寫(xiě)出的信息表。c[i][j]是X序列的前i個(gè)字符和Y序列的前j個(gè)字符的最長(zhǎng)公共子序列的長(zhǎng)度，b[i][j]是輔助信息表。已知X=”ABC”【圖片】根據(jù)表格內(nèi)容，回答X和Y的最長(zhǎng)公共子序列長(zhǎng)度及最長(zhǎng)公共子序列包含的符號(hào)

參考答案:

長(zhǎng)度2

“AC”

0-1背包問(wèn)題：現(xiàn)有一背包容量c=5，n=4。4個(gè)物品分別為：(Wi,Vi)|(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i個(gè)物品裝背包容量為j時(shí)的最優(yōu)值。【圖片】【圖片】其中第四行的數(shù)據(jù)沒(méi)有填寫(xiě)，分析問(wèn)題，將第四行的數(shù)據(jù)從如下選項(xiàng)中找出。

參考答案:

0

3

7

10

10

13

游艇租賃問(wèn)題：長(zhǎng)江游艇俱樂(lè)部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1~n，游客可在這些游艇出租站租用游艇，并在下游的任何出租站歸還游艇，限制只能從上游往下游行進(jìn)，游艇出租站i到出租站j直達(dá)的租金為r(i,j)（1<=i

參考答案:

圖2是將從1站到i站的最小費(fèi)用問(wèn)題劃分為2個(gè)子問(wèn)題即從第1站到第k站的最小費(fèi)用問(wèn)題和從k站到i站的最小費(fèi)用問(wèn)題。

矩陣連乘問(wèn)題：下圖是動(dòng)態(tài)規(guī)劃算法計(jì)算6個(gè)矩陣A1A2A3A4A5A6連乘所生成的信息表.【圖片】（a）表描述了計(jì)算順序，（b）表是m[i][j]的最優(yōu)值表，（c）表是輔助信息表（斷開(kāi)位置）。分析表格，給出A2A3A4A5A6五個(gè)矩陣連乘所需要的最少數(shù)乘次數(shù)，并用加括號(hào)的方法表示出其乘法順序。從如下選項(xiàng)中選擇。

參考答案:

10500,

(A2A3)((A4A5)A6)

求第n個(gè)斐波那契數(shù)的問(wèn)題，根據(jù)動(dòng)態(tài)規(guī)劃的二要素分析，是可以用動(dòng)態(tài)規(guī)劃算法去解決的，下面是用備忘錄方法（遞歸）解決的求第n個(gè)斐波那契數(shù)f[n]的程序.這里N是一個(gè)較大的正整數(shù)常量，注意備忘錄方法的設(shè)計(jì)要點(diǎn)（也就是，對(duì)于一個(gè)問(wèn)題，首先判斷是否該問(wèn)題已被解決過(guò)，如果解決，不再重復(fù)。另外，解決過(guò)的問(wèn)題，答案要記?。﹊ntf[N]={0,1,1};intfib(intn){if(【1】)returnf[n];elsereturn【2】;}代碼中【1】和【2】位置代碼缺失，請(qǐng)從下列選項(xiàng)中選出合適的語(yǔ)句補(bǔ)齊算法。

參考答案:

【1】f[n]>0

【2】f[n]=fib(n-1)+fib(n-2)

動(dòng)態(tài)規(guī)劃解題的步驟分為四步（1）分析最優(yōu)解的結(jié)構(gòu)（2）建立遞歸關(guān)系（3）計(jì)算最優(yōu)值（4）構(gòu)造最優(yōu)解。關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)？

參考答案:

計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問(wèn)題的最優(yōu)值，也就是先求解規(guī)模較大的問(wèn)題的最優(yōu)值。

數(shù)值概率算法求π的算法，是用半徑為1的圓外接一個(gè)正方形，然后模擬向正方形中隨機(jī)投放n個(gè)點(diǎn)，計(jì)數(shù)落在圓內(nèi)的點(diǎn)的個(gè)數(shù)為k，則π的近似值為

參考答案:

4k/n##%_YZPRLFH_%##4*k/n

素?cái)?shù)測(cè)試問(wèn)題的蒙特卡洛算法，n是一個(gè)待判定正整數(shù)。當(dāng)n是素?cái)?shù)時(shí)，有時(shí)會(huì)被判定為非素?cái)?shù)。該說(shuō)法正確嗎?

參考答案:

錯(cuò)誤

計(jì)算機(jī)中的隨機(jī)數(shù)是偽隨機(jī)的，因?yàn)樗蔷哂幸欢ㄒ?guī)律的，是按公式計(jì)算出來(lái)的。該說(shuō)法正確嗎？

參考答案:

正確

舍伍德算法思想是通過(guò)引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法，打破原來(lái)確定性算法在某些實(shí)例情況下，其時(shí)間復(fù)雜性必然遠(yuǎn)高于平均時(shí)間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想？

參考答案:

快速排序算法_跳躍表_線性時(shí)間選擇算法

n個(gè)城市的旅行售貨商問(wèn)題的回溯法中，r[i][j]是鄰接矩陣，表示i城市到j(luò)城市的距離，x[]是路徑信息,有A、B兩段描述A.該問(wèn)題的解空間樹(shù)，第一層只有一個(gè)分支，也就是指定第一個(gè)城市作為出發(fā)城市，因?yàn)槭黔h(huán)路的原因，指定哪個(gè)城市出發(fā)結(jié)果是一樣的，這樣做相當(dāng)于在樹(shù)的第一層剪掉了其他的n-1個(gè)分支，主要目的是提高搜索效率。自第二層開(kāi)始往下是一顆排列樹(shù)。B.該算法將第n-1層的結(jié)點(diǎn)看做是葉子結(jié)點(diǎn)，當(dāng)搜索至該葉子結(jié)點(diǎn)時(shí)，整個(gè)環(huán)路(如果存在的話)長(zhǎng)度就是路徑x[1..n-1]的長(zhǎng)度cc+r[n-1][n]+r[n][1]。根據(jù)A,B描述的正確與否，從如下選項(xiàng)中找到正確答案

參考答案:

A對(duì)，B錯(cuò)

子集和問(wèn)題：給定n個(gè)不同的正整數(shù)，已知其和大于c，問(wèn)有多少個(gè)不同的其和等于c的子集？下面給出的算法，解空間樹(shù)是子集樹(shù)，且n個(gè)數(shù)已按從小到大有序存放于a數(shù)組中。voidbacktrack(inti){if(sum==c)count++;elseif(i<=n){if(sum+a[i]<=c){sum+=a[i];backtrack(i+1);【】}}}請(qǐng)將【】位置缺失的代碼補(bǔ)齊，從下面選項(xiàng)中找到答案。

參考答案:

sum-=a[i];

backtrack(i+1);

在分治法中講到快速排序，如果每次使用partion函數(shù)導(dǎo)致分組出現(xiàn)嚴(yán)重不平衡情況下，算法效率不高，最壞情況下的時(shí)間復(fù)雜度為O（n^2）,通過(guò)改造partition函數(shù)，也就是每次隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)，這樣會(huì)很好地改善算法的性能，這種算法思想是？

參考答案:

舍伍德算法

n=12皇后問(wèn)題的三種不同的解決方案：回溯法、拉斯維加斯算法、拉斯維加斯算法+回溯法。對(duì)于給定的一個(gè)實(shí)例，(1)平均耗費(fèi)時(shí)間最少的是那種方案？，(2)平均耗費(fèi)時(shí)間最多的是那種方案？

參考答案:

(1)拉斯維加斯+回溯

(2)

回溯法

學(xué)習(xí)主定理和遞歸樹(shù)等求解遞歸方程方法，主要目的是解決求遞歸算法的時(shí)間復(fù)雜性問(wèn)題

參考答案:

正確

自然語(yǔ)言、偽代碼都可以描述算法，而流程圖不能描述算法

參考答案:

錯(cuò)誤

一致的p正確的偏y0的蒙特卡洛算法，下面解釋不正確的是?

參考答案:

運(yùn)行蒙特卡洛算法p次，至少有一次是正確的。

棋盤(pán)8X8的覆蓋問(wèn)題，其中一個(gè)點(diǎn)已經(jīng)被覆蓋，用L型模塊將其余完全覆蓋的分治策略。約定解決四個(gè)子問(wèn)題的順序?yàn)橛蚁拢笙?左上，右上。用數(shù)字標(biāo)識(shí)法填寫(xiě)覆蓋方案（如3個(gè)相連的整數(shù)值i構(gòu)成的L塊，代表是第i個(gè)被放入棋盤(pán)中的L型塊）。使用分治策略的算法有三種形式：1使用遞歸算法實(shí)現(xiàn)，2使用隊(duì)列存取分解出的子棋盤(pán)的非遞歸算法3.使用棧存取分解出的子棋盤(pán)的非遞歸算法。下圖中有三個(gè)覆蓋圖案（只標(biāo)出了前7塊L型模塊位置），問(wèn)自左至右分別是哪種算法實(shí)現(xiàn)的覆蓋方案？【圖片】【圖片】

參考答案:

遞歸算法，隊(duì)列算法，棧算法

下面哪些不是遞歸算法的特點(diǎn)

參考答案:

遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問(wèn)題的非遞歸算法要少

給定n個(gè)正整數(shù)組成的無(wú)序序列，要找到該序列的中位數(shù)，解決該問(wèn)題的最優(yōu)算法的時(shí)間復(fù)雜性是？

參考答案:

O（n）

遞歸程序代碼簡(jiǎn)短，結(jié)構(gòu)清晰，易讀性強(qiáng)，相比解決同一問(wèn)題的非遞歸程序，遞歸程序運(yùn)行時(shí)間短。

參考答案:

錯(cuò)誤

有一個(gè)問(wèn)題的蒙特卡洛算法，給定一個(gè)實(shí)例，已知運(yùn)行一次其答案是錯(cuò)誤的概率是1/8,現(xiàn)運(yùn)行k次該算法，其答案一直不變，問(wèn)該答案的正確率是？

參考答案:

1-(1/8)^k

有這樣一種算法，運(yùn)行一次一定能找到問(wèn)題的解，有時(shí)不知其是否正確，可以確定的是該解高概率（大于50%）是正確的。這種算法是？

參考答案:

蒙特卡洛算法

有這樣一種算法，運(yùn)行一次可能找不到問(wèn)題的解，運(yùn)行多次就一定能找到問(wèn)題的解，且運(yùn)行次數(shù)有界，這種算法是？

參考答案:

拉斯維加斯算法

回溯法中，剪枝函數(shù)能夠剪掉的分支越多，算法效率就越高。因此，我們?cè)谠O(shè)計(jì)回溯法時(shí)，就要設(shè)計(jì)剪枝函數(shù)能夠剪掉盡量多的分支。

參考答案:

錯(cuò)誤

回溯法的算法效率跟哪些因素有關(guān)？這里x【k】是分支上的取值。

參考答案:

計(jì)算限界函數(shù)值的時(shí)間_滿足隱約束函數(shù)和限界函數(shù)約束的所有x【k】的個(gè)數(shù)_滿足顯約束的x【k】的個(gè)數(shù)。_計(jì)算隱約束函數(shù)值的時(shí)間

一個(gè)人正站在門(mén)口，讓你猜他（她）是否要出門(mén)？，該問(wèn)題是不可判定問(wèn)題，該觀點(diǎn)是否正確？

參考答案:

正確

對(duì)于一個(gè)采用字符數(shù)組存放的長(zhǎng)度為n的字符串str，下面是用分治策略的遞歸算法去判斷字符串str是否為回文，如是回文，函數(shù)返回true，否則返回false。比如：“abcba”、“abba”是回文，“abc”則不是回文。boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}算法中【】處缺少語(yǔ)句，請(qǐng)分析算法，從如下選項(xiàng)中選擇語(yǔ)句補(bǔ)齊算法。

參考答案:

(1)n==1

(2)

str[n-1]

(3)str+1

(4)n-2

解決同一個(gè)問(wèn)題的算法策略可能有多個(gè)，使用不同算法策略設(shè)計(jì)的算法，其算法時(shí)間復(fù)雜性可能有顯著差異。

參考答案:

正確

一個(gè)問(wèn)題，確定了某個(gè)貪心策略，如果用貪心算法能夠構(gòu)造出問(wèn)題的最優(yōu)解，需要該問(wèn)題具備哪兩個(gè)條件？

參考答案:

最優(yōu)子結(jié)構(gòu)性質(zhì)_貪心選擇性質(zhì)

在算法設(shè)計(jì)與分析過(guò)程中，有算法設(shè)計(jì)，算法的正確性證明，算法的復(fù)雜性分析,程序設(shè)計(jì)等幾個(gè)重要步驟，下面哪種順序是正確的？

參考答案:

算法設(shè)計(jì)->算法的正確性證明->算法的復(fù)雜性分析->程序設(shè)計(jì)

教材例題：多機(jī)調(diào)度問(wèn)題，是用貪心算法求最優(yōu)解的一個(gè)例子，貪心策略是每次從剩余任務(wù)中選擇一個(gè)花費(fèi)時(shí)間最長(zhǎng)的任務(wù)，安排在占用時(shí)間最少的機(jī)器上。

參考答案:

錯(cuò)誤

棋盤(pán)nxn（【圖片】）的覆蓋問(wèn)題，其中一個(gè)點(diǎn)已經(jīng)被覆蓋，用L型模塊將其余完全覆蓋的分治算法。關(guān)于該算法時(shí)間復(fù)雜性描述不正確的是

參考答案:

T(n)=O(n^4)

對(duì)于一個(gè)采用字符數(shù)組存放的長(zhǎng)度為n的字符串str，下面是判斷是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”則不是回文boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}請(qǐng)補(bǔ)齊代碼后分析算法的時(shí)間復(fù)雜性，回答如下問(wèn)題

參考答案:

該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-2)+1，if

n>1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)

A公司處理器速度是B公司的100倍。對(duì)于復(fù)雜性為O(【圖片】)的算法，B公司的計(jì)算機(jī)可以在1小時(shí)內(nèi)處理規(guī)模為n的問(wèn)題，A公司的計(jì)算機(jī)在1小時(shí)內(nèi)能處理的問(wèn)題規(guī)模是多少？

參考答案:

10n

NP難問(wèn)題未必是NP問(wèn)題

參考答案:

正確

一個(gè)NPC問(wèn)題，首先是NP問(wèn)題，另外所有的其他NP問(wèn)題都能在多項(xiàng)式時(shí)間復(fù)雜性規(guī)約為該問(wèn)題

參考答案:

正確

pollard算法找到一個(gè)整數(shù)因子的時(shí)間復(fù)雜性是？

參考答案:

O()

回溯法是在一顆已經(jīng)建立起來(lái)的解空間樹(shù)中實(shí)現(xiàn)深度優(yōu)先搜索的算法。

參考答案:

錯(cuò)誤

有人說(shuō)可以設(shè)計(jì)蒙特卡洛算法去猜硬幣的反正面問(wèn)題，該說(shuō)法是否正確？

參考答案:

錯(cuò)誤

凸多邊形的三角剖分問(wèn)題。用動(dòng)態(tài)規(guī)劃算法求解最優(yōu)三角剖分，首先要分析最優(yōu)解的結(jié)構(gòu)，也就是將問(wèn)題分解為子問(wèn)題，并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問(wèn)題的方法，哪種是正確的將問(wèn)題劃分為子問(wèn)題的方案？正確的劃分方案共有幾種不同方式？【圖片】

參考答案:

左圖正確，14種

下面是求最長(zhǎng)公共子序列長(zhǎng)度和構(gòu)造最優(yōu)解的算法?！尽恐械恼Z(yǔ)句缺失，請(qǐng)從如下選項(xiàng)中找到正確的答案補(bǔ)齊算法。voidLCSLength(intm,intn,char*x,char*y,int**c,int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(j=1;j<=n;i++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){【1】;b[i][j]=2;}else{【2】;b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<

參考答案:

(1)c[i][j]=c[i-1][j]

(2)c[i][j]=c[i][j-1]

(3)LCS(i-1,j,x,b)

(4)LCS(i,j-1,x,b)

子集和問(wèn)題：給定n個(gè)不同的正整數(shù)，已知其和大于c，要求找出一個(gè)子集使其和等于c。該問(wèn)題除解空間樹(shù)是子集樹(shù)的回溯法外，還有解空間樹(shù)是排列樹(shù)的回溯算法，思考該問(wèn)題，從如下選項(xiàng)中找到關(guān)于該算法設(shè)計(jì)的正確的描述。

參考答案:

當(dāng)解空間樹(shù)是排列樹(shù)時(shí)，

搜索時(shí)，可以將從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑上的數(shù)看成是一個(gè)子集。_剪枝條件:當(dāng)路徑上的數(shù)之和>c時(shí)剪枝

可用動(dòng)態(tài)規(guī)劃算法解決的問(wèn)題需要滿足幾個(gè)基本要素，從下面選項(xiàng)中找出這些基本要素

參考答案:

重復(fù)子問(wèn)題_最優(yōu)子結(jié)構(gòu)性質(zhì)

符號(hào)三角形問(wèn)題的回溯算法如下half=（n+1）*n/4;//(n+1)*n/2是偶數(shù)voidbacktrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}【】backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}現(xiàn)要求將紅色代碼去掉，保持算法功能不改變，需在【】添加下面哪段代碼？

參考答案:

if((count<=half)&&(t*(t+1)/2-count<=half))

下圖中A~F頂點(diǎn)分別代表6個(gè)村莊，圖中的邊代表村莊之間的距離，為了滿足這六個(gè)村莊相互通信的需要（任意兩個(gè)村莊有線路可達(dá)），需要架設(shè)通信線路，這里要求代價(jià)最小化（即線路總長(zhǎng)度最小），請(qǐng)你分析問(wèn)題找到代價(jià)最小的方案，并計(jì)算出線路總長(zhǎng)度，從如下選項(xiàng)中找出答案?！緢D片】【圖片】

參考答案:

線路總長(zhǎng)度21

現(xiàn)有一樓梯共8級(jí)臺(tái)階，有一小朋友一步可以邁出1、2或3級(jí)臺(tái)階，問(wèn)小朋友有多少種不同的爬樓梯的方法

參考答案:

81

將一個(gè)遞歸算法改造為非遞歸算法，常用的數(shù)據(jù)結(jié)構(gòu)是？

參考答案:

棧

分治法解決問(wèn)題時(shí)，平衡子問(wèn)題思想是指：當(dāng)問(wèn)題劃分出的子問(wèn)題規(guī)?；疽恢聲r(shí)，算法計(jì)算效率高

參考答案:

正確

下面是優(yōu)先隊(duì)列式分支限界算法解裝載問(wèn)題（n個(gè)集裝箱裝船）的部分代碼，分析下面代碼1Templete2TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//返回最大裝載量Ew，最優(yōu)解bestx3MaxHeap>H(1000);//定義最大堆的容量為10004Type*r=newType[n+1];5r[n]=0;6for(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];7inti=1;8bbnode*E=0;9TypeEw=0;10while(i!=【1】){//搜索子集樹(shù)11if(Ew+w[i]<=c)AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);12AddLiveNode(H,E,Ew+r[i],false,i+1);13HeapNodeN;14H.DeleteMax(N);15i=N.level;16E=NNaNr;17Ew=N.uweight-【2】;18}19for（intj=n;j>0;j--）{20bestx[j]=E->lchild;E=E->parent;｝21returnEw;22}該題目中有二個(gè)位置【1】【2】代碼缺失，請(qǐng)補(bǔ)齊【2】的代碼

參考答案:

r[i-1]

爬樓梯問(wèn)題：有一樓梯共n級(jí)臺(tái)階，有一小朋友一次可以邁1，2或3級(jí)臺(tái)階，求共有多少不同的走法走完這n級(jí)臺(tái)階?；卮鹪搯?wèn)題最適合使用哪種算法？

參考答案:

動(dòng)態(tài)規(guī)劃

給定n個(gè)任務(wù)接受同一臺(tái)機(jī)器加工,任務(wù)i有服務(wù)時(shí)間和要求截止時(shí)間(ti,di),找出最小延遲方案，即所有任務(wù)延遲時(shí)間最大值的最小化問(wèn)題。如3個(gè)任務(wù)1、2、3，服務(wù)時(shí)間和截至?xí)r間為（2，4）（1，2）（7，7），如按照1-2-3順序安排，各任務(wù)的延遲為0，1，3，延遲的最大值為3。使用貪心算法，如下哪種貪心策略可得到最優(yōu)解？

參考答案:

以截止時(shí)間di從小到大安排

整數(shù)因子分解問(wèn)題：大于1的正整數(shù)n可以分解為n=x1*x2*…xm。如n=12時(shí)有如下形式12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*38種形式求正整數(shù)n共有多少種分解形式，函數(shù)p(intn)返回值為問(wèn)題的答案，代碼如下：intp(intn){if(【1】)return1;intk=0;for(intj=n;j>1;j--)if(n%j==0)k+=【2】;returnk;}代碼中【1】【2】處代碼缺失，請(qǐng)補(bǔ)齊【1】的代碼

參考答案:

n==1##%_YZPRLFH_%##1==n

整數(shù)因子分解問(wèn)題:大于1的正整數(shù)n可以分解為n=x1*x2*…xm.如n=12時(shí)有如下形式12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*38種形式求正整數(shù)n共有多少種分解形式，函數(shù)p(intn)返回值為問(wèn)題的答案，代碼如下：intp(intn){if(【1】)return1;intk=0;for(intj=n;j>1;j--)if(n%j==0)k+=【2】;returnk;}代碼中【1】【2】處代碼缺失，請(qǐng)補(bǔ)齊【2】的代碼

參考答案:

p(n/j)

有n個(gè)正整數(shù)組成的數(shù)組a，兩端的數(shù)不能刪除，中間每刪除一個(gè)數(shù)，其得分為其本身同其兩側(cè)的數(shù)的乘積，求其中間n-2個(gè)數(shù)逐個(gè)刪除后的最大得分。設(shè)m[i][j]為從a[i]到a[j]的子數(shù)組，將中間數(shù)全部刪除后的最大得分。從如下公式中選擇正確的m[i][j]的遞歸定義

參考答案:

m[i][j]=max(m[i][k]+m[