算法理論知識考核試題

一.選擇題

1.2n=0(100n2)［單■*

A.正確

B.錯誤V

2.1O=0(loglO)［單選題］*

A.正確V

B.錯誤

3.2n=0(3n)。()［單選題］*

A.正確V

B.錯誤

4.logn2=6(logn+5)［單選題］*

A.正確V

B.錯誤

5.針對JII頁序查找算法，影響它時間復雜度的因素只有算法的輸入序列()［單選題］*

A.正確

B.錯誤V

6.n!的時間復雜度為0(n)［單選題］*

A.正確V

B.錯誤

7.遞歸是指自己間接或直接調用自身［單選題］*

A.正確V

B.錯誤

8.算法的基本特征有（）［多選題］*

A.輸入V

B.輸出。

C.有限性V

D.確定性V

E.可行性V

9.漸進復雜性的含義是（）情況下的復雜性。［單選題］*

A.在最佳輸入情況下

B.問題規模趨向于無窮V

C.在最嗝入情況下

D.平均各種輸入之后

lO.n個連續自然數al...an連加和問題算法（利用等差數列求和公式）的輸入可以是什么（\［多選

題］*

A.al,nV

B.an.nV

C.al,anV

D.al,an,nV

11.平均時間復雜度是指（）：單選題］*

A.各種情況時間復雜度按概率的加權平均V

B.最好情況和最壞情況的時間復雜度的算術平均

C.各種情況時間復雜度按概率的算術平均

D.出現可能性最高的情況下的時間復雜度

12.算法的常見描述方式不包括（）［單選題］*

A.代碼

B.甘特圖V

C.偽代碼

D.漸呈圖

13.算法的基本特性不包括（）［單選題］*

A.先進性V

B.有窮性

C.有輸入輸出

D.無二義性

14.階乘問題求n!算法的時間復雜度為（I［單選題］*

A.nV

B.n!

C.2n

D.nA2

15.二分搜索（二分查找）算法的時間復雜度是（\［單選題］*

A.n

B.lognV

C.nA2

C.單位重量價值大的優先裝V

D.以上都不對

19.調度問題的算法設計策略是()[單選題]*

A.加工時間短的優先安排V

B.加工時間長的優先安排

C,等待時間短的優先安排

D.以上都不對

2O.n個元素的冒泡排序代碼如下：

defbubble_sort(arr):

foriinrange(len(arr)-1):

forjinrange(len(arr)-i-1):

ifarr[j]>arr[j+1]:

arr[j],arr[j+1]=arr[j+1],arr[j]

returnarr

請分析算法的時間復雜度，用。表示()[單選題]*

A.0(1)

B.0(n)

C.O(n的平方)V

D.O(nlogn)

21.百元買白雞問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，則翁、母、

雅各幾何？設計一算法，則該算法的輸入是()[單選題]*

A.100元

B.100只雞

C.各種雞的單價

D.無需任何輸入V

22.下面算法最好情況下的時間復雜度—，最壞情況下的時間復雜度為一

defbubble_sort(nums):

foriinrange(len(nums)-1):

swap_flag=False#改進后的冒泡，設置一個交換標志位

forjinrange(len(nums)-i-1):

ifnums[j]>nums[j+l]:

nums[j],nums[j4-l]=nums[j+l],nums[j]

swap_flag=True

ifnotswap_flag:

returnnums#若沒有元素交換,則表示已經有序

returnnums[單選題]*

A.O(n)、O(n2)V

23以下遞歸程序fun(5Q)輸出的第T元素是—,求解過程中最大層次為—

deffun(i,d):

if(i>landi%2!=0):

