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

1、20142014年9月份考試算法設(shè)計(jì)分析第二次作業(yè)月份考試算法設(shè)計(jì)分析第二次作業(yè)一、單項(xiàng)選擇題（本大題共一、單項(xiàng)選擇題（本大題共5050分，共分，共2020小題，每小題小題，每小題2.52.5分）分）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.上界函數(shù)bound計(jì)算結(jié)點(diǎn)所相應(yīng)價(jià)值的上界。privatestaticdoublebound(inti)計(jì)算結(jié)點(diǎn)所

3、相應(yīng)價(jià)值的上界doublecleft=ccw剩余容量doubleb=cp價(jià)值上界以物品單位重量?jī)r(jià)值遞減序裝填剩余容量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.在動(dòng)態(tài)規(guī)劃算法中，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以—（）的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。A.自左向右B.自右向左

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

5、用回溯法解n后問題時(shí)，用完全n叉樹表示解空間?？尚行约s束place剪去不滿足行、列和斜線約束的子樹，place中的if判斷條件應(yīng)為（）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.分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其（）兒子結(jié)點(diǎn)（分支），然后再從當(dāng)前的活結(jié)

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

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