緒論單元測(cè)試
1.山東師范大學(xué)的管教授在哪個(gè)問題上給出了比較好的解決方法。
A:郵遞員問題
B:背包問題
C:裝載問題
D:最大團(tuán)問題
答案:A
第一章測(cè)試
2.算法具備的四個(gè)基本性質(zhì)是（）
A:輸入
B:有限性
C:確定性
D:輸出
答案:ABCD
3.算法就是程序
A:錯(cuò)
B:對(duì)
答案:A
4.描述漸進(jìn)上界的符號(hào)是（）
A:Ω
B:ω
C:O
D:θ
答案:C
5.f(n)=3n2+n+1,下面不正確的是()
A:f(n)=O(n3)
B:f(n)=O(n2)
C:f(n)=O(2n)
D:f(n)=O(3n2)
答案:C
6.在算法分析中，我們希望找到更加高階的上界函數(shù)
A:錯(cuò)
B:對(duì)
答案:A
第二章測(cè)試
7.Strasn 矩陣乘法是利用（ ）實(shí)現(xiàn)的算法。
A:貪心法
B:分治策略
C:動(dòng)態(tài)規(guī)劃法
D:回溯法
答案:B
8.使用分治法求解不需要滿足的條件是（ ）
A:子問題不能夠重復(fù)
B:子問題的解可以合并
C:子問題必須是一樣的
D:原問題和子問題使用相同的方法解
答案:C
9.實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（ ）。
A:分治法
B:回溯法
C:動(dòng)態(tài)規(guī)劃法
D:貪心法
答案:A
10.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（ ）。
A:貪心法
B:回溯法
C:分治策略
D:動(dòng)態(tài)規(guī)劃法
答案:C
11.從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法
A:對(duì)
B:錯(cuò)
答案:A
第三章測(cè)試
12.動(dòng)態(tài)規(guī)劃算法一般分成（ ）三個(gè)階段。
A:求解
B:分析
C:分段
D:匯總
答案:ABC
13.動(dòng)態(tài)規(guī)劃的基本要素有（ ）？
A:備忘錄方法
B:最優(yōu)子結(jié)構(gòu)
C:子問題的重疊性質(zhì)
答案:ABC
14.用動(dòng)態(tài)規(guī)劃法求解的問題都可以分解為相互重疊的子問題。
A:對(duì)
B:錯(cuò)
答案:A
15.動(dòng)態(tài)規(guī)劃法利用遞推關(guān)系式（ ）計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。
A:循環(huán)
B:遞歸
C:自底向上
D:自頂向下
答案:C
16.最優(yōu)子結(jié)構(gòu)是問題可以用動(dòng)態(tài)規(guī)劃法求解的前提。
A:錯(cuò)
B:對(duì)
答案:B
第四章測(cè)試
17.貪心算法中每次做出的貪心選擇都是全局最優(yōu)選擇。
A:對(duì)
B:錯(cuò)
答案:B
18.下面問題不能使用貪心法解決的是
A:N皇后問題
B:最小花費(fèi)生成樹問題
C:背包問題
D:單源最短路徑問題
答案:A
19.背包問題的貪心算法所需的計(jì)算時(shí)間為
A:O（n2n）
B:O（n）
C:O（nlogn）
D:O（2n）
答案:C
20.哈夫曼編碼是自底向上構(gòu)造的
A:錯(cuò)
B:對(duì)
答案:B
21.Kruskal算法的時(shí)間復(fù)雜度是
A:O（eloge）
B:O（n）
C:O（nlogn）
D:O（2n）
答案:A
第五章測(cè)試
22.回溯法就是窮舉法
A:錯(cuò)
B:對(duì)
答案:A
23.回溯法使用的是廣度優(yōu)先遍歷
A:對(duì)
B:錯(cuò)
答案:B
24.回溯法必須尋找一個(gè)限界函數(shù)
A:對(duì)
B:錯(cuò)
答案:B
25.使用回溯法時(shí)可以考慮以下哪些方面()
A:約束函數(shù)
B:解空間結(jié)構(gòu)
C:解的向量形式
D:解的最優(yōu)子結(jié)構(gòu)性質(zhì)
答案:ABC
26.回溯法在處理n皇后問題時(shí)，必須把解空間組織成子集樹。
A:錯(cuò)
B:對(duì)
答案:A
第六章測(cè)試
27.分支限界法特別適合求解最優(yōu)值問題。
A:錯(cuò)
B:對(duì)
答案:B
28.分支限界法可以根據(jù)選擇活動(dòng)節(jié)點(diǎn)的不同分成().
A:深度優(yōu)先分支限界法
B:FIFO隊(duì)列式分支限界法
C:廣度優(yōu)先分支限界法
D:優(yōu)先隊(duì)列式分支限界法
答案:BD
29.在使用分支限界法解決TSP問題是，可以怎樣確定限界函數(shù)().
A:隨機(jī)找一個(gè)回路作為下界
B:每行最小值累加估算下界
C:使用貪心法估算上界
D:每行最小兩個(gè)值累加除以2估算下界
答案:BCD
30.分支限界法比回溯法效率高
A:對(duì)
B:錯(cuò)
答案:B
31.分支限界法只適合求極大值問題
A:錯(cuò)
B:對(duì)
答案:A
第七章測(cè)試
32.連續(xù)傅里葉(Fourier)變換實(shí)質(zhì)上是實(shí)函數(shù)在復(fù)數(shù)域上分解與合成。（ ）
A:對(duì)
B:錯(cuò)
答案:A
33.離散傅里葉(Fourier)變換實(shí)質(zhì)上是實(shí)數(shù)列利用基函數(shù)在復(fù)數(shù)域上分解與合成。（ ）
A:對(duì)
B:錯(cuò)
答案:A
34.余弦變換(DCT)是傅里葉變換的特例，且離散余弦變換(DCT)主要應(yīng)用于圖像壓縮。（ ）
A:對(duì)
B:錯(cuò)
答案:A
35.小波分析方法的應(yīng)用主要有( )
A:圖像邊緣檢測(cè)，圖像壓縮和重建
B:語(yǔ)音信號(hào)處理
C:時(shí)頻分析
D:地震信號(hào)分析
答案:ABCD
