算法選擇題初級版256道

1、算法選擇題（初級版）256道.二分搜索算法是利用（）實現(xiàn)的算法。單選題*A.分治策略（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.回溯法解旅行售貨員問題時的解空間樹是（）o單選題A.子集樹B.排列樹（正確答案）C.深度優(yōu)先生成樹D.廣度優(yōu)先生成樹單選題*3單選題*A.備忘錄法B.動態(tài)規(guī)劃法（正確答案）C.貪心法D.回溯法4.下面不是分支界限法搜索方式的是（）o單選題*A.廣度優(yōu)先B.最小耗費優(yōu)先C.最大效益優(yōu)先D.深度優(yōu)先（正確答案）5.采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為（）。單選題*A.O （n2An）B.O （nlogn）（正確答

2、案）C.O （2An）D.O （n）6.分支限界法求解最大團(tuán)問題時，活結(jié)點表的組織形式是（）。單選題*A.最小堆B.最大堆（正確答案）C棧D.數(shù)組.下面問題（）不能使用貪心法解決。單選題*A.單源最短路徑問題.N皇后問題（正確答案）C.最小花費生成樹問題D.背包問題.下列算法中不能解決0/1背包問題的是（）。單選題*A.貪心法（正確答案）B.動態(tài)規(guī)劃C.回溯法D.分支限界法單選題*.單選題*A.O (n2n)B.O （nlogn）（正確答案）C.O （2n）D.O （n）.二分查找是利用（）實現(xiàn)的算法。單選題*A.分治策略（正確答案）B.動態(tài)規(guī)劃法C.分支限界法D.概率算法.下列不是動態(tài)規(guī)劃算

3、法基本步驟的是（）。單選題*A.找出最優(yōu)解的性質(zhì)B.構(gòu)造最優(yōu)解（正確答案）C.算出最優(yōu)解D.定義最優(yōu)解.最大效益優(yōu)先是（）的一種搜索方式。單選題*A.分支界限法（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.在下列算法中有時找不到問題解的是（）。單選題*A.蒙特卡羅算法B.拉斯維加斯算法（正確答案）C.舍伍德算法D.數(shù)值概率算法14.對于動態(tài)規(guī)劃，下面說法錯誤的是（）14.對于動態(tài)規(guī)劃，下面說法錯誤的是（）單選題*A.動態(tài)規(guī)劃（dynamic programming）是運(yùn)籌學(xué)的一個分支B.動態(tài)規(guī)劃是求解決策過程（decision process最優(yōu)化的數(shù)學(xué)方法C.雖然動態(tài)規(guī)劃主要用于求解以時間

4、劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與 時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時間因素，把它 視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。D.動態(tài)規(guī)劃類似搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的 解題方法。（正確答案）15.衡量一個算法好壞的標(biāo)準(zhǔn)是（）。單選題*A.運(yùn)行速度快B.占用空間少C.時間復(fù)雜度低（正確答案）D.代碼短.以下不可以使用分治法求解的是（）。單選題*A.棋盤覆蓋問題B.選擇問題C.歸并排序D.0/1背包問題（正確答案）.實現(xiàn)循環(huán)賽日程表利用的算法是（）。單選題*A.分治策略（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.下列隨

5、機(jī)算法中運(yùn)行時有時候成功有時候失敗的是（）。單選題*A.數(shù)值概率算法B.舍伍德算法C.拉斯維加斯算法（正確答案）D.蒙特卡羅算法.對于分支限界法，下面不屬于分支限界法搜索方式的是（）。單選題*A.廣度優(yōu)先B.最小耗費優(yōu)先C.最大效益優(yōu)先D.層次優(yōu)先（正確答案）.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（）o單選題*A.備忘錄法B.動態(tài)規(guī)劃法C.貪心法D.回溯法（正確答案）.備忘錄方法是那種算法的變形（）。單選題*A.分治法B.動態(tài)規(guī)劃法（正確答案）C.貪心法D.回溯法22.哈夫曼編碼的貪心算法所需的計算時間為（）。單選題*O（n2n）O（nlogn）（正確答案）O（2n）O（n）23.最

6、長公共子序列算法利用的算法是（）單選題*A.分支界限法B.動態(tài)規(guī)劃法（正確答案）C.貪心法D.回溯法.實現(xiàn)棋盤覆蓋算法利用的算法是（）o單選題*A.分治法（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.下面是貪心算法的基本要素的是（）o單選題*A.重疊子問題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)（正確答案）D.定義最優(yōu)解.回溯法的效率不依賴于下列哪些因素（）。單選題*A.滿足顯約束的值的個數(shù)C.計算限界函數(shù)的時間B.計算約束函數(shù)的時間D.確定解空間的時間（正確答案）單選題*.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（）單選題*A.遞歸函數(shù)B.剪枝函數(shù)（正確答案）C.隨機(jī)數(shù)函數(shù)D.搜索函數(shù).下面關(guān)

