算法設計與分析習題解答(第2版)（簡體書）

本書是清華大學出版社出版的普通高等教育“十一五”國家級規劃教材《算法設計與分析（第2版）》（主教材）配套的輔助教材，對《算法設計與分析（第2版）》一書中的全部習題做了詳盡的解答。本書的內容是對《算法設計與分析（第2版）》的較深入的擴展，許多在主教材中無法講述的、較深入的主題通過習題的形式展現出來。為了加強學生靈活運用算法設計策略解決實際問題的能力，本書將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能夠上機實現。作者的教學實踐反映出這類算法實現題的教學效果非常好。作者還結合國家精品課程建設，進行了教材的立體化開發，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。 本書內容豐富，觀點新穎，理論聯系實際。不僅可以用作高等學校計算機科學與技術學科各專業本科生和研究生學習計算機算法設計的輔助教材，而且也適合廣大工程技術人員和自學讀者學習參考。

王曉東，男，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價，基于計算機網絡和信息安全的大規模問題求解算法與數據結構，信息可視化技術，幾何計算，并行和分布式算法設計，計算復雜性理論。先后主持了與算法設計與分析有關的國家自然科學基金項目、國家優秀留學回國人員基金項目、福建省杰出人才基金項目和省自然科學基金項目等7個研究課題；獲得國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程算法與數據結構和算法設計與分析的課程建設，獲福建省教學成果一等獎。在國內外重要學術刊物上發表有創見性的論文50余篇；出版《算法設計與分析》等學術著作7部，在算法復雜性研究方面取得了一系列理論研究和應用成果。例如，在對著名的凸殼問題的計算復雜性研究成果中推廣了關于判定樹模型下問題的計算復雜性下界著名的Ben-Or定理，并應用于分析凸殼問題的計算復雜性，在較一般的情況下改進和完善了國際算法界知名學者Aggarwal，Steele和Yao等提出的關于凸殼問題計算復雜性下界的結果。研究成果得到國內外同行專家的好評并被國內權威刊物所引用。

第1章　算法引論
　習題1-1　實參交換
　習題1-2　方法頭簽名
　習題1-3　數組排序判定
　習題1-4　函數的漸近表達式
　習題1-5　O（1）和O（2）的區別
　習題1-7　按漸近階排列表達式
　習題1-8　算法效率
　習題1-9　硬件效率
　習題1-10　函數漸近階
　習題1-11　n！的階
　習題1-12　平均情況下的計算時間復雜性
　算法實現題1-1　統計數字問題
　算法實現題1-2　字典序問題
　算法實現題1-3　最多約數問題
　算法實現題1-4　金幣陣列問題
　算法實現題1-5　最大間隙問題
第2章　遞歸與分治策略
　習題2-1　Hanoi塔問題的非遞歸算法
　習題2-2　7個二分搜索算法
　習題2-3　改寫二分搜索算法
　習題2-4　大整數乘法的O（n1Og（3/2））算法
　習題2-5　5次7//3位整數的乘法
　習題2-6　矩陣乘法
　習題2-7　多項式乘積
　習題2-8　不動點問題的O（1O9n）時間算法．
　習題2-9　主元素問題的線性時間算法
　習題2-10　無序集主元素問題的線性時間算法
　習題2-11　O（1）空間子數組換位算法
　習題2-12　O（1）空間合并算法
　習題2-13　n段合并排序算法
　習題2-14　自然合并排序算法
　習題2-15　最大值和最小值問題的最優算法
　習題2-16　最大值和次大值問題的最優算法
　習題2-17　整數集合排序
　習題2-18　第k小元素問題的計算時間下界”
　習題2-19　非增序快速排序算法
　習題2-20　隨機化算法
　習題2-21　隨機化快速排序算法
　習題2-22　隨機排列算法”
　習題2-23　算法qSort中的尾遞歸
　習題2-24　用棧模擬遞歸
　習題2-25　算法se1ect中的元素劃分
　習題2-26　O（nlogn）時間快速排序算法
　習題2-27　最接近中位數的k個數
　習題2-28　X和y的中位數
　習題2-29　網絡開關設計
　習題2-32　帶權中位數問題
　習題2-34　構造Gray碼的分治算法
　習題2-35　網球循環賽日程表
　算法實現題2-1　輸油管道問題（習題2-3O）
　算法實現題2-2　眾數問題（習題2-31）
　算法實現題2-3　郵局選址問題（習題2-32）
　算法實現題2-4　馬的Hami1tOn周游路線問題（習題2-33）
　算法實現題2-5　半數集問題
　算法實現題2-6　半數單集問題
　算法實現題2-7　士兵站隊問題
　算法實現題2-8　有重復元素的排列問題
　算法實現題2-9　排列的字典序問題
　……
第3章　動態規劃
第4章　貪心算法
第5章　回溯法
第6章　分支限界法
第7章　概率算法
第8章　NP完全性理論
第9章　近似算法
第10章　算法優化策略
第11章　在線算法設計
參考文獻