《計算機(jī)算法設(shè)計與分析》習(xí)題及答案

1、1《計算機(jī)算法設(shè)計與分析計算機(jī)算法設(shè)計與分析》習(xí)題及答案習(xí)題及答案一選擇題一選擇題1、二分搜索算法是利用（A）實現(xiàn)的算法。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是（A）。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解3、最大效益優(yōu)先是（A）的一搜索方式。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法4.回溯法解旅行售貨員問題時的解空間樹是（A）。A、子集樹B、排列樹C、深度優(yōu)先

2、生成樹D、廣度優(yōu)先生成樹5下列算法中通常以自底向上的方式求解最優(yōu)解的是（B）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法6、衡量一個算法好壞的標(biāo)準(zhǔn)是（C）。A運(yùn)行速度快B占用空間少C時間復(fù)雜度低D代碼短7、以下不可以使用分治法求解的是（D）。A棋盤覆蓋問題B選擇問題C歸并排序D01背包問題8.實現(xiàn)循環(huán)賽日程表利用的算法是（A）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法9下面不是分支界限法搜索方式的是（D）。A、廣度優(yōu)先B、最小

3、耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先10下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（D）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法11.備忘錄方法是那種算法的變形。（B）A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法12哈夫曼編碼的貪心算法所需的計算時間為（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13分支限界法解最大團(tuán)問題時，活結(jié)點表的組織形式是（B）。A、最小堆B、最大堆C、棧D、數(shù)組14最長公共子

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

5、策略（B）A遞歸函數(shù)B.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)19.（D）是貪心算法與動態(tài)規(guī)劃算法的共同點。341.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（B）。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解42采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43.以深度優(yōu)先方式系統(tǒng)搜索問題解的

6、算法稱為(D)。A、分支界限算法B、概率算法C、貪心算法D、回溯算法44.實現(xiàn)最長公共子序列利用的算法是（B）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法45.Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設(shè)計出解Hanoi塔問題的遞歸算法正確的為：（B）46.?動態(tài)規(guī)劃算法的基本要素為（C）A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪

7、心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D.預(yù)排序與遞歸調(diào)用Hanoi塔A.voidhanoi(intnintAintCintB)if(n0)hanoi(n1ACB)move(nab)hanoi(n1CBA)B.voidhanoi(intnintAintBintC)if(n0)hanoi(n1ACB)move(nab)hanoi(n1CBA)C.voidhanoi(intnintCintBintA)if(n0)hanoi(n1ACB)