算法選擇題初級(jí)版256道

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、態(tài)規(guī)劃的問(wèn)題必須滿足（）單選題*A.最優(yōu)化原理B.無(wú)前效性C.最優(yōu)化原理和后效性D.最優(yōu)化原理和無(wú)后效性（正確答案）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)用自身的算法稱(chēng)為（）。單選題*A.貪心算法B.遞歸算法（正確答案）C.迭代算法D.動(dòng)態(tài)規(guī)劃算法66.二分查找只適用（）存儲(chǔ)結(jié)構(gòu)。單選題*A.堆B.順序（正確答案）C.任意次序D.棧.應(yīng)用分治法的兩個(gè)前提是（）。單選題*A.問(wèn)題的可分性和解的

16、可歸并性（正確答案）B.問(wèn)題的可分性和解的存在性C.問(wèn)題的復(fù)雜性和解的可歸并性D.問(wèn)題的可分性和解的復(fù)雜性.優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值p來(lái)表示。結(jié)點(diǎn)優(yōu)先級(jí)的高低與p值大小相關(guān)，根據(jù)問(wèn)題的不同情況，采用（）來(lái)描述優(yōu)先隊(duì)列。單選題*A.先進(jìn)先出隊(duì)列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.（）能夠求得問(wèn)題的解但卻無(wú)法有效地判定解的正確性。單選題*A.數(shù)值概率算法B.蒙特卡羅算法（正確答案）C.拉斯維加斯算法D.舍伍得算法.對(duì)于n個(gè)元素的排序問(wèn)題。n = 2時(shí)只要作（）次比較即可排好序。單選題*A.3B.2C.1（正確答案）D.4.一般地講，當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法和備 忘錄算法相比：（）。單選題*A.效果一樣B.動(dòng)態(tài)規(guī)劃效果好（正確答案）C.備忘錄方法效果好D.無(wú)法判斷哪個(gè)效果好73.分支限界

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

19、是（）o單選題*A.該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決B.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題C利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解（正確答案）D.該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的.對(duì)于貨箱裝船問(wèn)題根據(jù)貪心策略首先選擇（）的貨箱然后選（）的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。單選題*A.最輕次輕（正確答案）B.最重次重C.最輕次重D.最重次輕.用回溯法解n后問(wèn)題時(shí)，用完全n叉樹(shù)表示解空間?？尚行约s束 place剪去不滿 足行、列和斜線約束的子樹(shù)，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é)點(diǎn)處，先生成其（）兒子結(jié)點(diǎn)（分支）， 然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)， 以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝 著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。單選題*A.一個(gè)B.二個(gè)C.任意多個(gè)D.所有的(正確答案).能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題還有一個(gè)顯著特征()，這個(gè)性質(zhì)并不

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

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

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

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

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

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

