算法理論知識(shí)考核試題及答案

算法理論知識(shí)考核試題

一.選擇題

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

A.正確

B.錯(cuò)誤V

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

A.正確V

B.錯(cuò)誤

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

A.正確V

B.錯(cuò)誤

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

A.正確V

B.錯(cuò)誤

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

A.正確

B.錯(cuò)誤V

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

A.正確V

B.錯(cuò)誤

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

A.正確V

B.錯(cuò)誤

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

A.輸入V

B.輸出。

C.有限性V

D.確定性V

E.可行性V

9.漸進(jìn)復(fù)雜性的含義是（）情況下的復(fù)雜性。［單選題］*

A.在最佳輸入情況下

B.問(wèn)題規(guī)模趨向于無(wú)窮V

C.在最嗝入情況下

D.平均各種輸入之后

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

題］*

A.al,nV

B.an.nV

C.al,anV

D.al,an,nV

11.平均時(shí)間復(fù)雜度是指（）：?jiǎn)芜x題］*

A.各種情況時(shí)間復(fù)雜度按概率的加權(quán)平均V

B.最好情況和最壞情況的時(shí)間復(fù)雜度的算術(shù)平均

C.各種情況時(shí)間復(fù)雜度按概率的算術(shù)平均

D.出現(xiàn)可能性最高的情況下的時(shí)間復(fù)雜度

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

A.代碼

B.甘特圖V

C.偽代碼

D.漸呈圖

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

A.先進(jìn)性V

B.有窮性

C.有輸入輸出

D.無(wú)二義性

14.階乘問(wèn)題求n!算法的時(shí)間復(fù)雜度為（I［單選題］*

A.nV

B.n!

C.2n

D.nA2

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

A.n

B.lognV

C.nA2

C.單位重量?jī)r(jià)值大的優(yōu)先裝V

D.以上都不對(duì)

19.調(diào)度問(wèn)題的算法設(shè)計(jì)策略是()[單選題]*

A.加工時(shí)間短的優(yōu)先安排V

B.加工時(shí)間長(zhǎng)的優(yōu)先安排

C,等待時(shí)間短的優(yōu)先安排

D.以上都不對(duì)

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

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

請(qǐng)分析算法的時(shí)間復(fù)雜度，用。表示()[單選題]*

A.0(1)

B.0(n)

C.O(n的平方)V

D.O(nlogn)

21.百元買(mǎi)白雞問(wèn)題：雞翁一，值錢(qián)五；雞母一，值錢(qián)三；雞雛三，值錢(qián)一；百錢(qián)買(mǎi)百雞，則翁、母、

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

A.100元

B.100只雞

C.各種雞的單價(jià)

D.無(wú)需任何輸入V

22.下面算法最好情況下的時(shí)間復(fù)雜度—，最壞情況下的時(shí)間復(fù)雜度為一

defbubble_sort(nums):

foriinrange(len(nums)-1):

swap_flag=False#改進(jìn)后的冒泡，設(shè)置一個(gè)交換標(biāo)志位

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#若沒(méi)有元素交換,則表示已經(jīng)有序

returnnums[單選題]*

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

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

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.斐波那契數(shù)列的第1項(xiàng)為1,第2項(xiàng)為2,以后每一項(xiàng)等于前面兩項(xiàng)之和，則第6項(xiàng)為—［單選題］

A.13V

25.冒泡排序時(shí)間復(fù)雜度是一，堆排序時(shí)間復(fù)雜度是［單選題］*

2

A.nxnlognV

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

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.物品可以切割的背包問(wèn)題的最佳貪心策略不一定能保證裝入背包的物品總價(jià)值最大"()［單選題］*

正確

錯(cuò)誤V

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

0.31,0.06。試構(gòu)造對(duì)應(yīng)的哈夫曼(Haffman)編碼，并畫(huà)出相應(yīng)的編碼樹(shù)，同時(shí)寫(xiě)出ml,m2,...ml0的編碼。

()［單選題］*

A.每個(gè)字符的編碼為從根節(jié)點(diǎn)到該字符所在葉子結(jié)點(diǎn)的路徑上的0,1組成的串。V

34.在10000個(gè)元素中找到前100個(gè)最大的元素，如果使用以下某個(gè)數(shù)據(jù)結(jié)構(gòu)作為輔助,比較合適的

是。()［單選題］*

A.堆，

B.并查集

C.循環(huán)鏈表

D.哈希表

