考研真题，部分内容如下
一，数据结构
1，单链表队列只能选择尾部插入头部插入，以及采用什么措施可以使得尾插入和头删除的时间复杂度达到o(1).10mark
2，DIJKSTRA算法的单元点最短路径给出了一段完整的伪代码要你填满四个空缺的语句。10mark
3.给定一组数值，如何建成优先堆，写出算法代码【10分】，分析其时间复杂度并给出结果【5分】
4.统计一个二叉树有两个非空子树的节点个数，它的时间复杂度如何【10分】
5.给定一组数值，提
【数据结构】
1. 单链表队列的优化：在单链表实现的队列中，通常尾插入和头删除的时间复杂度为O(n)，因为需要遍历找到队尾或队头。为了达到O(1)的时间复杂度，我们可以采用循环链表的设计，使得队头和队尾相接形成一个环，这样头删除只需将头结点指向下一个结点，尾插入只需将尾指针移动即可，无需遍历。
2. Dijkstra算法：这是一种用于求解带权有向图中源点到其他所有顶点最短路径的算法。其基本思想是使用优先队列（如最小堆）来存储待处理的顶点，并逐步更新顶点的最短路径。题目要求填写完整伪代码的四个空缺部分，具体填充应根据算法流程进行。
3. 建立优先堆：优先堆是一种特殊的完全二叉树，根节点的值不大于（或不小于）其任意子节点的值。给定一组数值，可以采用自底向上的方式构建优先堆。首先将所有元素作为叶子节点插入，然后逐层调整，确保每个父节点的值都小于或等于其子节点。算法时间复杂度为O(n)。
4. 二叉树非空子树统计：对于一个二叉树，统计有两个非空子树的节点个数，可以采用递归方法，如果一个节点的左子树和右子树都不为空，那么这个节点就满足条件。递归过程中，返回当前节点的子树满足条件的个数，加上自身是否满足条件的结果。时间复杂度为O(n)，因为每个节点只访问一次。
5. 提取最小k个数：使用快速选择算法可以在平均时间复杂度为O(n)的情况下找到数组中的最小k个数。快速选择算法是快速排序的一个变体，它只需要找出第k小的元素，而不需要对整个数组进行排序。
【软件工程】
1. CMMI（Capability Maturity Model Integration）是软件开发过程成熟度模型，分为五个等级，表示组织的软件开发能力和管理水平。
2. 抽象和逐步求精是软件开发过程中的两个关键概念，抽象是对复杂系统的简化表示，逐步求精则是将抽象逐步细化，直到得到可实现的细节。
3. 需求获取是软件开发早期阶段的重要活动，包括访谈、问卷调查、观察、原型演示等方法，用于收集用户需求。
4. 评价用例设计的质量通常考虑覆盖全面性、可执行性、无二义性和实际应用性。
5. 状态图描述对象在不同状态间的转换，例如台灯的状态可能包括开、关、弱光、强光等，通过事件（如按下开关）触发状态变化。
6. 数据流图（DFD）是系统分析阶段的工具，顶层图和一层图分别表示系统的整体输入、输出和主要处理，以及更具体的子处理过程。
7. 内聚度是衡量类中方法关联程度的指标，高内聚意味着方法紧密相关，不易被外部类复用。CBubbleSort类的冒泡排序方法可以提高内聚度，将其改为只负责排序，而将输入验证和输出处理等操作分离。
8. 白盒测试覆盖标准包括语句覆盖、判定覆盖、条件覆盖、路径覆盖等，确保代码的各个部分都得到充分测试。
9. 测试不仅仅是检查程序的正确性，还应包括发现错误、验证需求和确认系统质量等多个方面。
【计算机系统基础】
1. 流水线原理：在CPU中，流水线技术将指令执行划分为多个阶段，每个阶段并行处理，提高执行效率。影响效率的因素包括数据相关、控制相关和资源冲突等。
2. Amanda定律：描述了在多级缓存系统中，如何平衡各级缓存的大小和速度以最大化整体性能。
3. 存储器对流水线的影响：高速缓存的缺失命中会中断流水线，导致延迟，因此优化缓存性能对于保持流水线效率至关重要。
4. 提高存储器性能可通过增大缓存容量、采用更快的内存技术、优化缓存替换策略等方式，基于局部性原理，确保常用数据能快速访问。
