石家庄铁道学院《数据结构与C程序设计》考试大纲

《 数据结构 》考试大纲

主要参考书目：

《数据结构》 (C 语言版 ). 清华大学出版社 . 严蔚敏主编 .

《数据结构》 ( 第二版 ). 科学出版社 . 唐发根编著 .

一、绪论

1. 数据结构的基本概念，数据的逻辑结构、存储结构。

2. 抽象数据类型的定义、表示和实现。

3. 算法定义及算法的基本特性，算法分析的基本概念。

二、线性结构

1. 线性表的定义，线性表的基本操作，线性表的顺序存储结构和基本运算的实现，线性表的链式存储结构 ( 包括单链表、循环链表和双向链表 ) 和基本运算的实现，从时间和空间复杂度的角度综合比较线性表两种存储结构的特点及其适用场合。

2. 栈与队列的基本概念、基本操作，栈与队列的顺序存储结构、链式存储结构及实施插入、删除等基本操作对应的算法设计。

3 . 串的定义、存储表示和 基本操作，在定长顺序存储结构上实现串的基本操作算法。

4 . 数组的定义、顺序存储表示和基本运算的实现，特殊矩阵的压缩存储。

三、树与二叉树

1. 树与二叉树的基本概念，包括基本特征、基本操作。

2. 二叉树的基本性质、二叉树的二叉链表存储结构、二叉树的三种基本遍历算法 ( 前序、中序和后序 ) ；由二叉树的遍历序列恢复二叉树；二叉树遍历的应用。

3. 线索二叉树的建立和遍历，树和森林与二叉树的相互转换。

4. 最优二叉树 ( 哈夫曼树 ) 的特性，建立哈夫曼树和构造哈夫曼编码的方法

四、图

1. 图的定义，基本概念，图的分类。

2. 图的邻接矩阵存储方法、邻接表存储方法。

3. 图的深度优先和广度优先遍历算法。

4. 最小生成树 (Prim 算法和 Kruskal 算法 ) ，最短路径， AOV 网与拓扑排序。

五、查找

1. 顺序表和有序表的查找方法。

2. 二叉排序树的基本概念、建立和查找 ( 含算法 ) 。

3. 平衡二叉树的维护平衡的方法， B_- 和 B+ 树 。

4. 哈希查找和哈希表 。

六、内排序

1. 排序的基本概念，排序方法的分类。

2. 插入排序 ( 含折半插入排序 ) 、希尔排序、选择排序、归并排序、快速排序、堆排序。

3. 各种排序方法排序的特点及比较，各种排序算法的时空复杂度简单分析。

七、文件

数据文件的基本概念和基本术语，各类文件的特点、构造方法及其基本操作。

《 C 程序设计 》部分

主要参考书目

《 C 程序设计》 ( 第二版 ). 清华大学出版社 . 谭浩强编著 .

一、 C 语言概述

1. C 语言的历史、现状和特点。

2. C 语言的基本结构。

二、 基本数据类型与表达式

1. 数据类型，常量和变量，符号常量，变量的初始化。

2. 运算符和表达式。

三、简单的 C 程序设计

1. C 语句概述，程序的三种基本结构。

2. 赋值语句，数据输出，数据输入。

3. 逻辑运算和条件控制，关系运算符和关系表达式，逻辑运算符和逻辑表达式， IF 语句， SWITCH 语句。

四、循环语句

1. 循环结构程序设计概念， WHILE 语句， DO-WHILE 语句， FOR 语句， BREAK 语句和 CONTINUE 语句。

2. 循环的嵌套，几种循环的比较。

五、数组

1. 一维数组，二维数组。

2. 字符数组和字符串。

六、函数

1. 函数的定义，函数参数和函数的返回值，函数的一般调用，函数的嵌套调用，函数的递归调用，变量的作用域。

2. 数组作为函数参数，局部变量和全局变量，动态存储变量和静态存储变量，内部函数和外部函数。

3. 宏定义，文件包含处理，条件编译。

七、指针

1. 地址和指针的概念，指针变量和地址运算符。

2. 指针和数组，指针和字符串，指针和函数。

八、结构体与共用体

1. 结构和结构变量的定义，结构体类型变量的引用和初始化，结构体数组，指向结构体类型数据的指针，用指针处理链表。

2. 共用体的概念、引用方式及共用体类型数据的特点。

3. 枚举类型。

九、文件

1. C 文件概述，文件类型指针，文件的打开与关闭。

2. 文件的读写，文件的定位，出错检测。