算法分析與設(shè)計(jì).山東財(cái)經(jīng)大學(xué)中國(guó)大學(xué)mooc課后章節(jié)答案期末考試

題庫(kù)2023年

1.蒙特卡羅算法的結(jié)果未必正確，并且可能難以有效判定是否正確。

答案:

正確

2.T(n)=T(n-l)+1,T(l)=l,則T(n)=Q(_)

答案:

n

3.木板問(wèn)題：農(nóng)夫約翰為了修理柵欄，將一塊木板切割成N塊，N塊的長(zhǎng)度

和二原木板長(zhǎng)度。每次切割木板時(shí)的開(kāi)銷(xiāo)為該木板的長(zhǎng)度。木板長(zhǎng)15,切成

長(zhǎng)為1、2、3、4、5的木板。如何切割，使開(kāi)銷(xiāo)最??？(1)該問(wèn)題最好

使用()算法求解。A枚舉B貪心C分治D遞推(2)第一次切割成長(zhǎng)度為

—和—的兩塊。(3)切割的策略和一算法相同。AMSTB區(qū)間調(diào)度C哈

夫曼D區(qū)間劃分

答案：

B;6;9;C

4.背包問(wèn)題，背包容量C=20,物品價(jià)值p=[4,8,15,1,6,3],物品重量

w=[5,3,2,10,4,8],如果是0-1背包問(wèn)題，求裝入背包的最大價(jià)值和相應(yīng)

裝入物品。(1)該問(wèn)題最好使用()算法求解？A動(dòng)態(tài)規(guī)劃算法B貪心算法

C枚舉算法D分治算法(2)裝入背包的最大價(jià)值是,(3)最大價(jià)值對(duì)應(yīng)的物

品編號(hào)為_(kāi)_、_、__、_0(從小到大)

答案:

A;33;l;2;3;5

5.動(dòng)態(tài)規(guī)劃方程M[i]=min(M[j]+wij),l<i<j<n,則算法的時(shí)間復(fù)雜度為M2

答案:

正確

6.給定二分圖G二中無(wú)孤立點(diǎn)，|V|二n,其最大流算法求得最大流f,則G的最

大獨(dú)立數(shù)二n-f

答案:

正確

7.旅行商問(wèn)題的所有解，可以組織成一棵樹(shù)，包含了所有城市的排列組合。樹(shù)

的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑，定義了圖的一條周游路線。

答案:

正確

8.對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)

例的一個(gè)解空間。

答案

正確

9.Floyd算法是動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。

答案：

正確

10.f=O（g）當(dāng)且僅當(dāng)g=3⑴

答案：

正確

11.預(yù)流推進(jìn)算法的關(guān)鍵操作有()

答案：

重嬴號(hào).初始化.推進(jìn)

12.最小費(fèi)用最大流算法求得解需滿足()條件。

答案：

對(duì)于任意邊eiE:O￡f(e)￡c(e)_對(duì)任意頂點(diǎn)v,頂點(diǎn)的凈流量=0_每條邊的流

量乘以單位流量費(fèi)用之和最小

13.給定一分圖G=中無(wú)孤立點(diǎn)，其最大流算法求得最大流f,則G的最大匹配數(shù)

=f

答案：

正確

14.給定G=，G的匹配中任何兩條邊都沒(méi)有公共頂點(diǎn)。

答案：

正確

15.循環(huán)用于重復(fù)性的工作。循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬(wàn)變”。

答案：

正確

16.主方法可以求解滿足T(n)=aT(n/b)+f(n)形式的遞推方程，則下列關(guān)于方

程中的約束中不準(zhǔn)確的是？

答案:

17.Kruskal算法的預(yù)處理是邊權(quán)非遞減排序。

答案:

正確

18.區(qū)間劃分問(wèn)題的預(yù)處理方法是按照開(kāi)始時(shí)間遞減排序。

答案:

錯(cuò)誤

19.Kruskal算法的貪婪準(zhǔn)則是每一次選取不構(gòu)成環(huán)路的最小邊。

答案:

正確

20.原問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解是貪心算法的()性質(zhì)。

答案：

最屆子結(jié)構(gòu)性質(zhì)

21.算法的每一條指令必須要有確切的含義，必須是清楚的、無(wú)二義的。

答案:

正確

22.按照霍納法則，計(jì)算p(x)=anxn+an-lxn-1+...+alxl+aO的復(fù)雜度為0(n)

答案：

正確

23.N后問(wèn)題利用()減少搜索。

答案：

對(duì)麻性.約束函數(shù)一重排原理

24.分支限界法解0-1背包問(wèn)題時(shí)的解空間樹(shù)是()

答案：

子集樹(shù)

25.確定第i階段的收益函數(shù)和從第i階段出發(fā)到第n階段所獲得收益的最優(yōu)值,

建立動(dòng)態(tài)規(guī)劃基本方程。這種方法是()

答案：

反推

26.備忘錄方法使用()的遞歸方式。

答案：

自頂向下

27.下列算法中通常以自底向上的方式求解最優(yōu)解的是()o

答案：

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

28.f(n)=3nA3+7nA2+4nlogn=()(nA3)

答案：

n_o_o

29.f(n)=3nA3+7nA2+4nlogn=0(nA2)

答案：

錯(cuò)誤

30.位向量法生成子集，子集或運(yùn)算可以生成差集

答案：

錯(cuò)誤

31.確定性算法的每一計(jì)算步驟都確定，求解同一實(shí)例用同一算法求解兩次，所

得結(jié)果完全相同。

答案：

正確

32.給定網(wǎng)絡(luò)N=(V,E),設(shè)f為任意流,(A,B)是任意s-t割.則流值至少是割的容

量

答案：

錯(cuò)誤

33.貪心選擇通過(guò)一步步選擇得到問(wèn)題的解，每一步的局部最優(yōu)解都構(gòu)成全局最

優(yōu)解的一部分。

答案:

正確

34.問(wèn)題的最優(yōu)子結(jié)閡性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特

征。

答案：

正確

35.MST中若在樹(shù)中任意增加一條邊，將出現(xiàn)一個(gè)回路；若去掉一條邊，將變

成非連通圖。

答案：

正確

36.從大規(guī)模問(wèn)題逐步化為小規(guī)模問(wèn)題的算法是()

答案：

遞歸

37.折半查找長(zhǎng)度為n的線性表，平均查找長(zhǎng)度為()

答案：

logn

38.T(n)=2T(n/2)+nA2,T(l)=l,則T(n)=()

答案：

Q(nA2)

39.分支限界活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。

答案:

正確

40.設(shè)G是n階無(wú)孤立點(diǎn)的圖，則V*是G的頂點(diǎn)覆蓋，當(dāng)且僅當(dāng)V-V*是G的

獨(dú)立集。

答案：

正確

41.設(shè)f任意流,(A,R)是任意s-t割.則流值至多等于割的容量.

答案：

正確

42.f(n)=6x2An+nA2,f(n)的漸進(jìn)性態(tài)f(n)=OQ

答案：

2An

43.正推是從小規(guī)模的問(wèn)題推解出大規(guī)模問(wèn)題的一種方法

答案：

正確

44.堆排序的時(shí)間復(fù)雜度是0()o

答案：

0(nlogn)

45.堆排序的時(shí)間復(fù)雜度是()

答案：

nlogn

46.分治與遞歸都是從大規(guī)模問(wèn)題逐步化為小規(guī)模問(wèn)題，因此分治算法經(jīng)常使用

遞歸實(shí)現(xiàn)。

答案：

正確

47.兩個(gè)有序數(shù)組合并的時(shí)間不會(huì)超過(guò)兩個(gè)數(shù)組的長(zhǎng)度和。

