902数据结构与C语言程序设计考研大纲

个人资料整理，仅供个人学习使用

902 数据结构与C语言程序设计考研大纲

一、考试内容

（一）数据结构

1.线性表

1）线性表的定义

2）线性表的顺序存储和基本运算（查找、插入和删除）的实现

3）线性表的链式存储和基本运算（查找、插入和删除）的实现

4）线性表的应用

2.栈、队列和矩阵

1）栈和队列的定义

2）栈和队列的实现

（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现

（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现

（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或A VL Tree）（3）哈夫曼（Huffman）树和哈夫曼编码

4.图

1）图的基本概念2）图的存储

（1）数组表示法（邻接矩阵表示法）

（2）邻接表表示法

3）图的遍历（1）深度优先搜索（DFS）算法

（2）广度优先搜索（BFS）算法

4）图的应用

（1）最小（代价）生成树求解方法（Prim算法和Kruskal算法）（2）最短路径求解方法（Dijkstra算法和Floyd算法）（3）AOV-网和拓扑排序方法（4）AOE-网和关键路径求解方法

5.查找

1）查找的基本概念2）顺序查找法

1 / 3

个人资料整理，仅供个人学习使用

（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）基数排序

（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）函数调用，参数传递方式，递归调用。

2 / 3