南航2017计算机专业基础考研试题详解：数据结构、B-树与Dijkstra算法

南航2017年硕士研究生入学考试计算机专业基础A卷包含了数据结构、操作系统等多个核心知识点。首先，让我们详细探讨各个部分： 1. 数据结构部分（50分） - **家谱管理程序设计**（10分）：设计一个数据结构用于表示一个四代人家庭的家谱，如使用树形结构（如二叉树或图），其中每个节点代表一个家庭成员，包括其子节点。存储结构可以是递归定义，根节点表示第一代，每个子节点代表下一代。输出第k代所有人员的算法思想可以是深度优先搜索（DFS）或广度优先搜索（BFS），根据需求选择合适的遍历方式。 - **B-树操作**（10分）：题目要求建立3阶B-树，并插入与删除特定元素。B-树是一种自平衡的查找树，对于插入和删除操作，需要遵循B-树的特性，如每个节点至少包含k个子节点等。插入后可能需要重新调整树的结构以保持平衡。 2. 操作系统部分（50分） - **系统线程与用户线程的区别**（4分/题 × 2题 = 8分）：系统线程是内核级线程，由操作系统直接管理，而用户线程是应用级别的，运行在用户空间。区别在于调度、上下文切换开销、资源限制等。 - **分段式与分页式系统**（4分/题 × 1题 = 4分）：分段式系统将内存划分为多个逻辑段，每个段可独立分配，而分页系统将内存划分为固定大小的页，地址空间连续。两者在虚拟内存管理和内存碎片处理上有所差异。 - **缓冲区与缓冲模式**（4分）：缓冲是为了减少I/O操作对CPU的影响，提高数据传输效率。常见缓冲模式有直接、循环、双缓冲等，每种模式针对不同的应用场景和性能优化。 - **SPOOLing技术**（7分）：SPOOLing（Simultaneous Peripheral Operations On-line）是一种共享设备的技术，通过将I/O请求排队，让多个进程共享打印机等设备。它在操作系统中起到简化I/O操作、提高设备利用率的作用。 3. 其他问题 - **单链表合并**（10分）：算法思想是使用两个指针分别遍历两个链表，比较当前节点的值，较大者添加到结果链表，然后移动较小链表的指针。最后，将剩余未处理的较大量节点添加到结果链表。 - **成绩调整线性表**（10分）：算法思想是遍历线性表，遇到及格分数将其移动到新链表头部，同时记录移动过的元素数量。当达到不及格分数时，结束移动并返回已移动元素的数量。 - **作业调度**（16分）：计算两种调度算法（先来先服务和最短作业优先）的平均周转时间，需要考虑每个作业的执行时间和等待时间，按照算法规则计算总时间并取平均。 以上是南航2017学硕计算机专业基础A卷的主要知识点概览，涉及了数据结构中的树状表示、B-树操作，以及操作系统中的线程概念、内存管理、I/O技术和调度算法。这些知识点是考研计算机科学领域的重要考察内容，理解并掌握它们对于备考至关重要。