答案：

正確

48.最短路算法中適用于稀疏圖的是()

答案：

SPFA算法_Bellman算法

49.動(dòng)態(tài)規(guī)劃方程中子問(wèn)題個(gè)數(shù)為M3依賴(lài)的子問(wèn)題個(gè)數(shù)為Me,則算法的時(shí)

間復(fù)雜度為M(t+e)

答案:

正確

50.分治法將原問(wèn)題分解為若干個(gè)規(guī)模較小、相互獨(dú)立、完全相同的子問(wèn)題。

答案:

錯(cuò)誤

51.任務(wù)安排問(wèn)題：某公司有5個(gè)工作崗位，每個(gè)崗位需要1個(gè)人，現(xiàn)接到5

位待業(yè)者申請(qǐng)。A申請(qǐng)崗位1、2、3,B申請(qǐng)1、4,C和D申請(qǐng)4、5,E

申請(qǐng)5。最多一人就業(yè)？最多就業(yè)安排是：A安排—或_?B安排—該問(wèn)

題可以轉(zhuǎn)化為二分圖的()問(wèn)題A最大匹配B完美匹配C完備匹配D最小

匹配

答案：

4;2;3;1;A

5乙T(n)=ZT(n/Z)+nlogn,貝UT(n)二Q(__)

答案：

n(logn)A2##%_YZPRLFH_%##nlog(A2)n

53.找n個(gè)元素的中位數(shù)的分治算法的時(shí)間復(fù)雜度為0(_).

答案：

n

54.最高標(biāo)號(hào)預(yù)流推進(jìn)算法的時(shí)間復(fù)雜度為0()

答案：

nA2mAl/2

55.常見(jiàn)的分支限界法為()

答案：

優(yōu)區(qū)隊(duì)列式分支限界_FIFO分支限界一隊(duì)列式分支限界

56.備忘錄算法的特點(diǎn)()

答案：

從二到小計(jì)算_自頂向下計(jì)算

57.最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。

答案:

正確

58.DAG圖最長(zhǎng)路的反推關(guān)系是L(i)=1+max{L(j)：(i,j)為邊}

答案:

正確

59.Bellman算法在求解過(guò)程中，每次循環(huán)都要檢查修改所有頂點(diǎn)的路徑，也就

是說(shuō)源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度一直要到Bellman算法結(jié)束才確定卜來(lái)

答案:

正確

60.動(dòng)態(tài)規(guī)劃計(jì)算樹(shù)上的最大獨(dú)立集時(shí)，從葉子開(kāi)始，先計(jì)算子樹(shù)，逐步計(jì)算到

根節(jié)點(diǎn)。

答案:

正確

61.回溯法的兩種解空間樹(shù)為

答案：

排歹謫_子集樹(shù)

62.對(duì)于含有n個(gè)元素的子集樹(shù)問(wèn)題，最壞情況下其解空間的葉結(jié)點(diǎn)數(shù)目為

()O

答案：

2An

63.回溯法搜索解空間時(shí)，在搜索試探時(shí)選取x[i]的值順序是任意的，順序?qū)τ?/p>

計(jì)算量沒(méi)有差別。

答案：

錯(cuò)誤

64.隊(duì)列式分支限界法以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。

答案：

錯(cuò)誤

65.確定性算法的每一計(jì)算步驟都確定，求解同一實(shí)例用同一算法求解兩次，所

用時(shí)間和所得結(jié)果可能不同。

答案：

錯(cuò)誤

66.時(shí)間復(fù)雜度是指算法最壞情況下的運(yùn)行時(shí)間。

答案:

正確

67,以空間換時(shí)間的方法有()

答案：

動(dòng)家規(guī)劃一預(yù)構(gòu)造.預(yù)處理

68.回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但是，當(dāng)探

索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，

這種走不通就退回再走的技術(shù)，稱(chēng)為回溯法。

答案：

正確

69.從資源劃分，算法的復(fù)雜度分為0和0。

答案：

時(shí)間復(fù)雜度空間復(fù)雜度

70.分支限界法與回溯法，都是在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解。

答案：

正確

71.裝載問(wèn)題的剪枝函數(shù)有()

答案：

可行性約束函數(shù)：.上界函數(shù)：Cw+r￡bestw

72.隨機(jī)抽取數(shù)組元索k次，從最接近搜索元素x的位力順序搜索,順序搜索的平

均比較次數(shù)為O(n/(k+l)).

答案：

正確

73.(logn)A2=()(logn+5)

答案：

W

74.下面有關(guān)遞歸與遞推的說(shuō)法錯(cuò)誤的是()

答案：

一般來(lái)說(shuō)，遞歸的效率高于遞推

75.下面不是影響回溯算法效率的主要因素的是()

答案：

x[k]的優(yōu)先級(jí)

76.給定n個(gè)整數(shù)，n個(gè)數(shù)的取值范圍為下面有關(guān)計(jì)數(shù)排序的說(shuō)法正確的

是()

答案：

臺(tái)數(shù)排序最好情況下的時(shí)間復(fù)雜度為0(n+k)_計(jì)數(shù)排序的復(fù)雜度為0

(n+k)_計(jì)數(shù)排序的平均時(shí)間復(fù)雜度是0(n+k1計(jì)數(shù)排序最好情況下的

空間復(fù)雜度為0(n+k)

77.回溯算法的效率在很大程度上依賴(lài)的因素有()：

答案：

剪底時(shí)間：計(jì)算可行性約束函數(shù)constraint和上界函數(shù)bound的時(shí)間。.

產(chǎn)生x[k]的時(shí)間.滿足可行性約束函數(shù)和上界函數(shù)的所有x[k]的個(gè)數(shù).滿足

顯約束的x[k]值的個(gè)數(shù)

78.nA(l/logn}=0(l)

答案：

正確

79.對(duì)近似遞增序列的線性表從小到大排序，使用合并排序比較好。

答案：

錯(cuò)誤

80.給定圖G,BFS形成的層次網(wǎng)絡(luò)圖，是從起點(diǎn)到其它點(diǎn)的最短路。

答案：

正確

81.分析下列程序的上界0和下界W。for(i=1;i<n;i++)key=a[i];intj=i-l

while(j>=0&&a[j]>key)a[j+l]=a[j]j--a[j+l]=key該程序時(shí)間宜雜鹿的上

界是0(一)、下界是W(一

答案：

nA2;n

82.順序查找長(zhǎng)度為n的線性表，平均查找長(zhǎng)度為()

答案：

(n+l)/2

83.Iogl0=()(10)

答案：

0

84.lognA3=()⑵ogn+5)

答案：

0

85.下面程序的時(shí)間復(fù)雜度為()i=lwhile(i<=n)doi=i*2

答案：

O(logn)

86.算法復(fù)雜度分析的兩種方法是()

答案：

事露分析和事后統(tǒng)計(jì)

87.下面關(guān)于算法的說(shuō)法錯(cuò)誤的是()o

答案：

高一算法只有一種形式描述。

88.舍伍德算法設(shè)法消除最壞情況和特定實(shí)例的關(guān)聯(lián)性，達(dá)到平均實(shí)例的性能.

答案：

正確

89.增加拉斯維加斯算法的反復(fù)求解次數(shù),可使求解無(wú)效的概率任意小。

答案：

正確

96如果

p是一個(gè)素?cái)?shù)，且0

答案

錯(cuò)誤

91.給定連通圖G,BFS遍歷得到層次圖，同一層中存在連接兩個(gè)結(jié)點(diǎn)的邊，則

G是二分圖.

答案：