7、于NP問題說法正確的是（）。NP問題都是不可能解決的問題P類問題包含在NP類問題中（正確答案）NP完全問題是P類問題的子集NP類問題包含在P類問題中.蒙特卡羅算法是（）的一種。單選題A.分支界限算法B.概率算法（正確答案）C.貪心算法D.回溯算法30.下列哪一種算法不是隨機(jī)化算法（）。A.蒙特卡羅算法B.拉斯維加斯算法C.動態(tài)規(guī)劃算法（正確答案）D.舍伍德算法31.（）是貪心算法與動態(tài)規(guī)劃算法的共同點A.重疊子問題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)單選題*單選題*單選題*32單選題*單選題*單選題*32.矩陣連乘問題的算法可由（）設(shè)計實現(xiàn)單選題*A.分支界限算法B.動態(tài)規(guī)劃算法（正確答案）C.貪心

8、算法D.回溯算法. Strassel巨陣乘法是利用（）實現(xiàn)的算法。單選題*A.分治策略（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.使用分治法求解不需要滿足的條件是（）o單選題*A.子問題必須是一樣的（正確答案）B.子問題不能夠重復(fù)C.子問題的解可以合并D.原問題和子問題使用相同的方法求解.回溯法搜索狀態(tài)空間樹是按（）的順序。單選題*A.中序遍歷B.廣度優(yōu)先遍歷C.深度優(yōu)先遍歷（正確答案）D.層次優(yōu)先遍歷.實現(xiàn)合并排序利用的算法是（）o 單選題*A.分治策略（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.下列是動態(tài)規(guī)劃算法基本要素的是（）。單選題*A.定義最優(yōu)解B.構(gòu)造最優(yōu)解C.算出最優(yōu)解D

9、.子空間重疊性質(zhì)（正確答案）.采用廣度優(yōu)先策略搜索的算法是（）。單選題*A.分支限界法（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.在下列算法中得到的解未必正確的是（）o單選題*A.蒙特卡羅算法（正確答案）B.拉斯維加斯算法C.舍伍德算法D.數(shù)值概率算法.實現(xiàn)大整數(shù)的乘法是利用的算法（）。單選題*A.貪心法B.動態(tài)規(guī)劃法C.分治策略（正確答案）D.回溯法. 0/1背包問題的回溯算法所需的計算時間為（）。單選題*O （n2n）（正確答案）O （nlogn）O （2n）O （n）.動態(tài)規(guī)劃算法與貪心法的主要區(qū)別是（）。單選題*A.最優(yōu)子結(jié)構(gòu)（正確答案）B.貪心選擇性質(zhì)C.構(gòu)造最優(yōu)解D.定義最優(yōu)解

10、.實現(xiàn)最大子段和利用的算法是（）。單選題*A.分治策略B.動態(tài)規(guī)劃法（正確答案）C.貪心法D.回溯法.優(yōu)先隊列式分支限界法選取擴(kuò)展結(jié)點的原則是（）o 單選題*A.先進(jìn)先出B.后進(jìn)先出C.結(jié)點的優(yōu)先級（正確答案）D.隨機(jī).廣度優(yōu)先是（）的一種搜索方式。單選題*A.分支限界算法（正確答案）B.動態(tài)規(guī)劃法C.貪心算法D.回溯算法46.舍伍德算法是（）的一種單選題*A.分支界限算法B.概率算法（正確答案）C.貪心算法D.回溯算法47.對于下列算法，有時找不到問題解的是（）。單選題*A.蒙特卡羅算法B.拉斯維加斯算法（正確答案）C.快速排序算法D.數(shù)值概率算法.下列哪一種算法是隨機(jī)化算法（）。單選題*A

11、.貪心算法B.回溯法C.動態(tài)規(guī)劃算法D.舍伍德算法（正確答案）. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（題*A.重疊子問題（正確答案）B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.貪心選擇性質(zhì)D.定義最優(yōu)解.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為（）。單選題*A.分支界限算法B.概率算法C.貪心算法D.回溯算法（正確答案）.對于最長公共子序列，下面說法錯誤的是（）。單選題*A.最長公共子序列，英文縮寫為 LCS （Longest Common Subsequencee。其定義 是，一個序列S,如果分別是兩個或多個已知序列的子序列，且是所有符合此條 件序列中最長的，則S稱為已知序列的最長公共子序列。

12、B.最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的相似度工C.最長公共子用和最長公共子序列是不同的D.最長公共子用和最長公共子序列是相同的（正確答案）.當(dāng)一個算法的空間復(fù)雜度與問題的規(guī)模 n成正比時，則表示為（）。單選題*A.O（1）B.O（n）（正確答案）C.O（n*n）D.O1.當(dāng)一個算法的時間復(fù)雜性與問題的規(guī)模 n大小無關(guān)時，則表示為（）。單選 題*A.1B.O（1）（正確答案）C.O（n）D.O（0）.算法分析的兩個主要方面是（）。單選題*A.空間復(fù)雜度和時間復(fù)雜度（正確答案）B.正確性和簡單性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜度和程序復(fù)雜度.計算機(jī)算法指的是（）o單選題*A

13、.計算方法B.排序方法C.解決問題的方法和過程（正確答案）D.調(diào)度方法.多階段決策問題就是要在可以選擇的那些策略中間選取一個（）策略使在預(yù)定 的標(biāo)準(zhǔn)下達(dá)到最好的效果。單選題*A.最優(yōu)（正確答案）B.最差C.平衡D.任意.根據(jù)排序元素所在位置的不同，排序分（）o單選題*A.內(nèi)排序和外排序（正確答案）B.首排序和尾排序C.順序排序和逆序排序D.堆排序和棧排序58.算法必須具備輸入、輸出和（）等 5個特性。單選題*A.可執(zhí)行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性（正確答案）C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性單選題*單選題*A.經(jīng)分解得到子問題往往不是互相獨立的（正確答案）

