2019年西安电子科技大学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或AVL 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)顺序查找算法

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

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程序设计 第四版》 清华大学出版社