計算機(jī)算法設(shè)計與分析習(xí)題解答（第2版）

第1章 算法概述

算法分析題1

1-1 函數(shù)的漸近表達(dá)式

1-2 O(1)和O(2)的區(qū)別

1-3 按漸近階排列表達(dá)式

1-4 算法效率

1-5 硬件效率

1-6 函數(shù)漸近階

1-7 n!的階

1-8 3n 1問題

1-9 平均情況下的計算時間復(fù)雜性

算法實現(xiàn)題1

1-1 統(tǒng)計數(shù)字問題

1-2 字典序問題

1-3 最多約數(shù)問題

1-4 金幣陣列問題

1-5 最大間隙問題

第2章 遞歸與分治策略

算法分析題2

2-1 Hanoi塔問題的非遞歸算法

2-2 7個二分搜索算法

2-3 改寫二分搜索算法

2-4 大整數(shù)乘法的O(nmlog(3/2))算法

2-5 5次n/3位整數(shù)的乘法

2-6 矩陣乘法

2-7 多項式乘積

2-8 O(1)空間子數(shù)組換位算法

2-9 O(1)空間合并算法

2-10 n段合并排序算法

2-11 自然合并排序算法

2-12 第k小元素問題的計算時間下界

2-13 非增序快速排序算法

2-14 構(gòu)造Gray碼的分治算法

2-15 網(wǎng)球循環(huán)賽日程表

2-16 二叉樹T的前序、中序和后序序列

算法實現(xiàn)題2

2-1 眾數(shù)問題

2-2 馬的Hamilton周游路線問題

2-3 半數(shù)集問題

2-4 半數(shù)單集問題

2-5 有重復(fù)元素的排列問題

2-6 排列的字典序問題

2-7 集合劃分問題

2-8 集合劃分問題

2-9 雙色Hanoi塔問題

2-10 標(biāo)準(zhǔn)二維表問題

2-11 整數(shù)因子分解問題

第3章 動態(tài)規(guī)劃

算法分析題3

3-1 最長單調(diào)遞增子序列

3-2 最長單調(diào)遞增子序列的O(nlogn)算法

3-3 整數(shù)線性規(guī)劃問題

3-4 二維0-1背包問題

3-5 Ackermann函數(shù)

算法實現(xiàn)題3

3-1 獨立任務(wù)最優(yōu)調(diào)度問題

3-2 編輯距離問題

3-3 石子合并問題

3-4 數(shù)字三角形問題

3-5 乘法表問題

3-6 租用游艇問題

3-7 汽車加油行駛問題

3-8 最小m段和問題

3-9 圈乘運算問題

3-10 最大長方體問題

3-11 正則表達(dá)式匹配問題

3-12 雙調(diào)旅行售貨員問題

3-13 最大k乘積問題

3-14 最少費用購物問題

3-15 收集樣本問題

3-16 最優(yōu)時間表問題

3-17 字符串比較問題

3-18 有向樹k中值問題

3-19 有向樹獨立k中值問題

3-20 有向直線m中值問題

3-21 有向直線2中值問題

3-22 樹的最大連通分支問題

3-23 直線k中值問題

3-24 直線k覆蓋問題

3-25 m處理器問題

第4章 貪心算法

算法分析題4

4-1 程序最優(yōu)存儲問題

4-2 最優(yōu)裝載問題的貪心算法

4-3 Fibonacci序列的哈夫曼編碼

4-4 最優(yōu)前綴碼的編碼序列

算法實現(xiàn)題4

4-1 會場安排問題

4-2 最優(yōu)合并問題

4-3 磁帶最優(yōu)存儲問題

4-4 磁盤文件最優(yōu)存儲問題

4-5 程序存儲問題

4-6 最優(yōu)服務(wù)次序問題

4-7 多處最優(yōu)服務(wù)次序問題

4-8 d森林問題

4-9 汽車加油問題

4-10 區(qū)間覆蓋問題

