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

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