数据结构与软件工程考试回顾：算法调整与名词解释

在2017年的考试中，数据结构和软件工程部分的题目设计出现了显著变化。首先，数据结构部分的考察重点转移，以往侧重于算法题，但这一年选择题占比较大，涉及到数据结构的基本概念和时间复杂度分析。 1. 选择题部分： - 非线性结构的选择题考察了考生对基本概念的理解，正确答案是C. 二叉树，因为队列和栈都是线性结构。 - 第二题考核的是嵌套循环中的执行频度，两个外层循环各运行n次，因此总执行次数为n^2，答案是C. O(n^2)。 - 数组读取元素的时间复杂度通常为O(1)，因为直接访问索引位置不需要额外的时间，所以A. O(1)正确。 - 对于二叉树的中序遍历序列，没有具体给出树的形态，无法确定，需要考生根据给定的序列推断，题目略带歧义。 - 无向图的边的数量计算公式是(n-1)/2，这是由于每个节点与其他节点形成一条边，但不包括自环，答案是D. (n-1)/2。 2. 名词解释部分： - 搜索二叉树：一种特殊的二叉查找树，满足左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。 - 图的最小生成树：连接图中所有顶点的边的集合，使其边权之和最小，通常使用 Prim 或 Kruskal 算法求解。 - 堆：一种特殊的树形数据结构，通常分为最大堆和最小堆，用于实现优先队列等应用。 - 线性结构：数据元素之间存在一对一关系的结构，如数组和链表。 - 算法的时间复杂度：衡量算法效率的重要指标，描述执行算法所需时间与输入规模之间的增长关系。 软件工程部分： - 软件工程主要考察基础概念，如软件开发方法论和实践。 - 持续集成：一种软件开发实践，通过频繁地自动构建和测试代码，确保尽早发现问题。 3. 需求题： - 需求层次通常包括业务需求、用户需求、功能需求和非功能需求，图书馆管理系统的需求例子可能涉及借阅流程、图书分类、检索功能等。 4. 体系结构题： - 该题要求根据给定功能设计一个字符串大小写转换系统的体系结构，可能涉及分治策略或状态机设计，以及模块间的依赖关系。 5. 面向对象题： - 分析Person类的设计，可能关注类成员变量的合理性、构造函数是否冗余，以及类的封装性和继承性等原则。 6. 交互与协作题： - 对雇员所得税代码的分析会关注方法间的调用关系、依赖性和并发控制，以及接口设计的清晰度和责任划分。 总体来看，2017年的考试更注重基础概念的掌握和实际问题的解决能力，而非以往的难题深度。考生需要全面理解数据结构和软件工程的基本原理，并能灵活运用到实际问题中。