35.給定下面的有向、連通帶權(quán)圖用dijkstra算法，找從源點(diǎn)1到其他各個(gè)頂點(diǎn)的最短路徑。算法運(yùn)

行若干步以后，得到各數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)如下(數(shù)組下標(biāo)從1開(kāi)始,表示頂點(diǎn)編號(hào))：下標(biāo)112234567

88S11010110dist028163311pre01217147根據(jù)當(dāng)前狀態(tài),可判斷從初始狀態(tài)到當(dāng)前

狀態(tài)已經(jīng)做了()次貪心選擇。()［單選題］*

A.1

B.2

C.3

D.4V

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

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

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

A.(a,b)

B.(c,d)V

C.(b,c)

D.(Qf)

37.用Prim算法求解上圖的最小生成樹(shù)，初始時(shí)，集合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算法求解上圖的最小生成樹(shù)，初始時(shí)，集合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算法求解上圖的最小生成樹(shù)，第一步貪心選擇的邊是(1()［單選題］*

A.(a,b)

B.(b,c)

C.(c,g)

D.(c,f)V

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

A.O(n2)V

B.O(n3)

C.O(eloge)

D.O(nlogn)

41.背包問(wèn)題:n個(gè)物品和1個(gè)背包。對(duì)物品i,其價(jià)值為vi,重量為wi,背包的容量為W。如何選取物品裝

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

A.重量小的優(yōu)先裝入背包

B.體積小的優(yōu)先裝入背包

C.價(jià)值大的優(yōu)先裝入背包

D.單位重量的價(jià)值大的優(yōu)先裝入背包V

42調(diào)度問(wèn)題有n個(gè)客戶(hù)帶來(lái)n項(xiàng)任務(wù)每項(xiàng)加工時(shí)間已知，設(shè)為tij=l,2，…,n。從0時(shí)刻開(kāi)始，陸續(xù)安排

到一臺(tái)機(jī)器上加工。每個(gè)任務(wù)的完成時(shí)間是從0時(shí)刻到該任務(wù)加工完成的時(shí)間。為了使盡可能多的客戶(hù)滿(mǎn)

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

A.加工時(shí)間長(zhǎng)的優(yōu)先安排

B.加工時(shí)間短的優(yōu)先安排V

C.完成時(shí)間早的優(yōu)先安排

D.等待時(shí)間長(zhǎng)的優(yōu)先安排

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

A.面值大的錢(qián)幣優(yōu)先找出

B.面值小的錢(qián)幣優(yōu)先找出

C.面值小于待找錢(qián)數(shù)且面值最大的優(yōu)先找出，

D.以上都不對(duì)

44.物品不可拆開(kāi)的最優(yōu)裝載問(wèn)題的貪心策略是()。()［單選題］*

A.體積大的集裝箱優(yōu)先裝

B.體積小的集裝箱優(yōu)先裝

C,重量大的集裝箱優(yōu)先裝

D.重量小的集裝箱優(yōu)先裝V

45.會(huì)場(chǎng)安排問(wèn)題的最好的貪策略是()。()［單選題］*

A.在不沖突的情況下，開(kāi)始時(shí)間早的優(yōu)先安排

B.在不沖突的情況下，使用時(shí)間短的優(yōu)先安排

C.在不沖突的情況下，使用時(shí)間長(zhǎng)的優(yōu)先安排

D.在不沖突的情況下，結(jié)束時(shí)間早的優(yōu)先安排V

46.調(diào)度問(wèn)題的算法設(shè)計(jì)策略是(工()［單選題］*

A.加工時(shí)間短的優(yōu)先安排V

B.加工時(shí)間長(zhǎng)的優(yōu)先安排

C.等待時(shí)間短的優(yōu)先安排

D.以上都不對(duì)

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

A.二分查找

B.合并排序V

C.快速排序

D.最小值問(wèn)題

48.有關(guān)2個(gè)n位大整數(shù)乘法問(wèn)題說(shuō)法正確的是(1()［多選題］*

A.將兩個(gè)n位大整數(shù)分解為4個(gè)規(guī)模大致相等的n/2位整數(shù)的整數(shù)乘法問(wèn)題V

B.遞歸解決4個(gè)子問(wèn)題V

C.子問(wèn)題的解需要?dú)w并成原問(wèn)題的解V

D.子問(wèn)題的解本身就是原問(wèn)題的解

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

A.分解V

B.治理V

C.遞歸

D.合并

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

A,將規(guī)模較大的問(wèn)題劃分為規(guī)模較小的相同子問(wèn)題V

B.子問(wèn)題之間相互獨(dú)立V

C.子問(wèn)題之間不相互獨(dú)立

D.遞歸解決劃分得到的子問(wèn)預(yù)V

E.將子問(wèn)題的解歸并得至嫄問(wèn)題的解V

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

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

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

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

B1)+A1B1+A2B2)+A2B2V

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

