[北京語言大學]20秋《算法與數(shù)據(jù)分析》作業(yè)3
試卷總分:100    得分:100
第1題,用分支限界法設計算法的第二步是
A、針對所給問題，定義問題的解空間（對解進行編碼
B、確定易于搜索的解空間結構（按樹或圖組織解）
C、以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間
D、在搜索過程中用剪枝函數(shù)避免無效搜索
正確答案:


第2題,蒙特卡羅算法是以下的哪種
A、分支界限算法
B、概率算法
C、貪心算法
D、回溯算法
正確答案:


第3題,一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的
A、重疊子問題
B、最優(yōu)子結構性質(zhì)
C、貪心選擇性質(zhì)
D、定義最優(yōu)解
正確答案:


第4題,實現(xiàn)合并排序利用的算法是
A、分治策略
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


答案來源：（www.）,實現(xiàn)最大子段和利用的算法是
A、分治策略
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第6題,下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略
A、遞歸函數(shù)
B、.剪枝函數(shù)
C、。隨機數(shù)函數(shù)
D、.搜索函數(shù)
正確答案:


第7題,哈弗曼編碼的貪心算法所需的計算時間為
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
正確答案:


第8題,實現(xiàn)棋盤覆蓋算法利用的算法是
A、分治法
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第9題,合并排序算法是利用
A、分治策略
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


答案來源：（www.）,下面是貪心算法的基本要素的是
A、重疊子問題
B、構造最優(yōu)解
C、貪心選擇性質(zhì)
D、定義最優(yōu)解
正確答案:


第11題,矩陣連乘問題的算法可由動態(tài)規(guī)劃設計實現(xiàn)。
A、錯誤
B、正確
正確答案:


答案來源：（www.）,分支限界法是一種只帶有系統(tǒng)性的搜索算法。
A、錯誤
B、正確
正確答案:


第13題,矩陣連乘問題的算法可由動態(tài)規(guī)劃設計實現(xiàn)
A、錯誤
B、正確
正確答案:


第14題,拉斯維加斯算法找到的解不一定是正確解。
A、錯誤
B、正確
正確答案:


答案來源：（www.）,動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。
A、錯誤
B、正確
正確答案:


第16題,程序是算法用某種程序設計語言的具體實現(xiàn)
A、錯誤
B、正確
正確答案:


第17題,貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結構性質(zhì)
A、錯誤
B、正確
正確答案:


第18題,計算一個算法時間復雜度通?？梢杂嬎阊h(huán)次數(shù)、基本操作的頻率或計算步。
A、錯誤
B、正確
正確答案:


第19題,分支限界法與回溯法的求解目標相同
A、錯誤
B、正確
正確答案:


答案來源：（www.）,快速排序算法的性能取決于劃分的對稱性
A、錯誤
B、正確
正確答案: