[北京語言大學(xué)]20秋《算法與數(shù)據(jù)分析》作業(yè)1
試卷總分:100    得分:100
第1題,在下列算法中得到的解未必正確的是
A、蒙特卡羅算法
B、拉斯維加斯算法
C、舍伍德算法
D、數(shù)值概率算法
正確答案:


第2題,0-1背包問題的回溯算法所需的計(jì)算時(shí)間為
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
正確答案:


第3題,實(shí)現(xiàn)最長公共子序列利用的算法是
A、分治策略
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
正確答案:


第4題,以下不可以使用分治法求解的是
A、棋盤覆蓋問題
B、選擇問題
C、歸并排序
D、0/1背包問題
正確答案:


答案來源：（www.）,優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是
A、先進(jìn)先出
B、后進(jìn)先出
C、結(jié)點(diǎn)的優(yōu)先級(jí)
D、隨機(jī)
正確答案:


第6題,下列哪一種算法不是隨機(jī)化算法
A、蒙特卡羅算法
B、.拉斯維加斯算法
C、.動(dòng)態(tài)規(guī)劃算法
D、.舍伍德算法
正確答案:


第7題,回溯法解旅行售貨員問題時(shí)的解空間樹是
A、子集樹
B、排列樹
C、深度優(yōu)先生成樹
D、廣度優(yōu)先生成樹
正確答案:


第8題,下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是
A、數(shù)值概率算法
B、舍伍德算法
C、拉斯維加斯算法
D、蒙特卡羅算法
正確答案:


第9題,分支限界法解旅行售貨員問題時(shí)，活結(jié)點(diǎn)表的組織形式是
A、最小堆
B、最大堆
C、棧
D、數(shù)組
正確答案:


答案來源：（www.）,使用分治法求解不需要滿足的條件是
A、子問題必須是一樣的
B、子問題不能夠重復(fù)
C、子問題的解可以合并
D、原問題和子問題使用相同的方法解
正確答案:


第11題,算法的復(fù)雜性沒有時(shí)間復(fù)雜性和空間復(fù)雜性之分
A、錯(cuò)誤
B、正確
正確答案:


答案來源：（www.）,拉斯維加斯算法找到的解不一定是正確解
A、錯(cuò)誤
B、正確
正確答案:


第13題,分支限界法與回溯法的求解目標(biāo)相同
A、錯(cuò)誤
B、正確
正確答案:


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


答案來源：（www.）,設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟不包括根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解
A、錯(cuò)誤
B、正確
正確答案:


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


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


第18題,利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是蒙特卡羅算法
A、錯(cuò)誤
B、正確
正確答案:


第19題,使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問題，只使用約束條件進(jìn)行裁剪的是N皇后問題
A、錯(cuò)誤
B、正確
正確答案:


答案來源：（www.）,分治法的基本思想時(shí)將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問題的解
A、錯(cuò)誤
B、正確
正確答案: