數據結構教程(第4版)學習指導（簡體書）

《高等學校數據結構課程系列教材：數據結構教程學習指導（第4版）》是與《數據結構教程》（第4版）（李春葆等編著，清華大學出版社出版）配套的學習輔導書。兩書章次一一對應，內容包括緒論、線性表、棧和隊列、串、遞歸、數組和廣義表、樹形結構、圖、查找、內排序、外排序和文件。各章中除給出本章練習題的參考答案外，還總結了本章的知識體系結構，並補充了大量的練習題並予以解析。附錄中給出了幾份近年來本科生、研究生數據結構考試試題及參考答案。書中列出了全部的練習題，因此自成一體，可以脫離主教材單獨使用。
《高等學校數據結構課程系列教材：數據結構教程學習指導（第4版）》適合高等院校計算機及相關專業本科生及研究生使用。

李春葆，武漢大學計算機學院教授，主要研究方向為數據挖掘和算法設計，先後主持和參加多個大型研究項目。主要為本科生講授數據結構（15年以上）和軟件工程等課程，為研究生講授軟件開發新技術、數據倉庫與數據挖掘等課程，並出版十多部精品著作。

《"十二五"普通高等教育本科國家級規劃教材?高等學校數據結構課程系列教材:數據結構教程(第4版)學習指導》適合高等院校計算機及相關專業本科生及研究生使用。

第1章緒論
1．1本章知識體系結構
1．2教材中練習題及參考答案
1．3補充練習題及參考答案
1．3．1單項選擇題
1．3．2填空題
1．3．3判斷題
1．3．4簡答題
1．3．5算法設計及算法分析題

第2章線性表
2．1本章知識體系結構
2．2教材中練習題及參考答案
2．3補充練習題及參考答案
2．3．1單項選擇題
2．3．2填空題
2．3．3判斷題
2．3．4簡答題
2．3．5算法設計題

第3章棧和隊列
3．1本章知識體系結構
3．2教材中練習題及參考答案
3．3補充練習題及參考答案
3．3．1單項選擇題
3．3．2填空題
3．3．3判斷題
3．3．4簡答題
3．3．5算法設計題

第4章串
4．1本章知識體系結構
4．2教材中練習題及參考答案
4．3補充練習題及參考答案
4．3．1單項選擇題
4．3．2填空題
4．3．3判斷題
4．3．4簡答題
4．3．5算法設計題

第5章遞歸
5．1本章知識體系結構
5．2教材中練習題及參考答案
5．3補充練習題及參考答案
5．3．1單項選擇題
5．3．2填空題
5．3．3判斷題
5．3．4簡答題
5．3．5算法設計題

第6章數組和廣義表
6．1本章知識體系結構
6．2教材中練習題及參考答案
6．3補充練習題及參考答案
6．3．1單項選擇題
6．3．2填空題
6．3．3判斷題
6．3．4簡答題
6．3．5算法設計題

第7章樹形結構
7．1本章知識體系結構
7．2教材中練習題及參考答案
7．3補充練習題及參考答案
7．3．1單項選擇題
7．3．2填空題
……

第8章圖
第9章查找
第10章內排序
第11章外排序
第12章文件
附錄A四份本科生數據結構期末考試試題及參考答案
附錄B三份數據結構考研試題及參考答案
附錄C2009年全國計算機專業碩士學位研究生入學考試數據結構部分試題及參考答案
附錄D2010年全國計算機專業碩士學位研究生入學考試數據結構部分試題及參考答案
附錄E2011年全國計算機專業碩士學位研究生入學考試數據結構部分試題及參考答案

2.3.3判斷題
1.判斷以下敘述的正確性。
（1）分配給單鏈表的內存單元地址必須是連續的。
（2）與順序表相比，在鏈表中順序訪問所有節點，其算法的效率比較低。
（3）從長度為n的順序表中刪除任何一個元素，時間復雜度都是O（n）。
（4）向順序表中插入一個元素，平均要移動大約一半的元素。
（5）凡是為空的單鏈表都是不含任何節點的。
（6）如果單鏈表帶有頭節點，則插入操作永遠不會改變頭節點指針的值。
（7）在循環單鏈表中，任何一個節點的指針域都不可能為空。
答：（1）錯誤。分配給單鏈表的內存單元地址可以是不連續的。
（2）錯誤。在順序表和鏈表上順序訪問所有節點，時間復雜度均為O（n）。
（3）錯誤。刪除最后一個元素所需時間是O（1）。但從長度為n的順序表中刪除任一個元素，平均時間復雜度是O（n）。
（4）正確。
（5）錯誤。帶頭節點單鏈表為空時仍有一個頭節點。
（6）正確。
（7）正確。
2.判斷以下敘述的正確性。
（1）順序存儲方式的特點是存儲密度大且插入、刪除運算效率高。
（2）線性表的順序存儲結構優于鏈式存儲結構。
（3）順序存儲結構屬于靜態結構而鏈式存儲結構屬于動態結構。
（4）由于順序存儲結構要求連續的存儲區域，所以在存儲管理上不夠靈活。
（5）對于單鏈表來說，只有從頭節點開始才能掃描表中全部節點。
（6）對于循環單鏈表來說，從表中任一節點出發都能掃描整個鏈表。
（7）雙鏈表的特點是很容易找任一節點的前驅和后繼。
答：（1）錯誤。順序存儲方式的特點是存儲密度大，但插入、刪除運算效率低。
（2）錯誤。順序和鏈式存儲結構各有優缺點。
（3）正確。
（4）正確。
（5）正確。
（6）正確。
（7）正確。
2.3.4 簡答題
1.線性表有兩種存儲結構：一是順序表，二是鏈表，試問：
（1）如果有多個線性表同時共存，并且在處理過程中各表的長度會動態地發生變化，線性表的總數也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？
（2）若線性表的總數基本穩定且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，那么應采用哪種存取結構？為什么？
答：（1）應選用鏈式存儲結構。由于鏈式存儲結構可以用任意的存儲空間來存儲線性表中的各數據元素，且其存儲空間可以是連續的，也可以不連續；此外，這種存儲結構對元素進行插入和刪除操作時都無須移動元素，修改指針即可，所以很適用于線性表容量變化的情況，這種動態存儲結構適合于多個線性表同時共存。
（2）應選用順序存儲結構。由于順序存儲結構一旦確定了起始位置，線性表中的任何一個元素都可以進行隨機存取，即存取速度較高；并且由于線性表的總數基本穩定且很少進行插入和刪除操作，所以恰好避開了順序存儲結構的缺陷。
2.在線性表的如下鏈式存儲結構中，若未知鏈表頭節點的地址，僅已知P指針指向的節點，能否從中刪除該節點？為什么？