A2B2)+A2B2V

D.以上方法都不對(duì)。

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

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

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

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

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

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

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

B.快速排序基準(zhǔn)元素的選取可以是待排序元素中的任何一個(gè)元素。V

C.快速排序劃分的兩個(gè)子問(wèn)題規(guī)模大致相等。

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

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

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

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

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

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

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

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

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

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

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

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

A.循環(huán)賽日程表給定2k個(gè)運(yùn)動(dòng)員，采用2k/2的方法將運(yùn)動(dòng)員分成兩組.7

B.循環(huán)賽日程表算法先安排組內(nèi)的賽程，再安排兩組對(duì)打。V

C.循環(huán)賽日程表算法的邊界條件是兩個(gè)運(yùn)動(dòng)員,一天的比賽。V

D.循環(huán)賽日程表算法為2k個(gè)運(yùn)動(dòng)員安排了2k-1天的比賽。

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

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

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

C.二分查找根據(jù)比較的結(jié)果，好的情況是相等，算法結(jié)束。壞的情況是進(jìn)入其中一個(gè)子問(wèn)題繼續(xù)查找。V

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

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

A.分治法通過(guò)治理小問(wèn)題來(lái)治理大問(wèn)題。V

B.分治法遞歸治理小問(wèn)題。V

C.分治法需要將子問(wèn)題的解歸并成大問(wèn)題的解。V

D.治理子問(wèn)題時(shí)，會(huì)有重復(fù)性治理子問(wèn)題的現(xiàn)象。

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

A.分治法將規(guī)模大的問(wèn)題分解成規(guī)模較小的問(wèn)題解決。V

B.分治法劃分的小問(wèn)題相互重疊。

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

D.分治法劃分的小問(wèn)題規(guī)模小到一定程度時(shí)容易解決。V

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

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

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

A.Fibonacci(n)=0當(dāng)n=O時(shí)

B.Fibonacci(n)=l當(dāng)n=l時(shí)

C.Fibonacci(n)=Fibonacci(n-l)+Fibonacci(n-2)當(dāng)n〉1時(shí)V

D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當(dāng)n〉1時(shí)

61.下面代碼為求n!的遞歸算法，該代碼反應(yīng)的n!問(wèn)題遞歸實(shí)現(xiàn)的停止條件(邊界條件)為(I()

deffun(n):

if(n==1):

return1

else:

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

A.n!=l當(dāng)n=0時(shí)

B.n!=l當(dāng)n=l時(shí)。

C.n!=l當(dāng)n〈1時(shí)

D.n!=l當(dāng)n〈=1時(shí)

62.以下哪個(gè)問(wèn)題的時(shí)間復(fù)雜度與輸入序列有關(guān)(\()［單選題］*

A.二分查找V

B.最小值問(wèn)題

C.合并排序

D,以上都不對(duì)

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

defQ(R,low,high):

if(low<high):#僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序

pivotpos=Partition(R,low,high)。劃分后的基準(zhǔn)元素所對(duì)應(yīng)的位置

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

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

A.二分查找

B.二分求最值

C.合并排序

D.快速排序V

64.以下代碼功能為合并排序，請(qǐng)根據(jù)注釋按照數(shù)順序選擇合適的語(yǔ)句填入對(duì)應(yīng)的括號(hào)。

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

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

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.棋盤(pán)覆蓋問(wèn)題的分解方法為(工()［單選題］*

A.

B.

C.V

D.以上分解的方法都不對(duì)

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

A.O(logn)

B.O(nlogn)V

C.

D.

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

(2x3)，設(shè)表示Ai...Aj的最優(yōu)計(jì)算次序?qū)?yīng)的乘法計(jì)算次數(shù)(最優(yōu)值),P為存儲(chǔ)矩陣行列的數(shù)組，

其中P［i］是第i個(gè)矩陣的列、第i-1個(gè)矩陣的行。求解最優(yōu)值遞歸關(guān)系是為：，根據(jù)該遞歸關(guān)系式，求解過(guò)程

中得到下面最優(yōu)決策的二維表：由此，可得上述5個(gè)矩陣連乘的最優(yōu)計(jì)算次序?yàn)?［()［單選題］*

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

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

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

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

