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

第1章 算法概述 算法分析題1 1-1 函數(shù)的漸近表達式 1-2 O(1)和O(2)的區(qū)別 1-3 按漸近階排列表達式 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 標準二維表問題 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 正則表達式匹配問題 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 裝載問題改進回溯法1 5-2 裝載問題改進回溯法2 5-3 0-1背包問題的最優(yōu)解 5-4 最大團問題的迭代回溯法 5-5 旅行售貨員問題的費用上界 5-6 旅行售貨員問題的上界函數(shù) 算法實現(xiàn)題5 5-1 子集和問題 5-2 最小長度電路板排列問題 5-3 最小重量機器設(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 團頂點數(shù)的上界 6-7 團頂點數(shù)改進的上界 6-8 修改解旅行售貨員問題的分支限界法 6-9 解旅行售貨員問題的分支限界法中保存已產(chǎn)生的排列樹 6-10 電路板排列問題的隊列式分支限界法 算法實現(xiàn)題6 6-1 最小長度電路板排列問題 6-2 最小權(quán)頂點覆蓋問題 6-3 無向圖的最大割問題 6-4 最小重量機器設(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)分布隨機變量 7-2 隨機抽樣算法 7-3 隨機產(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 集合隨機元素算法 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 機器人路徑規(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 負載平衡問題 8-20 最長k可重區(qū)間集問題 8-21 最長k可重線段集問題 參考文獻