錯(cuò)誤

92.剩余網(wǎng)絡(luò)中后向邊(v,w)的費(fèi)用為cost(v,w).

答案：

錯(cuò)誤

93.有下界的流通問(wèn)題一定有可行流。

答案：

錯(cuò)誤

94.將有頂點(diǎn)容量限制的頂點(diǎn)u用一條邊(u,v)代替，頂點(diǎn)u的入邊仍為u的入

邊，頂點(diǎn)U的出邊變?yōu)轫旤c(diǎn)V的出邊。(u,v)的容量等于原先頂點(diǎn)U的容量。

變換后網(wǎng)絡(luò)的最大流等于原網(wǎng)絡(luò)的最大流

答案:

正確

95.給定二分圖G二中無(wú)孤立點(diǎn)，其最大流算法求得最大流f,則G的()=f

答案：

最大匹配數(shù).最小頂點(diǎn)覆蓋

96.設(shè)G是n階無(wú)孤立點(diǎn)的圖，V*是G的最小頂點(diǎn)覆蓋，則V-V*是G的()。

答案：

最大獨(dú)立集

97.FF算法的時(shí)間復(fù)雜度是()

答案：

mnC

98.分支限界法在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)結(jié)點(diǎn)有多次機(jī)會(huì)成

為活結(jié)點(diǎn)

答案：

錯(cuò)誤

99.回溯法和分支限養(yǎng)法的主要區(qū)別在于，回溯法求取問(wèn)題的一個(gè)解或所有解。

答案:

正確

100.分支限界法不能解決0/1背包問(wèn)題

答案:

錯(cuò)誤

101.分支界限法搜索方式包含（）O

答案：

廣度優(yōu)先.最大效益優(yōu)先.最小耗費(fèi)優(yōu)先

102.用分支限界法設(shè)計(jì)算法的步驟是：

答案：

針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）以廣度優(yōu)先或以最

小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)

避免無(wú)效搜索。.確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）

103.優(yōu)先隊(duì)列分支限界法解旅行商問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（）

答案：

最小堆

104.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（）

答案：

結(jié)金的優(yōu)先級(jí)

105.裝載問(wèn)題，當(dāng)所給的問(wèn)題規(guī)模為n時(shí)，通常有2、個(gè)葉結(jié)點(diǎn)。

答案：

正確

106.下列哪個(gè)結(jié)點(diǎn)屬于回溯法的結(jié)點(diǎn)類(lèi)型？()

答案：

活結(jié)點(diǎn).死結(jié)點(diǎn).擴(kuò)展結(jié)點(diǎn)

107.回溯法的效率依賴(lài)于下列哪些因素()

答案：

計(jì)算約束函數(shù)的時(shí)間.滿足顯約束的值的個(gè)數(shù)一計(jì)算限界函數(shù)的時(shí)間

108.旅行商問(wèn)題的回溯算法所需的計(jì)算時(shí)間為0()

答案：

n!

109.SPFA算法計(jì)算時(shí)，如果一個(gè)頂點(diǎn)入隊(duì)列的次數(shù)超過(guò)n,則存在負(fù)權(quán)回路。

答案：

正確

110.矩陣連乘問(wèn)題的不同子問(wèn)題個(gè)數(shù)為0(nA2)

答案：

正確

111.貪心和遞推算法是線性解決問(wèn)題，動(dòng)態(tài)規(guī)劃則是全面分階段地解決問(wèn)題。

答案:

正確

112.Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出,

則之后不變了，修改的僅僅是源點(diǎn)到還沒(méi)選擇的頂點(diǎn)的最短路徑長(zhǎng)度。

答案:

正確

113.下面哪些問(wèn)題的動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為Q(mn)?

答案：

LCS萬(wàn)列比對(duì).SPFA算法

114.分治算法與動(dòng)態(tài)規(guī)劃算法的相同點(diǎn)是()

答案：

遞服關(guān)系.最優(yōu)子結(jié)構(gòu)

115.Floyd算法的復(fù)雜度為0()

答案：

nA3

116.0PT[i][w]=max{0PT[i-l][w],0PT[i][w-w[i]]+v[i]},這是0問(wèn)題的遞推關(guān)系。

答案：

完全0?1背包

117.給定n個(gè)元素，找其中位數(shù)的時(shí)間是。(n)

答案:

正確

118.建立n個(gè)元素的最大堆的時(shí)間為0(n)

答案:

正確

119.減治法是把一個(gè)問(wèn)題轉(zhuǎn)化成一個(gè)子問(wèn)題來(lái)解決，從子問(wèn)題的解得到原問(wèn)題的

解。

答案:

正確

120.分治法在每一層遞歸上有三個(gè)步驟()

答案：

分解一合并—解決

121.對(duì)線性表進(jìn)行折半查找最方便的數(shù)據(jù)結(jié)構(gòu)是()

答案：

有序順序表

122.大整數(shù)乘法分治算法的時(shí)間為0()

答案：

nAlog3

123.一般來(lái)說(shuō)，遞推的效率高于遞歸，因此將遞歸轉(zhuǎn)化為遞推

答案:

正確

124.有些問(wèn)題采用倒布法，容易理解和解決。

答案:

正確

125.遞推是從問(wèn)題的最終目標(biāo)出發(fā)，逐漸將復(fù)雜問(wèn)題化為簡(jiǎn)單問(wèn)題，最終求得問(wèn)

題。

答案:

錯(cuò)誤

126.遞歸算法是直接或間接地調(diào)用自身的算法。

答案:

正確

127.T(n)=T(n-l)+n,T(l)=l,則T(n)=()

答案：

Q(nA2)_n(n+l)/2_W(nA2)_(nA2)

128.遞歸變?yōu)榉沁f歸的方法有()

答案：

遞也模擬棧一尾遞歸

129.下面有關(guān)遞歸與迭代的說(shuō)法錯(cuò)誤的是()

答案：

每本遞歸算法原則上總可以轉(zhuǎn)換成與它等價(jià)的迭代算法

130.區(qū)間選點(diǎn)問(wèn)題的預(yù)處理方法是按照區(qū)間的終點(diǎn)遞增排序

答案：

正確

131,貪心算法總能找到可行解，并且是最優(yōu)解。

答案：

錯(cuò)誤

132.貪心算法的思想是尋求局部最優(yōu)解，逐步達(dá)到全局最優(yōu)解

答案：

正確

133.問(wèn)題的可行解是滿足約束條件的解

答案：

正確

134.下面不是證明貪心算法證明方法的有()o

答案：

優(yōu)化

135.蠻力法適用于問(wèn)題的小規(guī)模實(shí)例。

答案:

正確

136.在某些問(wèn)題實(shí)例中枚舉是唯一的解決方法。

答案：

正確

137.0-1背包問(wèn)題的枚舉算法，如果在百萬(wàn)次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)

算的問(wèn)題規(guī)模估計(jì)是？

答案：

40

138.從小規(guī)模問(wèn)題推解出大規(guī)模問(wèn)題的算法是()

答案：

遞推

139.使用合適的數(shù)據(jù)結(jié)構(gòu)可以同時(shí)減少時(shí)間和空間

答案：

正確

140.時(shí)間復(fù)雜度就是算法運(yùn)行的時(shí)間的度量，衡量算法的效率。

答案:

正確

141.f(n)=0(g(n))則f(nr2=0(g(n)八2)

答案：

正確

142.順序查找適合的數(shù)據(jù)結(jié)構(gòu)是()

答案：

順序存儲(chǔ)一鏈?zhǔn)酱鎯?chǔ)

143.下面程序的時(shí)間復(fù)雜度是()i=lwhile(i〈=n)doi=i*5

