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