美高梅mgm1888
硕士研究生入学考试课程《数据结构》考试大纲
科目代码：863
科目名称：数据结构
第一部分 考试说明
一、考试性质
数据结构是计算机各专业的专业基础课。考核目标是测试计算机科学与技术及相近各专业的本科毕业生对于该课程的知识掌握程度,以保证被录取者具有本学科基本的专业理论基础及程序设计能力,以利于计算机科学与技术及软件工程学科的导师择优选拔硕士研究生。
考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各种基本查找表的概念、特征及其查找方法；基本的内排序方法及其应用；用C语言(或C++)进行算法描述,并对算法进行分析。
三、评价目标
考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和解决实际问题的能力,注重考查算法和程序设计的能力。
具体要求见本考试大纲第二部分的“考查要点”。
四、考试形式与试卷结构
1.答卷方式:闭卷,笔试。
2.答题时间:180 分钟。
3.考查内容及其考查比例
基本概念、基本知识、基本方法约占50%～60%；综合应用、算法和程序设计与算法分析约占50%～40%。
4.试卷结构与考试题型
试卷共150分,基本的考试题型有：
(1)单项选择题和多项选择题；
(2)填空题(基本概念、基本知识、基本方法)；
(3)简答题；
(4)应用题(求解问题)；
(5)算法和程序设计与分析题；
五、教材和参考书
教材: 《数据结构》(C语言版)，严蔚敏、吴伟民编著,清华大学出版社,2009.6
第二部分 考查要点
1.数据结构基本概念和术语
了解数据元素、数据结构、抽象数据类型、存储结构等概念；算法概念及算法设计的基本要求 ；
掌握算法分析方法、语句的频度和估算时间复杂度、空间复杂度分析方法。
2.线性表
理解线性表的定义和基本操作；线性表的抽象数据类型定义；
掌握线性表的顺序存储结构及应用方法；
掌握线性表的链式存储结构(单链表,双链表,循环链表)。
3.栈和队列
理解栈的定义和基本操作及栈的抽象数据类型定义；
掌握顺序栈及链式栈的操作方法；
掌握栈在递归算法、算术表达式求值及其它应用;
理解队列的定义和基本操作及队列的抽象数据类型；
掌握顺序队列及链式队列的操作方法；应用举例。
4.字符串
理解字符串的定义和基本操作及字符串的存储结构；
掌握字符串的基本操作；
了解字符串模式匹配应用。
5.数组
理解数组的定义和基本操作；
掌握数组的顺序存储结构及应用；
掌握特殊矩阵和稀疏矩阵的压缩存储。
6.树和二叉树
理解树的基本概念和基本操作,树的抽象数据类型;
理解二叉树的概念和性质,特殊二叉树及二叉树的存储结构；
掌握二叉树的生成与建立 ;
掌握遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历;
掌握线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历;
理解树的存储结构；
掌握树与二叉树之间的转换,森林与二叉树之间的转换,森林的遍历方法;
掌握树的路径长度和带权路径长度；
理解哈夫曼树(Huffman)的概念,并掌握哈夫曼算法, 哈夫曼编码树。
7.图
理解图的基本概念和基本操作，图的抽象数据类型。
掌握图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表，十字链表；邻接多重表。
掌握图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。
理解生成树、最小生成树的概念，并掌握克鲁斯卡尔(Kruskal)算法,普里姆(Prim)
算法。
掌握从一个顶点到其余各顶点的最短路径,每对顶点之间的最短路径。
9.查找
理解查找的概念,关键字比较次数,平均查找长度。
掌握顺序表的查找:顺序查找,折半查找,分块查找方法。
掌握树表的查找:二叉排序树,二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现。平衡二叉树。
掌握哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找方法,冲突处理方法。
10.排序
理解排序的稳定性、比较关键字次数、移动记录次数、顺序表的排序、链接表(单链表)等排序概念。
掌握若干内排序方法与算法：
a)交换排序:冒泡排序,快速排序。
b)插入排序:直接插入排序,2路插入排序,折半插入排序,希尔排序。
c)选择排序:直接选择排序,堆排序。
d)归并排序。
e)基数排序。
掌握各种排序算法的评价，了解其应用。
美高梅mgm1888
硕士研究生入学考试课程《软件工程》考试大纲
科目代码：864
科目名称：软件工程
第一部分 考试说明
一、考试目的
《软件工程》是计算机各专业的核心课程。考核目的是测试软件工程及相近各专业的本科毕业生对于该课程的知识掌握程度,以保证被录取者具有本学科基本的专业理论基础及软件需求定义、设计、开发的工程化基本能力,并方便软件工程学科及相近学科的导师择优选拔硕士研究生。
考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
考试范围涵盖软件工程相关的基本概念、过程模型，以及利用结构化方法、面向对象方法对软件系统进行可行性分析、需求定义、设计、实现、测试、维护、质量保证的基本技能、方法及工具。
三、考试形式与试卷结构
1.答卷方式:闭卷,笔试。
2.答题时间:180 分钟。
3.考查内容及其考查比例
基本概念、基本知识、基本方法约占60%～70%；综合应用约占40%～30%。
4.试卷结构与考试题型
试卷共150分,基本的考试题型有：
(1) 名词解释；
(2) 简答题；
(3) 论述题；
(4) 综合设计应用题。
四、教材和参考书
教材: 《软件工程导论》(第5版)，张海藩编著,清华大学出版社,2008.2
第二部分 考查要点
1. 软件工程学基本概念和术语
掌握软件工程、软件特征、软件工程方法学的基本概念；
掌握软件过程瀑布模型、快速原型模型、增量模型、螺旋模型、喷泉模型、RUP模型，以及各个模型的优缺点与适应场合。
理解软件危机产生的原因，消除软件危机的途径，认知软件工程的基本原理；
了解软件工程所涉及的10个知识域，及软件工程所涉及的相关学科。
2. 可行性研究与分析
深入理解软件系统可行性分析的目的与任务，熟知应从哪些方面进行可行性研究与分析；
掌握数据流图（DFD）的基本符号、分层细化原则及数据字典的内容，并能运用数据流图与数据字典描述实际软件系统；
了解国标定义的软件系统可行性分析报告的写法与内容。
3. 需求分析
深入理解软件需求分析的重要性、任务，及软件需求应包含的内容；
掌握软件需求获取的方法，并能利用相应的模型、工具清晰地表述软件需求；
了解国标定义的软件系统需求规格说明书的写法与内容。
4. 总体（概要）设计与详细设计
深入理解软件总体设计、详细设计目的、任务；；
掌握软件设计的基本原理及衡量模块独立性的定性准则，并能运用面向数据流的方法实现软件系统数据流图到软件系统结构图的映射；
掌握人机界面设计所涉及的问题，及详细设计所使用的常用工具。
了解国标定义的软件系统设计说明书的写法与内容。
5. 软件系统的实现、测试与维护
深入理解程序设计语言选择的实际标准、编码风格，以及软件测试的目标；
理解静态测试、动态测试方法的概念与含义，掌握大型软件程序测试的步骤，及各个步骤的概念、内容和达到的目的；
掌握白盒测试技术逻辑覆盖的含义与方法和黑盒测试技术的含义与方法，并能运用这些方法设计相应的测试用例。
深入理解软件系统维护的定义、类型及含义，熟悉决定软件可维护性的因素。
6. 面向对象方法实现软件系统分析、设计与实现
深入理解面向对象方法的基本概念及优点；
掌握利用UML工具建立软件系统对象模型、动态模型和功能模型的方法；
掌握面向对象分析（OOA）、面向对象设计（OOD）基本过程与准则，理解OOA与OOD之间无缝过渡的含义，及面向对象分析的关键；
能运用面向对象方法分析、设计实际的软件系统。
7. 软件质量保证与配置管理
理解软件质量的概念及质量保证措施的含义；
掌握软件配置管理的含义、软件配置内容及软件配置管理的过程；
深入理解软件能力成熟度模型（CMM/CMMI）的目的、等级及每个等级的基本内涵。
