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

試卷總分:100  得分:100

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

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

A.重疊子問題

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

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

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

2.最大效益優(yōu)先是下列哪項(xiàng)的一種搜索方式

A.分支界限法

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

C.貪心法

D.回溯法

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

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

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

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

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

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

A.備忘錄法

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

C.貪心法

D.回溯法

5.分支限界法與回溯法的相同點(diǎn)是

A.求解目標(biāo)相同

B.搜索方式相同

C.對擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式相同

D.都是一種在問題的解空間樹T中搜索問題解的算法

6.實(shí)現(xiàn)大整數(shù)的乘法是利用的算法

A.貪心法

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

C.分治策略

D.回溯法

7.矩陣連乘問題的算法可由什么設(shè)計(jì)實(shí)現(xiàn)

A.分支界限算法

B.動態(tài)規(guī)劃算法

C.貪心算法

D.回溯算法

8.分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是

A.最小堆

B.最大堆

C.棧

D.數(shù)組

9.回溯法搜索狀態(tài)空間樹是按照什么的順序

A.中序遍歷

B.廣度優(yōu)先遍歷

C.深度優(yōu)先遍歷

D.層次優(yōu)先遍歷

10.廣度優(yōu)先是什么的一種搜索方式

A.分支界限法

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

C.貪心法

D.回溯法

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

11.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。

12.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。

13.分治法的基本思想時(shí)將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問題的解

14.任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其規(guī)模無關(guān)。

15.分治法與動態(tài)規(guī)劃法的不同點(diǎn)是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的

16.分支限界法主要有隊(duì)列式（FIFO）分支限界法和優(yōu)先隊(duì)列式分支限界法。

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

18.問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題不可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。

19.解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法

20.利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是蒙特卡羅算法

奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學(xué)習(xí)
詳情請咨詢QQ : 3230981406或微信:aopopenfd777