數據結構精講與習題詳解：考研輔導與答疑解惑（簡體書）

《清華大學計算機系列教材．數據結構精講與習題詳解：考研輔導與答疑解惑》是清華大學出版社出版的《數據結構（C語言描述）》的配套教材。它不但彙集了“數據結構”課程常用習題的解析，還對教學中反映出來的許多學生不易通過自學理解的概念和知識做了講解，並針對學習“數據結構”課程給出了一些指導性建議和考試的樣例。本書緊扣全國碩士研究生計算機專業統考的考試大綱，對“數據結構”的主要知識點做了歸納，對358處疑難點做了點撥，按照考試大綱規定的題型，對417道選擇題和426道綜合應用題做了解答和分析，最後給出了2009-2012年計算機專業統考的真題和答案。實際上總題量超過1250題。
《清華大學計算機系列教材．數據結構精講與習題詳解：考研輔導與答疑解惑》可以作為大學本科計算機科學與技術、軟件工程和信息管理等專業的輔助教材，更適合作為考研複習的有效參考書，還可以作為廣大數據結構學習者的工具書。．

殷人昆，清華大學計算機系教授，1985年赴日本國東京理科大學做訪問學者，研究方向為軟件工程過程的質量管理和軟件產晶的質量評價。主要教學工作為計算機系大學本科“數據結構”、“軟件工程”和研究生“軟件工程設計與技術”、“軟件項目管理”課程負責人，主持教育部-微軟精品課程“數據結構”的建設。曾與人合作或單獨編寫和出版教材20餘部，其中，《數據結構》教材被評為教育部普通高等教育“十一五”國家級規劃教材，並於2005年獲“北京市糟品教材”。曾在核心刊物和專業會議發表論文多篇，並參加或主持多項科研項目。．

《清華大學計算機系列教材?數據結構精講與習題詳解:考研輔導與答疑解惑》是清華大學出版社出版的《數據結構（C語言描述）》的配套教材。它不但匯集了“數據結構”課程常用習題的解析，還對教學中反映出來的許多學生不易通過自學理解的概念和知識做了講解，并針對學習“數據結構”課程給出了一些指導性建議和考試的樣例。《清華大學計算機系列教材?數據結構精講與習題詳解:考研輔導與答疑解惑》可以作為大學本科計算機科學與技術、軟件工程和信息管理等專業的輔助教材，更適合作為考研復習的有效參考書，還可以作為廣大數據結構學習者的工具書。

第1章 數據結構緒論
1.1 數據結構的概念及分類
1.1.1 知識點複習
1.1.2 疑難點辨析
1.1.3 選擇題解析
1.1.4 應用題選講
1.2 算法和算法設計
1.2.1 知識點複習
1.2.2 疑難點辨析
1.2.3 選擇題解析
1.2.4 應用題選講
1.3 算法分析
1.3.1 知識點複習
1.3.2 疑難點辨析
1.3.3 選擇題解析
1.3.4 應用題選講

第2章 線性表
2.1 線性表
2.1.1 知識點複習
2.1.2 疑難點辨析
2.1.3 選擇題解析
2.1.4 應用題選講
2.2 順序表
2.2.1 知識點複習
2.2.2 疑難點辨析
2.2.3 選擇題解析
2.2.4 應用題選講
2.3 單鏈表
2.3.1 知識點複習
2.3.2 疑難點辨析
2.3.3 選擇題解析
2.3.4 應用題選講
2.4 線性鏈表的其他變形
2.4.1 知識點複習
2.4.2 疑難點辨析
2.4.3 選擇題解析
2.4.4 應用題選講
2.5 線性表的應用
2.5.1 知識點複習
2.5.2 疑難點辨析
2.5.3 選擇題解析
2.5.4 應用題選講

第3章 棧和隊列
3.1 棧
3.1.1 知識點複習
3.1.2 疑難點辨析
3.1.3 選擇題解析
3.1.4 應用題選講
3.2 隊列
3.2.1 知識點複習
3.2.2 疑難點辨析
3.2.3 選擇題解析
3.2.4 應用題選講
3.3 棧的應用
3.3.1 知識點複習
3.3.2 疑難點辨析
3.3.3 選擇題解析
3.3.4 應用題選講
3.4 隊列的應用
3.4.1 知識點複習
3.4.2 疑難點辨析
3.4.3 選擇題解析
3.4.4 應用題選講
3.5 在算法設計中使用遞歸
3.5.1 知識點複習
3.5.2 疑難點辨析
3.5.3 選擇題解析
3.5.4 應用題選講
3.6 雙端隊列
3.6.1 知識點複習
3.6.2 疑難點辨析
3.6.3 選擇題解析
3.6.4 應用題選講
……
第4章 多維數組、字符串與廣義表
第5章 樹與二叉樹
第6章 樹與二叉樹的應用
第7章 圖
第8章 查找
第9章 排序
第10章 外排序
附錄 全國碩士研究生入學考試“數據結構”真題分析
參考書目．

（3）如果在關鍵路徑上的任一關鍵活動出現時間延誤，則會使整個工程產生時間延誤。然而，如果同時存在幾條關鍵路徑，任一關鍵活動加速，不一定能加速整個工程的進度。只有“橋”（即某一處于所有關鍵路徑上的關鍵活動）的情況例外。
7.6.2 疑難點辨析
1.什么是拓撲排序？它是針對何種結構的？
（辨析）把一個偏序（有向）圖轉換為全序圖的過程叫做拓撲排序。排序結果把圖的所有頂點排在一個拓撲有序的序列中。該序列不但保留了原偏序圖中所有頂點的優先關系，而且給原先沒有關系的頂點之間也賦予了優先關系。
拓撲排序針對的是AOV網絡（工程計劃網絡）。
2.可以對一個有向圖的所有頂點重新編號，把所有表示邊的非零元素集中到鄰接矩陣的上三角部分。根據什么順序進行頂點的編號？
（辨析）首先對該有向圖做拓撲排序，把所有頂點排在一個拓撲有序的序列中。然后按該序列對所有頂點重新編號，使得每條有向邊的始頂點號小于終頂點號，就可把所有邊集中到鄰接矩陣的上三角部分。
3.拓撲排序的一個重要應用是判斷有向圖中是否有環。如何判斷？
（辨析）每次尋找一個入度為0的頂點，輸出它并把所有它發出的邊刪去，作為這些邊的終頂點的入度減1，如此重復，找到所有的頂點全部輸出，說明圖中沒有環；如果過程中還有頂點未輸出，但沒有入度為0的頂點了，說明圖中有環。
4.如果調用深度優先搜索算法，在每次遞歸結束并退出時輸出頂點，就可得到一個逆拓撲有序的序列。此方法有效性的前提是什么？
（辨析）前提是確保圖中無環。深度優先搜索算法在向前遍歷時沒有考慮選擇入度為0的頂點，所以圖中有環它也能向前遍歷，但得到的結果不能滿足要求。