《算法設計與分析》期末復習題

1、《算法分析與設計》試題庫 《算法分析與設計》試題庫(一)一、 選擇題1、二分搜索算法是利用（ A ）實現(xiàn)的算法。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是（ A ）。A、找出最優(yōu)解的性質 B、構造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解3、最大效益優(yōu)先是（ A ）的一搜索方式。A、分支界限法 B、動態(tài)規(guī)劃法 C

2、、貪心法 D、回溯法4、在下列算法中有時找不到問題解的是（ B ）。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法5. 回溯法解旅行售貨員問題時的解空間樹是（ B ）。A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹6．下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法7、衡量一個算法

3、好壞的標準是（C ）。A 運行速度快 B 占用空間少 C 時間復雜度低 D 代碼短8、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1 背包問題9. 實現(xiàn)循環(huán)賽日程表利用的算法是（ A ）。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法10、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法11．下

4、面不是分支界限法搜索方式的是（ D ）。A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先12．下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（ D ）。A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法13.備忘錄方法是那種算法的變形。（ B ）A、分支界限算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法26. 分支限界法解旅行售貨員問題時，活結點表的組織形式

5、是（ A ）。A、最小堆 B、最大堆 C、棧 D、數(shù)組27、Strassen 矩陣乘法是利用（ A ）實現(xiàn)的算法。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法29、使用分治法求解不需要滿足的條件是（A ）。A 子問題必須是一樣的B 子問題不能夠重復C 子問題的解可以合并D 原問題和子問題使用相同的方法解30、下面問題（B ）不能使用貪心法解決。A 單源最短路徑問題 B N 皇后問題 C

6、最小花費生成樹問題D 背包問題31、下列算法中不能解決 0/1 背包問題的是（A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法32、回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷33、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法34．實現(xiàn)合并排序利用的算法是（ A ）。A、分

7、治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法35．下列是動態(tài)規(guī)劃算法基本要素的是（ D ）。A、定義最優(yōu)解 B、構造最優(yōu)解 C、算出最優(yōu)解 D、子問題重疊性質36．下列算法中通常以自底向下的方式求解最優(yōu)解的是（ B ）。A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法37．采用廣度優(yōu)先策略搜索的算法是（ A ）。A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法38、合并排序算法是利用（