《算法與數(shù)據(jù)分析》測(cè)試題

試卷總分:100得分：100

一、單選題（共10道試題，共50分）

1.回溯法的效率不依賴于下列哪些因素

A.滿足顯約束的值的個(gè)數(shù)

B..計(jì)算約束函數(shù)的時(shí)間

C..計(jì)算限界函數(shù)的時(shí)間

D..確定解空間的時(shí)間

正確答案:D

2.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是

A.備忘錄法

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

C.貪心法

D.回溯法

正確答案:D

3.分治法所能解決的問題一般具有的兒個(gè)特征不包括

A.該問題的規(guī)模縮小到一定的程度就可以容易地解決

B.該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

C.利用該問題分解出的子問題的解不可以合并為該問題的解

D.原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問

題

正確答案：C

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

A.重疊子問題

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

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

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

正確答案：B

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

A.備忘錄法

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

C貪心法

D.回溯法

6.在下列算法中有時(shí)找不到問題解的是

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

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

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

A.分支界限算法

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

C.貪心算法

D.回溯算法

8.貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)是

A.重疊子問題

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

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

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

9.下列是動(dòng)態(tài)規(guī)劃算法基本要素的是

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

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

C.算出最優(yōu)解

D.子問題重疊性質(zhì)

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

A.遞歸函數(shù)

B..剪枝函數(shù)

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

D..搜索函數(shù)

二、判斷題（共10道試題，共50分）

1.貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，但不是貪心算法與動(dòng)態(tài)規(guī)劃

算法的主要區(qū)別

A.錯(cuò)誤

B.正確

2.優(yōu)先隊(duì)列式分支限界法是指按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的

節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

4.分治法與動(dòng)態(tài)規(guī)劃法的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分輯得

到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題

往往是互相獨(dú)立的

A.錯(cuò)誤

B.正確

5.隊(duì)列式(FIFO)分支限界法是指按照隊(duì)列先進(jìn)先出(FIFO)原則選取下一個(gè)節(jié)點(diǎn)為

擴(kuò)展節(jié)點(diǎn)

A.錯(cuò)誤

B.正確

6.回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。

A.錯(cuò)誤

B.正確

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

解

A.錯(cuò)誤

B.正確

8.分支限界法與回溯法完全不同

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

10.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題,

然后從這些子問題的解得到原問題的解。

A.錯(cuò)誤

B..正確

北語18春《算法與數(shù)據(jù)分析》作業(yè)2-0001

試卷總分：100得分：100

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

1.分治法所能解決的問題一般具有的幾個(gè)特征不包括

A.該問題的規(guī)?？s小到一定的程度就可以容易地解決

B.該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

C.利用該問題分解出的子問題的解不可以合并為該問題的解

D.原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問

題

2.下面關(guān)于NP問題說法正確的是

A.NP問題都是不可能解決的問題

B.P類問題包含在NP類問題中

C.NP完全問題是P類問題的子集

D.NP類問題包含在P類問題中

3.背包問題的貪心算法所需的計(jì)算時(shí)間為

A.O(n2n)

B.O(nlogn)

C.O(2n)

D.O(n)

4.關(guān)于分支限界法的搜索策略描述錯(cuò)誤的是

A.在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支）

B.從當(dāng)前的活結(jié)點(diǎn)表中選擇上一個(gè)擴(kuò)展結(jié)點(diǎn)。

C.為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn)程，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一

個(gè)函數(shù)值（限界）

D.根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索

朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解.

5.二分搜索算法是利用什么實(shí)現(xiàn)的算法

A.分治策略

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

C.貪心法

D.回溯法

6.在下列算法中有時(shí)找不到問題解的是

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

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

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

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

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

8.下面不是分支界限法搜索方式的是

A.廣度優(yōu)先

B.最小耗費(fèi)優(yōu)先

C.最大效益優(yōu)先

D.深度優(yōu)先

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

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

B.搜索方式相同

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

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

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

A.先進(jìn)先出

B.后進(jìn)先出

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

