《算法分析與設(shè)計(jì)》課后作業(yè)

1、算法分析與設(shè)計(jì)各章課后作業(yè)第一章課后作業(yè)1 .設(shè)某算法在輸入規(guī)模為 n時(shí)的計(jì)算時(shí)間為t(n)=10*2若在甲臺計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒，現(xiàn)有一臺運(yùn)彳t速度是甲的64倍的另一臺計(jì)算機(jī)乙，問在乙計(jì)算機(jī)上用同一算法在t秒內(nèi)能解決的問題的規(guī)模是多大？2 .按照漸近階從低到高的順序排列以下表達(dá)式：4n2, logn , 3n, 20n, 2, n2/3。又n!應(yīng)該排在哪一位？第二章課后作業(yè)1.用展開法求解下列遞推關(guān)系:t(n)= 32t (n / 2) +o(n),寫出t(n)的大。記號表示。2.下面是實(shí)現(xiàn)在a0=a1=an-1中搜索x的二分搜索算法，請根據(jù)二分搜索技術(shù)在下劃線處填充語句。算

2、法描述如下：templatepublic static int binarysearch(int 口a, int x, int n) / 在 a0=a1= amiddle) left = middle + 1;else right=return -1; /未找到x第三章課后作業(yè)1、選擇題。(1)下列算法中通常以自底向上的方式求解最優(yōu)解的是(a、備忘錄法日動(dòng)態(tài)規(guī)劃法貪心法回溯法(2)備忘錄方法是那種算法的變形。(a分治法b、動(dòng)態(tài)規(guī)劃法貪心法(3)矩陣連乘問題的算法可由()設(shè)計(jì)實(shí)現(xiàn)。a分支界限算法日動(dòng)態(tài)規(guī)劃算法c、貪心算法d、回溯算法2.計(jì)算題。設(shè)有0-1背包問題，物品個(gè)數(shù) n=5,背包容量c=1

3、0,物品的重量 w=(w1,w2,w3,w4,w5 )=2,2,6,5,4,物品的價(jià)值 v=(v1,v2,v3,v4,v5)=6,3,5,4,6。利用動(dòng)態(tài)規(guī)劃算法，求出不超過背包容量，怎樣選擇物品，使得裝入背包中物品的總價(jià)值最大。說明：表1就是計(jì)算m(i,j) 。m(i,j)為最優(yōu)值(即價(jià)值總和最大)，它表示背包容量為j ,可選擇物品為i,i+1,n時(shí)0-1背包問題的最優(yōu)值。請?zhí)顚懕?中空缺的內(nèi)容，并給出最優(yōu)值和選擇哪些物品。表1動(dòng)態(tài)規(guī)劃算法求0-1背包的過程(即計(jì)算mij)01234567891050000666666400006666610 300j1066 661 11020033669

4、910111006669121515第四章 課后作業(yè)1、選擇題。（ 1 ）下面是貪心算法的基本要素的是（ ）。a重疊子問題日構(gòu)造最優(yōu)解c貪心選擇t質(zhì) d定義最優(yōu)解（ 2 ）（ ）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。a重疊子問題r構(gòu)造最優(yōu)解g貪心選擇t質(zhì)d、最優(yōu)子結(jié)構(gòu)性質(zhì)（ 3 ）下面問題（）不能使用貪心法解決。a、單源最短路徑問題b、n皇后問題 c、最小花費(fèi)生成樹問題d、背包問題2、 對于字符集合 m=a,b,c,d,e,f ， 設(shè)這些字符在文本中出現(xiàn)的頻率分別為 8,1,3,10,6,5畫出字符集合m 的 huffman 編碼樹，并給出各字符的 huffman 編碼。第五章 課后作業(yè)1、選擇題

5、。1 ）回溯法解旅行售貨員問題時(shí)的解空間樹是（ ）。a子集樹以排列樹c、深度優(yōu)先生成樹d廣度優(yōu)先生成樹2 ）下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（）。a備忘錄法 r動(dòng)態(tài)規(guī)劃法c、貪心法d、回溯法（ 3 ）下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（ ）。a.遞歸函數(shù)b.剪枝函數(shù)c隨機(jī)數(shù)函數(shù)d.搜索函數(shù)2、回溯法中常見的兩類典型的解空間樹是哪些，請簡述之。1、選擇題。（ 1 ）廣度優(yōu)先是（第六章 課后作業(yè)）的一搜索方式。a、分支界限法b、動(dòng)態(tài)規(guī)劃法c、貪心法 d、回溯法（ 2 ）采用最大效益優(yōu)先搜索方式的算法是（ ）。a分支界限法以動(dòng)態(tài)規(guī)劃法（ 3 ）分支限界法解旅行售貨員問題時(shí)，

6、活結(jié)點(diǎn)表的組織形式是（ ）。a最小堆以最大堆c棧d、數(shù)組2、填空題。(1)分支限界法主要有 分支限界法和 分支限界法。(2)使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，皇后問題和0/1背包問題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 ,只使用約束條件進(jìn)行裁剪的是 (3)以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為。第七章課后作業(yè)1、選擇題。(1)蒙特卡羅算法是()的一種。a、分支界限算法b、概率算法c、貪心算法d、回溯算法(2)下列哪一種算法不是隨機(jī)化算法()。a.蒙特卡羅算法b.拉斯維加斯算法c.動(dòng)態(tài)規(guī)劃算法d.舍伍德算法(3)下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是()。a數(shù)值概率算法b舍伍德算法c拉斯維加斯算法 d蒙特卡羅算法2、填空題。(1)拉斯維加斯算法找到的