68.關(guān)于動(dòng)態(tài)規(guī)劃和回溯法的區(qū)別，以下表述不正確的是。()［單選題］*

A.動(dòng)態(tài)規(guī)劃和回溯法都可以用來(lái)求解最優(yōu)化問(wèn)題，但回溯法是基于枚舉解的思想，動(dòng)態(tài)規(guī)劃則是基于

構(gòu)造子問(wèn)題最優(yōu)值關(guān)系的方式

B.在遇到重普子問(wèn)題的時(shí)候，動(dòng)態(tài)規(guī)劃思想會(huì)使用存儲(chǔ)最優(yōu)值的方式直接排除，而回溯法一般做法是

設(shè)法避環(huán)和剪枝，降＜氐其影響

C.在求解相同問(wèn)題時(shí)，動(dòng)態(tài)規(guī)劃必然比回溯法浪費(fèi)空間，但是更節(jié)約時(shí)間，

69.關(guān)于動(dòng)態(tài)規(guī)劃與分治法的區(qū)別，表述不正確的是。(”單選題］*

A.動(dòng)態(tài)規(guī)劃劃分的子問(wèn)題一般具有重疊子問(wèn)題，分治法則通?；ゲ幌嘟?/p>

B.動(dòng)態(tài)規(guī)劃建立在描述子問(wèn)期最優(yōu)值關(guān)系的狀態(tài)轉(zhuǎn)移方程基礎(chǔ)上，分治法一般不需要建立類(lèi)似的最優(yōu)

值之間的數(shù)量關(guān)系

C.分治法能寫(xiě)成遞歸形式，動(dòng)態(tài)規(guī)劃不能寫(xiě)成遞歸形式V

D.動(dòng)態(tài)規(guī)劃一般用來(lái)求解最優(yōu)化問(wèn)題，分治法多不用于求解最優(yōu)化問(wèn)題，

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

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

A.15000

B.30000

C.45000V

D.450000000

7L規(guī)模為5矩陣連乘問(wèn)題，計(jì)算次序有()種。()［單選題］*

A.10

B.12

C.14V

D.16

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

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

)［單選題］*

