［華南理工大學］2006年博士生數據結構考試大綱_跨考網

［華南理工大學］2006年博士生數據結構考試大綱

　　考試科目代碼：205

　　適用招生專業(yè)：機械制造及其自動化

　　特別提示：

　　數據結構課程是一門實踐性強的課程，需要進行大量的練習，數據結構課程的習題類型一般分為三類：一類是概念題，常見的形式包括是非判斷題、簡答題、選擇題（單選或多選）與填空題幾種；另一類是算法題，包括算法設計與算法填空兩種形式；還有一類介于這兩類題型之間，稱為綜合題或者問題求解題，這類題概念性一般不強，也不是寫算法，可能是一種方法的具體應用，希望在復習中，多做一些相關的習題。

　　一、考試內容

　　1.數據結構的基本概念和術語

　　2.線性表

　　應掌握有關線性表地基本概念，了解線性表地基本操作有哪些；還要掌握線性表地順序存儲結構與鏈式存儲結構地構造原理和特點，在這兩種存儲結構上對線性表實施的一系列操作所對應的算法設計的原理和方法，如線性鏈表、循環(huán)鏈表與雙向鏈表的插入、刪除算法的設計等。

　　3.數組

　　在程序設計語言中，通常將數組定義為具有相同類型的數組元素的集合，數組的基本操作有存、取、修改、查找和排序等。掌握常用操作的算法設計。

　　4.堆棧與隊列

　　堆棧與隊列是計算機領域非常重要的數據結構，從邏輯上看，堆棧與隊列都是線性結構，掌握堆棧與隊列的基本概念、常用操作的算法設計等。

　　5.廣義表

　　廣義表的基本概念，廣義表的存儲結構，常用操作的算法設計等

　　6.串

　　字符串的基本概念、字符串的基本操作及其存儲結構等。會設計字符串的基本操作的算法。

　　7.樹與二叉樹

　　了解樹型結構的基本概念，掌握其名詞術語，如：結點的度、樹的度、葉結點、分支結點、樹的層次、樹的深度、樹林、樹的有序性等。掌握二叉樹的定義、類型、性質；二叉樹的存儲結構、二叉樹的遍歷；二叉排序樹的定義、建立、刪除、查找等。了解Huffman樹的概念。

　　8.圖

　　圖是非線性結構中比樹結構還要復雜的結構，掌握圖的定義、名詞術語，如：頂點的度、路徑、子圖、圖的連通、生成樹與最小生成樹等；掌握圖的存儲結構、基本操作及其一些算法的設計。

　　9.文件與查找

　　這里所涉及的文件是指命名的、具有相同性質的數據記錄組成的集合。掌握數據文件的名詞術語、文件的邏輯結構、物理結構及基本操作；掌握順序文件的基本概念、連續(xù)順序文件的順序查找法、排序連續(xù)順序文件的折半查找方法、鏈接順序文件的查找方法；索引文件、B－樹與B＋樹的定義和查找等；了解散列文件。

　　10.內排序

　　排序是一種十分基本和重要的操作，了解排序的基本概念，掌握各種內排序方法，會設計內排序的算法。

　　二、考試題型（分值，按100分計）

　　1、判斷題或選擇題（單選或多選）（20分）

　　2、簡答題（15分）

　　3、算法設計或算法填空（25分）

　　4、綜合題或者問題求解題（40分）

　　三、建議參考書（任選一本）

　　[1]《數據結構（C語言版）》，嚴蔚敏主編，清華大學出版社

　　[2]《數據結構題集（C語言版）》，嚴蔚敏，吳偉民編著，清華大學出版社

　　也可選其他相關的參考書。