自考算法設計分析課后答案

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

2、述優(yōu)先隊列。A.先進先出隊列B.后進先出的棧C.最大堆或最小堆D.隨機序列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.對于n個元素

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

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

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

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

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