2016年重慶交通大學數據結構考研大綱

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 重慶交通大學2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

重慶交通大學2016年全國碩士研究生招生考試

《數據結構》考試大綱

一、考試總體要求：

1、熟練掌握數據結構的基本概念，包括數據的邏輯結構、存儲結構和算法，掌握算法分析的基本概念，能進行算法復雜度的分析。

2、熟練掌握線性表的基本概念以及存儲結構的表示和實現，掌握在設定的存儲結構下各種類型線性表的算法設計。

3、熟練掌握棧和隊列的基本概念與性質，掌握在順序存儲和鏈式存儲結構下對棧和隊列的操作，以及利用棧與隊列解決實際問題的基本方法。

4、充分理解串的基本概念、熟練掌握串的存儲結構和相關的操作算法。

5、掌握數組、廣義表和稀疏矩陣的基本概念，存儲結構和基本操作的實現

6、充分理解樹型結構的基本概念,熟練掌握其邏輯特征，掌握樹的各種存儲結構的表示方法，能夠熟練地進行樹與二叉樹之間的轉換。

7、充分理解二叉樹的基本概念、性質；掌握樹的數組存儲表示和鏈表存儲表示；訓練掌握二叉樹的各種遍歷方法，以及各種遍歷的遞歸和非遞歸算法，掌握利用二叉樹的遍歷操作解決實際問題的方法。

8、充分理解線索二叉樹的基本概念，掌握其存儲結構的表示和實現，掌握線索二叉樹的建立和遍歷算法；掌握中序線索二叉樹的插入和刪除算法，掌握前序和后序線索化二叉排序樹的方法以及算法；掌握在中序線索二叉樹中查找某一結點的前趨和后繼結點的算法。

9、掌握堆的基本概念以及其操作。

10、充分理解樹的路徑長度的概念，熟練掌握Huffman樹的概念以及算法,了解Huffman編碼方法.

11、充分理解圖的基本概念以及其邏輯結構和特點，熟練掌握常用的兩種存儲方法（鄰接矩陣和鄰接表）以及在其存儲結構上的深度優先和廣度優先遍歷算法的設計，掌握圖的連通分量的算法思想。了解圖的其他存儲結構。掌握最小生成樹的Prim算法和Kruskal算法、掌握非負權值的圖的最短路徑概念、以及最常見的三種最短路徑的算法思想。掌握拓撲排序的算法思想以及其具體求解過程。

12、掌握數據文件的基本概念和數據文件的基本操作。

13、掌握散列表的概念以及散列方法、掌握散列函數的選擇(構造)原則、處理散列沖突的方法。

14、掌握查找或搜索的基本概念；掌握靜態查找表和動態查找表的概念；掌握線性查找的方法及其算法；掌握在有序線性表上進行折半查找的方法和算法。了解二叉搜索樹和AVL樹的概念。

15、充分了解各種排序方法的排序特點和排序過程，對于任意給出的數據元素序列，能夠熟練地采用指定排序方法進行排序，并且能夠對每一種排序方法排序過程中所進行的元素之間的比較次數、相應排序算法的時間、空間、排序的穩定性等性能進行分析。

★考試內容

1、數據結構概論

（1）數據結構的基本概念，數據的邏輯結構、存儲結構以及數據結構的分類。

（2）算法的定義、算法的性能分析以及算法的度量。

2、線性表

（1）線性表的定義以及線性表的基本操作。

（2）順序表的定義和特點；順序表上的各種操作算法實現以及其性能分析。

（3）順序表的應用。

（4）單鏈表的定義和各種算法實現以及其性能分析。

（5）單鏈表的應用。

3、棧與隊列

（1）棧與隊列的基本概念、基本性質。

（2）棧與隊列的順序存儲結構與鏈式存儲結構定義以及其操作和算法實現。

（3）棧與隊列的應用。

（4）遞歸的概念和遞歸工作棧。

（5）雙端隊列的概念以及其數組和鏈表表示。

4、串

（1）串的基本概念、串的基本操作和存儲結構。

（2）串的模式匹配算法和改進的KMP算法

5、數組和廣義表

（1）數組的概念、多維數組的實現。

（2）對稱矩陣和稀疏矩陣的壓縮存儲。

（3）廣義表的基本概念、表示和基本操作。

6、樹與二叉樹

（1）樹的定義和性質。

（2）二叉樹的概念、性質。

（3）二叉樹的存儲結構。

（4）二叉樹的遍歷及其應用。

（5）線索二叉樹。

（6）樹和森林。

（7）堆的概念（最大堆和最小堆）；堆的建立以及堆的插入和刪除算法。

（7）赫夫曼樹及其應用。

7、圖

（1）圖的定義，基本概念，圖的分類，常用名詞術語。

（2）圖的存儲結構。鄰接矩陣存儲表示和鄰接表存儲表示以及其算法實現。

（3）圖的遍歷操作概念以及其算法實現。

（4）最小生成樹，最短路徑，AOV網與拓撲排序。

8、文件及查找

（1）數據文件的基本概念和基本術語，數據文件的基本操作。

（2）順序文件、索引文件、散列(Hash)文件。

（3）靜態查找表和順序查找。

（4）基于有序表的折半查找以及其性能分析。

（5）散列表和散列方法；散列函數；處理散列沖突的基本方法。

（6）二叉搜索樹的概念；AVL樹的概念。

9、排序

（1）排序的基本概念，排序方法和分類。

（2）插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆排序法、歸并排序、基數排序。各種排序方法排序的原理、規律和特點，各種排序算法的時空復雜度分析。

二、考試形式與試卷結構

（一）考試形式

考試形式為筆試，考試時間為3小時，滿分為150分。

（二）試卷結構（題型）

1．單項選擇題和多項選擇題；

2．填空題(基本概念、基本知識、基本方法)；

3．簡答題；

4．應用題(求解問題)；

5．算法和程序設計填空題；

6．算法和程序設計與分析題；

7．其它題型。

三、主要參考書目

1、《數據結構》(第2版).殷人昆.清華大學出版社