算法設計與分析習題解答

第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章 在線算法設計
參考文獻

21世紀是知識經濟的時代，是人才競爭的時代。隨著21世紀的到來，人類已步入信息社會，信息產業正成為全球經濟的主導產業。計算機科學與技術在信息產業中佔據了最重要的地位，這就對培養21世紀高素質創新型計算機專業人才提出了迫切的要求。

為了培養高素質創新型人才，必須建立高水平的教學計劃和課程體系。在20多年跟蹤分析ACM和IEEE計算機課程體系的基礎上，緊跟計算機科學與技術的發展潮流，及時制定並修正教學計劃和課程體系是尤其重要的。計算機科學與技術的發展對高水平人才的要求，需要我們從總體上優化課程結構，精煉教學內容，拓寬專業基礎，加強教學實踐，特別注重綜合素質的培養，形成“基礎課程精深，專業課程寬新”的格局。

為了適應計算機科學與技術學科發展和計算機教學計劃的需要，要采取多種措施鼓勵長期從事計算機教學和科技前沿研究的專家教授積極參與計算機專業教材的編著和更新，在教材中及時反映學科前沿的研究成果與發展趨勢，以高水平的科研促進教材建設。同時適當引進國外先進的原版教材。

為了提高教學質量，需要不斷改革教學方法與手段，倡導因材施教，強調知識的總結、梳理、推演和挖掘，通過加快教案的不斷更新，使學生掌握教材中未及時反映的學科發展新動向，進一步拓廣視野。教學與科研相結合是培養學生實踐能力的有效途徑。高水平的科研可以為教學提供最先進的高新技術平台和創造性的工作環境，使學生得以接觸最先進的計算機理論、技術和環境。高水平的科研還可以為高水平人才的素質教育提供良好的物質基礎。學生在課題研究中不但能了解科學研究的艱辛和科研工作者的奉獻精神，而且能燻陶和培養良好的科研作風，鍛煉和培養攻關能力和協作精神。

進入21世紀，我國高等教育進入了前所未有的大發展時期，時代的進步與發展對高等教育質量提出了更高、更新的要求。2001年8月，教育部頒發了《關于加強高等學校本科教學工作，提高教學質量的若干意見》。文件指出，本科教育是高等教育的主體和基礎，抓好本科教學是提高整個高等教育質量的重點和關鍵。隨著高等教育的普及和高等學校的擴招，在校大學本科計算機專業學生的人數將大量上升，對適合21世紀大學本科計算機科學與技術學科課程體系要求的，並且適合中國學生學習的計算機專業教材的需求量也將急劇增加。為此，中國計算機學會和清華大學出版社共同規劃了面向全國高等院校計算機專業本科生的“21世紀大學本科計算機專業系列教材”。本系列教材借鑒美國ACM和〔FEE最新制定的Computing Curricula 2005（簡稱CC2005）課程體系，反映當代計算機科學與技術學科水平和計算機科學技術的新發展、新技術，並且結合中國計算機教育改革成果和中國國情。

中國計算機學會教育專業委員會和全國高等學校計算機教育研究會，在清華大學出版社的大力支持下，跟蹤分析CC2001，並結合中國計算機科學與技術學科的發展現狀和計算機教育的改革成果，研究出了《中國計算機科學與技術學科教程2002》（China ComputingCurricula 2002，簡稱CCC2002），該項研究成果對中國高等學校計算機科學與技術學科教育的改革和發展具有重要的參考價值和積極的推動作用。

“21世紀大學本科計算機專業系列教材”正是借鑒美國ACM和IEEE CC2005課程體系，依據CCC2002基本要求組織編寫的計算機專業教材。相信通過這套教材的編寫和出版，能夠在內容和形式上顯著地提高我國計算機專業教材的整體水平，繼而提高我國大學本科計算機專業的教學質量，培養出符合時代發展要求的具有較強國際競爭力的高素質創新型計算機人才。