2014年9月份考試算法設計分析第二次作業(yè)

1、20142014年9月份考試算法設計分析第二次作業(yè)月份考試算法設計分析第二次作業(yè)一、單項選擇題（本大題共一、單項選擇題（本大題共5050分，共分，共2020小題，每小題小題，每小題2.52.5分）分）1.優(yōu)先隊列的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的高低與p值大小相關(guān)，根據(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.上界函數(shù)bound計算結(jié)點所相應價值的上界。privatestaticdoublebound(inti)計算結(jié)點所

3、相應價值的上界doublecleft=ccw剩余容量doubleb=cp價值上界以物品單位重量價值遞減序裝填剩余容量while(i=nb=p[i]i裝填剩余容量裝滿背包if(i=n)（）returnbA.b=p[i]B.b=p[i]w[i]cleftC.b=p[i]w[i]cleftD.b=p[i]4.在動態(tài)規(guī)劃算法中，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以—（）的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。A.自左向右B.自右向左

4、C.自上向下D.自底向上5.（）能夠求得問題的解但卻無法有效地判定解的正確性A.數(shù)值概率算法B.蒙特卡羅算法C.拉斯維加斯算法D.舍伍得算法6.拉斯維加斯算法的一個顯著特征是它所做的隨機性決策有可能導致算法找不到所需的解。因此通常用一個（）方法表示拉斯維加斯型算法。A.boolean型B.概率C.統(tǒng)籌D.自定義7.對于n個元素的排序問題。n＝2時只要作（）次比較即可排好序A.3B.2A.最輕次輕B.最重次重C.最輕次重D.最重次輕16.

5、用回溯法解n后問題時，用完全n叉樹表示解空間?？尚行约s束place剪去不滿足行、列和斜線約束的子樹，place中的if判斷條件應為（）A.(Math.abs(kj)==Math.abs(x[j]x[k]))||(x[j]==x[k])B.(Math.abs(kj)==Math.abs(x[j]x[k])C.(x[j]==x[k])D.以上都不正確17.分支限界法的搜索策略是：在擴展結(jié)點處，先生成其（）兒子結(jié)點（分支），然后再從當前的活結(jié)

6、點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。A.一個B.二個C.任意多個D.所有的18.能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征（)這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不具備

7、優(yōu)勢。A.子問題的可求解性B.子問題的獨立性C.子問題的可合并性D.子問題的重疊性19.在任何一個的棋盤覆蓋中，用到的L型骨牌個數(shù)恰為（）。22A.(4k1)3B.(4k1)2C.(2k1)3D.(2k1)220.動態(tài)規(guī)劃的時間復雜度為（）A.O(n)B.O(n!)C.O(n2)D.O(n3)二、判斷題（本大題共二、判斷題（本大題共5050分，共分，共2020小題，每小題小題，每小題2.52.5分）分）1.從分治法的一般設計模式可以看出