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

1、算法分析與設(shè)計各章課后作業(yè)第一章 課后作業(yè)1. 設(shè)某算法在輸入規(guī)模為n時的計算時間為T(n)=10*2n。若在甲臺計算機上實現(xiàn)并完成該算法的時間為t秒，現(xiàn)有一臺運行速度是甲的64倍的另一臺計算機乙，問在乙計算機上用同一算法在t秒內(nèi)能解決的問題的規(guī)模是多大？ 2.按照漸近階從低到高的順序排列以下表達式：4n2，logn，3n，20n，2，n2/3。又n!應(yīng)該排在哪一位？第二章 課后作業(yè)1. 用展開法求解下列遞推關(guān)系：T(n)=，寫出T(n)的大O記號表示。2. 下面是實現(xiàn)在a0=a1=an-1中搜索x的二分搜索算法，請根據(jù)二分搜索技術(shù)在下劃線處填充語句。算法描述如下：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、動態(tài)規(guī)劃法C、貪心法D、回溯法（2）備忘錄方法是那種算法的變形。（ ）A、分治法 B、動態(tài)規(guī)劃法C、貪心法D、回溯法（3）矩陣連乘問題的算法可由（）設(shè)計實現(xiàn)。A、分支界限算法B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法2計算題。設(shè)有0-1背包問題，物品個數(shù)n=5，背包容量

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

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

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

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