計算機算法設計與分析習題解答（第2版）

《計算機算法設計與分析習題解答（第2版）》作譯者是王曉東，2012年06月由電子工業出版社出版。

基本介紹

• 書名：計算機算法設計與分析習題解答(第2版)
• 作者：王曉東
• ISBN：9787121161346, 7121161346
• 頁數：311頁
• 定價：39.80
• 出版社：電子工業出版社
• 出版時間：2012年6月1日
• 裝幀：平裝
• 開本：16

內容簡介

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

目 錄

第1章 算法概述

算法分析題1

1-1 函式的漸近表達式

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

1-3 按漸近階排列表達式

1-4 算法效率

1-5 硬體效率

1-6 函式漸近階

1-7 n!的階

1-8 3n+1問題

1-9 平均情況下的計算時間複雜性

算法實現題1

1-1 統計數字問題

1-2 字典序問題

1-3 最多約數問題

1-4 金幣陣列問題

1-5 最大間隙問題

第2章 遞歸與分治策略

算法分析題2

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

2-2 7個二分搜尋算法

2-3 改寫二分搜尋算法

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

2-5 5次n/3位整數的乘法

2-6 矩陣乘法

2-7 多項式乘積

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

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

2-10 n段合併排序算法

2-11 自然合併排序算法

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

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

2-14 構造Gray碼的分治算法

2-15 網球循環賽日程表

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

算法實現題2

2-1 眾數問題

2-2 馬的Hamilton週遊路線問題

2-3 半數集問題

2-4 半數單集問題

2-5 有重複元素的排列問題

2-6 排列的字典序問題

2-7 集合劃分問題

2-8 集合劃分問題

2-9 雙色Hanoi塔問題

2-10 標準二維表問題

2-11 整數因子分解問題

第3章 動態規劃

算法分析題3

3-1 最長單調遞增子序列

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

3-3 整數線性規劃問題

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

3-5 Ackermann函式

算法實現題3

3-1 獨立任務最優調度問題

3-2 編輯距離問題

3-3 石子合併問題

3-4 數字三角形問題

3-5 乘法表問題

3-6 租用遊艇問題

3-7 汽車加油行駛問題

3-8 最小m段和問題

3-9 圈乘運算問題

3-10 最大長方體問題

3-11 正則表達式匹配問題

3-12 雙調旅行售貨員問題

3-13 最大k乘積問題

3-14 最少費用購物問題

3-15 收集樣本問題

3-16 最優時間表問題

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 程式最優存儲問題

4-2 最優裝載問題的貪心算法

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

4-4 最優前綴碼的編碼序列

算法實現題4

4-1 會場安排問題

4-2 最優合併問題

4-3 磁帶最優存儲問題

4-4 磁碟檔案最優存儲問題

4-5 程式存儲問題

4-6 最優服務次序問題

4-7 多處最優服務次序問題

4-8 d森林問題

4-9 汽車加油問題

4-10 區間覆蓋問題

4-11 刪數問題

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

4-13 非單位時間任務安排問題

4-14 多元Huffman編碼問題

4-15 最優分解問題

第5章 回溯法

算法分析題5

5-1 裝載問題改進回溯法1

5-2 裝載問題改進回溯法2

5-3 0-1背包問題的最優解

5-4 最大團問題的疊代回溯法

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

5-6 旅行售貨員問題的上界函式

算法實現題5

5-1 子集和問題

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

5-3 最小重量機器設計問題

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

5-5 無分隔設定字典問題

5-6 無和集問題

5-7 n色方柱問題

5-8 整數變換問題

5-9 拉丁矩陣問題

5-10 排列寶石問題

5-11 重複拉丁矩陣問題

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

5-13 工作分配問題

5-14 布線問題

5-15 最佳調度問題

5-16 無優先權運算問題

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

5-18 世界名畫陳列館問題（不重複監視）

5-19 算m點問題

5-20 部落衛隊問題

5-21 子集樹問題

5-22 0-1背包問題

5-23 排列樹問題

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

5-25 最短加法鏈問題

第6章 分支限界法

算法分析題6

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

6-2 釋放結點空間的佇列式分支限界法

6-3 及時刪除不用的結點

6-4 用最大堆存儲活結點的優先佇列式分支限界法

6-5 釋放結點空間的優先佇列式分支限界法

6-6 團頂點數的上界

6-7 團頂點數改進的上界

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

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

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

算法實現題6

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

6-2 最小權頂點覆蓋問題

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

6-4 最小重量機器設計問題

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

6-6 n皇后問題

6-7 布線問題

6-8 最佳調度問題

6-9 無優先權運算問題

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

6-11 子集空間樹問題

6-12 排列空間樹問題

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

6-14 子集空間樹問題

6-15 排列空間樹問題

6-16 一般解空間的優先佇列式分支限界法

6-17 推箱子問題

第7章 機率算法

算法分析題7

7-1 模擬常態分配隨機變數

7-2 隨機抽樣算法

7-3 隨機產生m個整數

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

7-5 生日問題

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

7-7 用數組模擬有序鍊表

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

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

7-10 整數因子分解算法

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

7-12 重複3次的蒙特卡羅算法

7-13 集合隨機元素算法

7-14 由蒙特卡羅算法構造拉斯維加斯算法

7-15 產生素數算法

7-16 矩陣方程問題

算法實現題7

7-1 模平方根問題

7-2 素數測試問題

7-3 集合相等問題

7-4 逆矩陣問題

7-5 多項式乘積問題

7-6 皇后控制問題

7-7 3-SAT問題

7-8 戰車問題

第8章 線性規劃與網路流 算法分析題8

8-1 線性規劃可行區域無界的例子

8-2 單源最短路與線性規劃

8-3 網路最大流與線性規劃

8-4 最小費用流與線性規劃

8-5 運輸計畫問題

8-6 單純形算法

8-7 邊連通度問題

8-8 有向無環網路的最大流

8-9 無向網路的最大流

8-10 最大流更新算法

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

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

8-13 中國郵路問題

算法實現題8

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

8-2 太空飛行計畫問題

8-3 最小路徑覆蓋問題

8-4 魔術球問題

8-5 圓桌問題

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

8-7 試題庫問題

8-8 機器人路徑規劃問題

8-9 方格取數問題

8-10 餐巾計畫問題

8-11 航空路線問題

8-12 軟體補丁問題

8-13 星際轉移問題

8-14 孤島營救問題

8-15 汽車加油行駛問題

8-16 數字梯形問題

8-17 運輸問題

8-18 分配工作問題

8-19 負載平衡問題

8-20 最長k可重區間集問題

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

參考文獻