專升本《算法分析與程序設計》期末考試復習題及參考答案

《算法分析與程序設計》專升本1、最大效益優(yōu)先是（

）的一種搜索方式。A、分支界限法

B、動態(tài)規(guī)劃法

C、貪心法

D、回溯法2、在下列算法中有時找不到問題解的是（

）。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法

D、數(shù)值概率算法3、回溯法解旅行售貨員問題時的解空間樹是（

）。A、子集樹 B、排列樹 C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹4、下列算法中通常以自底向上的方式求解最優(yōu)解的是（

）。A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法5、衡量一個算法好壞的標準是（）。

A、運行速度快B、占用空間少C、時間復雜度低D、代碼短6、下面不是分支界限法搜索方式的是（

）。A、廣度優(yōu)先 B、最小耗費優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先7、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（

）。A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法8、備忘錄方法是那種算法的變形。（）A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法9、哈夫曼編碼的貪心算法所需的計算時間為（

）。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）10、分支限界法解最大團問題時，活結點表的組織形式是（

）。A、最小堆 B、最大堆 C、棧 D、數(shù)組11、回溯法的效率不依賴于下列哪些因素（）A、滿足顯約束的值的個數(shù) B、計算約束函數(shù)的時間C、計算限界函數(shù)的時間 D、確定解空間的時間12、下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（

）A、遞歸函數(shù) B、剪枝函數(shù) C、隨機數(shù)函數(shù) D、搜索函數(shù)13、下面關于NP問題說法正確的是（）

A、NP問題都是不可能解決的問題

B、P類問題包含在NP類問題中

C、NP完全問題是P類問題的子集

D、NP類問題包含在P類問題中14、蒙特卡羅算法是（

）的一種。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法15、下列哪一種算法不是隨機化算法（

）A.蒙特卡羅算法B.拉斯維加斯算法C.動態(tài)規(guī)劃算法D.舍伍德算法16、（

）是貪心算法與動態(tài)規(guī)劃算法的共同點。A、重疊子問題 B、構造最優(yōu)解 C、貪心選擇性質 D、最優(yōu)子結構性質17、分支限界法解旅行售貨員問題時，活結點表的組織形式是（

）。A、最小堆 B、最大堆 C、棧 D、數(shù)組18、Strassen矩陣乘法是利用（

）實現(xiàn)的算法。A、分治策略

B、動態(tài)規(guī)劃法

C、貪心法

D、回溯法19、使用分治法求解不需要滿足的條件是（）。

A、子問題必須是一樣的

B、子問題不能夠重復

C、子問題的解可以合并

D、原問題和子問題使用相同的方法解20、下面問題（）不能使用貪心法解決。

A、單源最短路徑問題 B、N皇后問題

C、最小花費生成樹問題 D、背包問題21、下列算法中不能解決0/1背包問題的是（）

A、貪心算法B動態(tài)規(guī)劃C回溯法D分支限界法22、實現(xiàn)合并排序利用的算法是（

）。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法23、下列不是動態(tài)規(guī)劃算法基本要素的是（

）。A、定義最優(yōu)解 B、構造最優(yōu)解 C、算出最優(yōu)解 D、子問題重疊性質24、下列算法中通常以自底向下的方式求解最優(yōu)解的是（

）。A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法25、采用廣度優(yōu)先策略搜索的算法是（

）。A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法12345678910ABBBCDDBBB11121314151617181920DBBBCDAAAB2122232425二多選1、算法是滿足下述性質的指令序列。（）A、編程性B、輸入性C、確定性D、有限性2、以下那些問題能用分治法解決（）A、大整數(shù)的乘法B、快速排序算法C、合并排序D、Strassen矩陣乘法3、以下那些是動態(tài)規(guī)劃的基本步驟（）A、找出最優(yōu)解的性質，并刻劃其結構特征B、遞歸地定義最優(yōu)值。C、以自底向上的方式計算出最優(yōu)值。D、根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。4、貪心算法并不從整體最優(yōu)上加以考慮，它作出的選擇只是在某種意義上局部最優(yōu)選擇。但是對許多問題它能產生整體最優(yōu)解，以下那些問題滿足貪心算法的性質（）A、單源最短路經(jīng)問題B、最小生成樹問題C、哈夫曼問題D、0-1背包問題5、具有限界函數(shù)的深度優(yōu)先生成樹法稱為回溯法，以下選項中是回溯法解題步驟的是（）A、針對所給問題，定義問題的解空間。B、確定易于搜索的解空間結構。C、以深度優(yōu)先方式搜索解空間。D、在搜索過程中用剪枝函數(shù)避免無效搜索。1.BCD2.ABCD3.ABCD4.ABC5.ABCD三判斷1、算法的研究對象僅限于整數(shù)維空間。（）2、分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中。（）3、背包問題可以用貪心算法求解。（）4、回溯法適用于解組合數(shù)較小的問題。（）5、隊列式分支限界法搜索解空間樹的方式與解空間樹的廣度優(yōu)先遍歷算法相同。()6、O(1)與O(2)是有區(qū)別的。（）7、隨機化算法可在很大程度上降低算法的復雜度。（）8、在分支限界法中，每一個活結點有多次機會成為擴展結點。（）9、二叉樹的前序序列和中序序列可以惟一確定此二叉樹的后序序列。（）10、Hanoi塔問題的遞歸算法與非遞歸算法實際上是一回事。（）11、不能用自然語言的方式來描述算法。（）12、快速排序的運行時間與劃分是否對稱有關。（）13、解裝載問題的優(yōu)先隊形式分支限界法用最大優(yōu)先隊列存儲活結點表。（）14、遞歸算法求解問題時，每次產生的子問題總是新問題。（）15、無向連通帶權圖的所有生成樹中，耗費最小的生成樹稱為最小生成樹。（）16、矩陣相乘的基本運算是矩陣之間對應兩個數(shù)的相乘及相加。（）17、直接或循環(huán)地調用自身的算法稱為遞歸算