答案：

Q(logn)

144.設(shè)f(N)、g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自

然數(shù)NO,使得當(dāng)N>N0時(shí)有f(N)>Cg(N),則稱(chēng)函數(shù)f(N)當(dāng)N充分

大時(shí)有下界g(N),記作f(N)=W(g(N))，即f(N)的階()g(N)

的階。

答案：

不低于

145.算法復(fù)雜度分析的兩種基本方法為()和()

答案：

事后統(tǒng)計(jì)事前分析

146.問(wèn)題的兩個(gè)要素是輸入和實(shí)例。

答案：

錯(cuò)誤

147.一個(gè)問(wèn)題的同一實(shí)例可以有不同的表示形式。

答案：

正確

148.同?數(shù)學(xué)模型使用不同的數(shù)據(jù)結(jié)構(gòu)會(huì)有不同的算法，有效性有很大差別。

答案：

正確

149.計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的每個(gè)實(shí)例求解。

答案：

錯(cuò)誤

150.最大獨(dú)立集問(wèn)題和()問(wèn)題等價(jià)。

答案：

最小頂點(diǎn)覆蓋.最大團(tuán)

151問(wèn)題變換的方法有()

答案：

表達(dá)變換.問(wèn)題均簡(jiǎn)一實(shí)例簡(jiǎn)單化

152.描述算法的基本方法有()。(1)自然語(yǔ)言(2)流程圖(3)偽代碼(4)機(jī)器語(yǔ)言

答案：

B.⑴(2)(3)

153.按照霍納法則，計(jì)算p(x)=anxn+an-lxn?l+...+alxl+aO的數(shù)量級(jí)為()

答案：

154.問(wèn)題變換的目的有()。(1)復(fù)雜變簡(jiǎn)單(2)未知變已知(3)隱式變顯式(4)難

解變易解(5)以上都是。

答案：

(5)

155.算法與程序的區(qū)別是()

答案：

有窮性

156.解決問(wèn)題的基本步驟是()o(1)算法設(shè)計(jì)(2)算法實(shí)現(xiàn)(3)數(shù)學(xué)建模

(4)算法分析(5)正確性證明

答案：

⑶⑴⑸(4)(2)

157.下面說(shuō)法關(guān)于算法與問(wèn)題的說(shuō)法錯(cuò)誤的是()。

答案：

證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。

158.下面關(guān)于程序和算法的說(shuō)法正確的是()o

答案：

算上是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求解_算法的每一

步驟必須要有確切的含義，必須是清楚的、無(wú)二義的。一程序是算法用某種

程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。

159,給定兩張喜歡列表，穩(wěn)定匹配問(wèn)題的輸出是()

答案：

最二匹配.沒(méi)有不穩(wěn)定配對(duì)_完美匹配.穩(wěn)定匹配

160.給定一個(gè)實(shí)例，如果一個(gè)算法能得到正確解答，稱(chēng)這個(gè)算法解答了該問(wèn)題。

答案：

錯(cuò)誤

161.證明算法不正確，只需給出一個(gè)反例，算法不能正確處理即可。

答案：

正確

162.同一算法只有一種形式描述

答案:

錯(cuò)誤

163.算法必須在有窮時(shí)間終止

答案：

正確

164.一個(gè)問(wèn)題的算法必須在有窮時(shí)間終止，并且對(duì)一切合法的輸入都能得出滿足

要求的結(jié)果。

答案：

正確

165.下面程序的時(shí)間復(fù)雜度為()x=lfori=ltondoforj=ltoidofork=ltojdo

x++

答案：

nA3

166.對(duì)近似遞增序列的線性表從小到大排序，使用哪種方法好?

答案：

插入排序

167.給定圖G=(V,E),|V|二n,|E|二m,遍歷其鄰接表的時(shí)間復(fù)雜度為0()

答案：

n+m

168.兩個(gè)n*n的矩陣相加的時(shí)間復(fù)雜度是()

答案：

0(nA2)_0(nA2)_W(nA2)

169.f(n)=O(g(n))且g(n)=O(h(n)),則h(n)=O(f(n))

答案:

錯(cuò)誤

170.如果一個(gè)算法是多項(xiàng)式時(shí)間算法，該算法是有效的，是好算法。

答案：

正確

171.n!=o(2An)

答案：

錯(cuò)誤

172.常數(shù)階算法的運(yùn)行時(shí)間與規(guī)模n無(wú)關(guān)。

答案：

正確

173.A公司處理器速度是B公司的100倍。對(duì)于復(fù)雜度為M2的算法，B公司

的計(jì)算機(jī)可以在1小時(shí)內(nèi)處理規(guī)模為n的問(wèn)題，A公司的計(jì)算機(jī)在1小時(shí)

能處理的問(wèn)題規(guī)模是0

答案：

10n

174.直接插入排序的時(shí)間復(fù)雜度是（）。

答案：

0(nA2)

175.選擇排序的時(shí)間復(fù)雜度是0(一)

答案：

nA2

176.分?jǐn)?shù)拆分問(wèn)題的枚舉算法通過(guò)()方法進(jìn)行了優(yōu)化。

答案：

減3枚舉變量的值域.優(yōu)化數(shù)學(xué)模型.減少枚舉變量

177.枚舉算法的優(yōu)化方法有()

答案：

優(yōu)化算法.減少枚舉變量.優(yōu)化數(shù)學(xué)模型_減少枚舉變量的值域

178.冒泡排序的時(shí)間復(fù)雜度為W(nA2)

答案：

錯(cuò)誤

179.0-1背包問(wèn)題的枚舉算法的時(shí)間復(fù)雜度為0(2、)

答案:

錯(cuò)誤

180.增量構(gòu)造法生成子集前需要對(duì)集合中元素從小到大排列。

答案：

正確

181.二進(jìn)制法生成子集，子集與運(yùn)算可以生成并集

答案：

錯(cuò)誤

182.分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.

答案：

錯(cuò)誤

183.未來(lái)與過(guò)去無(wú)關(guān)指的是()的性質(zhì)

答案：

無(wú)后效性

184.使目標(biāo)函數(shù)最大(小)的解是問(wèn)題的()

答案：

最優(yōu)解

185.對(duì)于稠密圖，使用()算法計(jì)算MST更適合

答案:

Prim

186.區(qū)間調(diào)度問(wèn)題貪心算法的時(shí)間復(fù)雜度是()

答案：

O(nlogn)

187.區(qū)間問(wèn)題包含0

答案：

區(qū)間調(diào)度一區(qū)間覆蓋.區(qū)間劃分一區(qū)間選點(diǎn)

188.貪心算法總能找到可行解，但未必是最優(yōu)解。

答案：

正確

189.如果圖G中每條邊的權(quán)重都是互不相同的，圖G必定只有一顆最小生成樹(shù)。

答案：

正確

190.任意變長(zhǎng)碼的平溝碼長(zhǎng)最小

答案：

錯(cuò)誤

191.哈夫曼編碼的貪婪準(zhǔn)則是從隊(duì)列中選擇頻率最小的兩個(gè)。

答案:

正確

192.哈夫曼編碼給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的

編碼，可以大大縮短總碼長(zhǎng)。

答案：

正確

193.求解高階遞推方程一般使用()迭代方法

答案：

差消迭代

194.遞歸一般用于解決問(wèn)題有()：

答案：

易據(jù)的結(jié)構(gòu)形式是按遞歸定義的一數(shù)據(jù)的定義是按遞歸定義的。.問(wèn)題解法按

遞歸實(shí)現(xiàn)。

195.求解快速排序時(shí)間復(fù)雜度使用的方法有()