27、分類(lèi)，以下（）描述最為準(zhǔn)確。單選題*A.采用FIFO隊(duì)列的隊(duì)列式分支限界法B.采用最小值堆的優(yōu)先隊(duì)列式分支限界法C.采用最大值堆的優(yōu)先隊(duì)列式分支限界法D.以上都常用針對(duì)具體問(wèn)題可以選擇采用其中某種更為合適的方式（正確答案）.對(duì)布線問(wèn)題以下（）是不正確描述。單選題*A.布線問(wèn)題的解空間是一個(gè)圖B.可以對(duì)方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡(jiǎn)化 對(duì)邊界的判定C.采用廣度優(yōu)先的標(biāo)號(hào)法找到從起點(diǎn)到終點(diǎn)的布線方案，這個(gè)方案如果存在的話不 一定是最短的（正確答案）D.采用先入先出的隊(duì)列作為活結(jié)點(diǎn)表以，終點(diǎn)b為擴(kuò)展結(jié)點(diǎn)或活結(jié)點(diǎn)隊(duì)列為空作為算法結(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時(shí)，算法增長(zhǎng)率最大的是（）o單選題*5An（正確答案）2010g2An2nA23nlog3An.T(n)表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法效率最優(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個(gè)村莊，其坐標(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個(gè)村莊服務(wù)，請(qǐng)問(wèn)郵局應(yīng)該蓋在()才能使郵局到 9個(gè)村 莊的距離和最短。單選題*(4.5, 0)(4.5, 4.5)(5, 5)(正確答案)(5, 0).n個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水水桶有大有小水桶必須打滿水水流 恒定。如下()說(shuō)法不正確單選題*A,讓水桶大的人先打水可以使得每個(gè)人排隊(duì)時(shí)間之和最小(正確答案)B.讓水桶小的人先打水可以使得每個(gè)人排隊(duì)時(shí)間之和最小C.讓水桶小的人先打水在某個(gè)確定的時(shí)間t內(nèi)可以讓盡可能多的人打上水D.若要在盡可能短的時(shí)間內(nèi)n

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

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

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

33、, 3, 6, 1)。該問(wèn)題的最大效益值為()。單選題*101110115(正確答案)120.找最小生成樹(shù)的算法Kruskal的時(shí)間復(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時(shí)執(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);上述算法的時(shí)間復(fù)雜度為()。單選題*O(2An)(正確答案)O(nlogn)火叫/吟119.當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí)，可以使用()來(lái)消除或減少問(wèn)題的好壞實(shí)例間的這種差別。單選題*A.數(shù)值概率算法B.舍伍德算法(正確答案)C.拉斯維加斯算法D.蒙特卡羅算法120.當(dāng)輸入規(guī)模為n時(shí)，算法增長(zhǎng)率最快的是（）o單選題*A. 12nB.10010g2AnC. 2nA2（正確答案）D.3n1og3An121.關(guān)于0/1背包問(wèn)題，以下描述正確的是（）。單選題*A.可以使用貪心算法找到最優(yōu)解B.能找到多項(xiàng)

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

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

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

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

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

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

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

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

43、ik*bkj;它的漸近時(shí)間復(fù)雜度為（）。單選題*O（nA2）O（nA3）（正確答案）O（n）O（nA4）單選題*.二分搜索過(guò)程的算法行為可以用一棵（）來(lái)描述單選題*A.二叉排序樹(shù)B.二叉判定樹(shù)（正確答案）C.子集樹(shù)D.排列樹(shù).用貪心法求解背包問(wèn)題時(shí)，為了使收益最大化要選擇（）的物品裝入背包。單選題*A.單位重量收益最大（正確答案）B.收益最大C.重量最大D.重量最小.一個(gè)遞歸算法必須包括（）。單選題*A.遞歸部分B.終止條件和遞歸部分（正確答案）C.迭代部分D.終止條件和迭代部分158.有六個(gè)元素6, 5, 4, 3, 2, 1的順序進(jìn)棧，則下列哪一個(gè)不是合法的出棧序列（）。單選題*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.棧和隊(duì)列的共同點(diǎn)是（）159.棧和隊(duì)列的共同點(diǎn)是（）單選題*A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素（正確答案）D.沒(méi)有共同點(diǎn)160.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn) 個(gè)數(shù)是（）。單選題*A.9B.11（正確答案）C.15D.不確定.排序趟數(shù)與原始序列有關(guān)的排序方法是（）排序法。單選題*A.插入B.選擇C.冒泡（正確答案）D.快速.如果給定權(quán)值總數(shù)有n個(gè)，則其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（）。單

45、選題*A.不確定B.2nC.2n+1D.2n-1（正確答案）.一個(gè)棧的輸入序列為123 - n,若輸出序列的第一個(gè)元素是n,那么輸出第i 三息）個(gè)元素是（）。單選題*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.下列哪個(gè)問(wèn)題不能用貪心法求解（）。單選題*A.哈夫曼編碼問(wèn)題B.單源最短路徑問(wèn)題C.0/1背包問(wèn)題（正確答案）D.最小生成樹(shù)問(wèn)

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

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

48、最優(yōu)值C.迭代的方式計(jì)算出最優(yōu)值D.遞推的方式算出最優(yōu)值.最優(yōu)二叉搜索樹(shù)即是（）的二叉搜索樹(shù)。單選題*A.最小平均查找時(shí)間（正確答案）B.最小最壞查找時(shí)間C.最小平均存儲(chǔ)空間D.最小最壞存儲(chǔ)空間.當(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).下面程序段的時(shí)間復(fù)雜度是()。for (i=0; ifor (j=0; j 單選題*O(

49、n)O(n3)O(n2)(正確答案)O(n4).快速排序算法是基于分治策略的一個(gè)算法，其基本思想是，對(duì)于輸入的子數(shù)組 ap:r,按以下三個(gè)步驟進(jìn)行排序：()。單選題*A.分解、遞歸求解、合并(正確答案)B.遞歸求解、分解、合并C.合并、遞歸求解、分解D.分解、合并、遞歸求解178.最優(yōu)裝載問(wèn)題可用貪心算法求解，采用()先裝的貪心選擇策略，可產(chǎn)生最優(yōu) 裝載問(wèn)題的最優(yōu)解。單選題*A.重量最重者B.單位重量收益大C.重量最輕者(正確答案)D.收益最大單選題*179.寫(xiě)出下列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).寫(xiě)出下列f(n)的漸進(jìn)性態(tài),若f(n)=3n+2,則f(n)=()。單選題*O(1)O(n)(正確答案)O(n2)O(n3).寫(xiě)出下列f(n)的漸進(jìn)性態(tài)，若f(n)=6*2n+n,則f(n)=()。單選題*O(1)O(2n)(正確答案)O(n2)O(n3).若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是()。單選題*A.問(wèn)題規(guī)模(正確答案)B.語(yǔ)句條數(shù)C.循環(huán)層數(shù)D.函數(shù)數(shù)量.背包問(wèn)題可獲得最優(yōu)解的輸入是按()。單選題*A.重量密度排序B.價(jià)值密度排序（正確答案）C.單位重量收益大小排序D.重量大小排序.合并排序法的基本思想是：將待排序元素分成大小大致相同的（）個(gè)子集合， 分別對(duì)每個(gè)子集合進(jìn)行排序，最