2019年硕士研究生招生考试大纲 考试科目名称：软件工程学科专业基础 考试科目代码：893 一、考试要求 软件工程学科专业基础考试大纲适用于北京工业大学信息学部（0835）软 件工程学科的硕士研究生招生考试。考试内容包含数据结构与算法和 C 语言程 序设计部分，这两门课程是软件工程学科的重要基础理论课。数据结构与算法 考试内容主要包括数据结构的基本概念和术语、线性表、栈和队列、数组、串 和广义表、树和二叉树、集合与字典、搜索结构、图和内部排序。要求考生对 其中的基本概念有很深入的理解，掌握算法的设计及评价方法，具有综合运用 所学知识分析问题和解决问题的能力。C 语言程序设计的考试内容主要包括 C 语言基础、算法初步、数据组织、程序组织和应用程序设计五部分，要求考生 掌握 C 语言的基本语法、基本语句、基本控制结构以及程序设计的一般方法， 具有熟练使用 C 语言编程解决实际问题的能力。 二、考试内容 数据结构与算法部分： （一）数据结构的基本概念和术语 （1）掌握数据结构的基本概念和术语 （2）掌握数据结构的逻辑结构、存储结构 （3）熟练掌握抽象数据类型的表示方法 （4）熟练掌握算法的时间复杂度、空间复杂度的分析方法 （二）线性表 （1）掌握线性表的逻辑结构 （2）掌握线性表的顺序存储结构及插入删除、查找、遍历等操作的实现 （3）掌握线性表的链式存储结构及插入删除、查找、遍历等操作的实现 （三）栈和队列 （1）掌握栈的定义、栈的抽象数据类型及存贮表示 （2）熟练掌握栈操作的实现 （3）熟练掌握递归算法 （4）掌握队列的定义、队列的抽象数据类型及存贮表示 （5）熟练掌握队列操作的实现及应用 （四）数组、串和广义表 （1）理解数组的定义、存贮表示及应用 （2）理解串的定义、运算和存贮表示的特点 （3）掌握串运算的算法 （4）掌握广义表的定义、ADT、存贮表示 （5）掌握广义表的遍历算法 （五）树 （1）掌握树结构的概念、术语和 ADT （2）掌握二叉树的性质和存贮表示 （3）熟练掌握二叉树遍历算法及运用 （4）掌握二叉树线索化技术 （5）掌握树和森林的存贮表示、与二叉树的转化方法及树的遍历 （6）熟练掌握树的应用（Huffman 树） （六）集合与字典 （1）掌握集合的概念、术语、ADT 及操作的实现 （2）掌握字典的概念、术语、ADT 及操作的实现 （七）搜索结构 （1）熟练掌握静态查找技术 （2）熟练掌握动态查找技术 （3）掌握 B 树及链树的存贮表示与查找 （4）熟练掌握哈希表技术 （5）掌握查找技术的综合分析评价方法 （八）图 （1）掌握图的基本概念、术语和 ADT （2）掌握图的存贮方法 （3）熟练掌握图的 DFS 和 BFS 搜索算法及应用 （4）熟练掌握最短路径算法及应用 （5）熟练掌握拓扑排序算法及应用 （九）内部排序 （1）掌握排序的概念及术语 （2）熟练掌握插入排序、冒泡排序、选择排序、快速排序、归并排序、 堆排序及基数排序算法 （3）掌握排序方法的最好、最坏情况分析 C 语言程序设计部分： 1、C 语言基础，包括变量声明、控制结构和输入输出。 2、算法初步，包括流程图、穷举法、递推与迭代法。 3、数据组织，包括数组、字符串、结构体、指针、指针数组、文件和链表。 4、程序组织，包括标准函数、自定义函数、函数与数组、函数与指针、递 归算法与递归函数、变量作用域和生存期。 5、应用程序设计，基于上述数据组织和程序组织进行应用程序设计。 三、参考书目 1、殷人昆编著. 数据结构(用面向对象方法与 C+语言描述) (第 2 版). 清 华大学出版社，2012-09-01 2、严蔚敏等编著，数据结构(C 语言版)。清华大学出版社，2011 年 11 月 3、C 语言大学实用教程，苏小红等，电子工业出版社，2012 年出版 4、C 语言教程，Al Kelley 、Ira Pohl，机械工业出版社，2007 年出版