算法設(shè)計(jì)與分析試卷(A)及答案

---------------------------------------

課程名稱(chēng) 1、一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與2、這種不斷回頭尋找目標(biāo)的方法稱(chēng)為回溯法

編號(hào)

--------

3、直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法4、記號(hào)在算法復(fù)雜性的表示法中表示

----------------------------

7、下列各步驟的先后順序是②③④①。①調(diào)試程序②分析問(wèn)題③設(shè)計(jì)算法④編寫(xiě)程 9、貪心算法從初始階段開(kāi)始，每一個(gè)階段總是作一個(gè)使局部最優(yōu)的貪心選擇。------------------------------------------------

10、拉斯維加斯算法找到的解一定是正確的 A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法2、下列不是基本計(jì)算模型的是（B）。-1-A、回溯法B、分支限界法C、回溯法和分支限界法D、動(dòng)態(tài)規(guī)劃B6、FIFO是（A B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法7、投點(diǎn)法是（B B、概率算法C、貪心算法D、回溯算法（B）對(duì)輸入進(jìn)行預(yù)處理。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法

A、P類(lèi)問(wèn)題 C、NP完全問(wèn)題D、P類(lèi)語(yǔ)言n210n-1;14+5/n+1/n2;①因?yàn)椋簂im

(n210n-1)n2n210n-1

n2是n210n-1;的漸近表達(dá)式。②因?yàn)椋簂imn

(145/n1/n2)140;由漸145/n1/n2 -2-

數(shù)值，最后給出裝載方案及背包中物品的重量和價(jià)值。物品A 重量35 價(jià)值10 x0x1x0x1x0x1 4 x0x1x0 4 x05 x1x0 5 x06 x0x0 zx3x2x2 3 x3xx2x 71 2 3 x2x4x 124 2 x4x3x8x 106 2 3 x0 -3-最優(yōu)解函數(shù)的最大值為：解為：-4-0

時(shí)間復(fù)雜度2、回溯法3、遞歸算法

5、原問(wèn)題的較小模式遞歸技術(shù)6、問(wèn)題的計(jì)算復(fù)雜性分析有一個(gè)共同的客觀(guān)尺度7、②③④①8、問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解9、局部最優(yōu)10、

(n210n-1)n2n210n-1

n2是n210n-1;的漸近表達(dá)式。

(145/n1/n2)140;由漸近表達(dá)式的定義易知：145/n1/n21

1

1

0

0

1

0

0

1

0

x10x0

-5-a．4040305035150115190.625(1,1,1,1,7,0,0)40 b.4040305030150115177.5(1,1,1,1,0,7,0) d.4040303530150105167.5

(1,1,1,0,1,3,0)e.4040503530150130175(1,1,0,1,1,f.4040503510150130170.71

(1,1,0,1,1,0,) h.4040353010150140146.85(1,1,0,0,1,1,2) i.4030503530150125167.5(1,0,1,1,1,5,0) j.403