算法設計與分析復習題目及答案

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、貪心法D、回溯法4、在下列算法中有時找不到問題解的是（B）。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法5.回溯法解旅行售貨員問題時的解空間樹是（B

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

3、時有時候成功有時候失敗的是（C）A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法11下面不是分支界限法搜索方式的是（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.分支限界法解旅行售貨員問題時，活結點表的組織形式是（A）。A

4、、最小堆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單源最短路徑問題BN皇后問題C最小花費生成樹問題D背包問題31、下列算法中不能解決01背包問題的是（A）A貪心法B動態(tài)規(guī)劃C回溯法

5、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、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法35下列是動態(tài)規(guī)劃算法基本要素的是（D）。A、定義最優(yōu)解B、構造最優(yōu)解C、算出最優(yōu)解D、子問題重疊性質36下列算法中通常以自底向下的方式