2021年碩士研究生考試復(fù)試 數(shù)據(jù)結(jié)構(gòu) 科目考試大綱

一、考查目標(biāo)

《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)中的一門重要的基礎(chǔ)理論課，該課程考核的內(nèi)容主要包括復(fù)雜度分析、鏈表、棧和隊列、遞歸、二叉樹、B-樹、圖、堆與優(yōu)先級隊列、排序、哈希方法等。通過本課程學(xué)習(xí)，理解計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，掌握各類數(shù)據(jù)結(jié)構(gòu)的靈活應(yīng)用，為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并掌握算法的時間復(fù)雜度和空間復(fù)雜度的簡要分析技術(shù)。

二、考核形式與試卷結(jié)構(gòu)

(一)試卷滿分及考試時間

滿分為100分，考試時間為2小時。

(二)答題方式

答題方式為閉卷、筆試。

(三)試卷內(nèi)容結(jié)構(gòu)

客觀題，包括選擇題、填空題、判斷題。主觀題，包括程序設(shè)計和代碼編寫題。

(四)試卷題型結(jié)構(gòu)

客觀題20%—30%分，程序設(shè)計和代碼編寫題占70%—80%分。

三、考查內(nèi)容及要求

(一)數(shù)據(jù)結(jié)構(gòu)和算法簡介

1. 數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念。

2. 各種算法描述方法和算法設(shè)計。

3. 算法的復(fù)雜度分析。

(二)線性結(jié)構(gòu)

1. 線性表的概念、定義、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

2. 掌握線性表的順序結(jié)構(gòu)及其各種基本運算。

3. 單鏈表、循環(huán)鏈表、雙向鏈表的存儲結(jié)構(gòu)及其各種基本運算，鏈表的應(yīng)用。

4. 棧的定義、表示、實現(xiàn)和應(yīng)用。

5. 遞歸的概念和遞歸的實現(xiàn)過程。

6. 隊列的定義以及順序和鏈?zhǔn)酱鎯�結(jié)構(gòu)的實現(xiàn)。

7. 串的基本概念及順序和鏈?zhǔn)酱鎯�結(jié)構(gòu)，串的各種基本運算，串的模式匹配算法。

8. 數(shù)組的順序存儲結(jié)構(gòu)。

9. 稀疏矩陣的三元組存儲結(jié)構(gòu)和基本運算，十字鏈表存儲結(jié)構(gòu)。

10. 廣義表的基本概念，廣義表的存儲結(jié)構(gòu)。

(三)樹結(jié)構(gòu)

1. 樹的基本概念及其存儲結(jié)構(gòu)。

2. 掌握二叉樹的定義、性質(zhì)以及各種存儲結(jié)構(gòu)和遍歷算法。

3. 線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法。

4. 哈夫曼樹的概念、存儲結(jié)構(gòu)和應(yīng)用。

(四)圖結(jié)構(gòu)

1. 圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)。

2. 十字鏈表，鄰接多重表等存儲結(jié)構(gòu)。

3. 掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。

4. 圖的連通性、最小生成樹的概念。

5. 求最小生成樹算法。

(五)查找

1. 查找的概念及其效率的評價方法。

2. 靜態(tài)查找表的概念，熟練掌握順序、折半和分塊查找算法。

3. 動態(tài)查找表和二叉排序樹的概念。

4. 平衡二叉樹的概念。

5. 哈希表的含義，掌握哈希函數(shù)的構(gòu)造和處理沖突的基本方法。

(六)排序

1. 插入類排序的算法：直接插入排序、希爾排序。

2. 交換類排序的算法：冒泡排序、快速排序。

3. 選擇類排序的算法：簡單選擇排序、堆排序。

4. 歸并排序、基數(shù)排序的思想，外排序的概念。

四、考試用具說明

考試時僅需要攜帶筆。

五、參考書目或參考資料

1. 《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社，2011。