1)+Fibonacci(num-2)o(

A.Fibonacci(n)=0當(dāng)n=0時(shí)

B.Fibonacci(n)=l當(dāng)n=l時(shí)

C.Fibonacci(n)=Fibonacci(n-l)+Fibonacci(n-2)當(dāng)n〉1時(shí)V

D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當(dāng)n〉1時(shí)

73.下面代碼為求n!的遞歸算法，該代碼反應(yīng)的n!問(wèn)題遞歸實(shí)現(xiàn)的停止條件(邊界條件)為(、()

deffun(n):

if(n==1):

return1

else:

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

A.n!=l當(dāng)n=0時(shí)

B.n!=l當(dāng)n=l時(shí)V

C.n!=l當(dāng)n〈1時(shí)

D.n!=l當(dāng)n〈=l時(shí)

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

A.0(logn)

B.9(n)V

C.0(nlogn)

D.0(n*n)

75.以下哪個(gè)問(wèn)題的時(shí)間復(fù)雜度與輸入序列有關(guān)(工()［單選題］*

A.二分查找，

B.最小值問(wèn)題

C.合并排序

D.以上都不對(duì)

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

defQ(R,low,high):

if(low<high):#僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序

pivotpos=Partition(R,low,high)#劃分后的基準(zhǔn)元素所對(duì)應(yīng)的位置

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

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

A,二分查找

B.二分求最值

C.合并排序

D.快速排序V

77.以下代碼功能為合并排序，請(qǐng)根據(jù)注釋按照數(shù)順序選擇合適的語(yǔ)句填入對(duì)應(yīng)的括號(hào)。

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

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

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.矩陣連乘問(wèn)題中有多個(gè)矩陣相乘，問(wèn)題是安排矩陣相乘的先后順序，使總乘法次數(shù)最少，例如有

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

正確

錯(cuò)誤，

79.以動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題，背包容量可以曷王意實(shí)數(shù)。()［單選題］*

正確

錯(cuò)誤V

80.有關(guān)矩陣連乘問(wèn)題說(shuō)法正確的是()。()［多選題］

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

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

的乘法次數(shù)為0。V

C.設(shè)矩陣Ai...Aj連乘最少的乘法次數(shù)為矩陣Ai...Aj連乘的子問(wèn)題為矩陣Ai...Ak連乘和矩

陣Ak+l...Aj連乘，則最優(yōu)值的遞歸關(guān)系式表示為c[i][j]=c[i][k]+c[k+l][j]+piqjqk

D.矩陣連乘問(wèn)題的時(shí)間復(fù)雜度為O(n2)

81.動(dòng)態(tài)規(guī)劃的基本要素是()。()[多選題]*

A.重疊子問(wèn)題V

B.最優(yōu)子結(jié)構(gòu)性質(zhì)V

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

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

82.有關(guān)動(dòng)態(tài)規(guī)劃描述正確的是()。()[多選題]*

A.動(dòng)態(tài)規(guī)劃將多階段決策問(wèn)題轉(zhuǎn)化為單階段決策問(wèn)題。V

B.動(dòng)態(tài)規(guī)劃往往用于求解某種最優(yōu)性質(zhì)的問(wèn)題。V

C.適用動(dòng)態(tài)規(guī)劃求解的問(wèn)題經(jīng)分解得到的各個(gè)子問(wèn)題往往不是相互獨(dú)立的。V

D.動(dòng)態(tài)規(guī)劃求解時(shí)往往采用填表的方法記錄問(wèn)題最優(yōu)值。V

E.動(dòng)態(tài)規(guī)劃劃分的各子問(wèn)題與原問(wèn)題相同，一般遞歸求解子問(wèn)題。V

F.動(dòng)態(tài)規(guī)劃求解某種最優(yōu)性質(zhì)的問(wèn)題時(shí)，整體的最優(yōu)值和子問(wèn)題的最優(yōu)值之間存在遞歸關(guān)系.V

83.設(shè)c[i皿表示序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。則它的遞推關(guān)系式為：則根據(jù)給定的X二二｛A,

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

A.233

B.222

C.344V

D.333

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

題]*

A.BCBAV

B.BCDA

C.BDAB

D.BCAA

85.按照順序排列動(dòng)態(tài)規(guī)劃的求解步驟，正確的是()(1)遞歸定義最優(yōu)值。(2)以自底向上的方式計(jì)算

出最優(yōu)值，并記錄相關(guān)信息。(3)分析最優(yōu)解子結(jié)構(gòu)性質(zhì)。(4)構(gòu)造出最優(yōu)解。()［單選題］*

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

B.⑴，⑶，⑵,⑷

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

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

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

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

(constraint(t)andbound(t)):x[t]=i做其他相關(guān)標(biāo)識(shí)

Backtrack(t+1)做其他相關(guān)標(biāo)識(shí)的反操作

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)):做相關(guān)標(biāo)識(shí)

Backtrack(t+1)做相關(guān)標(biāo)識(shí)的反操作if(bound(t)):做相關(guān)標(biāo)識(shí)Backtrack(t+1)

做相關(guān)標(biāo)識(shí)的反操作

87.最優(yōu)化問(wèn)題優(yōu)化目標(biāo)是使求目標(biāo)函數(shù)最大化，基于回溯法求解該問(wèn)題。如果對(duì)于解空間的任何分支

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

少搜索節(jié)點(diǎn)的角度，哪個(gè)界限更優(yōu)？()［單選題］*

A.Ibl

B.lb2V

C.二者等價(jià)

D.依賴(lài)于具體輸入

88.0-1背包問(wèn)題的解空間結(jié)構(gòu)屬于(I()［單選題］*

A.排列樹(shù)

B.子集樹(shù)V

C.滿(mǎn)n叉樹(shù)

D,隱式圖

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

A.回溯法一般會(huì)將解空間組織成樹(shù)形結(jié)構(gòu)并按照深度優(yōu)先的順序遍歷

B.回溯法可以適用于求所有解、某個(gè)解、最優(yōu)解等各種問(wèn)題

C.回溯法能夠保證生成時(shí)間復(fù)雜度較低的算法V

D.回溯法的編程中，有"當(dāng)前搜索路徑”的概念，需要保存當(dāng)前路徑上節(jié)點(diǎn)的狀態(tài)

90.現(xiàn)有一個(gè)用于求解最優(yōu)化問(wèn)題的回溯算法,在搜索過(guò)程中涉及的函數(shù)的描述，錯(cuò)誤的是()[單選題]

A.違反約束函數(shù)的分支不屬于問(wèn)題的定義域

B.違反限界函數(shù)的分支不需要訪(fǎng)問(wèn)，不能夠得到更優(yōu)解

C.目標(biāo)函數(shù)是衡量解的優(yōu)劣程度的函數(shù)

D.在目標(biāo)函數(shù)最小化問(wèn)題中，限界函數(shù)應(yīng)當(dāng)使用上界V

91.關(guān)于旅行商問(wèn)題的說(shuō)法，錯(cuò)誤的是()[單選題]*

A.旅行商問(wèn)題的解空間與最短路徑問(wèn)題相同V

B.旅行商問(wèn)題的優(yōu)化目標(biāo)是回路長(zhǎng)度最短

C.有4個(gè)點(diǎn)的旅行商問(wèn)題的兩個(gè)回路，ABCDA和BCDAB,實(shí)際上是兩個(gè)相同的回路

D.旅行商問(wèn)題無(wú)法用窮舉求解，因?yàn)榛芈窋?shù)目太多

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