4-11 刪數(shù)問題

4-12 磁帶最大利用率問題

4-13 非單位時間任務(wù)安排問題

4-14 多元Huffman編碼問題

4-15 最優(yōu)分解問題

第5章 回溯法

算法分析題5

5-1 裝載問題改進(jìn)回溯法1

5-2 裝載問題改進(jìn)回溯法2

5-3 0-1背包問題的最優(yōu)解

5-4 最大團(tuán)問題的迭代回溯法

5-5 旅行售貨員問題的費用上界

5-6 旅行售貨員問題的上界函數(shù)

算法實現(xiàn)題5

5-1 子集和問題

5-2 最小長度電路板排列問題

5-3 最小重量機(jī)器設(shè)計問題

5-4 運動員最佳配對問題

5-5 無分隔符字典問題

5-6 無和集問題

5-7 n色方柱問題

5-8 整數(shù)變換問題

5-9 拉丁矩陣問題

5-10 排列寶石問題

5-11 重復(fù)拉丁矩陣問題

5-12 羅密歐與朱麗葉的迷宮問題

5-13 工作分配問題

5-14 布線問題

5-15 最佳調(diào)度問題

5-16 無優(yōu)先級運算問題

5-17 世界名畫陳列館問題

5-18 世界名畫陳列館問題（不重復(fù)監(jiān)視）

5-19 算m點問題

5-20 部落衛(wèi)隊問題

5-21 子集樹問題

5-22 0-1背包問題

5-23 排列樹問題

5-24 一般解空間搜索問題

5-25 最短加法鏈問題

第6章 分支限界法

算法分析題6

6-1 0-1背包問題的棧式分支限界法

6-2 釋放結(jié)點空間的隊列式分支限界法

6-3 及時刪除不用的結(jié)點

6-4 用最大堆存儲活結(jié)點的優(yōu)先隊列式分支限界法

6-5 釋放結(jié)點空間的優(yōu)先隊列式分支限界法

6-6 團(tuán)頂點數(shù)的上界

6-7 團(tuán)頂點數(shù)改進(jìn)的上界

6-8 修改解旅行售貨員問題的分支限界法

6-9 解旅行售貨員問題的分支限界法中保存已產(chǎn)生的排列樹

6-10 電路板排列問題的隊列式分支限界法

算法實現(xiàn)題6

6-1 最小長度電路板排列問題

6-2 最小權(quán)頂點覆蓋問題

6-3 無向圖的最大割問題

6-4 最小重量機(jī)器設(shè)計問題

6-5 運動員最佳配對問題

6-6 n皇后問題

6-7 布線問題

6-8 最佳調(diào)度問題

6-9 無優(yōu)先級運算問題

6-10 世界名畫陳列館問題

6-11 子集空間樹問題

6-12 排列空間樹問題

6-13 一般解空間的隊列式分支限界法

6-14 子集空間樹問題

6-15 排列空間樹問題

6-16 一般解空間的優(yōu)先隊列式分支限界法

6-17 推箱子問題

第7章 概率算法

算法分析題7

7-1 模擬正態(tài)分布隨機(jī)變量

7-2 隨機(jī)抽樣算法

7-3 隨機(jī)產(chǎn)生m個整數(shù)

7-4 集合大小的概率算法

7-5 生日問題

7-6 易驗證問題的拉斯維加斯算法

7-7 用數(shù)組模擬有序鏈表

7-8 O(n3/2)舍伍德型排序算法

7-9 n后問題解的存在性

7-10 整數(shù)因子分解算法

7-11 非蒙特卡羅算法的例子

7-12 重復(fù)3次的蒙特卡羅算法

7-13 集合隨機(jī)元素算法

7-14 由蒙特卡羅算法構(gòu)造拉斯維加斯算法

7-15 產(chǎn)生素數(shù)算法

7-16 矩陣方程問題

算法實現(xiàn)題7

7-1 模平方根問題

