### 北京交通大学901软件工程2021年初试大纲知识点解析
#### 一、901软件工程
**1. 软件工程概论**
- **软件危机与软件工程产生的背景：** 介绍了软件开发过程中遇到的问题，如成本超支、进度延迟、功能不满足需求等，这些问题导致了“软件危机”。为了应对这些问题，软件工程学科应运而生。
- **软件的概念与定义：** 讲解了软件的基本定义，包括程序、数据及相关文档的集合。
- **软件工程的研究对象与基本原理：** 研究对象主要是软件产品的生命周期内的各个阶段；基本原理包括分阶段进行、团队合作、持续改进等。
- **软件工程工具和环境：** 工具包括需求分析工具、设计工具、编程工具、测试工具等；环境则指开发软件所需的硬件、操作系统等基础条件。
- **软件生存周期：** 描述了软件从构思、分析、设计、实施到维护的全过程。
- **软件过程模型：** 如瀑布模型、螺旋模型、增量模型等。
**2. 需求分析**
- **需求分析的目标和任务：** 目标是准确理解和表达用户的需求；任务包括需求获取、分析、规格说明编写等。
- **软件系统的可行性分析：** 包括经济可行性、技术可行性、操作可行性等。
- **需求获取：** 通过访谈、问卷调查等方式获取用户需求。
- **需求规格说明书：** 文档化的用户需求，为后续设计提供依据。
- **数据流建模（数据流图）：** 通过图形化的方式表示系统的输入、输出、处理过程等。
- **实体-关系建模（E-R图）：** 表达实体间的关联关系。
- **系统行为建模：** 如状态图、活动图等，用于描述系统的动态行为。
- **用例建模（用例图）：** 描述系统的功能需求。
- **面向对象建模：** 使用UML等工具进行对象、类、关系等的建模。
**3. 软件概要设计与详细设计**
- **概要设计的任务与步骤：** 确定软件架构、模块划分、接口设计等。
- **软件设计的基本原则：** 如模块化、信息隐藏、耦合与内聚等。
- **抽象与逐步求精方法：** 通过逐步细化来提高设计质量。
- **详细设计的任务：** 确定每个模块的具体实现细节。
- **结构化程序设计：** 强调程序结构清晰、易于理解。
- **面向对象程序设计：** 以对象为核心，强调封装、继承、多态等概念。
- **程序流程图：** 用图形化方式展示程序执行流程。
- **模型-视图-控制器框架（MVC）：** 一种常见的设计模式，将应用程序分为三个部分。
**4. 面向对象的程序设计方法**
- **基本概念：** 如类、对象、封装、消息传递、继承、多态等。
- **统一建模语言 UML 的基础知识：** UML 是一种标准化的建模语言，用于软件系统的可视化建模。
- **类图、时序图：** 分别用于表示系统的静态结构和动态行为。
**5. 软件验证技术**
- **软件测试的目标、过程和步骤：** 测试的目标是发现并修复错误，确保软件质量；过程通常包括单元测试、集成测试、系统测试等。
- **代码复审：** 由同行对代码进行检查，以发现潜在问题。
- **白盒测试、黑盒测试：** 白盒测试关注内部逻辑结构；黑盒测试仅考虑输入输出关系。
- **测试用例设计技术：** 如路径覆盖、条件覆盖、边界值分析等。
- **调试：** 定位并修正程序中的错误。
**6. 软件维护技术**
- **软件维护的基本概念和基本活动：** 维护是指软件交付后为适应环境变化而进行的一系列修改工作。
- **软件维护过程：** 包括问题报告、问题分析、修改设计与代码、重新测试等步骤。
- **软件可维护性：** 描述软件易于修改的程度。
- **软件再工程技术：** 对现有软件进行分析、重构，以提高其质量和可维护性。
**7. 软件质量保证**
- **软件质量的概念：** 软件质量包括功能性、可靠性、易用性等多个方面。
- **软件评审技术：** 通过审查文档或代码来识别缺陷。
- **软件质量保证的原理和措施：** 包括制定质量计划、执行质量控制、持续改进等。
- **软件配置管理的概念和方法：** 确保软件版本的一致性和可控性。
**8. 软件项目管理**
- **项目管理的概念：** 包括项目计划、组织、执行、监控等方面。
- **软件度量：** 通过对项目数据的收集和分析来评估项目状态。
- **软件项目的评估：** 成本估计、效益分析等。
- **软件风险分析和管控：** 识别可能的风险，并采取相应措施减轻或消除这些风险的影响。
#### 二、10101数据结构
**1. 概述**
- **数据结构的基本概念：** 包括数据的逻辑结构、存储结构等。
- **算法的五个特性：** 输入、输出、确定性、有限性、可行性。
- **计算语句频度和估算算法时间复杂度和空间复杂度的方法：** 如大O符号表示法。
- **抽象数据类型：** 将数据结构和操作封装在一起。
**2. 线性表**
- **线性表的逻辑结构：** 一种线性序列的数据结构。
- **线性表的顺序存储结构和链式存储结构：** 分别利用数组和链表实现。
- **线性表在顺序结构上实现基本操作的方法：** 如插入、删除等。
- **线性表在链式结构上实现基本操作的方法：** 如插入、删除等。
- **比较线性表两种存储结构的不同特点及其适用场合：** 顺序存储结构适合随机访问，链式存储结构适合频繁插入和删除。
**3. 栈和队列**
- **栈的特点：** 先进后出（LIFO）。
- **在顺序存储结构上栈的基本操作的实现：** 如入栈、出栈等。
- **在链式存储结构上栈的基本操作的实现：** 如入栈、出栈等。
- **递归算法中栈的作用：** 保存函数调用过程中的局部变量和返回地址。
- **栈的典型应用实例：** 如括号匹配、逆波兰表示法等。
- **队列的特点：** 先进先出（FIFO）。
- **在顺序存储结构上循环队列基本操作的实现：** 如入队、出队等。
- **在链式存储结构上链队列的基本操作的实现：** 如入队、出队等。
- **队列的典型应用实例：** 如任务调度、缓冲区等。
**4. 数组和广义表**
- **数组的存储结构：** 一种连续存储的数据结构。
- **数组在行序为主序的存储结构中的地址计算方法：** 如一维数组到多维数组的映射。
- **特殊矩阵的压缩存储方法：** 如稀疏矩阵、对称矩阵等。
- **稀疏矩阵的三元组表示以及运算处理方法：** 通过三元组存储稀疏矩阵。
- **广义表的概念：** 一种支持嵌套列表的数据结构。
**5. 树与二叉树**
- **二叉树的概念：** 一种特殊的树形结构，每个节点最多有两个子节点。
- **二叉树的各种存储结构：** 如顺序存储、链式存储等。
- **二叉树的性质：** 如高度、节点数量等之间的关系。
- **按各种次序遍历二叉树的递归算法：** 如前序、中序、后序遍历。
- **按各种次序遍历二叉树的非递归算法：** 如栈辅助的非递归遍历。
- **建立二叉树的各种算法：** 如构建二叉搜索树。
- **建立最优二叉树和哈夫曼编码的方法：** 通过最小化加权路径长度来构建最优二叉树。
- **树的各种存储结构及其特点：** 如孩子-兄弟表示法。
- **树与二叉树、森林与二叉树的相互转换：** 通过特定规则将树转换为二叉树。
- **树与等价类划分问题：** 树可以用来表示不同等价类之间的关系。
**6. 图**
- **图的基本概念：** 包括顶点、边、有向图、无向图等。
- **图的存储结构：** 如邻接矩阵、邻接表等。
- **图的深度优先遍历和广度优先遍历：** 不同的遍历策略。
- **最小生成树（PRIM算法和Kruscal算法）：** 找出图中所有顶点间连通且权重最小的子图。
- **某一点到其他各点之间的最短路径（迪杰斯特拉算法）：** 找出两点间的最短路径。
- **拓扑排序：** 对有向无环图进行排序。
- **关键路径和关键活动：** 在项目网络图中找出最长路径和关键活动。
**7. 查找算法**
- **顺序查找算法及特点：** 逐一比较目标元素。
- **折半查找算法及特点：** 在有序数组中进行查找。
- **索引查找的过程和特点：** 通过建立索引来加速查找过程。
- **二叉排序树的构造方法和查找过程：** 二叉搜索树的基本操作。
- **二叉平衡树的旋转平衡方法：** 如AVL树的旋转操作。
- **B-树的特点及其建立过程和查找过程：** 多路搜索树的一种。
- **哈希表的构造方法和查找方法：** 通过哈希函数快速定位元素。
- **各种查找算法在等概率情况下查找成功和查找失败时的平均查找长度：** 如哈希表的查找长度通常较短。
