南京信息工程大學碩士研究生招生入學考試考試大綱

科目代碼：F18

科目名稱：數據結構

一、數據結構及相關基本概念

     1．了解什么是數據結構。

    2．理解數據結構有關的概念和術語：數據、數據元素、數據對象、數據結構、線性結構、樹形結構、圖結構、集合結構。

3．了解抽象數據類型的概念與表示。

4. 掌握算法及其分析：算法的定義，特性，時間復雜度，空間復雜度。

二、線性表  

    1．了解線性表的概念：定義，特點，線性表抽象數據類型定義。

    2．掌握線性表的順序表示與實現。

    3．掌握線性表的鏈接表示與實現。

   4．掌握線性表的應用。  

三、棧和隊列

     1．掌握棧的概念，特點，抽象數據類型棧的定義。

    2．掌握棧的順序表示和實現，棧的鏈接表示和實現。

3．掌握隊列的概念，特點，抽象數據類型隊列的定義。

4．掌握隊列的順序表示和實現，隊列的鏈接表示和實現。

5．掌握棧和隊列的應用。

四、串

    1．理解串類型的定義：串的定義，特點，串的抽象數據類型定義。

    2．掌握串的表示和實現。

3．掌握串的模式匹配。

4．了解串的應用。

五、數組和廣義表

1．掌握數組：定義，特點，數組元素存儲位置的計算。

2．掌握特殊矩陣的壓縮存儲及其運算。

    3．了解廣義表：定義，特點，存儲及運算。

 六、樹和二叉樹

    1．理解樹的定義及相關概念。

2．掌握二叉樹定義及性質。

3．掌握二叉樹的順序存儲結構合連接存儲結構。

4．掌握二叉樹的遍歷運算及其實現。

5．掌握線索二叉樹的概念和構造。

6．掌握哈夫曼樹和哈夫曼編碼。

7．掌握樹和森林的特點，樹的存儲結構，樹和森林的遍歷，樹和森林與二叉樹的轉換。

七、圖

     1．理解圖的定義及相關概念。

2．掌握圖的存儲結構：鄰接矩陣，鄰接表。

3．掌握圖的常用運算：圖的遍歷，無向圖的連通分量和生成樹，最小生成樹，有向無環圖及其應用、最短路徑。

八、查找 

1．理解查找的定義及相關概念。

2．掌握靜態查找表：順序表的查找，有序表的查找，索引順序表的查找。

3．掌握動態查找表：二叉排序樹，平衡二叉樹，B-樹。

4．掌握哈希表及其查找。

九、內部排序 

1．理解排序的定義及相關概念。

2．掌握常用的排序方法：直接插入排序，二分法插入排序，直接選擇排序，冒泡排序，希爾排序，快速排序，堆排序，歸并排序，基數排序等。

3．理解各類內部排序方法的特點：時間復雜度，空間復雜度，穩定性。

十、其他規定：考試方式為閉卷筆試，總分150分，考試時間為180分鐘。