D.隨機(jī)

二、判斷題（共10道試題，共50分）

1.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)。

A.錯(cuò)誤

B.正確

2.回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

4.快速排序算法不是基于分治策略的一種排序算法。

A.錯(cuò)誤

B.正確

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

法的主要區(qū)別。

A.錯(cuò)誤

B.正確

6.分支限界法與回溯法都是一種在問題的解空間樹T中搜索問題解的算法

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

8.舍伍德算法總能求得問題的一個(gè)解。

A.錯(cuò)誤

B.正確

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

解

A.錯(cuò)誤

B.正確

10.數(shù)值概率算法常用于數(shù)值問題的求解。

A.錯(cuò)誤

B.正確

北語18春《算法與數(shù)據(jù)分析》作業(yè)3-0001

試卷總分：100得分：100

一、單選題（共10道試題，共50分）

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

A.重疊子問題

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

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

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

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

A.先進(jìn)先出

B.后進(jìn)先出

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

D.隨機(jī)

3.衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是

A.運(yùn)行速度快

B.占用空間少

C.時(shí)間復(fù)雜度低

D.代碼短

4.下面不是分支界限法搜索方式的是

A.廣度優(yōu)先

B.最小耗費(fèi)優(yōu)先

C.最大效益優(yōu)先

D.深度優(yōu)先

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

A.分治策略

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

C.貪心法

D晌溯法

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

A.子問題必須是一樣的

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

C.子問題的解可以合并

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

7.貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是

A.最優(yōu)子結(jié)構(gòu)

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

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

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

8.合并排序算法是利用

A.分治策略

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

C.貪心法

D.回溯法

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

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

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

A.分治策略

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

C.貪心法

D.回溯法

二、判斷題（共10道試題，共50分）

1.快速排序算法不是基于分治策略的一種排序算法。

A.錯(cuò)誤

B.正確

2.大整數(shù)乘積算法是用分治法來設(shè)計(jì)的。

A.錯(cuò)誤

B.正確

3.分支限界法與回溯法都是一種在問題的解空間樹T中搜索問題解的算法

A.錯(cuò)誤

B.正確

4.分支限界法與回溯法完全不同

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B正確

7.使用回溯法進(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

皇后問題

A.錯(cuò)誤

B.正確

8.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。

A.錯(cuò)誤

B.正確

9.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性

四條性質(zhì)。

A.錯(cuò)誤

B.正確

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

的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法，分支限界法

A.錯(cuò)誤

B.正確

北語18春《算法與數(shù)據(jù)分析》作業(yè)4-0001

試卷總分：100得分：100

一、單選題（共10道試題，共50分）

1.二分搜索算法是利用什么實(shí)現(xiàn)的算法

A.分治策略

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

C貪心法

D.回溯法

2.下面是貪心穿法的基本要素的是

A.重疊子問題

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

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

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

3.衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是

A.運(yùn)行速度快

B.占用空間少

C.時(shí)間復(fù)雜度低

Ddtfi馬短

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

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

5.貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)是

A.重疊子問題

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

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

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

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

A.子問題必須是一樣的

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

C.子問題的解可以合并

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

7.回溯法的效率不依賴于下列哪些因素

A.滿足顯約束的值的個(gè)數(shù)

B..計(jì)算約束函數(shù)的時(shí)間

C..計(jì)算限界函數(shù)的時(shí)間

D..確定解空間的時(shí)間

8.舍伍德算法是以下的哪一種

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

9.下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是

A.找出最優(yōu)解的性質(zhì)

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

C.算出最優(yōu)解

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

10.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

二、判斷題（共10道試題，共50分）

1.快速排序算法不是基于分治策略的一種排序算法。

A.錯(cuò)誤

B.正確

2.算法的“確定性”指的是組成算法的每條指令是清晰的，有歧義的。

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

4.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題,

然后從這些子問題的解得到原問題的解。

A.錯(cuò)誤

B.正確

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

A.錯(cuò)誤

B.正確

6.常