23秋《算法與數(shù)據(jù)分析》作業(yè)3

試卷總分:100  得分:100

一、單選題 (共 10 道試題,共 50 分)

1.用分支限界法設(shè)計(jì)算法的第二步是

A.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼

B.確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）

C.以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間

D.在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索

2.蒙特卡羅算法是以下的哪種

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

3.一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的

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

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

C.貪心選擇性質(zhì)

D.定義最優(yōu)解

4.實(shí)現(xiàn)合并排序利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

5.實(shí)現(xiàn)最大子段和利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

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

A.遞歸函數(shù)

B..剪枝函數(shù)

C.。隨機(jī)數(shù)函數(shù)

D..搜索函數(shù)

7.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

8.實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是

A.分治法

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

C.貪心法

D.回溯法

9.合并排序算法是利用

A.分治策略

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

C.貪心法

D.回溯法

10.下面是貪心算法的基本要素的是

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

B.構(gòu)造最優(yōu)解

C.貪心選擇性質(zhì)

D.定義最優(yōu)解

二、判斷題 (共 10 道試題,共 50 分)

11.矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。

12.分支限界法是一種只帶有系統(tǒng)性的搜索算法。

13.矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)

14.拉斯維加斯算法找到的解不一定是正確解。

15.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。

16.程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)

17.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)

18.計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。

19.分支限界法與回溯法的求解目標(biāo)相同

20.快速排序算法的性能取決于劃分的對(duì)稱(chēng)性

奧鵬，國(guó)開(kāi)，廣開(kāi)，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請(qǐng)咨詢(xún)QQ : 3230981406或微信:aopopenfd777