答案：

迭A法.遞歸樹(shù).主定理_歸納法

196.尾遞歸中的遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語(yǔ)句且它的返回值不屬于表

達(dá)式的一部分。

答案：

正確

197.一般來(lái)說(shuō)，遞歸的效率高于遞推。

答案:

錯(cuò)誤

198.每個(gè)遞歸算法原則上總可以轉(zhuǎn)換成與它等價(jià)的迭代算法，反之不然。

答案：

錯(cuò)誤

199.由結(jié)果倒過(guò)來(lái)推解前提條件是倒推方法的一種。

答案：

正確

200.迭代法從原始遞布方程出發(fā)，反復(fù)將對(duì)應(yīng)方程左邊的函數(shù)用右邊等式帶入,

直至得到初值，然后將所得的結(jié)果化簡(jiǎn)。

答案：

正確

201.快速排序和插入徘序最好情況卜的時(shí)間復(fù)雜度是0(nlogn)

答案：

錯(cuò)誤

202.設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元

素，最好選用()法。

答案：

冒泡排序

203.軍事上迂回包圍、穿插分割、各個(gè)殲滅是（）思想。

答案:

分治

204.矩陣C中每一行選一個(gè)元素，使選擇的元素不同列，并且元素之和最小。

Job1Job2Job3Job4Persona9568Personb6437Personc5818Persond7

694最小元素和為最小元素和對(duì)應(yīng)的安拉?是a安排job、b安排job

_、c安排job一、d安排job_如果人數(shù)和任務(wù)數(shù)為n,時(shí)間復(fù)雜度是

答案：

16;2;l;3;4;n!

205.給定?個(gè)數(shù)字三角形，從頂至底有多條路徑，每?步可沿左斜線向下或沿右

斜線向下，路徑所經(jīng)過(guò)的數(shù)字之和為路徑得分，請(qǐng)求出最小路徑得分和相應(yīng)

路徑。738840274445265⑴該問(wèn)題最好使用（）算法求解？A動(dòng)態(tài)規(guī)

劃算法B貪心算法C枚舉算法D分治算法（2）最小路徑得分是_（相應(yīng)路徑

經(jīng)過(guò)的數(shù)字為_(kāi)_、—、—、—、—。［從頂?shù)降祝?/p>

答案：

A;20;7;3;4;4;2

2O6.T(n)=4T(n/2)+n,T(l)=l,則T(n)=Q(_)

答案：

nA2

207.下面程序的時(shí)間復(fù)雜度為0()k=lwhilen>=ldofori=ltondok=k+l

n=n/2returnk

答案:

208.調(diào)用一個(gè)偏真的蒙特卡羅算法，只要返回一次true,就可得到正確解。重復(fù)

調(diào)用4次，正確率從55%提高到95%,調(diào)用6次，提高到99%.

答案：

正確

209.增加蒙特卡羅算法的求解次數(shù)，可使求解錯(cuò)誤的概率任意小。

答案：

正確

210.當(dāng)最壞和平均情況差別較大時(shí),舍伍德算法可.以消除好壞實(shí)例的差別，達(dá)到

平均實(shí)例的性能.

答案：

正確

211.現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)

答案：

正確

212.拉斯維加斯算法肯定得到正確解或找不到解，一旦找到一個(gè)解，一定是正確解。

答案：

正確

213.分支限界算法的活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。

答案:

正確

214.使用限界函數(shù)作優(yōu)先級(jí)，第一個(gè)加入隊(duì)列的□?子就是最優(yōu)解

答案：

錯(cuò)誤

215.分支限界法以深度優(yōu)先的方式搜索解空間樹(shù)。

答案：

錯(cuò)誤

216.活結(jié)點(diǎn)是自身已生成，但其兒子還沒(méi)有全部生成的結(jié)點(diǎn)

答案：

正確

217.DAG動(dòng)態(tài)規(guī)劃算法中反推的開(kāi)始點(diǎn)是無(wú)山邊的頂點(diǎn)

答案：

正確

218.最大權(quán)獨(dú)立集包含結(jié)點(diǎn)u,不可能包含其兒子結(jié)點(diǎn)。

答案：

正確

219.不基于元素比較的排序算法可以在線性時(shí)間實(shí)現(xiàn)。

答案:

正確

220.遞歸方程是遞歸函數(shù)的要素之一

答案：

正確

221.遞歸是從問(wèn)題的最終目標(biāo)出發(fā)，逐漸將復(fù)雜問(wèn)題化為簡(jiǎn)單問(wèn)題，最終求得問(wèn)

題。

答案：

正確

222.把目標(biāo)函數(shù)作為貪婪準(zhǔn)則得到的解不一定是問(wèn)題的最優(yōu)解

答案：

正確

223.最小生成樹(shù)是唯一的。

答案：

錯(cuò)誤

224.如果圖G中每條邊的權(quán)重都是互不相同的，圖G可能存在多顆最小生成樹(shù)。

答案：

錯(cuò)誤

225.子集生成算法中一般需要對(duì)集合元素進(jìn)行定序。

答案：

正確

226.減少枚舉變量的值域可以減少枚舉算法的時(shí)間復(fù)雜度。

答案：

正確

227.求101og3An的漸進(jìn)表達(dá)式是6(n)

答案：

正確

228.21+1/n的漸進(jìn)表達(dá)式是0(1)

答案：

正確

229.f=o(g)且g=o(h)則f=o(h)

答案：

正確

23O.T(n)=l+l/2+l/3...+l/n=Q(lnn)

答案：

正確

231.好算法具有如下特性:當(dāng)輸入規(guī)模加倍時(shí)，算法降低C倍，C為常數(shù)。

答案:

正確

232.f(n)=3nA3+7nA2+4nlogn=W(nA2)

答案:

正確

233.時(shí)間復(fù)雜度是指算法最好情況下的運(yùn)行時(shí)間。

答案:

錯(cuò)誤

234.通過(guò)減少子問(wèn)題個(gè)數(shù)，降低分治算法時(shí)間復(fù)雜度的有（）

答案：

Strassen矩陣乘法大整數(shù)乘法

235.三分法的判定樹(shù)是三義樹(shù)

答案

正確

236.減治法減一個(gè)常量就是每次迭代減去一個(gè)相同的常數(shù)因子（一般為2）

答案:

錯(cuò)誤

237.改進(jìn)子問(wèn)題合并的時(shí)間復(fù)雜度可以減少分治算法的時(shí)間。

答案:

正確

238.任何基于元素比較的排序算法的時(shí)間復(fù)雜度＞=61ogn!立二Q(nlogn)

答案：

正確

239,給定n個(gè)元素，使用分治算法找k小元素，如果保證分治的兩個(gè)子數(shù)組中

最小的數(shù)組是原數(shù)組的￡倍，時(shí)間復(fù)雜度可.以由nlogn降低為n

答案：

正確

240.問(wèn)題A的實(shí)例可以變換為另一個(gè)問(wèn)題B的實(shí)例。如果問(wèn)題B的求解算法是

已知的，那么問(wèn)題A也可以求解。

答案：

正確

241.證明算法不正確，需要證明對(duì)任意實(shí)例算法都不能正確處理。

答案：

錯(cuò)誤

242.如果一個(gè)算法能應(yīng)用于問(wèn)題的任意實(shí)例，并保證得到正確解答，稱(chēng)這個(gè)算法

解答了該問(wèn)題。

答案:

正確

243.同一問(wèn)題可能有幾種不同的算法，解題思路和解題速度也會(huì)顯著不同。

答案：

正確

244.肯定獲得解，但不一定是準(zhǔn)確解的算法是()o

