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

試卷總分:100  得分:100

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

1.在下列算法中得到的解未必正確的是

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

D.數(shù)值概率算法

2.0-1背包問題的回溯算法所需的計(jì)算時(shí)間為

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

3.實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

4.以下不可以使用分治法求解的是

A.棋盤覆蓋問題

B.選擇問題

C.歸并排序

D.0/1背包問題

5.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是

A.先進(jìn)先出

B.后進(jìn)先出

C.結(jié)點(diǎn)的優(yōu)先級(jí)

D.隨機(jī)

6.下列哪一種算法不是隨機(jī)化算法

A.蒙特卡羅算法

B..拉斯維加斯算法

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

D..舍伍德算法

7.回溯法解旅行售貨員問題時(shí)的解空間樹是

A.子集樹

B.排列樹

C.深度優(yōu)先生成樹

D.廣度優(yōu)先生成樹

8.下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是

A.數(shù)值概率算法

B.舍伍德算法

C.拉斯維加斯算法

D.蒙特卡羅算法

9.分支限界法解旅行售貨員問題時(shí)，活結(jié)點(diǎn)表的組織形式是

A.最小堆

B.最大堆

C.棧

D.數(shù)組

10.使用分治法求解不需要滿足的條件是

A.子問題必須是一樣的

B.子問題不能夠重復(fù)

C.子問題的解可以合并

D.原問題和子問題使用相同的方法解

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

11.算法的復(fù)雜性沒有時(shí)間復(fù)雜性和空間復(fù)雜性之分

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

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

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

15.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟不包括根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解

16.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟有5步

17.貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

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

19.使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問題，只使用約束條件進(jìn)行裁剪的是N皇后問題

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

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