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

《902数据结构与c语言程序设计考研大纲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、902数据结构与C语言程序设计考研大纲一、考试内容（一）数据结构1.线性表　　1）线性表的定义2）线性表的顺序存储和基本运算（查找、插入和删除）的实现3）线性表的链式存储和基本运算（查找、插入和删除）的实现4）线性表的应用2.栈、队列和矩阵　1）栈和队列的定义2）栈和队列的实现（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现（3）队列的链式存储和基本操作（入队、出队和判队空）的实现（4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现3）栈和队列的应用4）矩阵的压缩存储（1）特殊矩阵（对称矩阵、三角矩阵、对角

2、矩阵）的压缩存储（2）稀疏矩阵的压缩存储3.树与二叉树1）树的基本概念2）二叉树（1）二叉树的定义及性质（2）二叉树的顺序存储和链式存储（3）二叉树的先序、中序、后序遍历和层序遍历运算（4）线索二叉树的定义3）树和森林（1）树的存储结构（2）树（森林）与二叉树的相互转换（3）树和森林的遍历4）树与二叉树的应用（1）二叉查找树（BinarySearchTree）（2）平衡二叉树（BalancedBinaryTree或Height-BalancedTree或AVLTree）（3）哈夫曼（Huffman）树和哈夫曼编码4.图1）图的基本概念2）图的存储（1）数组表示法（邻接矩阵表示法）（2）邻

3、接表表示法33）图的遍历（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、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）

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.函数

6、（1）函数原型与函数声明，标准库函数的应用；（2）函数的定义与声明；（3）函数调用，参数传递方式，递归调用。5.数组和结构体（1）一维数组和二维数组的定义与初始化；（2）字符数组的定义与初始化，字符数组与字符串，字符串运算函数；（3）结构体类型的定义，结构体变量的定义和引用；（4）数组与结构体的应用：数据集的表示与运算。6.指针（1）指针的基本概念，指针变量与指针指向的变量；（2）指针与数组：指向数组的指针变量的定义与运算，通过指针引用数组元素；（3）指针与字符串，指向字符串的指针变量的定义与应用；（4）指针与函数：函数参数为指针和数组，函数返回值为指针，函数指针；（5）指针与动态内存：

7、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.严蔚敏