答案：

數(shù)值隨機(jī)算法.蒙特卡羅算法

245.下列算法中能解決0/1背包問(wèn)題的是()

答案：

動(dòng)會(huì)規(guī)劃.分支限界法一回溯法

246.()肯定獲得最優(yōu)解。

答案：

枚舉算法.回溯算法

247.關(guān)于帶需求的流通下面說(shuō)法正確的是()o

答案：

對(duì)于任意邊eiE:O￡f(e)￡c(e)_供給和二需求和

248.給定二分圖G=中無(wú)孤立點(diǎn)，|V|=n,其最大流算法求得最大流f,則G的（）

答案：

最余頂點(diǎn)覆蓋.最大匹配數(shù)

249.0PTQ,w）:從1-i種物品中選擇，放入容量為w的背包時(shí)的最大價(jià)值。這

是（）問(wèn)題動(dòng)態(tài)規(guī)劃算法的遞推函數(shù)。

答案：

多重0/1背包.完全0/1背包

250.動(dòng)態(tài)規(guī)劃算法的特點(diǎn)（）

答案：

子問(wèn)題重疊一自底向上計(jì)算

251.動(dòng)態(tài)規(guī)劃算法的基本要素有（）和最優(yōu)子結(jié)構(gòu)性質(zhì)。

答案：

重疊子問(wèn)題性質(zhì)

252.下面不是動(dòng)態(tài)規(guī)劃的基本方法有（）。

答案：

舍入

253.動(dòng)態(tài)規(guī)劃方法使用（）計(jì)算方式。

答案：

自底向上

254.0PT(i,w):從1-i個(gè)物品中選擇，放入容量為w的背包時(shí)的最大價(jià)值。這

是()問(wèn)題動(dòng)態(tài)規(guī)劃算法的遞推函數(shù)。

答案：

0/1、背包.恰好裝滿的0/1背包

255.區(qū)間動(dòng)態(tài)規(guī)劃的計(jì)算次序是()

答案：

先小規(guī)模后大規(guī)模.先小區(qū)間后大區(qū)間

256.給定n個(gè)報(bào)告(編號(hào)1-n)和一個(gè)報(bào)告廳，每人報(bào)告的開(kāi)始時(shí)間si和結(jié)束時(shí)間

fi,(si,fi)I{(1,2)、(1,3)、(1,4)、(2,5)、(3,7)、(4,9)、

(5,6)、(6,8：、(7,9)},求最多可以安排的報(bào)告數(shù)和相應(yīng)報(bào)告。⑴

該問(wèn)題最好使用()算法求解。A枚舉B貪心C分治D動(dòng)態(tài)規(guī)劃(2)最多可

以安排的報(bào)告是_、__、

答案：

B;l;4;7;8

257.部分背包問(wèn)題，背包容量c=20,物品1,2...n,對(duì)應(yīng)的物品價(jià)值p=[4,8,

15,1,6,3],對(duì)應(yīng)的物品重量w=[5,3,2,10,4,8],求裝入背包的最大價(jià)值

和裝入物品。(1)該問(wèn)題最好使用()算法求解。A枚舉B貪心C分治D

遞推(2)裝入背包的最大價(jià)值是一(3)裝入背包的最大價(jià)值對(duì)應(yīng)的完整

物品是—、—、—、—O(編號(hào)從小到大)

答案：

B;35.25;l;2;3;5

258.T(n)=3T(n/4)+nlogn,T(l)=l,則T(n)=Q(_)

答案:

nlogn

259.設(shè)G=中無(wú)孤立點(diǎn)，|V|=n,則邊覆蓋數(shù)+匹配數(shù)=n

答案:

正確

260.給定網(wǎng)絡(luò)N=(V,E)的一個(gè)流f,任意一個(gè)節(jié)點(diǎn)滿足流出量等于流入量

答案:

錯(cuò)誤

261,隊(duì)列式分支限界以最大效益優(yōu)先方式產(chǎn)生狀態(tài)空間樹(shù)的結(jié)點(diǎn)。

答案:

錯(cuò)誤

262.如果解空間樹(shù)中，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n),則回溯法

所需的計(jì)算空間通常為O(h(n))。顯式地存儲(chǔ)整個(gè)解空間則需要0(2八h(n))

或O(h(n)!)內(nèi)存空間。

答案:

正確

263.回溯法為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，不斷地利用限界函

數(shù)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。

答案:

正確

264.回溯法搜索解空間時(shí)，在其它條件相當(dāng)?shù)那疤嵯拢尶扇≈底钌俚膞[i]優(yōu)先,

可以減少計(jì)算。

答案:

正確

265.對(duì)于稠密圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)

行n次SPFA算法

答案:

正確

266.DAG動(dòng)態(tài)規(guī)劃算法中正推的開(kāi)始點(diǎn)是無(wú)入邊的頂點(diǎn)

答案：

正確

267.一般來(lái)說(shuō)，迭代的效率高于遞歸

答案：

正確

268.每個(gè)迭代算法原則上總可以轉(zhuǎn)換成與它等價(jià)的遞歸算法；反之不然

答案:

正確

269.f=n(g)且g=C(h)則f=n(h)

答案:

正確

270.兩個(gè)n*n的矩陣相乘的時(shí)間復(fù)雜度是W(n9)

答案:

錯(cuò)誤

271.分塊查找適應(yīng)于分塊有序的順序存儲(chǔ)結(jié)構(gòu)或線性鏈表。

答案:

正確

272.計(jì)算機(jī)每次求解只是針對(duì)一個(gè)實(shí)例求解，問(wèn)題的描述針該問(wèn)題的所有實(shí)例。

答案:

正確

273.動(dòng)態(tài)規(guī)劃算法的基本要素有()。

答案：

無(wú)后效性.最優(yōu)子結(jié)構(gòu)性質(zhì).重疊子問(wèn)題性質(zhì)

274.下面描述分治算法正確的是()

答案：

最小堆中每個(gè)元素調(diào)整的次數(shù)不超過(guò)樹(shù)高Q(logn)。_二分法子問(wèn)題不獨(dú)立

的情況可以使用分治算法計(jì)算，但計(jì)算量大。一三分法的判定樹(shù)是三叉樹(shù)

275.求解遞推方程的方法有()

答案：

迭府法.遞歸樹(shù)一歸納法.主定理

276.貪心算法的常用證明方法有()o

答案：

反證.交換論證_界.領(lǐng)先

277.對(duì)于含有n個(gè)元素的排列樹(shù)問(wèn)題，最壞情況下其解空間的葉結(jié)點(diǎn)數(shù)目為

()O

答案：

n!

278.下面分治算法的說(shuō)法正確的是()

答案：

分治法的設(shè)計(jì)思想是大事化小，各個(gè)擊破，分而治之。一減治法是把一個(gè)問(wèn)

題轉(zhuǎn)化成一個(gè)子問(wèn)題來(lái)解決。一每次都將問(wèn)題分解為原問(wèn)題規(guī)模的一半進(jìn)行

求解，稱(chēng)為二分法

279.改進(jìn)分治算法的方法有()

答案：

改進(jìn)分治的均衡度.減少子問(wèn)題的個(gè)數(shù).減少合并的時(shí)間

280.分治算法的適用條件有()o

答案:

小規(guī)模子問(wèn)題可解_問(wèn)題可以分解為規(guī)模較小的子問(wèn)題一子問(wèn)題相互獨(dú)立一子

問(wèn)題可合并為問(wèn)題的解

281.最好情況下，時(shí)間復(fù)雜度為0(n)的排序算法有()

答案：

插入排序.冒泡排序.計(jì)數(shù)排序