fun(i-i//2,d+l)

if(i>l):

fun(i//2,d+l)()[單選題]*

A.ls4V

24.斐波那契數列的第1項為1,第2項為2,以后每一項等于前面兩項之和，則第6項為—［單選題］

A.13V

25.冒泡排序時間復雜度是一，堆排序時間復雜度是［單選題］*

2

A.nxnlognV

26.遞歸算法必須具備的兩個條件是一和()［單選題］*

A.邊界條件或停止條件、遞推方程或遞歸方程V

27.求遞推方程得到的解是()［單選題］*

A.O(nlogn)V

28.求遞推方程得到的解是［單選題］*

A.O(logn)V

29.求遞推方程的解是()［單選題］*

A.O(n的平方)V

30.求遞推方程得到的解是()［單選題］*

A.O(logn)V

31.求遞推方程的解是(”單選題］*

A.O(nA2)V

32.物品可以切割的背包問題的最佳貪心策略不一定能保證裝入背包的物品總價值最大"()［單選題］*

正確

錯誤V

33.設字符ml,m2的查閱頻率依次為:0.05,0.01,0.01,0.10,0.03,0.17,C.02,0.24,

0.31,0.06。試構造對應的哈夫曼(Haffman)編碼，并畫出相應的編碼樹，同時寫出ml,m2,...ml0的編碼。

()［單選題］*

A.每個字符的編碼為從根節點到該字符所在葉子結點的路徑上的0,1組成的串。V

34.在10000個元素中找到前100個最大的元素，如果使用以下某個數據結構作為輔助,比較合適的

是。()［單選題］*

A.堆，

B.并查集

C.循環鏈表

D.哈希表

35.給定下面的有向、連通帶權圖用dijkstra算法，找從源點1到其他各個頂點的最短路徑。算法運

行若干步以后，得到各數據結構的數據如下(數組下標從1開始,表示頂點編號)：下標112234567

88S11010110dist028163311pre01217147根據當前狀態,可判斷從初始狀態到當前

狀態已經做了()次貪心選擇。()［單選題］*

A.1

B.2

C.3

D.4V

.用算法求解上圖的最小生成樹，初始時，集合集合第六步貪心選

36PrimS=(a),V-S={b,c/d,e/frg),

擇的邊是(工()［單選題］*

A.(a,b)

B.(c,d)V

C.(b,c)

D.(Qf)

37.用Prim算法求解上圖的最小生成樹，初始時，集合S={a},集合V-S={b,c,d,e,f,g}，第三步貪心選

擇的邊是(>()［單選題］*

A.(a,b)

B.(b,c)

C.(c,d)

D.(c,f)V

38.用Prim算法求解上圖的最小生成樹，初始時，集合S={a},集合V-S={b,c,d,e,f/g),第一步貪心選

擇的邊是(1()［單選題］*

A.(a,b)V

B.(b,c)

C.(c,d)

D.(c,f)

39.用Kurskal算法求解上圖的最小生成樹，第一步貪心選擇的邊是(1()［單選題］*

A.(a,b)

B.(b,c)

C.(c,g)

D.(c,f)V

40.給定一個有向連通帶權圖G=(V,E),n個頂點，。條邊Qijsktra算法的時間復雜度為心()［單選題］*

A.O(n2)V

B.O(n3)

C.O(eloge)

D.O(nlogn)

41.背包問題:n個物品和1個背包。對物品i,其價值為vi,重量為wi,背包的容量為W。如何選取物品裝

入背包，使背包中所裝入的物品的總價值最大?物品可以分割。該問題的貪心策略是()。()［單選題］*

A.重量小的優先裝入背包

B.體積小的優先裝入背包

C.價值大的優先裝入背包

D.單位重量的價值大的優先裝入背包V

42調度問題有n個客戶帶來n項任務每項加工時間已知，設為tij=l,2，…,n。從0時刻開始，陸續安排

到一臺機器上加工。每個任務的完成時間是從0時刻到該任務加工完成的時間。為了使盡可能多的客戶滿

意,我們希望找到是的總等待時間最少的調度方案。該問題的貪心策略是()。()［單選題］*

A.加工時間長的優先安排

B.加工時間短的優先安排V

C.完成時間早的優先安排

D.等待時間長的優先安排

43.找零錢問題的貪心策略是0。()［單選題］*

A.面值大的錢幣優先找出

B.面值小的錢幣優先找出

C.面值小于待找錢數且面值最大的優先找出，

D.以上都不對

44.物品不可拆開的最優裝載問題的貪心策略是()。()［單選題］*

A.體積大的集裝箱優先裝

B.體積小的集裝箱優先裝

C,重量大的集裝箱優先裝

D.重量小的集裝箱優先裝V

45.會場安排問題的最好的貪策略是()。()［單選題］*

A.在不沖突的情況下，開始時間早的優先安排

B.在不沖突的情況下，使用時間短的優先安排

C.在不沖突的情況下，使用時間長的優先安排

D.在不沖突的情況下，結束時間早的優先安排V

46.調度問題的算法設計策略是(工()［單選題］*

A.加工時間短的優先安排V

B.加工時間長的優先安排

C.等待時間短的優先安排

D.以上都不對

47.以下問題中，哪些問題的分治算法消耗的時間與輸入序列無關。()［單選題］*

A.二分查找

B.合并排序V

C.快速排序

D.最小值問題

48.有關2個n位大整數乘法問題說法正確的是(1()［多選題］*

A.將兩個n位大整數分解為4個規模大致相等的n/2位整數的整數乘法問題V

B.遞歸解決4個子問題V

C.子問題的解需要歸并成原問題的解V

D.子問題的解本身就是原問題的解

49.分治算法的步驟有(1()［多選題］*

A.分解V

B.治理V

C.遞歸

D.合并

50.分治算法的思想是(［()［多選題］*

A,將規模較大的問題劃分為規模較小的相同子問題V

B.子問題之間相互獨立V

C.子問題之間不相互獨立

D.遞歸解決劃分得到的子問預V

E.將子問題的解歸并得至嫄問題的解V

51.大整數A和B的乘法，將A分成位數大致相等的兩部分A1和A2，將B分成位數大致相等的兩部

分B1和B2,以下描述正確的是()。()［多選題］*

A.子問題的解歸并為原問題搟的方法為:AxB=10nAlBl+10n/2(AlB2+A2Bl)+A2B2V

B.子問題的解歸并為原問題解的方法為:AxB=10nAlBl+10n/2(［Al-A2)(B2-

B1)+A1B1+A2B2)+A2B2V

C.子問題的解歸并為原問題解的方法為:AxB=10nAlBl+10n/2((Al+A2)(Bl+B2)-AlBl-

A2B2)+A2B2V

D.以上方法都不對。

52.關于快速排序分治算法時間復雜度描述正確的是()。()［多選題］*

A.快速排序分治算法最好情況下的時間復雜度為O(nlogn).V

B.快謝E序分治算法最壞情況下的時間復雜度為O(n2)7

C.快速排序分治算法平均情況下的時間復雜度為O(n2).

D.二快速排序分治算法平均盾況下的時間復雜度為O(nlogn).V

53.有關快速排序的分治算法描述正確的是()。()［多選題］*

A.快速排序A［left,right］,選取基準元素的方法，將待排序元素分解為兩個子問題。V

B.快速排序基準元素的選取可以是待排序元素中的任何一個元素。V

C.快速排序劃分的兩個子問題規模大致相等。

D.快速排序A［left,right］,遞歸算法的邊界條件是left>rightV

54.關于二分查找時間復雜度描述正確的是()。()［多選題］*

A.二分查找算法最好情況下的時間復雜度為O(1).V

B.二分查找算法最壞情況下的時間復雜度為0(n).

C.二分查找算法最壞情況下的時間復雜度為O(logn).V

D.二分查找算法平均情況下的時間復雜度為O(logn).V

55.有關合用^序的分治算法描述正確的是()。()［多選題］*

A.合押E序A［left,right］的元素，采用的分解方法是(left+right)/2。V

B.合并排序A［left,right］的元素，采用的分解方法是(right-left)/20

C.合并排序A［left,right］的元素，需要治理規模大致等于(right-left+l)/2的兩個子問題。V

D.合并排序需要將兩個有序的子序列歸并成一個有序的子序列。V

56.有關循環賽日程表分治算法描述正確的是()。()［多選題］*

A.循環賽日程表給定2k個運動員，采用2k/2的方法將運動員分成兩組.7

B.循環賽日程表算法先安排組內的賽程，再安排兩組對打。V

C.循環賽日程表算法的邊界條件是兩個運動員,一天的比賽。V

D.循環賽日程表算法為2k個運動員安排了2k-1天的比賽。

57.下述關于二分查找(折半查找)算法描述正確的是()。()［多選題］

A.二分查找是在任意給定的n個元素序列中查找指定元素。

B.二分查找的序列為AUeftjight］,分解操作為:(right-left)/2

C.二分查找根據比較的結果，好的情況是相等，算法結束。壞的情況是進入其中一個子問題繼續查找。V

D.若二分查找的序列為A［left,right］,用遞歸來解決子問題，則邊界條件是left〉right。V

58.分治算法核心就是分而治之,其中的"治"描述正確的是()。()［多選題］*

A.分治法通過治理小問題來治理大問題。V

B.分治法遞歸治理小問題。V

C.分治法需要將子問題的解歸并成大問題的解。V

D.治理子問題時，會有重復性治理子問題的現象。

59.分治算法的基本思想描述正確的是()。()［多選題］*

A.分治法將規模大的問題分解成規模較小的問題解決。V

B.分治法劃分的小問題相互重疊。

C.分治法一般采用遞歸的方法解決子問題。V

D.分治法劃分的小問題規模小到一定程度時容易解決。V

60.根據下面斐波那契數列的涕歸算法，可知斐波那契數列的第n項的遞歸式為(\defFibonacci(int

num):if(num==0||num==1):returnnumreturnFibonacci(num-

1)+Fibonacci(num-2)。()［單選題］*

A.Fibonacci(n)=0當n=O時

B.Fibonacci(n)=l當n=l時

C.Fibonacci(n)=Fibonacci(n-l)+Fibonacci(n-2)當n〉1時V

D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當n〉1時

61.下面代碼為求n!的遞歸算法，該代碼反應的n!問題遞歸實現的停止條件(邊界條件)為(I()

deffun(n):

if(n==1):

return1

else:

returnfun(n-1)*n［單選題］*

A.n!=l當n=0時

B.n!=l當n=l時。

C.n!=l當n〈1時

D.n!=l當n〈=1時

62.以下哪個問題的時間復雜度與輸入序列有關(\()［單選題］*

A.二分查找V

B.最小值問題

C.合并排序

D,以上都不對

63.以下函數的功能是()

defQ(R,low,high):

if(low<high):#僅當區間長度大于1時才須排序

pivotpos=Partition(R,low,high)。劃分后的基準元素所對應的位置

Q(Rlow,pivotpos?l)#對左區間遞歸排序

Q(R,pivotpos+l,high)#對右區間遞歸排序［單選題］*

A.二分查找

B.二分求最值

C.合并排序

D.快速排序V

64.以下代碼功能為合并排序，請根據注釋按照數順序選擇合適的語句填入對應的括號。

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

Merge(A,low,middle,high)#子問題的解合并成原問題的解［單選題］*

A.middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+l,high);

B.middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+l,high);V

C.middle=(low+high)/2;MergeSort(A,middle+l,high］;MergeSort(A,low,middle);

D.middle=(high-low)/2;MergeSort(A,middle4-l,high);MergeSort(A,low,middle);

65.棋盤覆蓋問題的分解方法為(工()［單選題］*

A.

B.

C.V

D.以上分解的方法都不對

66.合并排序的分治算法時間復雜度的是()。()［單選題］*

A.O(logn)

B.O(nlogn)V

C.

D.

67.解決給定的5個矩陣連乘問題：矩陣A1(3x21A2(2x5\A3(5x10\A4(10x2)和A5

(2x3)，設表示Ai...Aj的最優計算次序對應的乘法計算次數(最優值),P為存儲矩陣行列的數組，

其中P［i］是第i個矩陣的列、第i-1個矩陣的行。求解最優值遞歸關系是為：，根據該遞歸關系式，求解過程

中得到下面最優決策的二維表：由此，可得上述5個矩陣連乘的最優計算次序為(［()［單選題］*

A.(Al(A2(A3(A4A5))))

B.((A1A2)(A3(A4A5)))

C.((A1A2)((A3A4)A5))

D.(A1((A2(A3A4))A5))V

68.關于動態規劃和回溯法的區別，以下表述不正確的是。()［單選題］*

A.動態規劃和回溯法都可以用來求解最優化問題，但回溯法是基于枚舉解的思想，動態規劃則是基于

構造子問題最優值關系的方式

B.在遇到重普子問題的時候，動態規劃思想會使用存儲最優值的方式直接排除，而回溯法一般做法是

設法避環和剪枝，降＜氐其影響

C.在求解相同問題時，動態規劃必然比回溯法浪費空間，但是更節約時間，

69.關于動態規劃與分治法的區別，表述不正確的是。(”單選題］*

A.動態規劃劃分的子問題一般具有重疊子問題，分治法則通?；ゲ幌嘟?/p>

B.動態規劃建立在描述子問期最優值關系的狀態轉移方程基礎上，分治法一般不需要建立類似的最優

值之間的數量關系

C.分治法能寫成遞歸形式，動態規劃不能寫成遞歸形式V

D.動態規劃一般用來求解最優化問題，分治法多不用于求解最優化問題，

70.矩陣連乘問題中，A1矩陣大小是100*5,A2矩陣大小為5*30,A3矩陣大小為30*10,則乘法次序

(A1*A2)*A3需要的乘法次數是。()［單選題］*

A.15000

B.30000

C.45000V

D.450000000

7L規模為5矩陣連乘問題，計算次序有()種。()［單選題］*

A.10

B.12

C.14V

D.16

72.根據下面斐波那契數列的遞歸算法，可知斐波那契數列的第n項的遞歸式為(工defFibonacci(int

num):if(num==0||num==1):returnnumreturnFibonacci(num-

)［單選題］*

1)+Fibonacci(num-2)o(

A.Fibonacci(n)=0當n=0時

B.Fibonacci(n)=l當n=l時

C.Fibonacci(n)=Fibonacci(n-l)+Fibonacci(n-2)當n〉1時V

D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當n〉1時

73.下面代碼為求n!的遞歸算法，該代碼反應的n!問題遞歸實現的停止條件(邊界條件)為(、()

deffun(n):

if(n==1):

return1

else:

returnfun(n-1)*n［單選題］*

A.n!=l當n=0時

B.n!=l當n=l時V

C.n!=l當n〈1時

D.n!=l當n〈=l時

74.合并排序的空間復雜度為0。()［單選題］*

A.0(logn)

B.9(n)V

C.0(nlogn)

D.0(n*n)

75.以下哪個問題的時間復雜度與輸入序列有關(工()［單選題］*

A.二分查找，

B.最小值問題

C.合并排序

D.以上都不對

76.以下函數的功能是()

defQ(R,low,high):

if(low<high):#僅當區間長度大于1時才須排序

pivotpos=Partition(R,low,high)#劃分后的基準元素所對應的位置

Q(R,low,pivotpos-l)#對左區間遞歸排序

Q(R,pivotpos+l,high)#對右區間遞歸排序［單選題］*

A,二分查找

B.二分求最值

C.合并排序

D.快速排序V

77.以下代碼功能為合并排序，請根據注釋按照數順序選擇合適的語句填入對應的括號。

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

Merge(A,low,middle,high)#子問題的解合并成原問題的解。()［單選題］*

A.middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+l,high);

B.middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+l,high);V

C.middle=(low+high)/2;MergeSort(A,middle+l,high］;MergeSort(A,low,middle);

D.middle=(high-low)/2;MergeSort(A,middle+Lhigh);MergeSort(A,low,middle);

78.矩陣連乘問題中有多個矩陣相乘，問題是安排矩陣相乘的先后順序，使總乘法次數最少，例如有

［A］［B］C三個矩陣，則可行的順序有ABC\ACB\CAB\CBA\BAC\BCA六個。()［單選題］*

正確

錯誤，

79.以動態規劃求解0-1背包問題，背包容量可以曷王意實數。()［單選題］*

正確

錯誤V

80.有關矩陣連乘問題說法正確的是()。()［多選題］

A.矩陣AL.Aj連乘，其中Ak的行列為(pkxq切水=廿+1,4,其結果矩陣的行列為9ixqj)0V

B.n個矩陣連乘A1...An,其子問題為Ai...Aj連乘,lwiwjwn,其中i=j表示規模為1的子問題,其需要

的乘法次數為0。V

C.設矩陣Ai...Aj連乘最少的乘法次數為矩陣Ai...Aj連乘的子問題為矩陣Ai...Ak連乘和矩

陣Ak+l...Aj連乘，則最優值的遞歸關系式表示為c[i][j]=c[i][k]+c[k+l][j]+piqjqk

D.矩陣連乘問題的時間復雜度為O(n2)

81.動態規劃的基本要素是()。()[多選題]*

A.重疊子問題V

B.最優子結構性質V

C.自底向上的求解方式V

D.自頂向下的遞歸求解方式

82.有關動態規劃描述正確的是()。()[多選題]*

A.動態規劃將多階段決策問題轉化為單階段決策問題。V

B.動態規劃往往用于求解某種最優性質的問題。V

C.適用動態規劃求解的問題經分解得到的各個子問題往往不是相互獨立的。V

D.動態規劃求解時往往采用填表的方法記錄問題最優值。V

E.動態規劃劃分的各子問題與原問題相同，一般遞歸求解子問題。V

F.動態規劃求解某種最優性質的問題時，整體的最優值和子問題的最優值之間存在遞歸關系.V

83.設c[i皿表示序列Xi和Yj的最長公共子序列的長度。則它的遞推關系式為：則根據給定的X二二｛A,

B,C,B,D,A,B｝和Y=｛B,D,C,A,B,A｝從上到下填寫缺失值。()[單選題]*

A.233

B.222

C.344V

D.333

84.給定序歹JX={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A},它們的最長公共子序列是(工()[單選

題]*

A.BCBAV

B.BCDA

C.BDAB

D.BCAA

85.按照順序排列動態規劃的求解步驟，正確的是()(1)遞歸定義最優值。(2)以自底向上的方式計算

出最優值，并記錄相關信息。(3)分析最優解子結構性質。(4)構造出最優解。()［單選題］*

A.(1),(2),(3)X4)

B.⑴，⑶，⑵,⑷

C.(3),(1),(2),(4/

D.(1),(2),(4),⑶

86.以下算法框架中，哪個是排列樹模型的算法設計模式(1()［單選題］*

A.defBacktrack(t):if(t>n):output(x)else:foriinrange(l,m+l):if

(constraint(t)andbound(t)):x[t]=i做其他相關標識

Backtrack(t+1)做其他相關標識的反操作

B.defBacktrack(t):if(t>n):output(x)else:foriinrange(t,n+l):

x[t],x[i]*-x[i]zx[t]if(constraint(t)andbound(t)):Backtrack(t+1)

x[t],x[i]*-x[i],x[t]V

C.defBacktrack(intt):if(t>=n):output(x)else:foriin

range(s(n,t),e(n,t)):x[t]=d(i)if(constraint(t)andbound(t)):

Backtrack(t+1)

D.defBacktrack(intt):if(t>n):output(x)if(constraint(t)):做相關標識

Backtrack(t+1)做相關標識的反操作if(bound(t)):做相關標識Backtrack(t+1)

做相關標識的反操作

87.最優化問題優化目標是使求目標函數最大化，基于回溯法求解該問題。如果對于解空間的任何分支

X,均可求出目標函數值的兩個上界Ibl(X)和lb2(X),且總有Ibl(X)>=lb2(X),則如果想用于剪枝,從減

少搜索節點的角度，哪個界限更優？()［單選題］*

A.Ibl

B.lb2V

C.二者等價

D.依賴于具體輸入

88.0-1背包問題的解空間結構屬于(I()［單選題］*

A.排列樹

B.子集樹V

C.滿n叉樹

D,隱式圖

89.以下關于回溯法的說法，，昔誤的是()［單選題］*

A.回溯法一般會將解空間組織成樹形結構并按照深度優先的順序遍歷

B.回溯法可以適用于求所有解、某個解、最優解等各種問題

C.回溯法能夠保證生成時間復雜度較低的算法V

D.回溯法的編程中，有"當前搜索路徑”的概念，需要保存當前路徑上節點的狀態

90.現有一個用于求解最優化問題的回溯算法,在搜索過程中涉及的函數的描述，錯誤的是()[單選題]

A.違反約束函數的分支不屬于問題的定義域

B.違反限界函數的分支不需要訪問，不能夠得到更優解

C.目標函數是衡量解的優劣程度的函數

D.在目標函數最小化問題中，限界函數應當使用上界V

91.關于旅行商問題的說法，錯誤的是()[單選題]*

A.旅行商問題的解空間與最短路徑問題相同V

B.旅行商問題的優化目標是回路長度最短

C.有4個點的旅行商問題的兩個回路，ABCDA和BCDAB,實際上是兩個相同的回路

D.旅行商問題無法用窮舉求解，因為回路數目太多

92.以下有關旅行商問題的遞歸代碼，根據注釋判斷空缺部分填寫正確的是(1defTraveling⑴:()#

到達葉子結點#g存儲圖的鄰接矩陣，x是存儲解向量，初始化為x[l:n]={l,2，…,n},cl是當前已走的路經長

度，bestl是當前已找到的最短路徑長度。if(g[x[n]][1]!=ooand(cl+g[x[n]][l]<bestl)):forjin

range(l,n+l):bestx[j]=x[j]bestl=cl+g[x[n]][l]else:#沒有到達葉子結點()#控制當前節點的分

支數目，即對xt的所有可能的取值。if(g[x[t-l]][x[j]]!=ooand(cl+g[x[t-l]][x[j]]<bestl)):#保存第t

個要去的城市編號到x也中，進入到第t+1層x[t],x[j]=x[jLx[t]#交換兩個元素的值d+=g[x[t-l]]岡川

Travelings1)#從第t+1層的擴展結點繼續搜索#第t+1層芟索完畢，回溯到第t層cl-=g[x[t-l]][x[j]]

x[t],xU]=x[j],x[t]o(C)[單選題]*

A.空1:if(t==n)空2:for(j=t;j<=n;j++)

B.空1:if(t>n-l)空2:for(j=l;j<=n;j++)

C.空1:if(t>n)空2:for(j=t;j<=n;j++)V

D.空1:if（t>=n-l）空2:for（j=l；j<=n;j++）

93.有關回溯法說法正確的是（工（）［多選題］*

A.回溯法是一種深度優先搜索的搜索算法V

B.回溯法是一種"能進則進、進不了則換、換不了則退（回溯）”的搜索方法V

C.回溯法是一種寬（廣）度優先搜索的搜索算法

D.回溯法是一種最大效益或最小費用優先搜索的方法

94有關n皇后問題說法正確的是（工（）多選題］*

A.該問題的解的形式為（xLx2,,xn）,xi表示第i個皇后位于第i行、第xi列（i=L23“.n）V

B.該問題的初始狀態為：（0,0，…,0）7

C.該問題的解空間的組織結構可以是排列樹，也可以是滿n叉樹。V

D.該問題只需要設置約束條件，不需要限界條件。V

E、該問題解向量中的任意兩個分量xi,xj滿足：xi/xj且|i-j|#|xi-xjM

95.兩個分量xi,xj滿足:xiwxj且|i-j罔xi-xj|

下述有關搜索過程描述錯誤的是（1（）［多選題］*

A.當解空間結構是一棵樹時,搜索從根開始

B.搜索過程中,正在生成孩子的節點稱為擴展節點

C.搜索過程中，所有孩子節點均已生成的節點稱為擴展節點V

D.搜索過程中，所有孩子節點均已生成的節點稱為活結點節點，

E.搜索過程中所有孩子節點均已生成的節點稱為死節點V

F.搜索過程動態生成的樹稱為搜索樹V

96.以下描述中，影響回溯法的搜索效率的是（1（）［多選題］*

A.問題的解空間，即搜索范圍，

B.設定的約束函數和限界函數V

C.搜索方法

D.滿足約束條件和限界條件的節點數目V

97.以下有關子集樹的描述中說法正確的是（工（）［多選題］*

A.當所給的問題是從n個元素組成的集合S中找出滿足某種性質的一個子集時，相應的解空間樹稱為

子集樹。V

B.子集樹模型解的形式為n元組（xlfx2，…,xn）,分量xi（i=l,2，…,n）表示第i個元素是否在子集中。V

C.子集樹模型的解向量中,分量xi的取值為0或1,xi=O表示第i個元素不在子集中；xi=l表示第i

個元素在子集中。V

D.旅行售貨員問題可以開用子集樹模型求解

E.最優裝載問題可以采用子集樹模型求解

F.0-1背包問題可以采用子集樹模型求解

98.有關子集樹描述中，說法錯誤的是（工（）［多選題］*

A.子集樹的根結點為問題的初始狀態V

B.子集樹的中間結點為搜索過程中形成的某中間狀態V

C.子集樹的葉子結點為問題結束狀態V

D.子集樹的分支表示從一個狀態過渡到另一個狀態的行為寸

E.子集樹中從根結點到葉子結點的路徑是一個可行解（一個子集）7

F.子集樹的深度等于問題的規模加IV

99有關0-1背包問題說法正確的是（工（）［多選題］*

A.該問題的解的形式為（xLx2.......xn）,xi（i=L23“.n）的取值為0或IV

B.該問題的解空間的組織結內可以是排列樹。

C.該問題需要設置約束條件，也可以設置限界條件。V

D.該問題只需要設置約束條件，不需要限界條件。

100.有關下圖說法正確的是（）。（）［多選題］*

A.該樹表示的問題的規模為37

B.該樹為一棵排列樹V

C.該樹表示的問題規模為4。

D.該樹為一棵子集樹

101.有關批處理作業調度問題說法正確的是（工（）［多選題］*

A.該問題的解形式為（xLx2,,..,xn）A取值范圍為令S={12…，解則xi￡S-{xl,x2，…,xi-1}j=L2,..”nV

B.該問題的解空間的組織結溝是排列樹。V

C.該問題需要設置約束條件，不需要限界條件。

D.該問題不需要設置約束條件，只需要限界條件。V

E.該問題既需要設置約束條件，也需要限界條件。V

102.有關旅行售貨員問題說法正確的是（1（）［單選題］*

A.該問題的解形式為（xLx2,...,xn）,xi取值范圍為:令S={1,2，…,n},則xi￡S-{xl,x2…xi-1}

B.該問題的解空間的組織結溝是排列樹。V

C.該問題需要設置約束條件，不需要限界條件。

D.該問題不需要設置約束條件，只需要限界條件°

E.該問題既需要設置約束條件，也可以設置限界條件。

103.有關回溯法說法正確的是（工（）［多選題］*

A.回溯法是一種深度優先搜索的搜索算法V

B.回溯法是一種“能進則進、進不了則換、換不了則退（回溯）"的搜索方法V

C.回溯法是一種寬（廣）度優先搜索的搜索算法

D.回溯法是一種最大效益或最小費用優先搜索的方法

104有關n皇后問題說法正確的是（工（）［多選題］*

A.該問題的解的形式為（xl,x2，…，xn）,xi表示第i個皇后位于第i行、第xi到J（i=l,23...nW

B.該問題的初始狀態為：（0,0—0）7

C.該問題的解空間的組織結構可以是排列樹，也可以是滿n叉樹。V

D.該問題只需要設置約束條件，不需要限界條件。V

E.該問題解向量中的任意兩個分量x網滿足：xiHxj且|i-j罔xi-xj|V

105.以下描述中，影響回溯法的搜索效率的是（1（）侈選題］*

A.問題的解空間，即搜索范31V

B.設定的約束函數和限界函數，

C.搜索方法

D.滿足約束條件和限界條件的節點數目V

106.有關隨機化算法錯誤的是（＞（）［單選題］*

A.隨機化算法的特征是對所求解問題的同一實例用同一隨機化算法求解兩次可能得到完全不同的效

果，這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。

B.數值隨機化算法常用于數值問題的求解，所得到的解都是精確解。V

C.蒙特卡羅算法用于求問題的準確解，但解不一定正確.

D.舍伍德算法引入隨機性來降低最壞情況出現的概率，從而消除或減少問題好壞實例之間的時間消耗

的差異。

107.有關估算n值的隨機化算法說法錯誤的是（工（）［單選題］*

A.估算n值的隨機化算法估算的近似值的精度隨算法消耗的時間的增加而提高

B.估算TI值的隨機化算法隨機實驗次數越多，估算的TT值精度越高

C.估算TI值的隨機化算法是數值隨機化算法。

D.估算TI值的隨機化算法估算的近似值的精度與算法消耗的時間無關V

108.有關主元素問題的蒙特卡羅算法說法錯誤的是。（）［單選題］*

A.主元素問題的蒙特卡羅算法每次執行都返回True或False,True表示有主元素，False表示沒有主

兀素。

B.主元素問題的蒙特卡羅算法返回True的解是正確解，False的解不一定是正確解。

C.主元素問題的蒙特卡羅算法得到正確解的概率隨算法消耗的時間的增加而降低。V

D.主元素問題的蒙特卡羅算法得到的解為正確解的概率大于0.5。

109.有關素數測試問題算法說法正確的是。（）［單選題］*

A.根據Wilson定理，可以設計素數測試的隨機化算法。

B.可以采用試除法，設計素數測試的隨機化算法。

C.根據二次探測定理設計的素數測試蒙特卡羅算法得到的解為正確解的概率大于0.5V

D.根據二次探測定理，可以設計素數測試的蒙特卡羅算法，當算法返回True時，解一定正確；當返回

False時，解不一定正確。

110有關n皇后問題的拉斯維加斯算法說法正確的是。（）［單選題］*

A.n皇后問題的拉斯維加斯算法可以采用對不沖突的多個列位置進行隨機。V

B.n皇后問題的拉斯維加斯算法得到接的概率小于0?

C.n皇后問題的拉斯維加斯算法每次運行都能得到一種n個皇后的放置方案。

D.多次運行n皇后問題的拉斯維加斯算法并不能提高算法得到解的概率。

111.有關隨機快速排序算法說法錯誤的是。（）［單選題］*

A.隨機快速排序與快速排序的區別是隨機快速排序隨機選擇基準元素，而快速排序的確定性算法選擇

固定位置的元素作為基準元素。

B.隨機快速排序通過對快速徘序引入隨機性，降低了快速排序最好和最壞情況出現的概率。

C.隨機快速排序的時間復雜度趨于O（nlogn）。

D.隨機快速排序每次運行都能夠得到解，但是得到的解不一定正確。V

112.有關整數n的因子分解問題說法正確的是。（）［單選題］*

A.整數的因子分解就是將整數n分解多個因子的乘積，并不要求因子的素數性。

B.整數的因子分解問題不可以轉化為因子分割問題。

C.因子分割不可以采用試除法找出整數n的因子。

D.Pollard算法，只要給足夠的時間，肯定能找到整數n的因子。V

113.以下有關隨機數產生的線性同余法說法正確的是。（）［單選題］*

A.線性同余法產生的隨機數是偽隨機數。V

B.線性同余法的系數是模數的倍數時，隨機數的隨機性能好。

C.線性同余法的系數、增量、模數越大，隨機數的隨機性能越差。

D.線性同余法的系數與模數巨質，隨機數的隨機性能差。

114.以下有關隨機選擇第k小算法正確的是。（）［單選題］*

A.隨機選擇第k小算法中的建機性和隨機快速排序的隨機性一樣，都是隨機選擇基準元素。V

B.隨機選擇第k小算法是對線性時間選擇算法中劃分過程進行了隨機其他和線性時間選擇算法一樣。

C.隨機選擇第k小算法劃分過程結束后，要在比基準元素小的子問題中查找第k小"

D.隨機選擇第k小算法中的隨機性和隨機快速排序的隨機性不同隨機快速排序是隨機選擇基準元素,