2018年中国海洋大学912数据结构和软件工程考研大纲

中国海洋大学
2018 年硕士研究生招生考试大纲
002 信息科学与工程学院
初试考试大纲
912 数据结构和软件工程
一、考试性质
数据结构和软件工程是软件工程学术学位硕士研究生入学
考试的专业基础课程。二、考察目标
数据结构部分要求考生能系统理解数据结构的基本概
念和基本原理，掌握与运用算法分析与设计的综合能力。本
考试旨在三个层次上考察考生对数据结构等知识掌握的程
度和运用能力。三个层次的基本要求分别为：
1、基础知识：对数据结构基本概念、基础知识掌握情
况的考核，该部分考核比例为 30%；
2、基本能力：用所学的数据结构的知识和方法求解某
些问题，给出正确的答案和问题，该部分考核比例为 40%；
3、算法分析与设计：对于给定的问题，能够运用所学
的知识进行综合分析，设计出求解问题的算法，并能对此算
法进行简单的时间和空间分析，该部分考核比例为 30%。
软件工程部分考核学生对软件工程的基本概念、原理和
方法的理解程度，对软件生存周期各阶段的任务、过程和工
具的掌握情况，综合运用专业知识进行软件分析、设计、实
现、维护的能力。考试题型：填空题或选择题（30%），简答
题（30%），综合分析题（40%）。
三、考试形式
本考试为闭卷、笔试考试，满分 150 分，考试时间 180
分钟，其中数据结构 90 分，软件工程 60 分。
四、考试内容
数据结构部分：
第 1 章 绪论
主要内容：掌握数据、数据类型、数据结构、算法等基
本概念，初步掌握算法分析的方法，理解有关描述算法所使
用的语言的说明等。
第 2 章 线性表
主要内容：线性表的定义及基本运算，掌握线性表的逻
辑结构和两种存储表示方法，以及定义在逻辑结构上的各种
基本运算在存储结构上如何实现，不同的链表（是否加头结
点、设尾指针、循环、单向、双向等）适用的场合。
第 3 章 栈和队列
主要内容：掌握栈和队列的定义、栈和队列的顺序表示
与实现，栈和队列的应用，能够熟练进行递归算法的设计。
第 5 章 数组和广义表
主要内容：掌握数组的定义，数组的顺序表示和实现，
稀疏矩阵的压缩存储及运算的实现，广义表的定义，广义表
的存储结构，熟悉广义表的递归算法。
第 6 章 树和二叉树
主要内容：掌握树的定义和基本术语，二叉树的定义、
性质、存储结构，遍历二叉树和线索二叉树，树的存储结构，
森林与二叉树的转换，树和森林的遍历，最优二叉树（赫夫
曼树），赫夫曼编码。理解树的递归定义及各种操作的递归
算法。
第 7 章 图
主要内容：掌握图的定义和术语，图的数组表示法、邻
接表等存储结构，掌握深度优先遍历和广度优先遍历，无向
图的连通分量和生成树，最小生成树，拓扑排序，关键路径，
最短路径等的求解过程。
第 9 章 查找
主要内容：掌握顺序表、有序表的查找算法，二叉排序
树的查找、插入及删除算法，平衡二叉树的建立过程，B-树
的查找、插入及删除过程，哈希表的构造方法，处理冲突的
方法，哈希表的查找及其分析。各种查找算法时间性能分析
与对比。
第 10 章 内部排序
主要内容：掌握直接插入排序，其他插入排序，希尔排
序，快速排序，简单选择排序，树形选择排序，堆排序，归
并排序，多关键字排序，链式基数等各种排序方法的基本思
想、排序过程，掌握各种排序方法的算法和空间性能分析及
各种排序方法的比较和选择。
软件工程部分：
1、软件工程基本概念
软件危机的概念、原因以及消除途径；软件工程的概念、
基本原理、方法学；软件生命周期，主要软件过程的特点。
2、可行性研究
可行性研究的任务、过程；用符号等表示系统的流程图
与数据流图；数据字典的内容、方法、用途以及实现过程；
成本/效益分析方法。
3、需求分析
需求分析的任务、要求以及获得需求的主要方法；实体
-联系图；状态转换图；层次方框图；IPO 图；验证软件需求
的方法
4、总体设计
总体设计的过程、原理、模块化、抽象、逐步求精等过
程；层次图和 HIPO 图、结构图；面向数据流的设计方法的
概念、变换分析、事务分析和设计优化，内聚和耦合。
5、详细设计
结构化程序设计；程序流程图、盒图、PAD 图、判定树、
判定表；面向数据结构的设计方法，Jackson 图及方法；程序
复杂程度的定量度量。
6、实现
编码风格；测试的定义和目标；单元测试；集成测试过
程及方法；白盒、黑盒测试技术；BRO 测试；条件测试，测
试用例设计。
7、维护
软件维护的定义、特点；主要的维护活动；软件再工程
过程。
8、面向对象方法学
面向对象方法学的要点、优点；面向对象的基本概念；
面向对象建模；对象模型；动态模型；功能模型以及三种模
型之间的关系。
9、面向对象分析设计
面向对象分析的概念与基本过程；确定类、对象、关联、
属性等建立对象模型；ＵＭＬ的基本概念，顺序图、用例图
等图形的作法；面向对象的设计。
10、软件项目管理
估算软件规模；开发工作量估算；开发时间、进度估算；
关键路径、机动时间；软件配置及管理过程；能力成熟度模
型。
五、是否需使用计算器
否。