到達(dá)葉子結(jié)點(diǎn)#g存儲(chǔ)圖的鄰接矩陣，x是存儲(chǔ)解向量，初始化為x[l:n]={l,2，…,n},cl是當(dāng)前已走的路經(jīng)長(zhǎng)

度，bestl是當(dāng)前已找到的最短路徑長(zhǎng)度。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:#沒(méi)有到達(dá)葉子結(jié)點(diǎn)()#控制當(dāng)前節(jié)點(diǎn)的分

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

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

Travelings1)#從第t+1層的擴(kuò)展結(jié)點(diǎn)繼續(xù)搜索#第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.有關(guān)回溯法說(shuō)法正確的是（工（）［多選題］*

A.回溯法是一種深度優(yōu)先搜索的搜索算法V

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

C.回溯法是一種寬（廣）度優(yōu)先搜索的搜索算法

D.回溯法是一種最大效益或最小費(fèi)用優(yōu)先搜索的方法

94有關(guān)n皇后問(wèn)題說(shuō)法正確的是（工（）多選題］*

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

B.該問(wèn)題的初始狀態(tài)為：（0,0，…,0）7

C.該問(wèn)題的解空間的組織結(jié)構(gòu)可以是排列樹(shù)，也可以是滿(mǎn)n叉樹(shù)。V

D.該問(wèn)題只需要設(shè)置約束條件，不需要限界條件。V

E、該問(wèn)題解向量中的任意兩個(gè)分量xi,xj滿(mǎn)足：xi/xj且|i-j|#|xi-xjM

95.兩個(gè)分量xi,xj滿(mǎn)足:xiwxj且|i-j罔xi-xj|

下述有關(guān)搜索過(guò)程描述錯(cuò)誤的是（1（）［多選題］*

A.當(dāng)解空間結(jié)構(gòu)是一棵樹(shù)時(shí),搜索從根開(kāi)始

B.搜索過(guò)程中,正在生成孩子的節(jié)點(diǎn)稱(chēng)為擴(kuò)展節(jié)點(diǎn)

C.搜索過(guò)程中，所有孩子節(jié)點(diǎn)均已生成的節(jié)點(diǎn)稱(chēng)為擴(kuò)展節(jié)點(diǎn)V

D.搜索過(guò)程中，所有孩子節(jié)點(diǎn)均已生成的節(jié)點(diǎn)稱(chēng)為活結(jié)點(diǎn)節(jié)點(diǎn)，

E.搜索過(guò)程中所有孩子節(jié)點(diǎn)均已生成的節(jié)點(diǎn)稱(chēng)為死節(jié)點(diǎn)V

F.搜索過(guò)程動(dòng)態(tài)生成的樹(shù)稱(chēng)為搜索樹(shù)V

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

A.問(wèn)題的解空間，即搜索范圍，

B.設(shè)定的約束函數(shù)和限界函數(shù)V

C.搜索方法

D.滿(mǎn)足約束條件和限界條件的節(jié)點(diǎn)數(shù)目V

97.以下有關(guān)子集樹(shù)的描述中說(shuō)法正確的是（工（）［多選題］*

A.當(dāng)所給的問(wèn)題是從n個(gè)元素組成的集合S中找出滿(mǎn)足某種性質(zhì)的一個(gè)子集時(shí)，相應(yīng)的解空間樹(shù)稱(chēng)為

子集樹(shù)。V

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

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

個(gè)元素在子集中。V

D.旅行售貨員問(wèn)題可以開(kāi)用子集樹(shù)模型求解

E.最優(yōu)裝載問(wèn)題可以采用子集樹(shù)模型求解

F.0-1背包問(wèn)題可以采用子集樹(shù)模型求解

98.有關(guān)子集樹(shù)描述中，說(shuō)法錯(cuò)誤的是（工（）［多選題］*