14、B.經(jīng)分解得到子問題往往是互相獨立的C.經(jīng)分解得到子問題往往是互相交叉的D.經(jīng)分解得到子問題往往是任意的.二分搜索算法的基本思想是將 n個元素分成個數(shù)大致相同的兩半，取 an/2與x 進(jìn)行比較：如果（），則只要在數(shù)組a的左半部繼續(xù)搜索x。單選題*xan/2x=an/2.活動安排問題就是在所給的活動集合中，選出（）的相容活子集。 單選題*A.最小B.任意C.最大（正確答案）D.一個.在對問題的解空間樹進(jìn)行搜索的方法中一個活結(jié)點最多有一次機(jī)會成為活結(jié)點的是（）。單選題*A.回溯法B.分支限界法（正確答案）C.回溯法和分支限界法D.回溯法求解子集樹問題63.適用動態(tài)規(guī)劃的問題必須滿足（）63.適用動

15、態(tài)規(guī)劃的問題必須滿足（）單選題*A.最優(yōu)化原理B.無前效性C.最優(yōu)化原理和后效性D.最優(yōu)化原理和無后效性（正確答案）64.算法的每種運(yùn)算必須要有確切的定義不能有二義性，以下符合算法確定性運(yùn)算 的是（）。單選題*A.5/0B.將6或7與x相加（正確答案）C.未賦值變量參與運(yùn)算D.f（n）=f（n-1）+2 , F（1）=10, n 為自然數(shù)65.直接或間接的調(diào)用自身的算法稱為（）。單選題*A.貪心算法B.遞歸算法（正確答案）C.迭代算法D.動態(tài)規(guī)劃算法66.二分查找只適用（）存儲結(jié)構(gòu)。單選題*A.堆B.順序（正確答案）C.任意次序D.棧.應(yīng)用分治法的兩個前提是（）。單選題*A.問題的可分性和解的

16、可歸并性（正確答案）B.問題的可分性和解的存在性C.問題的復(fù)雜性和解的可歸并性D.問題的可分性和解的復(fù)雜性.優(yōu)先隊列的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴(kuò)展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的高低與p值大小相關(guān)，根據(jù)問題的不同情況，采用（）來描述優(yōu)先隊列。單選題*A.先進(jìn)先出隊列B.后進(jìn)先出的棧C.最大堆或最小堆（正確答案）D.隨機(jī)序列.階乘函數(shù)用遞歸定義 Public static int factorial (int n) if (n=0) return 1； return (

17、) : 單選題*n*factorial(n)n*factorial(n-1)(正確答案)n*factorial(n-2)n*factorial(n+1)70.（）能夠求得問題的解但卻無法有效地判定解的正確性。單選題*A.數(shù)值概率算法B.蒙特卡羅算法（正確答案）C.拉斯維加斯算法D.舍伍得算法.對于n個元素的排序問題。n = 2時只要作（）次比較即可排好序。單選題*A.3B.2C.1（正確答案）D.4.一般地講，當(dāng)一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法和備 忘錄算法相比：（）。單選題*A.效果一樣B.動態(tài)規(guī)劃效果好（正確答案）C.備忘錄方法效果好D.無法判斷哪個效果好73.分支限界

18、法與回溯法都是在問題的解空間樹T上搜索問題的解，二者（）o單選題*A.求解目標(biāo)不同搜索方式相同B.求解目標(biāo)不同搜索方式也不同（正確答案）C.求解目標(biāo)相同搜索方式不同D.求解目標(biāo)相同搜索方式也相同.遞歸算法不適用以下場合（）o單選題*A.數(shù)據(jù)的定義形式按遞歸定義B.數(shù)據(jù)之間的關(guān)系即數(shù)據(jù)結(jié)構(gòu)按遞歸定義C.問題解法按遞歸算法實現(xiàn)D.概率問題（正確答案）.若當(dāng)子問題之間包含公共的子子問題時，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時一般用（）法較好單選題復(fù)地解公共的子問題，此時一般用（）法較好單選題*A.動態(tài)規(guī)劃（正確答案）B.分治C.貪心D.概率.分治法所能解決的問題應(yīng)具有的最關(guān)鍵特征

19、是（）o單選題*A.該問題的規(guī)?？s小到一定的程度就可以容易地解決B.該問題可以分解為若干個規(guī)模較小的相同問題C利用該問題分解出的子問題的解可以合并為該問題的解（正確答案）D.該問題所分解出的各個子問題是相互獨立的.對于貨箱裝船問題根據(jù)貪心策略首先選擇（）的貨箱然后選（）的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。單選題*A.最輕次輕（正確答案）B.最重次重C.最輕次重D.最重次輕.用回溯法解n后問題時，用完全n叉樹表示解空間。可行性約束 place剪去不滿 足行、列和斜線約束的子樹，place中的if判斷條件應(yīng)為（）。單選題*（Math.abs（k-j）=Math.ab

