《算法分析與設計》(李春葆版)課后選擇題答案與解析

《算法及其分析》課后選擇題答案及詳解第1

章——概論1.下列于算法的說法中確的有（

Ⅰ.求解某一類題的算法是唯一

Ⅱ.算法必須在限步操作之后停

Ⅲ.算法的每一操作必須是明確，不能有歧義或義模糊

Ⅳ.算法執(zhí)行后定產(chǎn)生確定的結(jié)

A.1個B.2個C.3個D.4個2.T(n)表示當輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是（）。T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)=

T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有窮性、確定性和輸出性，因而Ⅱ、Ⅲ、Ⅳ正確，而解決某一類問題的算法不一定是唯一的。答案為C。2.答：選項A的時間復雜度為O(n)。選項B的時間復雜度為O(n)。選項C的時間復雜度為O(log2n)。選項D的時間復雜度為O(nlog2n)。答案為C。第3

章─分治法1.分治法的設計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（）。

A.問題規(guī)模相同，問題性質(zhì)相同B.問題規(guī)模相同，問題性質(zhì)不同C.問題規(guī)模不同，問題性質(zhì)相同D.問題規(guī)模不同，問題性質(zhì)不同

2.在尋找n個元素中第k小元素問題中，如快速排序算法思想，運用分治算法對n個元素進行劃分，如何選擇劃分基準？下面（）答案解釋最合理。A.隨機選擇一個元素作為劃分基準B.取子序列的第一個元素作為劃分基準C.用中位數(shù)的中位數(shù)方法尋找劃分基準D.以上皆可行。但不同方法，算法復雜度上界可能不同

3.對于下列二分查找算法，以下正確的是（）。

A.

int

x)

{intlow=0,high=n-1;

while(low<=high)

{intmid=(low+high)/2;

if(x==a[mid])returnmid;

if(x>a[mid])low=mid;

elsehigh=mid;}return

–1;}B.

int

x)

{ intlow=0,high=n-1;

while(low+1!=high)

{intmid=(low+high)/2;

if(x>=a[mid])low=mid;

elsehigh=mid;

}

if(x==a[low])returnlow;

elsereturn

–1;

}

C.

intintx)

{ intlow=0,high=n-1;

while(low<high-1)

{intmid=(low+high)/2;if(x<a[mid])

high=mid;

elselow=mid;

}

if(x==a[low])returnlow;

elsereturn

–1;

}

D.int

x)

{if(n>0&&x>=a[0])

{intlow=

high=n-1;

while(low<high){intmid=(low+high+1)/2;

if(x<a[mid])

high=mid-1;

elselow=mid;

}

if(x==a[low])returnlow;

}

return

–1;

}答案解析：1.答：C。2.答：D。3.答：以a[]={1，2，3，4，5}為例說明。選項A中在查找5時出現(xiàn)死循環(huán)。選項B中在查找5時返回-1。選項C中在查找5時返回-1。選項D正確。第5

章─回溯法1.回溯法在問題的解空間樹中，按（）策略，從根結(jié)點出發(fā)搜索解空間樹。

A.廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D.深度優(yōu)先2.關(guān)于回溯法以下敘述中不正確的是（）。A.回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜索一個問題的所有解或任意解B.回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C.回溯算法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當前擴展結(jié)點的路徑

D.回溯算法在生成解空間的任一結(jié)點時，先判斷該結(jié)點是否可能包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向祖先結(jié)點回溯3.回溯法的效率不依賴于下列哪些因素（）。A.確定解空間的時間C.計算約束函數(shù)的時間B.滿足顯約束的值的個數(shù)D.計算限界函數(shù)的時間4.下面（）函數(shù)是回溯法中為避免無效搜索采取的策略。A.遞歸函數(shù)B.剪枝函數(shù)C.隨機數(shù)函數(shù)D.搜索函數(shù)答案解析：1.答：D。2.答：回溯算法是采用深度優(yōu)先遍歷的，需要借助系統(tǒng)棧結(jié)構(gòu)來保存從根結(jié)點到當前擴展結(jié)點的路徑。答案為C。3.答：回溯法解空間是虛擬的，不必確定整個解空間。答案為A。4.答：B。第6

章─分枝限界法1.分枝限界法在問題的解空間樹中，按（）策略，從根結(jié)點出發(fā)搜索解空間樹。A.廣度優(yōu)先B.活結(jié)點優(yōu)先C.擴展結(jié)點優(yōu)先D.深度優(yōu)先2.常見的兩種分枝限界法為（）。A.廣度優(yōu)先分枝限界法與深度優(yōu)先分枝限界法

B.隊列式（FIFO）分枝限界法與堆棧式分枝限界法C.排列樹法與子集樹法D.隊列式（FIFO）分枝限界法與優(yōu)先隊列式分枝限界法

3.分枝限界法求解0/1背包問題時，活結(jié)點表的組織形式是（）。A.小根堆B.大根堆C.棧4.采用最大效益優(yōu)先搜索方式的算法是（）。A.分支界限法B.動態(tài)規(guī)劃法C.貪心法D.回溯法

