一、考試要求：

 

本課程要求掌握數(shù)據(jù)結(jié)構(gòu)的基本理論知識，常用數(shù)據(jù)結(jié)構(gòu)及對應(yīng)的基本算法，以及數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)技能。內(nèi)容包括線性表、棧、隊列、樹、圖等常見結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對應(yīng)的常用基本算法，以及查找和排序的基本概念和常用算法。會做簡單的算法分析，包括算法的時間代價和空間代價。會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法。課程考試中既測試對基本知識、基本理論的掌握程度，又測試對基本知識與基本理論的靈活運用能力。

 

二、考試要點：

 

1.緒論

 

（1）數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語；

 

（2）算法描述的方法；

 

（3）邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算三方面的要領(lǐng)及相互關(guān)系；

 

（4）算法復雜度的分析方法。

 

2.線性表

 

（1）線性表的邏輯特性；

 

（2）兩類不同的存儲結(jié)構(gòu)（順序和鏈式存儲結(jié)構(gòu)）的異同；

 

（3）單鏈表、循環(huán)鏈表、雙向鏈表的特點；

 

（4）線性表在順序存儲結(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析；

 

（5）線性表在鏈式存儲結(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析；

 

（6）用時間和空間復雜度分析線性表的特點。

 

3.棧和隊列

 

（1）棧和隊列的基本概念；

 

（2）棧和隊列在存儲結(jié)構(gòu)上的基本運算的實現(xiàn)；

 

（3）循環(huán)隊列中對邊界條件的處理；

 

（4）棧的典型應(yīng)用并能編程實現(xiàn)。

 

4.串

 

（1）串的邏輯結(jié)構(gòu)定義；

 

（2）串的基本運算及其實現(xiàn)；

 

（3）串的堆分配存儲結(jié)構(gòu)；

 

（4）串的模式匹配算法。

 

5.數(shù)組和廣義表

 

（1）數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；

 

（2）數(shù)組在以行為主的存儲結(jié)構(gòu)中地址的計算方法；

 

（3）特殊矩陣的壓縮存儲方式及下標變換公式；

 

（4）稀疏矩陣壓縮存儲方法的特點和適用范圍，三元組表示的稀疏矩陣進行矩陣運算時采用的處理方法。

 

6.樹和二叉樹

 

（1）樹的定義和基本術(shù)語；

 

（2）二叉樹的定義；

 

（3）二叉樹的結(jié)構(gòu)特性及相應(yīng)的證明方法；

 

（4）二叉樹的各種存儲結(jié)構(gòu)特點及使用范圍；

 

（5）二叉樹的各種遍歷算法；

 

（6）線索二叉樹的定義；

 

（7）樹的存儲結(jié)構(gòu)；

 

（8）樹和二叉樹的轉(zhuǎn)換方法；

 

（9）最優(yōu)二叉樹的特性；

 

（10）建立最優(yōu)二叉樹和實現(xiàn)Huffman編碼的方法。

 

7.圖

 

（1）圖的基本概念；

 

（2）圖的兩種常用的存儲結(jié)構(gòu)特點及實現(xiàn)；

 

（3）圖的兩類遍歷算法：深度優(yōu)先、廣度優(yōu)先；

 

（4）圖的應(yīng)用：最小生成樹、最短路徑的算法實現(xiàn)。

 

8.查找

 

（1）靜態(tài)查找表和動態(tài)查找表的定義；

 

（2）順序查找、二分查找以及塊查找的基本思想和算法實現(xiàn)；

 

（3）二叉排序樹的概念及查找過程；

 

（4）哈希查找的基本思想、哈希函數(shù)的構(gòu)造方法、處理沖突的方法；

 

（5）各種算法的時間性能（平均查找長度）分析。

 

9.排序

 

（1）排序的基本概念、排序算法的穩(wěn)定性；

 

（2）冒泡排序、插入排序、選擇排序、快速排序、希爾排序和堆排序的基本思想、排序過程、算法實現(xiàn)、時間和空間性能的比較分析結(jié)論；

 

（3）歸并排序和基數(shù)排序的基本思想。

 

三、參考書目

 

《數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）》，嚴蔚敏、李冬梅、吳偉民，人民郵電出版社，2016年，ISBN：9787115379504

原文標題：重慶科技學院2023年碩士學位研究生招生考試初試自命題科目考試大綱