[北京語言大學(xué)]20秋《算法與數(shù)據(jù)分析》作業(yè)2
試卷總分:100    得分:100
第1題,采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
正確答案:


第2題,在下列算法中有時(shí)找不到問題解的是
A、蒙特卡羅算法
B、拉斯維加斯算法
C、舍伍德算法
D、數(shù)值概率算法
正確答案:


第3題,最長公共子序列算法利用的算法是
A、分支界限法
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第4題,下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是
A、備忘錄法
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


答案來源：（www.）,Strassen矩陣乘法是利用什么實(shí)現(xiàn)的算法
A、分治策略
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第6題,以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為
A、分支界限算法
B、概率算法
C、貪心算法
D、回溯算法
正確答案:


第7題,下列算法中不能解決0/1背包問題的是
A、貪心法
B、動(dòng)態(tài)規(guī)劃
C、回溯法
D、分支限界法
正確答案:


第8題,備忘錄方法是那種算法的變形
A、分治法
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第9題,下面關(guān)于NP問題說法正確的是
A、NP問題都是不可能解決的問題
B、P類問題包含在NP類問題中
C、NP完全問題是P類問題的子集
D、NP類問題包含在P類問題中
正確答案:


答案來源：（www.）,舍伍德算法是以下的哪一種
A、分支界限算法
B、概率算法
C、貪心算法
D、回溯算法
正確答案:


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


答案來源：（www.）,設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟有5步
A、錯(cuò)誤
B、正確
正確答案:


第13題,貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，但不是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別
A、錯(cuò)誤
B、正確
正確答案:


第14題,回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。
A、錯(cuò)誤
B、正確
正確答案:


答案來源：（www.）,從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法。
A、錯(cuò)誤
B、正確
正確答案:√


第16題,算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。
A、錯(cuò)誤
B、正確
正確答案:


第17題,分治法與動(dòng)態(tài)規(guī)劃法的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的
A、錯(cuò)誤
B、正確
正確答案:


第18題,舍伍德算法總能求得問題的一個(gè)解。
A、錯(cuò)誤
B、正確
正確答案:


第19題,快速排序算法的性能取決于劃分的對(duì)稱性
A、錯(cuò)誤
B、正確
正確答案:


答案來源：（www.）,回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。
A、錯(cuò)誤
B、正確
正確答案: