計算機算法設計與分析習題解答（第5版）簡(jiǎn)介，目錄書(shū)摘

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

王曉東，男，1957年出生，山東人，中**員，現任福建工程學(xué)院副院長(cháng)，教授，博士生導師，福建省計算機學(xué)會(huì )理事長(cháng)。先后擔任福州大學(xué)計算機系主任、數學(xué)與計算機科學(xué)學(xué)院院長(cháng)，2007年8月起擔任泉州師范學(xué)院副院長(cháng)。主講課程：算法與數據結構、算法設計與分析、文獻閱讀與選題報告。

目    錄
第1章  算法概述 1
算法分析題1 1
1-1  函數的漸近表達式 1
1-2  O(1)和O(2)的區別 1
1-3  按漸近階排列表達式 1
1-4  算法效率 1
1-5  硬件效率 1
1-6  函數漸近階 2
1-7  n!的階 2
1-8  3n+1問(wèn)題 2
1-9  平均情況下的計算時(shí)間復雜性 2
算法實(shí)現題1 3
1-1  統計數字問(wèn)題 3
1-2  字典序問(wèn)題 4
1-3  最多約數問(wèn)題 4
1-4  金幣陣列問(wèn)題 6
1-5  最大間隙問(wèn)題 8
第2章  遞歸與分治策略 11
算法分析題2 11
2-1  證明Hanoi塔問(wèn)題的遞歸算法與非遞歸算法實(shí)際上是一回事 11
2-2  判斷這7個(gè)算法的正確性 12
2-3  改寫(xiě)二分搜索算法 15
2-4  大整數乘法的O(nmlog(3/2))算法 16
2-5  5次n/3位整數的乘法 16
2-6  矩陣乘法 18
2-7  多項式乘積 18
2-8  O(1)空間子數組換位算法 19
2-9  O(1)空間合并算法 21
2-10  段合并排序算法 27
2-11  自然合并排序算法 28
2-12  第k小元素問(wèn)題的計算時(shí)間下界 29
2-13  非增序快速排序算法 31
2-14  構造Gray碼的分治算法 31
2-15  網(wǎng)球循環(huán)賽日程表 32
2-16  二叉樹(shù)T的前序、中序和后序序列 35
算法實(shí)現題2 36
2-1  眾數問(wèn)題 36
2-2  馬的Hamilton周游路線(xiàn)問(wèn)題 37
2-3  半數集問(wèn)題 44
2-4  半數單集問(wèn)題 46
2-5  有重復元素的排列問(wèn)題 46
2-6  排列的字典序問(wèn)題 47
2-7  集合劃分問(wèn)題 49
2-8  集合劃分問(wèn)題 50
2-9  雙色Hanoi塔問(wèn)題 51
2-10  標準二維表問(wèn)題 52
2-11  整數因子分解問(wèn)題 53
第3章  動(dòng)態(tài)規劃 54
算法分析題3 54
3-1  最長(cháng)單調遞增子序列 54
3-2  最長(cháng)單調遞增子序列的O(nlogn)算法 54
3-3  整數線(xiàn)性規劃問(wèn)題 55
3-4  二維0-1背包問(wèn)題 56
3-5  Ackermann函數 57
算法實(shí)現題3 59
3-1  獨立任務(wù)最優(yōu)調度問(wèn)題 59
3-2  最優(yōu)批處理問(wèn)題 61
3-3  石子合并問(wèn)題 67
3-4  數字三角形問(wèn)題 68
3-5  乘法表問(wèn)題 69
3-6  租用游艇問(wèn)題 70
3-7  汽車(chē)加油行駛問(wèn)題 70
3-8  最小m段和問(wèn)題 71
3-9  圈乘運算問(wèn)題 72
3-10  最大長(cháng)方體問(wèn)題 78
3-11  正則表達式匹配問(wèn)題 79
3-12  雙調旅行售貨員問(wèn)題 83
3-13  最大k乘積問(wèn)題 84
3-14  最少費用購物問(wèn)題 86
3-15  收集樣本問(wèn)題 87
3-16  最優(yōu)時(shí)間表問(wèn)題 89
3-17  字符串比較問(wèn)題 89
3-18  有向樹(shù)k中值問(wèn)題 90
3-19  有向樹(shù)獨立k中值問(wèn)題 94
3-20  有向直線(xiàn)m中值問(wèn)題 98
3-21  有向直線(xiàn)2中值問(wèn)題 101
3-22  樹(shù)的最大連通分支問(wèn)題 103
3-23  直線(xiàn)k中值問(wèn)題 105
3-24  直線(xiàn)k覆蓋問(wèn)題 109
3-25  m處理器問(wèn)題 113
第4章  貪心算法 116
算法分析題4 116
4-1  程序最優(yōu)存儲問(wèn)題 116
4-2  最優(yōu)裝載問(wèn)題的貪心算法 116
4-3  Fibonacci序列的哈夫曼編碼 116
4-4  最優(yōu)前綴碼的編碼序列 117
算法實(shí)現題4 117
4-1  會(huì )場(chǎng)安排問(wèn)題 117
4-2  最優(yōu)合并問(wèn)題 118
4-3  磁帶最優(yōu)存儲問(wèn)題 118
4-4  磁盤(pán)文件最優(yōu)存儲問(wèn)題 119
4-5  程序存儲問(wèn)題 120
4-6  最優(yōu)服務(wù)次序問(wèn)題 120
4-7  多處最優(yōu)服務(wù)次序問(wèn)題 121
4-8  d森林問(wèn)題 122
4-9  虛擬汽車(chē)加油問(wèn)題 123
4-10  區間覆蓋問(wèn)題 124
4-11  刪數問(wèn)題 124
4-12  磁帶最大利用率問(wèn)題 125
4-13  非單位時(shí)間任務(wù)安排問(wèn)題 126
4-14  多元Huffman編碼問(wèn)題 127
4-15  最優(yōu)分解問(wèn)題 128
第5章  回溯法 130
算法分析題5 130
5-1  裝載問(wèn)題改進(jìn)回溯法1 130
5-2  裝載問(wèn)題改進(jìn)回溯法2 131
5-3  0-1背包問(wèn)題的最優(yōu)解 132
5-4  最大團問(wèn)題的迭代回溯法 134
5-5  旅行售貨員問(wèn)題的費用上界 135
5-6  旅行售貨員問(wèn)題的上界函數 136
算法實(shí)現題5 137
5-1  子集和問(wèn)題 137
5-2  最小長(cháng)度電路板排列問(wèn)題 138
5-3  最小重量機器設計問(wèn)題 140
5-4  運動(dòng)員最佳配對問(wèn)題 141
5-5  無(wú)分隔符字典問(wèn)題 142
5-6  無(wú)和集問(wèn)題 144
5-7  n色方柱問(wèn)題 145
5-8  整數變換問(wèn)題 150
5-9  拉丁矩陣問(wèn)題 151
5-10  排列寶石問(wèn)題 152
5-11  重復拉丁矩陣問(wèn)題 154
5-12  羅密歐與朱麗葉的迷宮問(wèn)題 156
5-13  工作分配問(wèn)題 158
5-14  布線(xiàn)問(wèn)題 159
5-15  最佳調度問(wèn)題 160
5-16  無(wú)優(yōu)先級運算問(wèn)題 161
5-17  世界名畫(huà)陳列館問(wèn)題 163
5-18  世界名畫(huà)陳列館問(wèn)題（不重復監視） 166
5-19  算m點(diǎn)問(wèn)題 169
5-20  部落衛隊問(wèn)題 171
5-21  子集樹(shù)問(wèn)題 173
5-22  0-1背包問(wèn)題 174
5-23  排列樹(shù)問(wèn)題 176
5-24  一般解空間搜索問(wèn)題 177
5-25  最短加法鏈問(wèn)題 179
第6章  分支限界法 185
算法分析題6 185
6-1  0-1背包問(wèn)題的棧式分支限界法 185
6-2  釋放結點(diǎn)空間的隊列式分支限界法 187
6-3  及時(shí)刪除不用的結點(diǎn) 188
6-4  用最大堆存儲活結點(diǎn)的優(yōu)先隊列式分支限界法 189
6-5  釋放結點(diǎn)空間的優(yōu)先隊列式分支限界法 192
6-6  團頂點(diǎn)數的上界 194
6-7  團頂點(diǎn)數改進(jìn)的上界 194
6-8  修改解旅行售貨員問(wèn)題的分支限界法 195
6-9  試修改解旅行售貨員問(wèn)題的分支限界法，使得算法保存已產(chǎn)生的排列樹(shù) 197
6-10  電路板排列問(wèn)題的隊列式分支限界法 199
算法實(shí)現題6 201
6-1  最小長(cháng)度電路板排列問(wèn)題 201
6-2  最小權頂點(diǎn)覆蓋問(wèn)題 203
6-3  無(wú)向圖的最大割問(wèn)題 206
6-4  最小重量機器設計問(wèn)題 209
6-5  運動(dòng)員最佳配對問(wèn)題 212
6-6  n后問(wèn)題 214
6-7  布線(xiàn)問(wèn)題 216
6-8  最佳調度問(wèn)題 218
6-9  無(wú)優(yōu)先級運算問(wèn)題 220
6-10  世界名畫(huà)陳列館問(wèn)題 223
6-11  子集空間樹(shù)問(wèn)題 226
6-12  排列空間樹(shù)問(wèn)題 229
6-13  一般解空間的隊列式分支限界法 232
6-14  子集空間樹(shù)問(wèn)題 236
6-15  排列空間樹(shù)問(wèn)題 241
6-16  一般解空間的優(yōu)先隊列式分支限界法 246
6-17  推箱子問(wèn)題 250
第7章  概率算法 256
算法分析題7 256
7-1  模擬正態(tài)分布隨機變量 256
7-2  隨機抽樣算法 256
7-3  隨機產(chǎn)生m個(gè)整數 257
7-4  集合大小的概率算法 258
7-5  生日問(wèn)題 258
7-6  易驗證問(wèn)題的拉斯維加斯算法 259
7-7  用數組模擬有序鏈表 260
7-8  O(n3/2)舍伍德型排序算法 260
7-9  n后問(wèn)題解的存在性 260
7-10  整數因子分解算法 262
7-11  非蒙特卡羅算法的例子 262
7-12  重復3次的蒙特卡羅算法 263
7-13  集合隨機元素算法 263
7-14  由蒙特卡羅算法構造拉斯維加斯算法 265
7-15  產(chǎn)生素數算法 265
7-16  矩陣方程問(wèn)題 265
算法實(shí)現題7 266
7-1  模平方根問(wèn)題 266
7-2  素數測試問(wèn)題 268
7-3  集合相等問(wèn)題 269
7-4  逆矩陣問(wèn)題 269
7-5  多項式乘積問(wèn)題 270
7-6  皇后控制問(wèn)題 270
7-7  3-SAT問(wèn)題 274
7-8  戰車(chē)問(wèn)題 275
第8章  線(xiàn)性規劃與網(wǎng)絡(luò )流 278
算法分析題8 278
8-1  線(xiàn)性規劃可行區域無(wú)界的例子 278
8-2  單源最短路與線(xiàn)性規劃 278
8-3  網(wǎng)絡(luò )最大流與線(xiàn)性規劃 279
8-4  最小費用流與線(xiàn)性規劃 279
8-5  運輸計劃問(wèn)題 279
8-6  單純形算法 280
8-7  邊連通度問(wèn)題 281
8-8  有向無(wú)環(huán)網(wǎng)絡(luò )的最大流 281
8-9  無(wú)向網(wǎng)絡(luò )的最大流 281
8-10  最大流更新算法 282
8-11  混合圖歐拉回路問(wèn)題 282
8-12  單源最短路與最小費用流 282
8-13  中國郵路問(wèn)題 282
算法實(shí)現題8 283
8-1  飛行員配對方案問(wèn)題 283
8-2  太空飛行計劃問(wèn)題 284
8-3  最小路徑覆蓋問(wèn)題 285
8-4  魔術(shù)球問(wèn)題 286
8-5  圓桌問(wèn)題 287
8-6  最長(cháng)遞增子序列問(wèn)題 287
8-7  試題庫問(wèn)題 290
8-8  機器人路徑規劃問(wèn)題 291
8-9  方格取數問(wèn)題 294
8-10  餐巾計劃問(wèn)題 298
8-11  航空路線(xiàn)問(wèn)題 299
8-12  軟件補丁問(wèn)題 300
8-13  星際轉移問(wèn)題 301
8-14  孤島營(yíng)救問(wèn)題 302
8-15  汽車(chē)加油行駛問(wèn)題 304
8-16  數字梯形問(wèn)題 307
8-17  運輸問(wèn)題 311
8-18  分配工作問(wèn)題 314
8-19  負載平衡問(wèn)題 315
8-20  最長(cháng)k可重區間集問(wèn)題 317
8-21  最長(cháng)k可重線(xiàn)段集問(wèn)題 319
第9章  串與序列的算法 323
算法分析題9 323
9-1  簡(jiǎn)單子串搜索算法最壞情況復雜性 323
9-2  后綴重疊問(wèn)題 323
9-3  改進(jìn)前綴函數 323
9-4  確定所有匹配位置的KMP算法 324
9-5  特殊情況下簡(jiǎn)單子串搜索算法的改進(jìn) 325
9-6  簡(jiǎn)單子串搜索算法的平均性能 325
9-7  帶間隙字符的模式串搜索 326
9-8  串接的前綴函數 326
9-9  串的循環(huán)旋轉 327
9-10  失敗函數性質(zhì) 327
9-11  輸出函數性質(zhì) 328
9-12  后綴數組類(lèi) 328
9-13  最長(cháng)公共擴展查詢(xún) 329
9-14  最長(cháng)公共擴展性質(zhì) 332
9-15  后綴數組性質(zhì) 333
9-16  后綴數組搜索 334
9-17  后綴數組快速搜索 335
算法實(shí)現題9 338
9-1  安全基因序列問(wèn)題 338
9-2  最長(cháng)重復子串問(wèn)題 342
9-3  最長(cháng)回文子串問(wèn)題 343
9-4  相似基因序列性問(wèn)題 344
9-5  計算機病毒問(wèn)題 345
9-6  帶有子串包含約束的最長(cháng)公共子序列問(wèn)題 347
9-7  多子串排斥約束的最長(cháng)公共子序列問(wèn)題 349
參考文獻 351