2021年北京航空航天大学研究生入学考试自命题991考试大纲

991“数据结构与C语言程序设计”考试大纲（2021版）

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

“数据结构”部分

一、绪论

包括但不限于数据结构和算法的基本概念，主要内容有：数据的逻辑结构与存储结构的基本概念；算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

二、线性表

包括但不限于线性表的概念、各种存储结构、操作和应用，主要内容有：线性关系、线性表的定义，线性表的基本操作；线性表的顺序存储结构和操作的实现；线性链表及其操作；循环链表及其操作；双向链表及其操作；链表的应用。

三、数组

包括但不限于数组的存储结构和操作，主要内容有：．一维数组和二维数组的存储；矩阵的压缩存储的基本概念；对称矩阵、对角矩阵以及三角矩阵的压缩存储。

四、堆栈与队列

包括但不限于堆栈与队列的基本概念、操作和应用，主要内容有：堆栈与队列的基本概念与基本操作；堆栈与队列的顺序存储结构与链式存储结构的构造原理；在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；堆栈和队列在解决各类实际问题中应用。

五、树与二叉树

包括但不限于树的基本概念和操作，二叉树的基本概念、操作和应用，主要内容有：树与二叉树的基本概念、基本特征和名词术语；完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；二叉树的顺序存储结构与二叉链表存储结构的基本原理；二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法（包括递归和非递归算法）的设计与应用；线索二叉树的基本概念；二叉排序树的基本概念、建立(插入)、删除结点、查找以及平均查找长度（ASL）的计算；哈夫曼树的基本概念和简单应用。

六、图

包括但不限于图的基本概念和操作，主要内容有：图的基本概念、名词术语；图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；图的深度优先搜索与广度优先搜索，连通分量；最小（代价）生成树、最短路径、AOV网与拓扑排序、AOE网与关键路径的基本概念和算法原理。

七、文件及查找

包括但不限于文件及查找的基本概念、操作和应用，主要内容有：顺序查找法以及平均查找长度（ASL）的计算；折半查找法以及平均查找长度（ASL）的计算，包括查找过程对应的“判定树”的构造；B-树和B+树的基本概念；散列（Hash）表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

八、内排序

包括但不限于内排序的基本概念、各类算法实现原理和应用，主要内容有：排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算；插入排序法（含折半插入排序法）；选择排序法；泡排序法；谢尔（Shell）排序法；快速排序法；堆积（Heap）排序法；二路归并排序法。

“C语言程序设计”部分

一、C程序的基本结构

包括但不限于C语言程序的基本组成、编译运行过程等内容。

二、常量、变量和表达式

包括但不限于C语言常量、变量和表达式的基本概念和使用，主要内容有：常量：数字常量、字符常量和字符串字面量；变量：变量名和变量类型，变量的赋值和类型转换；算术表达式：算术运算符、增量（自增）和减量（自减）运算符、位运算和复合赋值运算符；强制类型转换；数据输入/输出函数；常量的符号表示方法：常量宏、枚举常量。

三、条件语句和开关语句

包括但不限于条件语句和开关语句的基本概念和使用，主要内容有：关系运算符和逻辑运算符；运算符的优先级；逻辑表达式；条件语句：条件、复合语句、条件语句的嵌套和级联、条件运算符和条件表达式；switch开关语句。

四、循环语句

包括但不限于循环语句的基本概念和使用，主要内容有：while语句、for语句和do while语句；循环语句的选择和使用；逗号表达式；循环语句的嵌套；循环中的非常规控制（break和continue）、goto语句。

五、函数

包括但不限于函数的基本概念和使用，主要内容有：函数的基本概念；函数的调用、结构和定义；函数的调用关系和返回值；局部变量、全局变量和静态变量；函数参数的传递；常见标准库函数的使用；递归函数。

六、数组

包括但不限于数组的基本概念和使用，主要内容有：一维数组：定义和初始化、复制、数组参数；字符串和字符数组；标准字符串函数；二维数组：定义、引用、访问、数组参数。

七、指针

包括但不限于指针的基本概念和使用，主要内容有：地址与指针；指针变量：定义和赋值、访问、参数和返回值；指针运算：指针与整数的加减、指针相减和比较、强制类型转换和void*指针、不合法的指针运算、指针类型与数组类型的差异；指针与数组；指向二维数组的指针、多重指针和指针数组；函数指针。

八、结构和联合

包括但不限于结构和联合的基本概念和使用，主要内容有：结构：结构类型的定义和访问、包含结构的结构；联合：联合类型的定义和访问；类型定义语句（typedef）；复杂类型的解读。

九、输入/输出和文件

包括但不限于输入/输出和文件的基本概念和使用，主要内容有：输入/输出的基本过程和文件类型；文件的打开、创建和关闭；文件数据的正文（文本）格式读写；读写操作中的定位；文件数据的二进制格式读写