7-2 素數(shù)測試問題

7-3 集合相等問題

7-4 逆矩陣問題

7-5 多項式乘積問題

7-6 皇后控制問題

7-7 3-SAT問題

7-8 戰(zhàn)車問題

第8章 線性規(guī)劃與網(wǎng)絡(luò)流 算法分析題8

8-1 線性規(guī)劃可行區(qū)域無界的例子

8-2 單源最短路與線性規(guī)劃

8-3 網(wǎng)絡(luò)最大流與線性規(guī)劃

8-4 最小費用流與線性規(guī)劃

8-5 運輸計劃問題

8-6 單純形算法

8-7 邊連通度問題

8-8 有向無環(huán)網(wǎng)絡(luò)的最大流

8-9 無向網(wǎng)絡(luò)的最大流

8-10 最大流更新算法

8-11 混合圖歐拉回路問題

8-12 單源最短路與最小費用流

8-13 中國郵路問題

算法實現(xiàn)題8

8-1 飛行員配對方案問題

8-2 太空飛行計劃問題

8-3 最小路徑覆蓋問題

8-4 魔術(shù)球問題

8-5 圓桌問題

8-6 最長遞增子序列問題

8-7 試題庫問題

8-8 機(jī)器人路徑規(guī)劃問題

8-9 方格取數(shù)問題

8-10 餐巾計劃問題

8-11 航空路線問題

8-12 軟件補丁問題

8-13 星際轉(zhuǎn)移問題

8-14 孤島營救問題

8-15 汽車加油行駛問題

8-16 數(shù)字梯形問題

8-17 運輸問題

8-18 分配工作問題

8-19 負(fù)載平衡問題

8-20 最長k可重區(qū)間集問題

8-21 最長k可重線段集問題

參考文獻(xiàn)2100433B

本書是與普通高等教育“十一五”國家級規(guī)劃教材《計算機(jī)算法設(shè)計與分析（第4版）》配套的輔助教材和國家精品課程教材，分別對主教材中的算法分析題和算法實現(xiàn)題給出了解答或解題思路提示。為了提高學(xué)生靈活運用算法設(shè)計策略解決實際問題的能力，本書還將主教材中的許多習(xí)題改造成算法實現(xiàn)題，要求學(xué)生設(shè)計出求解算法并上機(jī)實現(xiàn)。

• 配套教材

《計算機(jī)算法設(shè)計與分析（第5版）》有配套教材——《計算機(jī)算法設(shè)計與分析習(xí)題解答（第5版）》 。

本書是與“十二五”普通高等教育本科國家級規(guī)劃教材《計算機(jī)算法設(shè)計與分析（第5版）》配套的輔助教材和國家精品課程教材，分別對主教材中的算法分析題和算法實現(xiàn)題給出了解答或解題思路提示。為了提高學(xué)生靈活運用算法設(shè)計策略解決實際問題的能力，本書還將主教材中的許多習(xí)題改造成算法實現(xiàn)題，要求學(xué)生設(shè)計出求解算法并上機(jī)實現(xiàn)。本書教學(xué)資料包含各章算法實現(xiàn)題、測試數(shù)據(jù)和答案，可在華信教育資源網(wǎng)免費注冊下載。本書內(nèi)容豐富，理論聯(lián)系實際，可作為高等學(xué)校計算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息與計算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計算機(jī)算法設(shè)計的輔助教材，也是工程技術(shù)人員和自學(xué)者的參考書。

王曉東，男，1957年出生，山東人，中共黨員，現(xiàn)任福建工程學(xué)院副院長，教授，博士生導(dǎo)師，福建省計算機(jī)學(xué)會理事長。先后擔(dān)任福州大學(xué)計算機(jī)系主任、數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院院長，2007年8月起擔(dān)任泉州師范學(xué)院副院長。主講課程：算法與數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計與分析、文獻(xiàn)閱讀與選題報告。 2100433B