282.時(shí)間復(fù)雜度為0(M2)的排序算法有()

答案：

直接選擇排序.冒泡排序.快速排序.插入排序

283.時(shí)間復(fù)雜度為O(nlogn)的排序算法有()

答案：

堆排序_合并排序

284.通過(guò)降低子問(wèn)題合并時(shí)間，降低分治算法時(shí)間復(fù)雜度的有()

答案：

大整數(shù)乘法.最接近點(diǎn)對(duì)—計(jì)數(shù)逆序

285.貪心算法的基本要素是()

答案：

貪心選擇的性質(zhì).無(wú)后效性性質(zhì).最優(yōu)子結(jié)構(gòu)性質(zhì)

286.子集生成方法有()

答案：

增量構(gòu)造法.二進(jìn)制法一位向量法

287.下面時(shí)間復(fù)雜度的描述正確的是()

答案：

從n個(gè)數(shù)中查找最小值的時(shí)間復(fù)雜度為O(n)_k)gn!=e(nlogn)

288.問(wèn)題變換的目的和方式有()o

答案：

復(fù),變簡(jiǎn)單.未知變已知_難解變易解.隱式變顯式

289.算法的性質(zhì)有()

答案：

確定性_有窮性.輸出一輸入

290.動(dòng)態(tài)規(guī)劃算法把原問(wèn)題分為交叉的子問(wèn)題，解決子問(wèn)題，記錄子問(wèn)題的解,

合并為原問(wèn)題的解。

答案:

正確

291.0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。

答案:

錯(cuò)誤

292.通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題規(guī)模呈多項(xiàng)式增長(zhǎng)。動(dòng)態(tài)規(guī)劃算法對(duì)于每個(gè)子

問(wèn)題求解一次，并保存子問(wèn)題結(jié)果，因此只需要多項(xiàng)式時(shí)間。

答案:

正確

293.0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法可以使用一維數(shù)組實(shí)現(xiàn)。

答案:

正確

294.矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣連乘，不同的計(jì)算次序計(jì)算量相同。

答案:

錯(cuò)誤

295.回溯算法和分支限界法的問(wèn)題的解空間樹(shù)不會(huì)是（）。

答案：

無(wú)序樹(shù)

296.下面哪種函數(shù)不是回溯法中為避免無(wú)效搜索采取的策略（）

答案：

遞后函數(shù)

297.備忘錄與遞歸算法的不同點(diǎn)是（）

答案：

子問(wèn)題重疊

298.Bellman算法的時(shí)間復(fù)雜度為0()

答案：

mn

299.隨機(jī)快速排序的時(shí)間復(fù)雜度是()o

答案：

0(nlogn)

300.下面有關(guān)遞歸與循環(huán)的說(shuō)法錯(cuò)誤的是()

答案：

遞后方法相比循環(huán)方法大大地減少了算法的計(jì)算量。

301.給定圖G=(V,E),|V|=n,|E|=m,其鄰接表的空間復(fù)雜度為0()

答案：

m+n

3O2.nA2/3=()(n+nlogn)

答案：

3O3.(6n+5)=()(nA2-n)/2

答案：

o

304.下列算法中，通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（）。

答案：

回溯法

305.下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（）

答案：

剪枝函數(shù)

306.裝載問(wèn)題的回溯算法所需的計(jì)算時(shí)間為。（）

答案：

2An

307.下面有關(guān)動(dòng)態(tài)規(guī)劃算法錯(cuò)誤的是

答案：

0-1、背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算法。

308.可能獲得解，且一定是準(zhǔn)確解的算法是（）o

答案：

拉加維加斯算法

309.下面說(shuō)法錯(cuò)誤的是()

答案：

舍后德算法總是有解，且解總是正確的，改進(jìn)了算法的平均性能。

310.備忘錄與動(dòng)態(tài)規(guī)劃算法的不同點(diǎn)是()

答案：

自而向下計(jì)算

311.動(dòng)態(tài)規(guī)劃和分治算法的共同點(diǎn)是

答案：

最屆子結(jié)構(gòu)性質(zhì)

312.動(dòng)態(tài)規(guī)劃方程M[i,j]=min(M[i,k]+M[k,j]+wij),l<i<k<j<n,則算法的則算法

的時(shí)間復(fù)雜度為()。

答案：

nA3

313.Floyd算法的時(shí)間復(fù)雜度為0()

答案：

nA3

314.減少子問(wèn)題合并的時(shí)間，就是減少時(shí)間復(fù)雜度函數(shù)T(n)-aT(n/b)+f(n)中的

()值。

答案:

f(n)

315.Strassen矩陣乘法分治算法的時(shí)間為()

答案：

nAlog7

316.中印戰(zhàn)爭(zhēng)西山口戰(zhàn)役劉伯承提出的“打頭、截尾、剖腹、擊背”是()思想。

答案：

分治

317.兩個(gè)n/2長(zhǎng)度的有序數(shù)組合并為新的有序數(shù)組的時(shí)間為()

答案：

n

318.插入排序的時(shí)間復(fù)雜度是()o

答案：

0(nA2)

319.未來(lái)與過(guò)去無(wú)關(guān)，指的是無(wú)()性質(zhì)。

答案：

無(wú)后效性

320.原問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解，這是()性質(zhì)

答案?

最加子結(jié)構(gòu)

321.0-1背包問(wèn)題的枚舉算法，如果在萬(wàn)億次每秒的計(jì)算機(jī)上運(yùn)行，1年可以計(jì)

算的問(wèn)題規(guī)模估計(jì)是？

答案：

60

322.()生成子集，便于實(shí)現(xiàn)集合的操作。

答案：

二進(jìn)制法

323.分塊查找256個(gè)元素的數(shù)組，每塊的最佳長(zhǎng)度是

答案：

16

324.假設(shè)算法A的計(jì)算時(shí)間為T(mén)(n)=n^2在計(jì)算機(jī)A上輸入規(guī)模為n時(shí)算法A

的運(yùn)行時(shí)間為t秒。計(jì)算機(jī)B的運(yùn)行速度是A的64倍，在t秒時(shí)間計(jì)算機(jī)

B運(yùn)行算法A的輸入規(guī)模是一

答案：

8n

325.哈夫曼編碼的平溝碼長(zhǎng)最小

答案：

正確

326.假設(shè)算法A的計(jì)算時(shí)間為T(mén)(n)=2=,在計(jì)算機(jī)A上輸入規(guī)模為n時(shí)算法A

的運(yùn)行時(shí)間為t秒。計(jì)算機(jī)B的運(yùn)行速度是A的64倍，在t秒時(shí)間計(jì)算機(jī)

B運(yùn)行算法A的輸入規(guī)模是一

答案：

n+6

327.下面不是以空間浜時(shí)間的方法有()

答案?

數(shù)據(jù)壓縮

328.下面描述錯(cuò)誤的是()

答案：

空間復(fù)雜度是算法執(zhí)行所需所有空間的資源量。

329.f(n)=Q(g(n)),則g(n)為f(n)的()

答案：

下界

330.給定n個(gè)元素的數(shù)組A,n=l(T3,使用折半查找比使用順序查找大約快一倍。

答案：

100

331.待排序文件基本有序時(shí)，下面哪種排序方法，效率最差?

答案：

快速排序

332.待排序文件基本有序時(shí)，下面哪種排序方法，效率最高?

答案：

冒泡排序

333.(logn!)=()(nA3/2)

答案：

334.1ognA2=()(nAl/2)

答案：

o

335.從長(zhǎng)度為n的數(shù)組中多次查找數(shù)據(jù)，使用（）方法好?

答案：

排諄后折半查找

336.設(shè)p是一個(gè)實(shí)數(shù)，且1/2

答案：

正確

337.蒙特卡羅算法的結(jié)果肯定是?個(gè)正確解。

答案：

錯(cuò)誤

338.借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌,

可收到舍伍德算法的效果。

答案：

正確

339.對(duì)于給定的正整數(shù)n,判定n是一個(gè)素?cái)?shù)的充要條件是(41)塢-l(modn)。

