專升本《算法分析與程序設(shè)計(jì)》期末考試復(fù)習(xí)題及參考答案

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

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

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

C、貪心法

D、回溯法2、在下列算法中有時(shí)找不到問(wèn)題解的是（

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

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

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

）。A、備忘錄法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法5、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（）。

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

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

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

）。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）10、分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（

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

）A、遞歸函數(shù) B、剪枝函數(shù) C、隨機(jī)數(shù)函數(shù) D、搜索函數(shù)13、下面關(guān)于NP問(wèn)題說(shuō)法正確的是（）

A、NP問(wèn)題都是不可能解決的問(wèn)題

B、P類問(wèn)題包含在NP類問(wèn)題中

C、NP完全問(wèn)題是P類問(wèn)題的子集

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

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

B、概率算法

C、貪心算法

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

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

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

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

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

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

C、貪心法

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

A、子問(wèn)題必須是一樣的

B、子問(wèn)題不能夠重復(fù)

C、子問(wèn)題的解可以合并

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

A、單源最短路徑問(wèn)題 B、N皇后問(wèn)題

C、最小花費(fèi)生成樹(shù)問(wèn)題 D、背包問(wèn)題21、下列算法中不能解決0/1背包問(wèn)題的是（）

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

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

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

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

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