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

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

-選擇IS

1.2n=0(100n2)［單選題］*

A.正確

B.錯(cuò)誤√

2.10=θ(logl0)［單選甄*

A.正確√

B.錯(cuò)誤

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

A.正確V

B.錯(cuò)誤

4.Iogn2=θ(logn+5)［單選題*

A.正確√

B.錯(cuò)誤

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

A.正確

B.錯(cuò)誤√

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

A.正確V

B.錯(cuò)誤

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

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

A.正確√

B.錯(cuò)誤

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

A.輸入√

B.輸出√

C.有限性√

D.確定性√

E.可行性V

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

A.在最佳輸入情況下

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

C.在最壞輸入情況下

D.平均各種輸入之后

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

題］*

A.al,n√

B.an,n√

C.al,an√

D.al,an,n√

11.平均時(shí)間復(fù)雜度是指（）［單選題］*

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

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

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

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

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

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

A.代碼

B.甘特圖√

C.偽代碼

D.流程圖

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

A.先進(jìn)性√

B.有窮性

C.有輸入輸出

D.無二義性

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

A.n√

B.n!

C.2n

D.n^2

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

A.n

B.IognV

C.n^2

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

D.2n

16.漢諾塔問題的時(shí)間復(fù)雜度是（I_。（）［單選題］*

A.n!

B.2^n√

C.2n

D.Iogn

17.下述描述算法的方式采用的是算法的哪種描述方式（）？

算法:gcd（m,n）

輸入：非負(fù)整數(shù)m,n,其中m,n不全為0

輸出：m與n的最大公約數(shù)

l.whilem>0do

2.r-nmodm

3.n*—m

4.m—r

5.returnn［單選題］*

A.自然語言

B.程序流程圖

C.偽碼√

D.程序設(shè)計(jì)語言

18.背包問題的算法設(shè)計(jì)策略是（）［單選題］*

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

B.價(jià)值大的優(yōu)先裝

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

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

D.以上都不對(duì)

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

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

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

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

D.以上都不對(duì)

20.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ù)雜度，用0表示()[單選題]*

A.0(1)

B.0(n)

C.O(n的平方)√

D.O(nlogn)

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

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

A.100元

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

B.IOO只雞

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

D.無需任何輸入√

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

defbubble.Sort(nums):

foriinrange(len(nums)-1):

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

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

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

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

SwapJIag=True

ifnotswap_flag:

returnnums#若沒有元素交換，則表示已經(jīng)有序

returnnums[單選題]*

A.0(n)、0(n2)√

23.以下遞歸程序fun(5,0)輸出的第一個(gè)元素是_,求解過程中最大層次為一

deffun(i,d):

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

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

if(i>l):

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

A.1、4√

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

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

A.13√

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

2

A.nxnlogn√

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

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

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

A.O(nlogn)√

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

A.O(logn)√

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

A.O(n的平方)√

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

A.O(logn)√

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

A.0(n^2)√

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

正確

錯(cuò)誤V

設(shè)字符的查閱頻率依次為

33.ml,m2f...mlO:0.05,0.01,0.01,0.10,0.03,0.17,0.02,0.24,

試構(gòu)造對(duì)應(yīng)的哈夫曼編碼，并畫出相應(yīng)的編碼樹，同時(shí)寫出的編碼。

0.31,0.06o(Haffman)ml,m2,…mlθ

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

()［單選題］*

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

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開始，表示頂點(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.4√

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

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

A.(a,b)

B.(c,d)√

C.(b,c)

D.(c,f)

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

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

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

A.(a,b)

B.(b,c)

C.(c,d)

D.(c,f)√

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

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

A.(a,b)√

B.(b,c)

C.(c,d)

D.(c,f)

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

A.(a,b)

B.(b,c)

C.(c,g)

D.(c,f)√

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

A.O(n2)√

B.O(n3)

C.O(eloge)

D.O(nlogn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

D.以上都不對(duì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

D.以上都不對(duì)

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

A.二分查找

B.合并排序√

C.快速排序

D.最小值問題

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

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

B.遞歸解決4個(gè)子問題√

C.子問題的解需要?dú)w并成原問題的解√

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

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

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

A.分解√

B.治理√

C.遞歸

D.合并

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

A.將規(guī)模較大的問題劃分為規(guī)模較小的相同子問題√

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

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

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

E.將子問題的解歸并得到原問題的解V

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

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

A.子問題的解歸并為原問題解的方法為:AXB=IOnAlBl+10n∕2(AlB2+A2Bl)+A2B2√

B.子問題的解歸并為原問題解的方法為：AXB=IOnAlBl+10n∕2((Al-A2)(B2-

B1)+A1B1+A2B2)+A2B2√

C.子問題的解歸并為原問題解的方法為:AXB=IOnAlBl+10n∕2((Al+A2)(Bl+B2)-AlBL

A2B2)+A2B2√

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

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

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

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

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

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

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

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

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

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

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

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

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

A.二分查找算法最好情況下的時(shí)間復(fù)雜度為0Q)?√

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

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

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

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

A.合并排序A［left,right］的元素,采用的分解方法是(Ieft+right)∕2°√

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

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

D.合并排序需要將兩個(gè)有序的子序列歸并成一個(gè)有序的子序列?！?/p>

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

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

B.循環(huán)賽日程表算法先安排組內(nèi)的賽程再安排兩組對(duì)打?！?/p>

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

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

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

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

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

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

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

D.若二分查找的序列為A［left,right］,用遞歸來解決子問題則邊界條件是left>right?！?/p>

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

A.分治法通過治理小問題來治理大問題?！?/p>

B.分治法遞歸治理小問題?！?/p>

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

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

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

A.分治法將規(guī)模大的問題分解成規(guī)模較小的問題解決?！?/p>

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

C.分治法一般采用遞歸的方法解決子問題?！?/p>

D.分治法劃分的小問題規(guī)模小到一定程度時(shí)容易解決?！?/p>

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

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

［單選題］*

1)+Fibonacci(num-2)0()

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í)√

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

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

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

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)nC時(shí)

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

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