20、s（xj-xk）|xj=xk）（正確答案）（Math.abs（k-j）=Math.abs（xj-xk）（xj-xk）D.以上都不正確.分支限界法的搜索策略是：在擴(kuò)展結(jié)點處，先生成其（）兒子結(jié)點（分支）， 然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展對點。為了有效地選擇下一擴(kuò)展結(jié)點， 以加速搜索的進(jìn)程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝 著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解。單選題*A.一個B.二個C.任意多個D.所有的(正確答案).能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征()，這個性質(zhì)并不

21、是動態(tài)規(guī)劃 適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不具 備優(yōu)勢。單選題*A.子問題的可求解性B.子問題的獨立性C.子問題的可合并性D.子問題的重疊性(正確答案).在任何一個2好的棋盤覆蓋中，用到的L型骨牌個數(shù)恰為()。單選題*A.(4Ak-1)/3(正確答案)B.(4Ak-1)/2C.(2Ak-1)/3D.(2Ak-1)/2.以Bionic旅行路線問題為例，動態(tài)規(guī)劃的時間復(fù)雜度為()。單選題*O(n)O(n!)O(n2)(正確答案)O(n3)83.一個算法應(yīng)該包含如下幾條性質(zhì)除了()83.一個算法應(yīng)該包含如下幾條性質(zhì)除了()單選題*A.二義性（正確答案）B.有限性

22、C.正確性D.可終止性.解決一個問題通常有多種方法。若說一個算法有效”是指（）。單選題*A.這個算法能在一定的時間和空間資源限制內(nèi)將問題解決B.這個算法能在人的反應(yīng)時間內(nèi)將問題解決C.這個算法比其他已知算法都更快地將問題解決D.A和C（正確答案）.當(dāng)輸入規(guī)模為n時算法增長率最小的是（）o單選題*A.5nB.2010g2n（正確答案）C.2nD.3n1og3n.漸進(jìn)算法分析是指（）o單選題*A.算法在最佳情況、最差情況和平均情況下的代價B.當(dāng)規(guī)模逐步往極限方向增大時對算法資源開銷增長率”上的簡化分析（正確答案）C.數(shù)據(jù)結(jié)構(gòu)所占用的空間D.在最小輸入規(guī)模下算法的資源代價.當(dāng)上下限表達(dá)式相等時我們使

23、用下列哪種表示法來描述算法代價（）o單選題*A.大O表示法B.大Q表示法C. 表示法（正確答案）D.小o表示法88.采用順序搜索法”從一個長度為N的隨機(jī)分布數(shù)組中搜尋值為 K的元素，以下 對順序搜索法分析正確的是（）。單選題*A.最佳情況、最差情況和平均情況下順序搜索法的漸進(jìn)代價都相同B.最佳情況的漸進(jìn)代價要好于最差情況和平均情況的漸進(jìn)代價（正確答案）C.最佳情況和平均情況的漸進(jìn)代價要好于最差情況的漸進(jìn)代價D.最佳情況的漸進(jìn)代價要好于平均情況的漸進(jìn)代價而平均情況的漸進(jìn)代價要好于最 差情況的漸進(jìn)代價.遞歸通常用（）來實現(xiàn)。單選題*A.有序的線性表B.隊列C.棧（正確答案）D.數(shù)組.分治法的設(shè)計思

24、想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題分 別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（）。單選題*A.問題規(guī)模相同，問題性質(zhì)相同B.問題規(guī)模相同，問題性質(zhì)不同C.問題規(guī)模不同，問題性質(zhì)相同（正確答案）D.問題規(guī)模不同，問題性質(zhì)不同 91.在尋找n個元素中第k小元素問題中如快速排序算法思想運(yùn)用分治算法對元素進(jìn)行劃分如何選擇劃分基準(zhǔn)下面（）單選題*A.隨機(jī)選擇一個元素作為劃分基準(zhǔn)B.取子序列的第一個元素作為劃分基準(zhǔn)C.用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D,以上皆可行。但不同方法算法復(fù)雜度上界可能不同（正確答案）.對于0/1背包問題和背包問題的解法下面（）單

25、選題*0/1背包問題和背包問題都可用貪心算法求解0/1背包問題可用貪心算法求解但背包問題則不能用貪心算法求解0/1背包問題不能用貪心算法求解但可以使用動態(tài)規(guī)劃或搜索算法求解，而背 包問題則可以用貪心算法求解（正確答案）D.因為0/1背包問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)所以不能用貪心算法求解.關(guān)于回溯搜索法的介紹，下面（）是不正確描述。單選題*A.回溯法有通用解題法”之稱它可以系統(tǒng)地搜索一個問題的所有解或任意解B.回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C.回溯算法在生成解空間的任一結(jié)點時先判斷該結(jié)點是否可能包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向祖先結(jié)點回溯D,回溯算法

26、需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑（正確答案）.關(guān)于回溯算法和分支限界法以下（）是不正確描述。單選題*A.回溯法中每個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點（正確答案）B.分支限界法中活結(jié)點一旦成為擴(kuò)展結(jié)點就一次性產(chǎn)生其所有兒子結(jié)點在這些兒子 結(jié)點中那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄其余兒子加入活結(jié)點表 中C.回溯法采用深度優(yōu)先的結(jié)點生成策略D.分支限界法采用廣度優(yōu)先或最小耗費優(yōu)先最大效益優(yōu)先的結(jié)點生成策略.優(yōu)先隊列通常用以下（）數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。單選題*A.棧B.堆（正確答案）C.隊列D.二叉查找樹.分支限界算法中根據(jù)從活結(jié)點表中選擇下一擴(kuò)展結(jié)點的不同方式可有幾種常用