A.子集樹(shù)的根結(jié)點(diǎn)為問(wèn)題的初始狀態(tài)V

B.子集樹(shù)的中間結(jié)點(diǎn)為搜索過(guò)程中形成的某中間狀態(tài)V

C.子集樹(shù)的葉子結(jié)點(diǎn)為問(wèn)題結(jié)束狀態(tài)V

D.子集樹(shù)的分支表示從一個(gè)狀態(tài)過(guò)渡到另一個(gè)狀態(tài)的行為寸

E.子集樹(shù)中從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑是一個(gè)可行解（一個(gè)子集）7

F.子集樹(shù)的深度等于問(wèn)題的規(guī)模加IV

99有關(guān)0-1背包問(wèn)題說(shuō)法正確的是（工（）［多選題］*

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

B.該問(wèn)題的解空間的組織結(jié)內(nèi)可以是排列樹(shù)。

C.該問(wèn)題需要設(shè)置約束條件，也可以設(shè)置限界條件。V

D.該問(wèn)題只需要設(shè)置約束條件，不需要限界條件。

100.有關(guān)下圖說(shuō)法正確的是（）。（）［多選題］*

A.該樹(shù)表示的問(wèn)題的規(guī)模為37

B.該樹(shù)為一棵排列樹(shù)V

C.該樹(shù)表示的問(wèn)題規(guī)模為4。

D.該樹(shù)為一棵子集樹(shù)

101.有關(guān)批處理作業(yè)調(diào)度問(wèn)題說(shuō)法正確的是（工（）［多選題］*

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

B.該問(wèn)題的解空間的組織結(jié)溝是排列樹(shù)。V

C.該問(wèn)題需要設(shè)置約束條件，不需要限界條件。

D.該問(wèn)題不需要設(shè)置約束條件，只需要限界條件。V

E.該問(wèn)題既需要設(shè)置約束條件，也需要限界條件。V

102.有關(guān)旅行售貨員問(wèn)題說(shuō)法正確的是（1（）［單選題］*

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

B.該問(wèn)題的解空間的組織結(jié)溝是排列樹(shù)。V

C.該問(wèn)題需要設(shè)置約束條件，不需要限界條件。

D.該問(wèn)題不需要設(shè)置約束條件，只需要限界條件°

E.該問(wèn)題既需要設(shè)置約束條件，也可以設(shè)置限界條件。

103.有關(guān)回溯法說(shuō)法正確的是（工（）［多選題］*

A.回溯法是一種深度優(yōu)先搜索的搜索算法V

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

C.回溯法是一種寬（廣）度優(yōu)先搜索的搜索算法

D.回溯法是一種最大效益或最小費(fèi)用優(yōu)先搜索的方法

104有關(guān)n皇后問(wèn)題說(shuō)法正確的是（工（）［多選題］*

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

B.該問(wèn)題的初始狀態(tài)為：（0,0—0）7

C.該問(wèn)題的解空間的組織結(jié)構(gòu)可以是排列樹(shù)，也可以是滿(mǎn)n叉樹(shù)。V

D.該問(wèn)題只需要設(shè)置約束條件，不需要限界條件。V

E.該問(wèn)題解向量中的任意兩個(gè)分量x網(wǎng)滿(mǎn)足：xiHxj且|i-j罔xi-xj|V

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

A.問(wèn)題的解空間，即搜索范31V

B.設(shè)定的約束函數(shù)和限界函數(shù)，

C.搜索方法

D.滿(mǎn)足約束條件和限界條件的節(jié)點(diǎn)數(shù)目V

106.有關(guān)隨機(jī)化算法錯(cuò)誤的是（＞（）［單選題］*

A.隨機(jī)化算法的特征是對(duì)所求解問(wèn)題的同一實(shí)例用同一隨機(jī)化算法求解兩次可能得到完全不同的效

果，這兩次求解問(wèn)題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。

B.數(shù)值隨機(jī)化算法常用于數(shù)值問(wèn)題的求解，所得到的解都是精確解。V

C.蒙特卡羅算法用于求問(wèn)題的準(zhǔn)確解，但解不一定正確.

D.舍伍德算法引入隨機(jī)性來(lái)降低最壞情況出現(xiàn)的概率，從而消除或減少問(wèn)題好壞實(shí)例之間的時(shí)間消耗

的差異。

107.有關(guān)估算n值的隨機(jī)化算法說(shuō)法錯(cuò)誤的是（工（）［單選題］*

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

B.估算TI值的隨機(jī)化算法隨機(jī)實(shí)驗(yàn)次數(shù)越多，估算的TT值精度越高

C.估算TI值的隨機(jī)化算法是數(shù)值隨機(jī)化算法。

D.估算TI值的隨機(jī)化算法估算的近似值的精度與算法消耗的時(shí)間無(wú)關(guān)V

108.有關(guān)主元素問(wèn)題的蒙特卡羅算法說(shuō)法錯(cuò)誤的是。（）［單選題］*

A.主元素問(wèn)題的蒙特卡羅算法每次執(zhí)行都返回True或False,True表示有主元素，F(xiàn)alse表示沒(méi)有主

兀素。

B.主元素問(wèn)題的蒙特卡羅算法返回True的解是正確解，F(xiàn)alse的解不一定是正確解。

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

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

109.有關(guān)素?cái)?shù)測(cè)試問(wèn)題算法說(shuō)法正確的是。（）［單選題］*

A.根據(jù)Wilson定理，可以設(shè)計(jì)素?cái)?shù)測(cè)試的隨機(jī)化算法。

B.可以采用試除法，設(shè)計(jì)素?cái)?shù)測(cè)試的隨機(jī)化算法。

C.根據(jù)二次探測(cè)定理設(shè)計(jì)的素?cái)?shù)測(cè)試蒙特卡羅算法得到的解為正確解的概率大于0.5V

D.根據(jù)二次探測(cè)定理，可以設(shè)計(jì)素?cái)?shù)測(cè)試的蒙特卡羅算法，當(dāng)算法返回True時(shí)，解一定正確；當(dāng)返回

False時(shí)，解不一定正確。

110有關(guān)n皇后問(wèn)題的拉斯維加斯算法說(shuō)法正確的是。（）［單選題］*

A.n皇后問(wèn)題的拉斯維加斯算法可以采用對(duì)不沖突的多個(gè)列位置進(jìn)行隨機(jī)。V

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

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

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

111.有關(guān)隨機(jī)快速排序算法說(shuō)法錯(cuò)誤的是。（）［單選題］*

A.隨機(jī)快速排序與快速排序的區(qū)別是隨機(jī)快速排序隨機(jī)選擇基準(zhǔn)元素，而快速排序的確定性算法選擇

固定位置的元素作為基準(zhǔn)元素。

B.隨機(jī)快速排序通過(guò)對(duì)快速徘序引入隨機(jī)性，降低了快速排序最好和最壞情況出現(xiàn)的概率。

C.隨機(jī)快速排序的時(shí)間復(fù)雜度趨于O（nlogn）。

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

112.有關(guān)整數(shù)n的因子分解問(wèn)題說(shuō)法正確的是。（）［單選題］*

A.整數(shù)的因子分解就是將整數(shù)n分解多個(gè)因子的乘積，并不要求因子的素?cái)?shù)性。

B.整數(shù)的因子分解問(wèn)題不可以轉(zhuǎn)化為因子分割問(wèn)題。

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

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

113.以下有關(guān)隨機(jī)數(shù)產(chǎn)生的線(xiàn)性同余法說(shuō)法正確的是。（）［單選題］*

A.線(xiàn)性同余法產(chǎn)生的隨機(jī)數(shù)是偽隨機(jī)數(shù)。V

B.線(xiàn)性同余法的系數(shù)是模數(shù)的倍數(shù)時(shí)，隨機(jī)數(shù)的隨機(jī)性能好。

C.線(xiàn)性同余法的系數(shù)、增量、模數(shù)越大，隨機(jī)數(shù)的隨機(jī)性能越差。

D.線(xiàn)性同余法的系數(shù)與模數(shù)巨質(zhì)，隨機(jī)數(shù)的隨機(jī)性能差。

114.以下有關(guān)隨機(jī)選擇第k小算法正確的是。（）［單選題］*

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

B.隨機(jī)選擇第k小算法是對(duì)線(xiàn)性時(shí)間選擇算法中劃分過(guò)程進(jìn)行了隨機(jī)其他和線(xiàn)性時(shí)間選擇算法一樣。

C.隨機(jī)選擇第k小算法劃分過(guò)程結(jié)束后，要在比基準(zhǔn)元素小的子問(wèn)題中查找第k小"

D.隨機(jī)選擇第k小算法中的隨機(jī)性和隨機(jī)快速排序的隨機(jī)性不同隨機(jī)快速排序是隨機(jī)選擇基準(zhǔn)元素,