A.二分直找√

B.最小值問題

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(R,low,pivotp。S-I)擬寸左區(qū)間遞歸排序

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

A.二分查找

B.二分求最值

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

C.合并排序

D.快速排序√

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

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

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

A.middle=(high-low)∕2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);

B.middle=(low+high)∕2;MergeSort(A,low,middle);MergeScIrt(A,middle+Lhigh)W

C.middle=(low+high)∕2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);

D.middle=(high-low)∕2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);

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

A.

B.

C.√

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

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

A.O(Iogn)

B.O(nlogn)√

C.

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

D.

67.解決給定的5個(gè)矩陣連乘問題：矩陣Al(3×21A2(2×5\A3(5×10?A4(10×2)和A5

(2x3),設(shè)m［i］［j］表示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)系式，求解過程

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

A.(A1(A2(A3(A4A5))))

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

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

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

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

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

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

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

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

C.在求解相同問題時(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ī)劃劃分的子問題一般具有重疊子問題，分治法則通常互不相交

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

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

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

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

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

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

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

A.15000

B.30000

C.45000√

D.450000000

71.規(guī)模為5矩陣連乘問題,計(jì)算次序有()種。()［單選題］*

A.10

B.12

C.14√

D.16

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

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

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

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í)√

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

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

deffun(n):

if(n==1):

return1

else:

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

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í)

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

A.θ(logn)

B.θ(n)√

C.θ(nlogn)

D.θ(n*n)

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

A.二分查找√

B.最小值問題

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-I)板寸左區(qū)間遞歸排序

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

A.二分查找

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

B.二分求最值

C.合并排序

D.快速排序√

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

defMergeSort(A,low,high):

if(low<high):

()#分解

()#遞歸序列左半部分

()#遞歸序列右半部分

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

A.middle=(high-low)∕2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);

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

C.middle=(low+high)∕2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);

D.middle=(high-low)∕2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);

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

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

正確

錯(cuò)誤V

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

正確

錯(cuò)誤V

80有關(guān)矩陣連乘問題說法正確的是()。()侈選題］*

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

A.矩陣Ai...Aj連乘其中Ak的行列為(Pk×qk),k=i,i+l,.,j,其結(jié)果矩陣的行列為(Pi×qj)o√

B.n個(gè)矩陣連乘A1...An,其子問題為A[.人)連乘,1。勺介,其中1可表示規(guī)模為1的子問題,其需要

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

C.設(shè)矩陣Ai...Aj連乘最少的乘法次數(shù)為c[i][j],矩陣Ai...Aj連乘的子問題為矩陣Ai...Ak連乘和矩

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

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

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

A.重疊子問題√

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

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

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

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

A.動(dòng)態(tài)規(guī)劃將多階段決策問題轉(zhuǎn)化為單階段決策問題?！?/p>

B.動(dòng)態(tài)規(guī)劃往往用于求解某種最優(yōu)性質(zhì)的問題?！?/p>

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

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

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

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

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

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

A.233

B.222

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

C.344√

D.333

84.給定序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A},它們的最長(zhǎng)公共子序列是（1（）［單選

題]*

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

B.⑴,⑶,⑵,(4)

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

D.⑴,⑵,⑷,⑶

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

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

(constraint^)andbound(t)):×[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):

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

×[t],×[i]*-×[i],×[t]√

C.defBacktrack(intt):if(t>=n):output(×)else:forin

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

range(s(nzt)ze(nzt)):×[t]=d(i)if(constraint^)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)化問題優(yōu)化目標(biāo)是使求目標(biāo)函數(shù)最大化，基于回溯法求解該問題。如果對(duì)于解空間的任何分支

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

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

A.Ibl

B.Ib2√

