北京語言大學《算法與數(shù)據(jù)分析》作業(yè)4答卷

20秋《算法與數(shù)據(jù)分析》作業(yè)4試卷總分:100得分:100一、單選題(共10道試題,共50分)下面是貪心算法的基本要素的是重疊子問題構(gòu)造最優(yōu)解貪心選擇性質(zhì)定義最優(yōu)解答案:C2.最大效益優(yōu)先是下列哪項的一種搜索方式分支界限法動態(tài)規(guī)劃法貪心法回溯法答案:A3.用分支限界法設(shè)計算法的第二步是針對所給問題，定義問題的解空間（對解進行編碼確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間在搜索過程中用剪枝函數(shù)避免無效搜索答案:B4.下列算法中通常以自底向上的方式求解最優(yōu)解的是備忘錄法動態(tài)規(guī)劃法貪心法回溯法答案:B5.分支限界法與回溯法的相同點是求解目標相同搜索方式相同對擴展結(jié)點的擴展方式相同都是一種在問題的解空間樹T中搜索問題解的算法答案:D6.實現(xiàn)大整數(shù)的乘法是利用的算法貪心法動態(tài)規(guī)劃法分治策略回溯法答案:C7.矩陣連乘問題的算法可由什么設(shè)計實現(xiàn)分支界限算法動態(tài)規(guī)劃算法貪心算法回溯算法答案:B8.分支限界法解最大團問題時，活結(jié)點表的組織形式是最小堆最大堆棧數(shù)組答案:B9.回溯法搜索狀態(tài)空間樹是按照什么的順序中序遍歷廣度優(yōu)先遍歷深度優(yōu)先遍歷層次優(yōu)先遍歷答案:C10.廣度優(yōu)先是什么的一種搜索方式分支界限法動態(tài)規(guī)劃法貪心法回溯法答案:A二、判斷題(共10道試題,共50分)11.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。答案:正確12.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。答案:正確13.分治法的基本思想時將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解答案:正確14.任何可用計算機求解的問題所需的時間都與其規(guī)模無關(guān)。答案:錯誤15.分治法與動態(tài)規(guī)劃法的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的答案:正確16.分支限界法主要有隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。答案:正確17.拉斯維加斯算法找到的解不一定是正確解答案:錯誤18.問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題不可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。答案:錯誤19.解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法答案:正確20.利用