|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
1
902 數據結構與 C 語言程序設計考研大綱
一、考試內容
（一）數據結構
1.線性表
1）線性表的定義
2）線性表的順序存儲和基本運算（查找、插入和刪除）的實現
3）線性表的鏈式存儲和基本運算（查找、插入和刪除）的實現
4）線性表的應用
2.棧、隊列和矩陣
1）棧和隊列的定義
2）棧和隊列的實現
（1）棧的順序存儲和基本操作（入棧、出棧和判棧空、棧滿）的實現
（2）棧的鏈式存儲和基本操作（入棧、出棧和判?？眨┑膶崿F
（3）隊列的鏈式存儲和基本操作（入隊、出隊和判隊空）的實現
（4）循環隊列的定義和基本操作（入隊、出隊和判隊空、隊滿）的實現
3）棧和隊列的應用
4）矩陣的壓縮存儲
（1）特殊矩陣（對稱矩陣、三角矩陣、對角矩陣）的壓縮存儲
（2）稀疏矩陣的壓縮存儲
3.樹與二叉樹
1）樹的基本概念
2）二叉樹
（1）二叉樹的定義及性質
（2）二叉樹的順序存儲和鏈式存儲
（3）二叉樹的先序、中序、后序遍歷和層序遍歷運算
（4）線索二叉樹的定義
3）樹和森林
（1）樹的存儲結構
（2）樹（森林）與二叉樹的相互轉換
（3）樹和森林的遍歷
4）樹與二叉樹的應用
（1）二叉查找樹（Binary Search Tree）
（2）平衡二叉樹（Balanced Binary Tree 或 Height-Balanced Tree 或 AVL Tree）
（3）哈夫曼（Huffman）樹和哈夫曼編碼
4.圖
1）圖的基本概念
2）圖的存儲
（1）數組表示法（鄰接矩陣表示法）
（2）鄰接表表示法
2
3）圖的遍歷
（1）深度優先搜索（DFS）算法
（2）廣度優先搜索（BFS）算法
4）圖的應用
（1）最小（代價）生成樹求解方法（Prim 算法和 Kruskal 算法）
（2）最短路徑求解方法（Dijkstra 算法和 Floyd 算法）
（3）AOV-網和拓撲排序方法
（4）AOE-網和關鍵路徑求解方法
5.查找
1）查找的基本概念
2）順序查找法
（1）順序查找算法
（2）平均查找長度計算
3）折半查找法
（1）折半查找算法
（2）折半查找判定樹的構造
（3）平均查找長度計算
4）動態查找表
（1）二叉查找樹（也稱為二叉排序樹）的構造及查找、插入和刪除運算
（2）平衡二叉樹的構造及查找運算
（3）B-樹的特點及查找運算
（4）平均查找長度計算
5）哈希表
（1）哈希表的構造及查找運算
（2）平均查找長度計算
6）字符串的模式匹配
（1）基本的模式匹配算法
（2）KMP 模式匹配算法（模式串的 next 函數計算）
6.內部排序
1）簡單排序方法
（1）直接插入排序算法
（2）冒泡排序算法
（3）簡單選擇排序算法
（4）簡單排序算法的時間復雜度、空間復雜度及穩定性分析
2）快速排序
（1）劃分過程及分析
（2）快速排序算法及其時間復雜度、空間復雜度及穩定性分析
3）堆排序
（1）堆的定義及初始堆的建立
（2）堆排序算法及其時間復雜度、空間復雜度及穩定性分析
4）歸并排序
（1）歸并過程及分析
（2）二路歸并排序算法的時間復雜度、空間復雜度及穩定性分析
5）基數排序
3
（1）多關鍵排序方法
（2）鏈式基數排序方法及特點
6）內部排序方法的比較和應用
（二）C 語言程序設計
1. C 語言基礎
（1）數據類型（基本類型和復合類型），常量與變量，運算符與表達式，類型轉換；
（2）關鍵字（保留字），用戶定義標識符；
（3）typedef，sizeof，static，extern，const。
2. 預處理
（1）宏定義（#define）與宏替換；
（2）條件編譯：#if，#ifndef、#ifdef、#else、#elif、#endif。
3. 語句
if、switch、while、do-while、for、break、continue、return等語句的控制邏輯與應用。
4. 函數
（1）函數原型與函數聲明，標準庫函數的應用；
（2）函數的定義與聲明；
（3）函數調用，參數傳遞方式，遞歸調用。
5. 數組和結構體
（1）一維數組和二維數組的定義與初始化；
（2）字符數組的定義與初始化，字符數組與字符串，字符串運算函數；
（3）結構體類型的定義，結構體變量的定義和引用；
（4）數組與結構體的應用：數據集的表示與運算。
6. 指針
（1）指針的基本概念，指針變量與指針指向的變量；
（2）指針與數組：指向數組的指針變量的定義與運算，通過指針引用數組元素；
（3）指針與字符串，指向字符串的指針變量的定義與應用；
（4）指針與函數：函數參數為指針和數組，函數返回值為指針，函數指針；
（5）指針與動態內存：malloc、calloc、realloc、free等函數的應用；
（6）常量指針與指針常量。
7. 輸入輸出
（1）標準輸入輸出：scanf、printf、getchar、putchar等函數的應用；
（2）文件輸入輸出：FILE指針定義，文件打開方式，fopen、freopen、fclose、feof、fgetc、
fputc、fgets、fputs、fscanf、fprintf、fread、fwrite等函數的應用。
二、參考書目
1. 嚴蔚敏，吳偉民 編著 《數據結構（C 語言版）》 清華大學出版社
2. C 語言標準：ISO/IEC 9899:1999(E)，Programming Language—C （簡稱為 C99）
3. 譚浩強 著 《C 程序設計 第四版》 清華大學出版社
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
