上海理工大学2020年数据结构及软件工程考研初试考试大纲.docx

新祥旭考研官网 http:/www.xxxedu.net/上海理工大学 2020 年数据结构及软件工程考研初试考试大纲考试科目：869 数据结构及软件工程第一部分：数据结构一、参考书目数据结构（C 语言版），严蔚敏等主编，清华大学出版社，2012 年二、 考试内容要求1、了解数据结构及其分类、数据结构与算法的密切关系。2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。4、掌握数据结构在排序和查找等常用算法中的应用。5、初步掌握文件组织方法和索引技术。三、考试内容1、 数据结构基本概念及简单的算法分析 1)什么是数据结构2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言3) 数据结构的抽象层次4) 算法定义5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.2、 数组1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例3) 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配3、链表 1) 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表2) 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法3) 双向链表 4、栈和队列 1) 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示2) 队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3) 队列的应用举例4) 优先级队列：优先级队列的定义；优先级队列的存储表示5、递归 1) 递归的概念2) 迷宫问题3) 递归过程与递归工作栈新祥旭考研官网 http:/www.xxxedu.net/4) 利用栈实现的迷宫问题非递归解法5) 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广 6) 义表的访问算法；广义表的递归算法 6、树与森林1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3) 二叉树的表示：数组表示；链表存储表示4) 二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二 叉树遍历的游标类；不用栈的二叉树中序遍历算法5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 堆：堆的定义；堆的建立；堆的插入与删除7) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历二叉树的计数8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码7、集合与搜索 1) 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型2) 等价类：等价关系与等价类；确定等价类的链表方法；并查集3) 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索4) 二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除；与二叉搜索树相关的中序游标类5) AVI 树：AVI 树的定义；平衡化旋转；AVI 树的插入和删除；AVI 树的高度8、 图 1) 图的基本概念：图的基本概念；图的抽象数据类型2) 图的存储表示：邻接矩阵；邻接表；邻接多重表3) 图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量4) 最小生成树：克鲁斯卡尔算法；普里姆算法5) 活动网络：用顶点表示活动的网络；用边表示活动的网络9、排序 1) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序2) 交换排序：起泡排序；快速排序3) 选择排序：直接选择排序；锦标赛排序；堆排序4) 归并排序：归并；迭代的归并排序算法；递归的表归并排序5) 基数排序：多关键码排序；链式基数排序6) 外排序：外排序的基本过程；k 路平衡归并；初始归并段的生成；最佳归并树10、索引与散列结构 1) 静态索引结构：线性索引；倒排表；m 路静态查找树2) 动态索引结构：动态的 m 路查找树；b_树；b_树的插入；b_树的删除；b+树3) 散列：词典的抽象数据类型；散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析第二部分：软件工程一、参考书目新祥旭考研官网 http:/www.xxxedu.net/张海藩，牟永敏 著，软件工程导论（第 6 版），清华大学出版社，2013 年二、考试内容范围掌握软件工程的基本概念、基本原理和基本方法；掌握可行性研究、需求分析、软件设计、软件测试、维护和演化、软件过程和管理等方面的基础知识，建立软件开发的系统化和工程化的概念和质量意识，能够综合利用软件工程的方法与技术。1、软件工程概述1）软件的本质特征和软件开发的本质困难2）软件危机的产生及软件工程的起源3）软件工程的定义 4）软件工程学科的重要地位2、软件生命周期1）需求：需求的定义和类型、需求工程过程、需求规格说明、需求评审设计：高层设计和详细设计2）测试：验证与确认、单元测试、集成测试、系统测试和验收测试、回归测试和部署 3）维护和演化：演化的基本概念、演化和维护活动、程序理解和逆向工程、系统和过程的再工程过程 4）项目管理：人员组织和管理、项目计划和跟踪、软件估算、风险控制、配置管理 3、 软件过程模型（一）1）瀑布模型 2）演化模型及增量和迭代方法的本质特征3）螺旋模型 4、软件过程模型（二）1）统一软件开发过程模型 2）敏捷过程模型 5、 可行性分析1）可行性研究的目标2）可行性研究的过程和预期结果3）经济可行性的基本概念和评估方法4）技术可行性的基本概念5）合规可行性的基本概念6、需求工程概述1）软件需求的根本挑战 2）软件需求的制品3）需求工程过程需求获取、分析、规约和验证4）需求管理需求跟踪、优先级和需求变更 5）领域模型和数据字典 7、结构化需求分析1）建模基础：模型和视图2）系统流程图 3）数据流图 4）实体-联系图 5）状态转换图 、IPO 图8、面向对象需求分析（一）新祥旭考研官网 http:/www.xxxedu.net/1）UML 建模基础2）用例和用例图 3）用例图的基本符号与用例关系 4）用例描述 9、面向对象需求分析（二）1）用活动图、顺序图和通信图描述用户需求2）领域的概念类与类图3）类之间的关系4）概念模型的创建步骤与建模举例10、软件设计基础1）总体设计和详细设计的概念2）软件设计过程3）软件设计的基本原理 4）软件设计的启发式规则 5）非功能性需求和软件设计 11、人机界面设计1）一般的人机界面设计原则2）人机交互方式和界面风格3）人机界面分析与建模4）界面设计活动和设计原则5）界面设计的实现工具6）可用性和人机交互评价12、软件体系结构基础1）软件体系结构视图 2）软件体系结构模式初步 3）基于构件的软件开发和 UML 构件图 4）使用 UML 部署图描述部署模型13、 结构化软件设计1）层次图、HIPO 图和结构图2）程序流程图、盒图3）判定表和判定树 4）面向数据流的设计方法 14、面向对象软件设计1）需求分析的精化-实体类、边界类和控制类 2）类图和对象图3）CRC 技术4）类之间的关系 5）从分析类到射击类 6）使用状态机图进行设计建模7）使用活动图、顺序图和通信图进行设计建模15、程序设计语言和编码1）程序设计语言2）编程规范和程序设计风格新祥旭考研官网 http:/www.xxxedu.net/3）软件设计质量度量 4）McCabe 复杂度分析 16、 软件测试、 软件维护和演化1）软件测试的目的2）软件测试策略和模型3）白盒测试4）黑盒测试5）软件测试完成标准6）软件维护的概念7）软件维护过程8）软件演化和再工程技术