27、分類，以下（）描述最為準(zhǔn)確。單選題*A.采用FIFO隊列的隊列式分支限界法B.采用最小值堆的優(yōu)先隊列式分支限界法C.采用最大值堆的優(yōu)先隊列式分支限界法D.以上都常用針對具體問題可以選擇采用其中某種更為合適的方式（正確答案）.對布線問題以下（）是不正確描述。單選題*A.布線問題的解空間是一個圖B.可以對方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡化 對邊界的判定C.采用廣度優(yōu)先的標(biāo)號法找到從起點到終點的布線方案，這個方案如果存在的話不 一定是最短的（正確答案）D.采用先入先出的隊列作為活結(jié)點表以，終點b為擴(kuò)展結(jié)點或活結(jié)點隊列為空作為算法結(jié)束條件.下述表達(dá)不正確的是（）。單選題*

28、A.nA2+2An的漸進(jìn)表達(dá)式上界函數(shù)是0（2An）B.nA2+2An的漸進(jìn)表達(dá)式下界函數(shù)是歐（2An）C.lognA3的漸進(jìn)表達(dá)式上界函數(shù)是O（logn）D.lognA3的漸進(jìn)表達(dá)式下界函數(shù)是歐（nA3）（正確答案）99.當(dāng)輸入規(guī)模為n時，算法增長率最大的是（）o單選題*5An（正確答案）2010g2An2nA23nlog3An.T(n)表示當(dāng)輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是()。單選題*T(n)=T(n-1)+1 , T(1)=1T(n)=2n2T(n)=T(n/2)+1 , T(1)=1 (正確答案)T(n)=3nlog2n.有9個村莊，其坐標(biāo)位置如下表所示：i 1 2 3

29、 4 5 6 7 8 9 x(i) 1 2 3 4 5 6 7 8 9y(i) 1 2 3 4 5 6 7 8 9現(xiàn)在要蓋一所郵局為這9個村莊服務(wù)，請問郵局應(yīng)該蓋在()才能使郵局到 9個村 莊的距離和最短。單選題*(4.5, 0)(4.5, 4.5)(5, 5)(正確答案)(5, 0).n個人拎著水桶在一個水龍頭前面排隊打水水桶有大有小水桶必須打滿水水流 恒定。如下()說法不正確單選題*A,讓水桶大的人先打水可以使得每個人排隊時間之和最小(正確答案)B.讓水桶小的人先打水可以使得每個人排隊時間之和最小C.讓水桶小的人先打水在某個確定的時間t內(nèi)可以讓盡可能多的人打上水D.若要在盡可能短的時間內(nèi)n

30、個人都打完水按照什么順序其實都一樣.對于含有n個元素的子集樹問題，最壞情況下其解空間的葉結(jié)點數(shù)目為() 單選題*2n-12n(正確答案)2n+1-1D.2n+1.以下關(guān)于判定問題難易處理的敘述中正確的是()。單選題*A.可以由多項式時間算法求解的問題是難處理的B.需要超過多項式時間算法求解的問題是易處理的C.可以由多項式時間算法求解的問題是易處理的(正確答案)D.需要超過多項式時間算法求解的問題是不能處理的.回溯法在解空間樹T上的搜索方式是()。單選題*A.深度優(yōu)先(正確答案)B.廣度優(yōu)先C.最小耗費優(yōu)先D.活結(jié)點優(yōu)先.設(shè)f(N), g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自然數(shù)

31、N0,使得當(dāng)N N0時有f(N) g(N),則稱函數(shù)f(N)當(dāng)N充分大時有上界g(N),記作f(N)=O(g(N),即f(N)的階()g(N)的階。單選題*A.不高于(正確答案)B.不低于C.等價于D.逼近.以下（）不能在線性時間完成排序單選題*A.計數(shù)排序B.基數(shù)排序C.堆排序（正確答案）D.桶排序.以下（）不一定得到問題的最優(yōu)解。單選題*A.貪心算法（正確答案）B.回溯算法C.分支限界法D.動態(tài)規(guī)劃法.下列不屬于一個好的算法應(yīng)具有的特性的是（）。單選題*A.正確性B.簡明性C.無限性（正確答案）D.最優(yōu)性.算法分析是（）。單選題*A.將算法用某種程序設(shè)計語言恰當(dāng)?shù)乇硎境鰜鞡.在抽象數(shù)據(jù)集合

