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

試卷總分:100  得分:100

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

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

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

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

2.0-1背包問題的回溯算法所需的計算時間為

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

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

A.分治策略

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

C.貪心法

D.回溯法

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

A.棋盤覆蓋問題

B.選擇問題

C.歸并排序

D.0/1背包問題

5.優(yōu)先隊列式分支限界法選取擴展結點的原則是

A.先進先出

B.后進先出

C.結點的優(yōu)先級

D.隨機

6.下列哪一種算法不是隨機化算法

A.蒙特卡羅算法

B..拉斯維加斯算法

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

D..舍伍德算法

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

A.子集樹

B.排列樹

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

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

8.下列隨機算法中運行時有時候成功有時候失敗的是

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

B.舍伍德算法

C.拉斯維加斯算法

D.蒙特卡羅算法

9.分支限界法解旅行售貨員問題時，活結點表的組織形式是

A.最小堆

B.最大堆

C.棧

D.數(shù)組

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

A.子問題必須是一樣的

B.子問題不能夠重復

C.子問題的解可以合并

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

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

11.算法的復雜性沒有時間復雜性和空間復雜性之分

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

13.分支限界法與回溯法的求解目標相同

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

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

16.設計動態(tài)規(guī)劃算法的主要步驟有5步

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

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

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

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

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