5.優(yōu)先隊列式分枝限界法選取擴展結(jié)點的原則是（）。A.先進先出B.后進先出C.結(jié)點的優(yōu)先級D.隨機答案解析：1.答：A。2.答：D。3.答：B。4.答：A。5.答：C。第7

章─貪心法1.下面是貪心算法的基本要素的是（）。

A.重疊子問題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)D.定義最優(yōu)解2.下面問題（）不能使用貪心法解決。

A.單源最短路徑問題B.n皇后問題C.最小花費生成樹問題D.背包問題3.采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復雜度為（）。A.O(n)B.O(n)C.O(n)D.O(nlog2n)

4.關(guān)于0/1背包問題以下描述正確的是（）。A.可以使用貪心算法找到最優(yōu)解B.能找到多項式時間的有效算法C.使用教材介紹的動態(tài)規(guī)劃方法可求解任意0－1

背包問題D.對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做0/1背包問題5.一棵哈夫曼樹共有215個結(jié)點，對其進行哈夫曼編碼，共能得到（）個不同的碼A.107B.108C.214D.215答案解析：1.答：C。2.答：n皇后問題的解不滿足貪心選擇性質(zhì)。答案為B。3.答：D。4.答：由于背包問題可以取物品的一部分，所以總價值一定大于等于做0/1背包問題。答案為D。5.答：這里n=215，哈夫曼樹中n1=0，而n0=n2+1，n=n0+n1+n2=2n0-1，n0=(n+1)/2=108。答案為B。第8

章─動態(tài)規(guī)劃1.下列算法中通常以自底向上的方式求解最優(yōu)解的是（）。

備忘錄法B.動態(tài)規(guī)劃法C.貪心法D.回溯法2.備忘錄方法是（）算法的變形。A.分治法B.回溯法C.貪心法D.動態(tài)規(guī)劃法3.下列是動態(tài)規(guī)劃算法基本要素的是（）。A.定義最優(yōu)解B.構(gòu)造最優(yōu)解C.算出最優(yōu)解D.子問題重疊性質(zhì)4.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（）A.貪心選擇性質(zhì)B.重疊子問題C.最優(yōu)子結(jié)構(gòu)性質(zhì)D.定義最優(yōu)解答案解析：1.答：B。2.答：D。3.答：D。4.答：C。第9

章─圖算法設計1..以下不屬于貪心算法的是（）。A.Prim

算法B.Kruskal

算法C.Dijkstra算法D.深度優(yōu)先遍歷2.一個有n個頂點的連通圖的生成樹是原圖的最小連通子圖，且包含原圖中所有n個頂點，并且有保持圖聯(lián)通的最少的邊。最大生成樹就是權(quán)和最大生成樹，現(xiàn)在給出一個無向帶權(quán)圖的鄰接矩陣為{{0，4，5，0，3}，{4，0，4，2，3}，{5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}}，其中權(quán)為0

表示沒有邊。一個圖為求這個圖的最大生成樹的權(quán)和是（）。A.11B.12C.13D.14E.15答案解析：1.答：D。2.答：采用類似Kurskal

算法來求最大生成樹，第1

步取最大邊（0，2），第2步取邊（0，1），第3步取邊（0，4），第4步取最大邊（1，3），得到的權(quán)和為14。答案為D。第11章─計算復雜性理論1.旅行商問題是NP問題嗎？A.否B.是

C.至今尚無定論

2.下面有關(guān)P問題，NP問題和NPC問題，說法錯誤的是（）。

A.如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題B.NP問題是指可以在多項式的時間里驗證一個解的問題C.所有的P類問題都是NP問題D.NPC問題不一定是個NP問題，只要保證所有的NP問題都可以約化到它即可答案解析：1.答：B。2.答：D。第12章─概率算法和近似算法1.蒙特卡羅算法是（）的一種。A.分枝限界算法B.貪心算法C.概率算法D.回溯算法2.在下列算法中有時找不到問題解的是（）。A.蒙特卡羅算法B.拉斯維加斯算法C.舍伍德算法D.數(shù)值概率算法3.在下列算法中得到的解未必正確的是（）。A.蒙特卡羅算法B.拉斯維加斯算法C.舍伍德算法D.數(shù)值概率算法4.總能求得非數(shù)值問題的一個解，且所求得的解總是正確的是（）。A.蒙特卡羅算法B.拉斯維加斯算法C.數(shù)值概率算法D.舍伍德算法5.目前可以采用（）在多項式級時間內(nèi)求出旅行商問題的一個近似最優(yōu)解。A.回溯法B.蠻力法C.近似算法D.都不可能

6.下列敘述錯誤的是（）。A.概率算法的期望執(zhí)行時間是指反復解同一個輸入實例所花的平均執(zhí)行時間

B.概率算法的平均期望時間是指所有輸入實例上的平均期望執(zhí)行時間C.概率算法的最壞期望事件是指最壞輸入實例上的期望執(zhí)行時間D.概率算法的期望執(zhí)行時間是指所有輸入實例上的所花的平均執(zhí)行時間7.下列敘述錯誤的是（）。

A.數(shù)值概率算法一般是求數(shù)值計算問題的近似解B.MonteCarlo總能求得問題的一個解，但該解未必正確C.LasVegas