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

第1章  算法概述 1

算法分析題1 1

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

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

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

1-4  算法效率 1

1-5  硬件效率 1

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

1-7  n!的階 2

1-8  3n+1問題 2

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

算法實(shí)現(xiàn)題1 3

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

1-2  字典序問題 4

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

1-4  金幣陣列問題 6

1-5  最大間隙問題 8

第2章  遞歸與分治策略 11

算法分析題2 11

2-1  證明Hanoi塔問題的遞歸算法與非遞歸算法實(shí)際上是一回事 11

2-2  判斷這7個(gè)算法的正確性 12

2-3  改寫二分搜索算法 15

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

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

2-6  矩陣乘法 18

2-7  多項(xiàng)式乘積 18

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

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

2-10  段合并排序算法 27

2-11  自然合并排序算法 28

2-12  第k小元素問題的計(jì)算時(shí)間下界 29

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

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

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

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

算法實(shí)現(xiàn)題2 36

2-1  眾數(shù)問題 36

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

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

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

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

2-6  排列的字典序問題 47

2-7  集合劃分問題 49

2-8  集合劃分問題 50

2-9  雙色Hanoi塔問題 51

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

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

第3章  動(dòng)態(tài)規(guī)劃 54

算法分析題3 54

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

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

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

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

3-5  Ackermann函數(shù) 57

算法實(shí)現(xiàn)題3 59

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

3-2  最優(yōu)批處理問題 61

3-3  石子合并問題 67

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

3-5  乘法表問題 69

3-6  租用游艇問題 70

3-7  汽車加油行駛問題 70

3-8  最小m段和問題 71

3-9  圈乘運(yùn)算問題 72

3-10  最大長方體問題 78

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

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

3-13  最大k乘積問題 84

3-14  最少費(fèi)用購物問題 86

3-15  收集樣本問題 87

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

3-17  字符串比較問題 89

3-18  有向樹k中值問題 90

3-19  有向樹獨(dú)立k中值問題 94

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

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

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

3-23  直線k中值問題 105

3-24  直線k覆蓋問題 109

3-25  m處理器問題 113

第4章  貪心算法 116

算法分析題4 116

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

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

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

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

算法實(shí)現(xiàn)題4 117

4-1  會場安排問題 117

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

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

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

4-5  程序存儲問題 120

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

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

4-8  d森林問題 122

4-9  虛擬汽車加油問題 123

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

4-11  刪數(shù)問題 124

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

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

4-14  多元Huffman編碼問題 127

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

第5章  回溯法 130

算法分析題5 130

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

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

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

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

5-5  旅行售貨員問題的費(fèi)用上界 135

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

算法實(shí)現(xiàn)題5 137

5-1  子集和問題 137

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

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

5-4  運(yùn)動(dòng)員最佳配對問題 141

5-5  無分隔符字典問題 142

5-6  無和集問題 144

5-7  n色方柱問題 145

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

5-9  拉丁矩陣問題 151

5-10  排列寶石問題 152

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

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

5-13  工作分配問題 158

5-14  布線問題 159

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

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

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

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

5-19  算m點(diǎn)問題 169

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

5-21  子集樹問題 173

5-22  0-1背包問題 174

5-23  排列樹問題 176

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

5-25  最短加法鏈問題 179

第6章  分支限界法 185

算法分析題6 185

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

6-2  釋放結(jié)點(diǎn)空間的隊(duì)列式分支限界法 187

6-3  及時(shí)刪除不用的結(jié)點(diǎn) 188

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

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

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

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

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

6-9  試修改解旅行售貨員問題的分支限界法，使得算法保存已產(chǎn)生的排列樹 197

6-10  電路板排列問題的隊(duì)列式分支限界法 199

算法實(shí)現(xiàn)題6 201

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

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

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

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

6-5  運(yùn)動(dòng)員最佳配對問題 212

6-6  n后問題 214

6-7  布線問題 216

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

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

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

6-11  子集空間樹問題 226

6-12  排列空間樹問題 229

6-13  一般解空間的隊(duì)列式分支限界法 232

6-14  子集空間樹問題 236

6-15  排列空間樹問題 241

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

6-17  推箱子問題 250

第7章  概率算法 256

算法分析題7 256

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

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

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

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

7-5  生日問題 258

7-6  易驗(yàn)證問題的拉斯維加斯算法 259

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

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

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

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

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

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

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

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

7-15  產(chǎn)生素?cái)?shù)算法 265

7-16  矩陣方程問題 265

算法實(shí)現(xiàn)題7 266

7-1  模平方根問題 266

7-2  素?cái)?shù)測試問題 268

7-3  集合相等問題 269

7-4  逆矩陣問題 269

7-5  多項(xiàng)式乘積問題 270

7-6  皇后控制問題 270

7-7  3-SAT問題 274

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

第8章  線性規(guī)劃與網(wǎng)絡(luò)流 278

算法分析題8 278

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

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

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

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

8-5  運(yùn)輸計(jì)劃問題 279

8-6  單純形算法 280

8-7  邊連通度問題 281

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

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

8-10  最大流更新算法 282

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

8-12  單源最短路與最小費(fèi)用流 282

8-13  中國郵路問題 282

算法實(shí)現(xiàn)題8 283

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

8-2  太空飛行計(jì)劃問題 284

8-3  最小路徑覆蓋問題 285

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

8-5  圓桌問題 287

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

8-7  試題庫問題 290

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

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

8-10  餐巾計(jì)劃問題 298

8-11  航空路線問題 299

8-12  軟件補(bǔ)丁問題 300

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

8-14  孤島營救問題 302

8-15  汽車加油行駛問題 304

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

8-17  運(yùn)輸問題 311

8-18  分配工作問題 314

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

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

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

第9章  串與序列的算法 323

算法分析題9 323

9-1  簡單子串搜索算法最壞情況復(fù)雜性 323

9-2  后綴重疊問題 323

9-3  改進(jìn)前綴函數(shù) 323

9-4  確定所有匹配位置的KMP算法 324

9-5  特殊情況下簡單子串搜索算法的改進(jìn) 325

9-6  簡單子串搜索算法的平均性能 325

9-7  帶間隙字符的模式串搜索 326

9-8  串接的前綴函數(shù) 326

9-9  串的循環(huán)旋轉(zhuǎn) 327

9-10  失敗函數(shù)性質(zhì) 327

9-11  輸出函數(shù)性質(zhì) 328

9-12  后綴數(shù)組類 328

9-13  最長公共擴(kuò)展查詢 329

9-14  最長公共擴(kuò)展性質(zhì) 332

9-15  后綴數(shù)組性質(zhì) 333

9-16  后綴數(shù)組搜索 334

9-17  后綴數(shù)組快速搜索 335

算法實(shí)現(xiàn)題9 338

9-1  安全基因序列問題 338

9-2  最長重復(fù)子串問題 342

9-3  最長回文子串問題 343

9-4  相似基因序列性問題 344

9-5  計(jì)算機(jī)病毒問題 345

9-6  帶有子串包含約束的最長公共子序列問題 347

9-7  多子串排斥約束的最長公共子序列問題 349

參考文獻(xiàn) 351