C.二者等價(jià)

D.依賴于具體輸入

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

A.排列樹

B.子集樹√

C.滿n叉樹

D.隱式圖

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

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

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

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

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

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

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

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

B.違反眼界函數(shù)的分支不需要訪問，不能夠得到更優(yōu)解

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

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

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

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

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

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

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

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

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

度,bestl是當(dāng)前已找到的最短路徑長(zhǎng)度。if(g[×[n]][1]!=∞and(cl+g[×[n]][l]<bestl)):forjin

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

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

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

TraVeling(t+1)#從第t+1層的擴(kuò)展結(jié)點(diǎn)繼續(xù)搜索#第1+1層搜索完畢回溯到第t層cl-=g[×[t-l]][×[j]]

×[t],×U]=×U],×[t].(C)[單選題]*

A.空1:if(t==n)空2:forQ=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

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

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

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

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

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

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

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

94.有關(guān)n皇后問題說法正確的是（1（）［多選題］*

A.該問題的解的形式為（XLx2,,xn）,Xi表示第i個(gè)皇后位于第i行、第Xi歹（J（i=L2,3,?.?n）√

B.該問題的初始狀態(tài)為：（0,0,…,0）√

C.該問題的解空間的組織結(jié)構(gòu)可以是排列樹，也可以是滿n叉樹?！?/p>

D.該問題只需要設(shè)置約束條件，不需要限界條件?！?/p>

E、該問題解向量中的任意兩個(gè)分量xi,xj滿足：×i≠xj且∣i-j∣HlXi-Xj∣√

95.兩個(gè)分量xi,xj滿足：xi≠xj且∣i-j∣H∣xi-xj∣

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

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

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

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

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

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

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

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

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

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

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

C.搜索方法

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

97.以下有關(guān)子集樹的描述中說法正確的是(】()［多選題］*

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

子集樹。√

B.子集樹模型解的形式為n元組(×1,×2,…,xn),分量×i(i=l,2n)表示第?個(gè)元素是否在子集中?！?/p>

C.子集樹模型的解向量中，分量Xi的取值為?；?,Xi=O表示第i個(gè)元素不在子集中;xi=l表示第i

個(gè)元素在子集中?！?/p>

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

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

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

98.有關(guān)子集樹描述中，說法錯(cuò)誤的是(】()［多選題］*

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

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

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

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

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

F.子集樹的深度等于問題的規(guī)模加

99.有關(guān)0-1背包問題說法正確的是(1()［多選題］*

A.該問題的解的形式為(xl,x2,,Xn),xi(i=l,2,3,...n)的取值為0或1√

B.該問題的解空間的組織結(jié)構(gòu)可以是排列樹。

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

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

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

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

A.該樹表示的問題的規(guī)模為3√

B.該樹為一棵排列樹√

C.該樹表示的問題規(guī)模為4。

D.該樹為一棵子集樹

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

A.該問題的解形式為（XLX2,…,Xn）Xi取值范圍為令S=Q,2,…,n}則xi∈S-{xl,x2×i-l},i=l,2,.,n√

B.該問題的解空間的組織結(jié)構(gòu)是排列樹?！?/p>

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

D.該問題不需要設(shè)置約束條件，只需要限界條件?！?/p>

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

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

A.該問題的解形式為（XLX2,…,×n）,Xi取值范圍為:令S={l,2n},則xi∈S-{xl,x2xi-l}

B.該問題的解空間的組織結(jié)構(gòu)是排列樹?！?/p>

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

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

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

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

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

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

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

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

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

104有關(guān)n皇后問題說法正確的是(1()［多選題］*

A.該問題的解的形式為(XLx2,,xn),×i表示第i個(gè)皇后位于第i行、第Xi列∣(i=l,2,3,...n)√

B.該問題的初始狀態(tài)為：(0,0,.,0)√

C.該問題的解空間的組織結(jié)構(gòu)可以是排列樹，也可以是滿n叉樹?！?/p>

D.該問題只需要設(shè)置約束條件，不需要限界條件?！?/p>

E.該問題解向量中的任意兩個(gè)分量xi,xj滿足：xi≠xj且∣i-j∣?IXi-Xj∣√

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

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

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

C.搜索方法

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

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

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

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

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

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

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

的差異。

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

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

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

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

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

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

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

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

兀素。

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

C.主元素問題的蒙特卡羅算法得到正確解的概率隨算法消耗的時(shí)間的增加而降低?！?/p>

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

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

A.根據(jù)WiISon定理，可以設(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.5√

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

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

IlO.有關(guān)n皇后問題的拉斯維加斯算法說法正確的是。()［單選題］*

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

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

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

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

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

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

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

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

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

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

C.Onlogno

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

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

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

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

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

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

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

A.線性同余法產(chǎn)生的隨機(jī)數(shù)是偽隨機(jī)數(shù)?！?/p>

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

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

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

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

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

B.隨機(jī)選擇