32、上執(zhí)行程序，以確定是否會產(chǎn)生錯誤的結(jié)果C.對算法需要多少計算時間和存儲空間作定量分析（正確答案）D.證明算法對所有可能的合法輸入都能算出正確的111.學(xué)校要舉行運(yùn)動會，請你設(shè)計一個能夠?qū)\(yùn)動員分?jǐn)?shù)自動排序的軟件，如果要 設(shè)計此軟件，以下最好的方法和步驟是（）。單選題*A.分析問題，編寫程序，設(shè)計算法，調(diào)試程序B.設(shè)計算法，編寫程序，提出問題，調(diào)試程序C.提出問題，設(shè)計算法，編寫程序，調(diào)試程序(正確答案)D.設(shè)計算法，提出問題，編寫程序，調(diào)試程序112.考慮背包問題：n=6, M=10, V (1:6) = (15, 59, 21, 30, 60, 5) , W (1:6) = (1, 5, 2

33、, 3, 6, 1)。該問題的最大效益值為()。單選題*101110115(正確答案)120.找最小生成樹的算法Kruskal的時間復(fù)雜度為()。單選題*O(n2)O(mlogn)O(nlogm)O(mlogm)(正確答案).算法與程序的區(qū)別在于算法具有()o單選題*A.能行性B.確定性C.有窮性(正確答案)D.輸入和輸出.設(shè)A1.60=11,12,7陰法折半查找在 A上搜索x=33、7、70、77時執(zhí)行的元素比較次數(shù)分別為a的元素比較次數(shù)分別為a、b、c、d,則()單選題*A.abcb=c=dC. ab=c=d(正確答案)D.ac0)(hanoi( n-1, a, c, b);move(a,

34、 b);hanoi( n-1, c, b, a);上述算法的時間復(fù)雜度為()。單選題*O(2An)(正確答案)O(nlogn)火叫/吟119.當(dāng)一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時，可以使用()來消除或減少問題的好壞實例間的這種差別。單選題*A.數(shù)值概率算法B.舍伍德算法(正確答案)C.拉斯維加斯算法D.蒙特卡羅算法120.當(dāng)輸入規(guī)模為n時，算法增長率最快的是（）o單選題*A. 12nB.10010g2AnC. 2nA2（正確答案）D.3n1og3An121.關(guān)于0/1背包問題，以下描述正確的是（）。單選題*A.可以使用貪心算法找到最優(yōu)解B.能找到多項

35、式時間的有效算法C.使用教材介紹的動態(tài)規(guī)劃方法可求解任意0/1背包問題D.對于同一背包與相同的物品，做背包問題取得的總價值一定大于等 于做0/1背包問題。（正確答案）122.設(shè)有n項獨立的作業(yè)1,2,m,由m臺相同的機(jī)器加工處理。作業(yè)i所需要的 處理時間為tio約定：任何一項作業(yè)可在任何一臺機(jī)器上處理，但未完工前不準(zhǔn)中 斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種調(diào)度方案， 使所給的n個作業(yè)在盡可能短的時間內(nèi)由 m臺機(jī)器處理完（nm）。對于多級調(diào) 度問題，使用哪種貪心策略比較合適（）。單選題*A.作業(yè)從小到大依次分配給空閑的機(jī)器B.作業(yè)從大到小依次分配給空閑的機(jī)器（正確答案）

36、C.每個機(jī)器分配一樣的作業(yè)數(shù)D.使用以上幾種貪心策略都能找到最優(yōu)解，所以都合適.使用二分搜索算法在1000個有序元素表中搜索一個特定元素，在最壞情況下，搜索總共需要比較的次數(shù)為（）。單選題*A.10（正確答案）B.11C.500D.1000.用數(shù)量級形式表示算法的執(zhí)行時間稱為算法的（）o單選題*A.時間復(fù)雜度（正確答案）B.空間復(fù)雜度C.處理器復(fù)雜度D.通信復(fù)雜度.下面哪個問題不是典型的NP完全問題（）。單選題*A. m-著色問題B.旅行商問題C.哈密爾頓回路問題D.排序問題（正確答案）.順序查找的時間復(fù)雜度為（）。單選題*O（n）（正確答案）O（logn）O（n2）O（nlogn）127.折

37、半查找的時間復(fù)雜度為（）127.折半查找的時間復(fù)雜度為（）單選題*O（n）O（logn）（正確答案）O（n2）O（nlogn）.算法的復(fù)雜性有時間復(fù)雜性和（）復(fù)雜性之分。單選題*A.處理器復(fù)雜性B.通信復(fù)雜性C.空間復(fù)雜性（正確答案）D.存儲復(fù)雜性.算法的復(fù)雜性有空間復(fù)雜性和（）復(fù)雜性之分。單選題*A.處理器復(fù)雜性B.通信復(fù)雜性C.時間復(fù)雜性（正確答案）D.存儲復(fù)雜性.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性 四條性質(zhì)。其中算法的 確定性”是指組成算法的每條（）是清晰的，無歧義的。 單選題*A.程序B.指令（正確答案）C.語句D.語句塊單選題*131.單選題*A.快

38、速排序B.希爾排序C.合并排序（正確答案）D.堆排序.解決0/1背包問題可以使用動態(tài)規(guī)劃，回溯法，分支限界法。其中不需要排序 的是（）。單選題*A.動態(tài)規(guī)劃（正確答案）B.回溯法C.分支限界法D.以上3種方法都需要排序.解決0/1背包問題時需要排序的方法是回溯法和（）。單選題*A.動態(tài)規(guī)劃B.分支限界法（正確答案）C.貪心法D.線性規(guī)劃.下面哪項是動態(tài)規(guī)劃算法基本要素之一（）。單選題*A.定義最優(yōu)解B.構(gòu)造最優(yōu)解C.算出最優(yōu)解D.最優(yōu)子結(jié)構(gòu)（正確答案）.快速排序算法是基于（）的一種排序算法。單選題*A.分治策略（正確答案）B.貪心C.回溯D.動態(tài)規(guī)劃.（）是貪心算法可行的第一個基本要素，也是貪

39、心算法與動態(tài)規(guī)劃算法的主要 區(qū)別。單選題*A.重疊子問題B.最優(yōu)子結(jié)構(gòu)C.貪心選擇性質(zhì)（正確答案）D.定義最優(yōu)解.如果無向連通圖G中不包含任何關(guān)節(jié)點，則稱該圖 G為（）。單選題*A.雙連通圖（正確答案）B.單連通圖C.強(qiáng)連通圖D.弱連通圖.使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點的求解方法稱為（）。單選題*A.動態(tài)規(guī)劃B.分支限界法C.貪心法D.回溯法（正確答案）（）算法框.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架和（）算法框架。單選題*A.排列樹（正確答案）B.二叉樹C.B樹D.B+樹.下列算法中通常以自頂向下的方式求解最優(yōu)解的是（）o單選題*A.分治法B.動態(tài)規(guī)劃法C.貪心

40、法（正確答案）D.回溯法.哈夫曼編碼可利用（）算法實現(xiàn)。單選題*A.分治策略B.動態(tài)規(guī)劃法C.貪心法（正確答案）D.回溯法.在對問題的解空間樹進(jìn)行搜索的方法中一個活結(jié)點有多次機(jī)會成為活結(jié)點的是 （）。單選題*A.回溯法（正確答案）B.分支限界法C.回溯法和分支限界法D.動態(tài)規(guī)劃.秦始皇吞并六國使用的遠(yuǎn)交近攻逐個擊破的連橫策略采用了以下哪種算法思想 （）。單選題*A.遞歸B.分治（正確答案）C.迭代D.模擬。.FIFO是（）的一搜索方式。單選題*A.分支限界法（正確答案）B.動態(tài)規(guī)劃法C.貪心法D.回溯法.投點法是（）的一種。單選題*A.分支界限算法B.概率算法（正確答案）C.貪心算法D.回溯算

41、法146.若線性規(guī)劃問題存在最優(yōu)解它一定不在（）。單選題*A.可行域的某個頂點上B.可行域的某條邊上C.可行域內(nèi)部（正確答案）D.以上都不對 147.在一般輸入數(shù)據(jù)的程序里輸入多多少少會影響到算法的計算復(fù)雜度，為了消除這種影響可用（）對輸入進(jìn)行預(yù)處理。單選題*A.蒙特卡羅算法B.拉斯維加斯算法（正確答案）C.舍伍德算法D.數(shù)值概率算法148.若L是一個NP完全問題，L經(jīng)過多項式時間變換后得到問題l則l是（） 單選題*A . P類問題（正確答案）NP難問題NP完全問題P類語言.不斷回頭尋找目標(biāo)的方法稱為（）。單選題*A.動態(tài)規(guī)劃B.貪心法C.回溯法（正確答案）D.概率算法.拉斯維加斯算法找到的解

42、一定是（）o單選題*A.不確定的B.正確的（正確答案）C.不正確的D.局部最優(yōu)的151.&記號在算法復(fù)雜性的表示法中表示（）。單選題*A.上界B.下界C.緊致界（正確答案）D.以上說法都不對152.一個無向連通圖不是雙向連通圖的充要條件是圖中存在（）。單選題*A.回路B.關(guān)節(jié)點（正確答案）C.最大團(tuán)D.最小團(tuán)153.一個算法是對特定問題求解的一種描述，它是（）。單選題*A.指令的有限序列（正確答案）B.程序的有限序列C.語句的有限序列D.代碼的有限序列.矩陣乘法如下：for （i=0; in; i+）for （j=0; jn; j+） Cij=0;for （k=0; kn; k+）Cij+=a

43、ik*bkj;它的漸近時間復(fù)雜度為（）。單選題*O（nA2）O（nA3）（正確答案）O（n）O（nA4）單選題*.二分搜索過程的算法行為可以用一棵（）來描述單選題*A.二叉排序樹B.二叉判定樹（正確答案）C.子集樹D.排列樹.用貪心法求解背包問題時，為了使收益最大化要選擇（）的物品裝入背包。單選題*A.單位重量收益最大（正確答案）B.收益最大C.重量最大D.重量最小.一個遞歸算法必須包括（）。單選題*A.遞歸部分B.終止條件和遞歸部分（正確答案）C.迭代部分D.終止條件和迭代部分158.有六個元素6, 5, 4, 3, 2, 1的順序進(jìn)棧，則下列哪一個不是合法的出棧序列（）。單選題*A.5,

44、4, 3, 6, 1,2B.4, 5, 3, 1,2, 6C.3, 4, 6, 5, 2, 1（正確答案）D.2, 3, 4, 1,5, 6159.棧和隊列的共同點是（）159.棧和隊列的共同點是（）單選題*A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素（正確答案）D.沒有共同點160.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，那么度為0的結(jié)點 個數(shù)是（）。單選題*A.9B.11（正確答案）C.15D.不確定.排序趟數(shù)與原始序列有關(guān)的排序方法是（）排序法。單選題*A.插入B.選擇C.冒泡（正確答案）D.快速.如果給定權(quán)值總數(shù)有n個，則其哈夫曼樹的結(jié)點總數(shù)為（）。單

45、選題*A.不確定B.2nC.2n+1D.2n-1（正確答案）.一個棧的輸入序列為123 - n,若輸出序列的第一個元素是n,那么輸出第i 三息）個元素是（）。單選題*A.不確定n-i+1（正確答案）in-i.下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。單選題* TOC o 1-5 h z 68,11,18,6923,93,7368 ,11,69,2318 ,93,7393,73 68,11, 69,23,18（正確答案）68 ,11,69,23, 1893,73.下列哪個問題不能用貪心法求解（）。單選題*A.哈夫曼編碼問題B.單源最短路徑問題C.0/1背包問題（正確答案）D.最小生成樹問

46、題.下列隨機(jī)算法一定有解但解不一定正確的是（）。單選題*SherwoodLasVegasMonteCarlo（正確答案）D.三者都不是167.在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實際價值的是（）情況 下的時間復(fù)雜度。單選題*A.最好B.最壞（正確答案）C.平均D.以上都不正確168.快速排序算法的性能取決于（）。單選題*A.劃分的對稱性（正確答案）B.數(shù)據(jù)的原始序列C.隨機(jī)選擇策略D.以上都不正確169.回溯法在問題的解空間樹中，按（）策略，從根節(jié)點出發(fā)搜索解空間樹。單選題*A.廣度優(yōu)先B.深度優(yōu)先（正確答案）C.隨機(jī)D.以上說法都不對170.大口符號用來描述增長率的下限，這個下限

47、的階越（），結(jié)果就越有價值。單選題*A.高（正確答案）B.低C.和具體問題有關(guān)D.以上都不正確171.設(shè)計動態(tài)規(guī)劃算法的步驟為：（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2） （） o （3）以自底向上的方式計算出最優(yōu)值。（4）計算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解。單選題*A.非遞歸的定義最優(yōu)值B.遞歸的定義最優(yōu)值（正確答案）C.迭代的定義最優(yōu)值D.遞推的定義最優(yōu)值.設(shè)計動態(tài)規(guī)劃算法的步驟為：（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2）遞歸的定義最優(yōu)值。（3） （） o （ 4）計算最優(yōu)值得到的信息，構(gòu)造最優(yōu) 解。單選題*A.以自底向上的方式計算出最優(yōu)值（正確答案）B.以自頂向下的方式計算出

48、最優(yōu)值C.迭代的方式計算出最優(yōu)值D.遞推的方式算出最優(yōu)值.最優(yōu)二叉搜索樹即是（）的二叉搜索樹。單選題*A.最小平均查找時間（正確答案）B.最小最壞查找時間C.最小平均存儲空間D.最小最壞存儲空間.當(dāng)（a1, a2, a3, a4, a5,a6）=（-2, 11, -4, 13, -5, -2）,最大子段和為（）。單選題 *A.24B.22C.20（正確答案）D.15175. 9n2+10n的漸近表達(dá)式是（）175. 9n2+10n的漸近表達(dá)式是（）單選題*O(n2)(正確答案)O(n3)O(n)O(n4).下面程序段的時間復(fù)雜度是()。for (i=0; ifor (j=0; j 單選題*O(

49、n)O(n3)O(n2)(正確答案)O(n4).快速排序算法是基于分治策略的一個算法，其基本思想是，對于輸入的子數(shù)組 ap:r,按以下三個步驟進(jìn)行排序：()。單選題*A.分解、遞歸求解、合并(正確答案)B.遞歸求解、分解、合并C.合并、遞歸求解、分解D.分解、合并、遞歸求解178.最優(yōu)裝載問題可用貪心算法求解，采用()先裝的貪心選擇策略，可產(chǎn)生最優(yōu) 裝載問題的最優(yōu)解。單選題*A.重量最重者B.單位重量收益大C.重量最輕者(正確答案)D.收益最大單選題*179.寫出下列f(n)的漸進(jìn)性態(tài)，若f(n)= C0, C0為常數(shù)，則f(n)=單選題*A.O(1)(正確答案)B.O(n)C.O(n2)D.

50、O(n3).寫出下列f(n)的漸進(jìn)性態(tài),若f(n)=3n+2,則f(n)=()。單選題*O(1)O(n)(正確答案)O(n2)O(n3).寫出下列f(n)的漸進(jìn)性態(tài)，若f(n)=6*2n+n,則f(n)=()。單選題*O(1)O(2n)(正確答案)O(n2)O(n3).若一個算法的時間復(fù)雜度用T(n)表示，其中n的含義是()。單選題*A.問題規(guī)模(正確答案)B.語句條數(shù)C.循環(huán)層數(shù)D.函數(shù)數(shù)量.背包問題可獲得最優(yōu)解的輸入是按()。單選題*A.重量密度排序B.價值密度排序（正確答案）C.單位重量收益大小排序D.重量大小排序.合并排序法的基本思想是：將待排序元素分成大小大致相同的（）個子集合， 分別對每個子集合進(jìn)行排序，最