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

1、算法分析與設(shè)計(jì)各章課后作業(yè)第一章 課后作業(yè)1. 設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=10*2n。若在甲臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒，現(xiàn)有一臺(tái)運(yùn)行速度是甲的64倍的另一臺(tái)計(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)=，寫出T(n)的大O記號(hào)表示。2. 下面是實(shí)現(xiàn)在a0=a1=an-1中搜索x的二分搜索算法，請(qǐng)根據(jù)二分搜索技術(shù)在下劃線處填充語(yǔ)句。算法描述如下：templatepublic

2、 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、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法（2）備忘錄方法是那種算法的變形。（ ）A、分治法 B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法（3）矩陣連乘問題的算法可由（）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法2計(jì)算題。設(shè)有0-1背包問題，物品個(gè)數(shù)n=5，背包容量

3、c=10，物品的重量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)值。請(qǐng)?zhí)顚懕?中空缺的內(nèi)容，并給出最優(yōu)值和選擇哪些物品。表1 動(dòng)態(tài)規(guī)劃算法求0-1背包的過程（即計(jì)算mij） ji0123456789105000066666640000666661030000666661020033669910

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

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

6、問題時(shí)，活結(jié)點(diǎn)表的組織形式是（ ）。A、最小堆B、最大堆 C、棧D、數(shù)組2、填空題。（1）分支限界法主要有 分支限界法和 分支限界法。（2）使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和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）拉斯維加斯算法找到的解一定