2019年北京航空航天大学991“数据结构与C语言程序设计”考试大纲

　　2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。试卷满分为150分。

　　“数据结构”部分

　　一、概述

　　1．数据的逻辑结构与存储结构的基本概念；

　　2．算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

　　二、线性表

　　1．线性关系、线性表的定义，线性表的基本操作；

　　2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；

　　3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

　　三、数组

　　1．一维数组和二维数组的存储；

　　2．矩阵的压缩存储的基本概念；

　　3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。

　　四、堆栈与队列

　　1．堆栈与队列的基本概念与基本操作；

　　2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；

　　3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；

　　4．堆栈和队列在解决实际问题中应用。

　　五、树与二叉树

　　1．树与二叉树的基本概念，基本特征、名词术语；

　　2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；

　　3．二叉树的顺序存储结构与二叉链表存储结的基本原理；

　　4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用；

　　5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。

　　六、图

　　1．图的基本概念、名词术语；

　　2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；

　　3．图的深度优先搜索与广度优先搜索；

　　4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。

　　七、文件及查找

　　1．顺序查找法以及平均查找长度(ASL)的计算；

　　2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；

　　3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

　　八、内排序

　　1．排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算；

　　2．插入排序法(含折半插入排序法)；

　　3．选择排序法；

　　4．(起)泡排序法；

　　5．谢尔(Shell)排序法；

　　6．快速排序法；

　　7．堆积(Heap)排序法，包括堆积的定义与构造；

　　“C语言程序设计”部分

　　一、C语言基本知识

　　1．C语言的特点以及C语言程序的组成；

　　2．数据类型，包括整型、实型、字符型等常量与变量和变量的赋值；用typedef定义类型；

　　3．各种类型数据之间的混合运算；

　　4．算术表达式、关系表达式和逻辑表达式，表达式sizeof的含义。

　　二、基本语句

　　1．赋值语句（含条件赋值语句）、条件语句（含if、if-else、switch）、循环语句（含while、do-while、for语句，包括循环嵌套和break语句与continue语句）；

　　2．输入/输出语句，包括整型、实型、字符型（含字符串）等类型数据的格式输入函数scanf和格式输出函数printf。

　　三、数组

　　1．一维数组和二维数组的定义、引用与初始化；

　　2．字符数组的定义、引用与初始化，字符数组的输入与输出，字符串和字符串处理函数的应用。

　　四、函数

　　1．函数的定义，函数参数（形参和实参）与函数的返回值；

　　2．函数的调用，包括函数的嵌套调用和函数的递归调用；

　　3．命令行参数的基本概念，带参数的主函数的概念和应用。

　　五、指针

　　1．指针的基本概念，包括定义、使用、指针变量作为函数参数和函数返回值以及函数指针；

　　2．数组与指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数；

　　3．字符串与指针，指向字符串的指针变量。

　　六、预处理指令

　　1．预处理指令的基本概念，文件包含和条件包含预处理指令；

　　2．宏替换，带参数的宏。

　　七、结构体与共用体

　　1．结构体的基本概念和特点，结构体变量的初始化与引用，结构体指针的使用；

　　2．结构体数组，包括结构体数组的定义、初始化及应用；

　　3．共用体的基本概念，共用体变量的引用。

　　八、位运算

　　1．位运算和位运算符；

　　2．位运算的应用。

　　九、文件

　　1．文件的基本概念，包括文件类型指针FILE与文件的使用方式；

　　2．文件的打开函数fopen与关闭函数fclose；

　　3．文件的状态，包括feof函数和ferror函数；

　　4．文件的读/写，包括fread和fwrite函数、fputc和fgetc函数、fgets与fputs函数的应用；

　　5．文件的输入函数fscanf和输出函数fprintf的应用；

　　6．文件的定位，包括rewind函数和fseek函数以及ftell函数的应用。

　　参考用书：

　　1．《数据结构教程第3版》唐发根编著北京航空航天大学出版社2017

　　2．《C程序设计》谭浩强编著清华大学出版社(版次不限)