北京語言大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《算法與數(shù)據(jù)分析》考試高頻考點(diǎn)參考題庫(kù)帶答案

長(zhǎng)風(fēng)破浪會(huì)有時(shí)，直掛云帆濟(jì)滄海。北京語言大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《算法與數(shù)據(jù)分析》考試高頻考點(diǎn)參考題庫(kù)帶答案（圖片大小可自由調(diào)整）第I卷一.綜合考核(共15題)1.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。()A.錯(cuò)誤B.正確2.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。()A.錯(cuò)誤B.正確3.最大效益優(yōu)先是下列哪項(xiàng)的一種搜索方式?()A.分支界限法B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法4.任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其規(guī)模無關(guān)。()A.錯(cuò)誤B.正確5.合并排序算法是利用()。A.分治策略B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法6.廣度優(yōu)先是什么的一種搜索方式?()A.分支界限法B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法7.蒙特卡羅算法是以下的哪種?()A.分支界限算法B.概率算法C.貪心算法D.回溯算法8.一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的()。A.重疊子問題B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.貪心選擇性質(zhì)D.定義最優(yōu)解9.下面是貪心算法的基本要素的是()。A.重疊子問題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)D.定義最優(yōu)解10.舍伍德算法是以下的哪一種?()A.分支界限算法B.概率算法C.貪心算法D.回溯算法11.下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是()。A.數(shù)值概率算法B.舍伍德算法C.拉斯維加斯算法D.蒙特卡羅算法12.下面關(guān)于NP問題說法正確的是()。A.NP問題都是不可能解決的問題B.P類問題包含在NP類問題中C.NP完全問題是P類問題的子集D.NP類問題包含在P類問題中13.分支限界法與回溯法的相同點(diǎn)是()。A.求解目標(biāo)相同B.搜索方式相同C.對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式相同D.都是一種在問題的解空間樹T中搜索問題解的算法14.利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是蒙特卡羅算法。()A.錯(cuò)誤B.正確15.實(shí)現(xiàn)合并排序利用的算法是()。A.分治策略B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法第II卷一.綜合考核(共15題)1.快速排序算法的性能取決于劃分的對(duì)稱性。()A.錯(cuò)誤B.正確2.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。()A.錯(cuò)誤B.正確3.Strassen矩陣乘法是利用什么實(shí)現(xiàn)的算法?()A.分治策略B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法4.分治法與動(dòng)態(tài)規(guī)劃法的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的。()A.錯(cuò)誤B.正確5.下列算法中不能解決0/1背包問題的是()。A.貪心法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分支限界法6.回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。()A.錯(cuò)誤B.正確7.采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為()。A.O(n2n)B.O(nlogn)C.O(2n)D.O(n)8.計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。()A.錯(cuò)誤B.正確9.用分支限界法設(shè)計(jì)算法的第二步是()。A.針對(duì)所給問題，定義問題的解空間(對(duì)解進(jìn)行編碼B.確定易于搜索的解空間結(jié)構(gòu)(按樹或圖組織解)C.以廣度優(yōu)先或以最小耗費(fèi)(最大收益)優(yōu)先的方式搜索解空間D.在搜索過程中用剪枝函數(shù)避免無效搜索10.分支限界法主要有隊(duì)列式(FIFO)分支限界法和優(yōu)先隊(duì)列式分支限界法。()A.錯(cuò)誤B.正確11.分支限界法解旅行售貨員問題時(shí)，活結(jié)點(diǎn)表的組織形式是()。A.最小堆B.最大堆C.棧D.數(shù)組12.解決0/1背包問題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。()A.錯(cuò)誤B.正確13.從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法。()A.錯(cuò)誤B.正確14.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。()A.錯(cuò)誤B.正確15.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為()。A.O(n2n)B.O(nlogn)C.O(2n)D.O(n)第III卷一.綜合考核(共15題)1.實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是()。A.分治策略B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法2.程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。()A.錯(cuò)誤B.正確3.0-1背包問題的回溯算法所需的計(jì)算時(shí)間為()。A.O(n2n)B.O(nlogn)C.O(2n)D.O(n)4.使用分治法求解不需要滿足的條件是()。A.子問題必須是一樣的B.子問題不能夠重復(fù)C.子問題的解可以合并D.原3、問題和子問題使用相同的方法解5.算法的復(fù)雜性沒有時(shí)間復(fù)雜性和空間復(fù)雜性之分。()A.錯(cuò)誤B.正確6.貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，但不是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。()A.錯(cuò)誤B.正確7.回溯法解旅行售貨員問題時(shí)的解空間樹是()。A.子集樹B.排列樹C.深度優(yōu)先生成樹D.廣度優(yōu)先生成樹8.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟有5步。()A.錯(cuò)誤B.正確9.下列算法中通常以自底向上的方式求解最優(yōu)解的是()。A.備忘錄法B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法10.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。()A.錯(cuò)誤B.正確11.備忘錄方法是哪種算法的變形?()A.分治法B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法12.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為()。A.分支界限算法B.概率算法C.貪心算法D.回溯算法13.分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是()。A.最小堆B.最大堆C.棧D.數(shù)組14.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟不包括根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。()A.錯(cuò)誤B.正確15.在下列算法中得到的解未必正確的是()。A.蒙特卡羅算法B.拉斯維加斯算法C.舍伍德算法D.數(shù)值概率算法第I卷參考答案一.綜合考核1.參考答案：B2.參考答案：B3.參考答案：A4.參考答案：A5.參考答案：A6.參考答案：A7.參考答案：B8.參考答案：B9.參考答案：C10.參考答案：B11.參考答案：C12.參考答案：B13.參考答案：D14.參考答案：B15.參考答案：A第II卷參考答案一.綜合考核1.參考答案：B2.參考答案：B3.參考答案：A4.參考答案：B5.參考答案：A6.參考答案：B7.參考答案：B8.參考答案：B9.參考答案：B10.參考答案：B11.參考答案：A12.參考答案：B13.參考答案：B14.參考答案：