[北京語言大學]20秋《算法與數(shù)據(jù)分析》作業(yè)4
試卷總分:100    得分:100
第1題,下面是貪心算法的基本要素的是
A、重疊子問題
B、構(gòu)造最優(yōu)解
C、貪心選擇性質(zhì)
D、定義最優(yōu)解
正確答案:


第2題,最大效益優(yōu)先是下列哪項的一種搜索方式
A、分支界限法
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第3題,用分支限界法設計算法的第二步是
A、針對所給問題，定義問題的解空間（對解進行編碼
B、確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）
C、以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間
D、在搜索過程中用剪枝函數(shù)避免無效搜索
正確答案:


第4題,下列算法中通常以自底向上的方式求解最優(yōu)解的是
A、備忘錄法
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


答案來源：（www.）,分支限界法與回溯法的相同點是
A、求解目標相同
B、搜索方式相同
C、對擴展結(jié)點的擴展方式相同
D、都是一種在問題的解空間樹T中搜索問題解的算法
正確答案:


第6題,實現(xiàn)大整數(shù)的乘法是利用的算法
A、貪心法
B、動態(tài)規(guī)劃法
C、分治策略
D、回溯法
正確答案:


第7題,矩陣連乘問題的算法可由什么設計實現(xiàn)
A、分支界限算法
B、動態(tài)規(guī)劃算法
C、貪心算法
D、回溯算法
正確答案:


第8題,分支限界法解最大團問題時，活結(jié)點表的組織形式是
A、最小堆
B、最大堆
C、棧
D、數(shù)組
正確答案:


第9題,回溯法搜索狀態(tài)空間樹是按照什么的順序
A、中序遍歷
B、廣度優(yōu)先遍歷
C、深度優(yōu)先遍歷
D、層次優(yōu)先遍歷
正確答案:


答案來源：（www.）,廣度優(yōu)先是什么的一種搜索方式
A、分支界限法
B、動態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第11題,以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。
A、錯誤
B、正確
正確答案:


答案來源：（www.）,算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。
A、錯誤
B、正確
正確答案:


第13題,分治法的基本思想時將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解
A、錯誤
B、正確
正確答案:


第14題,任何可用計算機求解的問題所需的時間都與其規(guī)模無關。
A、錯誤
B、正確
正確答案:


答案來源：（www.）,分治法與動態(tài)規(guī)劃法的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的
A、錯誤
B、正確
正確答案:


第16題,分支限界法主要有隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。
A、錯誤
B、正確
正確答案:


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


第18題,問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題不可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。
A、錯誤
B、正確
正確答案:


第19題,解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法
A、錯誤
B、正確
正確答案:


答案來源：（www.）,利用概率的性質(zhì)計算近似值的隨機算法是數(shù)值概率算法，運行時以一定的概率得到正確解的隨機算法是蒙特卡羅算法
A、錯誤
B、正確
正確答案: