自考算法設(shè)計(jì)分析課后答案

1、20132013年4月考試算法設(shè)計(jì)分析第二次作業(yè)月考試算法設(shè)計(jì)分析第二次作業(yè)一、單項(xiàng)選擇題（本大題共一、單項(xiàng)選擇題（本大題共3030分，共分，共1515小題，每小題小題，每小題2分）分）1.優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值p來表示。結(jié)點(diǎn)優(yōu)先級(jí)的高低與p值大小相關(guān)，根據(jù)問題的不同情況，采用（）來描

2、述優(yōu)先隊(duì)列。A.先進(jìn)先出隊(duì)列B.后進(jìn)先出的棧C.最大堆或最小堆D.隨機(jī)序列2.階乘函數(shù)用遞歸定義Publicstaticintfactial(intn)if(n==0)return1return()A.nfactial(n)B.nfactial(n1)C.nfactial(n2)D.nfactial(n1)3.（）能夠求得問題的解但卻無法有效地判定解的正確性A.數(shù)值概率算法B.蒙特卡羅算法C.拉斯維加斯算法D.舍伍得算法4.對(duì)于n個(gè)元素

3、的排序問題。n＝2時(shí)只要作（）次比較即可排好序A.3B.2C.1D.45.一般地講，當(dāng)一個(gè)問題的所有子問題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法和備忘錄算法相比：（）A.效果一樣動(dòng)態(tài)規(guī)劃效果好B.備忘錄方法效果好C.無法判斷D.哪個(gè)效果好6.分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解二者（）A.求解目標(biāo)不同搜索方式相同B.求解目標(biāo)不同搜索方式也不同C.求解目標(biāo)相同搜索方式不同D.求解目標(biāo)相同搜索方式也相同7.遞歸算法不能適用以下場(chǎng)

4、合（）A.數(shù)據(jù)的定義形式按遞歸定義B.數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義C.問題解法按遞歸算法實(shí)現(xiàn)D.概率問題8.當(dāng)子問題之間包含公共的子子問題則分治法要做許多不必要的工作重復(fù)地解公共的子問題此時(shí)一般用（）法較好A.動(dòng)態(tài)規(guī)劃A.O(n)B.O(n!)C.O(n2)D.O(n3)二、判斷題（本大題共二、判斷題（本大題共7070分，共分，共2020小題，每小題小題，每小題3.53.5分）分）1.從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出

5、的程序一般是一個(gè)遞歸過程。因此，分治法的計(jì)算效率通?？梢杂眠f歸方程來進(jìn)行分析。（）2.多階段決策問題中，每一個(gè)階段可能有若干個(gè)決策可供選擇()3.拉斯維加斯算法不會(huì)得到不正確的解，但有時(shí)找不到解。（）4.在通往邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧保存的每次調(diào)用的中間結(jié)果是局部變量和返回地址值。()5.要想在電腦上擴(kuò)大所處理問題的規(guī)模有效的途徑是提高算法的計(jì)算復(fù)雜度。()6.程序必須滿足算法具有數(shù)據(jù)輸出的性質(zhì)()7.反復(fù)應(yīng)用分治手段，可以

6、使子問題與原問題類型一致而其規(guī)模卻不斷縮小()8.一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有某種特定關(guān)系的量()9.最優(yōu)子結(jié)構(gòu)性質(zhì)特征反映了遞歸思想的應(yīng)用()10.遞歸邊界本身并不使用遞歸的定義()11.用分治法求解一個(gè)問題，所需的時(shí)間是由子問題的個(gè)數(shù)、大小以及把這個(gè)問題分解為子問題所需的工作總量來確定的。()12.應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個(gè)（最優(yōu)）解。（）13.好的約束函數(shù)能顯著地

7、減少所生成的結(jié)點(diǎn)數(shù)，但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。（）14.一個(gè)遞歸定義必須是有確切含義的必須一步比一步簡(jiǎn)單，最后是有終結(jié)的，不能無限循環(huán)下去()。15.最優(yōu)子結(jié)構(gòu)性質(zhì)是應(yīng)用分治法的前提()16.操作系統(tǒng)，它是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。()17.有些數(shù)據(jù)結(jié)構(gòu)如二叉樹等，由于其本身的遞歸特性、特別適合用遞歸的形式來描述。()18.概率算法的一個(gè)基本特