答案：

正確

340.在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除

這種影響可用()對(duì)輸入進(jìn)行預(yù)處理。

答案：

舍伍德算法

341.我們講的時(shí)間復(fù)雜度是()情況下的時(shí)間復(fù)雜度。

答案：

最壞

342.問(wèn)題的狀態(tài)生成法有。

答案：

深展優(yōu)先生成法.寬度優(yōu)先生成法

343.回溯法解題步驟:

答案：

針對(duì)所給問(wèn)題，定義問(wèn)題的解空間一確定易于搜索的解空間結(jié)構(gòu).以深度優(yōu)先

方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。

344.回溯法是按廣度優(yōu)先策略搜索解空間樹(shù)。

答案:

錯(cuò)誤

345.回溯法中，如果解空間樹(shù)是子集樹(shù)，當(dāng)所給的問(wèn)題規(guī)模為n時(shí)，通常有

2人n個(gè)葉結(jié)點(diǎn)，遍歷子集樹(shù)需0(2?)計(jì)算時(shí)間。

答案:

正確

346.回溯法不適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。

答案:

錯(cuò)誤

347.回溯法的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。

答案:

正確

348.旅行商問(wèn)題的限界函數(shù)是當(dāng)前路＞已記錄最小路程bestc

答案:

正確

349.下列算法中不能解決0/1背包問(wèn)題的是()

答案：

貪心法

350.FIFO是()的搜索方式。

答案：

分支限界

351.采用最大效益優(yōu)先搜索方式的算法是()o

答案.

分壬界限法

352.分支限界法與回溯法的不同點(diǎn)是什么？

答案：

搜索方式不同_存儲(chǔ)空間的要求不同.對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同一求解目標(biāo)

不同

353.設(shè)G二中無(wú)孤立點(diǎn)，M是G的最大匹配，N為G的最小邊覆蓋，貝ijMnN=0

答案：

錯(cuò)誤

354.層次網(wǎng)絡(luò)為剩氽圖基礎(chǔ)上的最短路徑圖。從源點(diǎn)出發(fā)，到達(dá)終點(diǎn)，肯定是最

短路徑。

答案：

正確

355.設(shè)G=中無(wú)孤立點(diǎn)。W為G的最小邊覆蓋，若G中存在相鄰邊就移去其中一

條。設(shè)移去的邊集為N,則W-N是G的最大匹配。

答案:

正確

356.有下界的流通問(wèn)題不一定有可行流。

答案:

正確

3S7.存在割（A,用使流值v（Q=割的容量cap（A,B）.,貝I」割（A,R）是最小割。

答案:

正確

358.改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過(guò)選擇（）增廣路，降低時(shí)間復(fù)雜度。

答案：

最去容量一最大瓶頸容量.最短路徑一邊數(shù)最少

359.使用限界函數(shù)作優(yōu)先級(jí)，第一個(gè)擴(kuò)展的葉子就是坡優(yōu)解

答案:

正確

360.分支限界法在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)結(jié)點(diǎn)有多次機(jī)會(huì)成

為活結(jié)點(diǎn)。

答案：

錯(cuò)誤

361.分支限界法解旅行商問(wèn)題時(shí)的解空間樹(shù)是（）。

答案：

排列樹(shù)

362.擴(kuò)展結(jié)點(diǎn)是所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)。

答案：

錯(cuò)誤

363.死結(jié)點(diǎn)是正在產(chǎn)生兒子的結(jié)點(diǎn)

答案：

錯(cuò)誤

364.旅行商問(wèn)題使用（）進(jìn)行剪枝。

答案：

下界函數(shù)一剪枝函數(shù).約束函數(shù)

365.剪枝函數(shù)包括（）和約束函數(shù)。

答案：

限界函數(shù)

366.狀態(tài)轉(zhuǎn)移方程表示狀態(tài)間的遞推關(guān)系，也是子問(wèn)題間的遞推關(guān)系。

答案：

正確

367.DAG圖最長(zhǎng)路的遞推函數(shù)d⑴表示從某個(gè)頂點(diǎn)i出發(fā)的最長(zhǎng)路長(zhǎng)度。

答案：

正確

368.確定第i階段的收益函數(shù)和從第1階段出發(fā)到第i階段末所獲得收益的最優(yōu)

值，建立動(dòng)態(tài)規(guī)劃基本方程。這種方法是()

答案：

正推

369.存在O(n2.376)時(shí)間的矩陣乘法分治算法

答案：

正確

370.最小堆中每個(gè)元素調(diào)整的次數(shù)不超過(guò)樹(shù)高Q(logn)。

答案：

正確

371.N個(gè)元素排序的時(shí)間復(fù)雜度不可能是線性時(shí)間。

答案：

錯(cuò)誤

372.分治法分解的子問(wèn)題與原問(wèn)題形式相同。

答案：

正確

373.減治法常見(jiàn)的形式有()

答案：

減可變規(guī)模一減一個(gè)常量一減一個(gè)常量因子

374.減少子問(wèn)題個(gè)數(shù)，就是減少時(shí)間復(fù)雜度函數(shù)T(n)=aT(n/b)+f(n)中的()值。

答案：

a

375.合并排序的時(shí)間復(fù)雜度是()

答案：

nlogn

376.遞歸是從簡(jiǎn)單問(wèn)題出發(fā)，一步步的向前發(fā)展，最終求得問(wèn)題，是正向的。

答案：

錯(cuò)誤

377遞歸函數(shù)的要素是()

答案：

邊界條件.遞歸方程

378.下面說(shuō)法正確的是()

答案：

用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。一回溯和分支限界都是動(dòng)態(tài)生成解空

間樹(shù)用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)

379.優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)，選取優(yōu)先級(jí)最高的結(jié)

點(diǎn)，成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。

答案:

正確

380.分支限界法與回溯法都是在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題的解，二者搜索

方式不同，但求解目標(biāo)相同。

答案:

錯(cuò)誤

381.解決旅行商問(wèn)題，采用的是優(yōu)先隊(duì)列式分支限界法。

答案:

正確

382.優(yōu)先隊(duì)列式分支限界為了加速搜索的進(jìn)程，按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí),

選取優(yōu)先級(jí)最高的結(jié)點(diǎn)，成為當(dāng)前擴(kuò)展結(jié)點(diǎn)

答案:

正確

383.貪心法處理問(wèn)題的核心是貪婪準(zhǔn)則的選取

答案:

正確

384.設(shè)C是一個(gè)環(huán)，f是C中的最大邊，那么最小生成樹(shù)中肯定包含f.

答案：

錯(cuò)誤

385.分支界限法采用深度優(yōu)先策略搜索。

答案：

錯(cuò)誤

386.Dinic算法的時(shí)間復(fù)雜度為()

答案：

mnA2

387.如果每條邊的最大容量為1,則時(shí)間復(fù)雜度是0(nm)的網(wǎng)絡(luò)流算法有()

答案：

FF算法

388,有下界的流通問(wèn)題，轉(zhuǎn)換為帶需求的流通問(wèn)題有可行的流通，下面錯(cuò)誤的是

()

答案：

每翥邊的流量不變

389.改進(jìn)FF網(wǎng)絡(luò)