2019 北航软件学院软件工程考研专业课991 考试大纲2019 年 “数据结构与 C 语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例 50%。试卷满分为 150 分。“数据结构”部分一、概述1数据的逻辑结构与存储结构的基本概念；2算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。二、线性表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 语言基本知识1C 语言的特点以及 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 函数的应用。