南航2016考研829计算机专业基础试题解析

"2016年南京航空航天大学硕士研究生入学考试初试试题，科目：829计算机专业基础，包含数据结构与操作系统两部分，主要考察了关键路径、平衡二叉树、基数排序、链表操作、完全二叉树判断、页面置换算法及其应用、CPU利用率计算等知识点。" 本资源是一份2016年南京航空航天大学计算机专业考研初试的真题试卷，涉及的主要知识点包括： 1. 数据结构部分： - **关键路径**：题目要求求解图中的关键路径并描述算法思想和步骤。关键路径是项目管理中的一种概念，用于找出完成项目所需的最短时间，涉及到拓扑排序和松弛操作。 - **平衡二叉树**：考生需要根据给定的关键字序列建立平衡二叉树，并展示插入和调整的过程。平衡二叉树（如AVL树或红黑树）是为了保持搜索效率而设计的，确保左右子树的高度差不超过1。 - **基数排序**：考生需解释基数排序的原理和所使用的数据结构，基数排序是一种非基于比较的排序算法，按照位数从低到高进行排序。 - **链表操作**：题目要求编写函数删除单链表中的重复结点，这需要理解链表的基本操作，如遍历、比较和修改节点。 - **完全二叉树判断**：编写函数判断给定的二叉树是否为完全二叉树，完全二叉树是指除最后一层外，每一层都被完全填满，并且所有的结点都尽可能地集中在左端。 2. 操作系统部分： - **页面置换算法**：阐述其在虚拟存储管理中的重要性，以及FIFO（先进先出）算法的应用和缺点。FIFO可能导致Belady's异常，即增加物理内存页框反而增加缺页率。 - **FIFO算法分析**：计算给定页面走向在不同物理页框数下的缺页中断次数，这需要理解页面替换算法的工作原理。 - **CPU利用率**：分别在顺序环境和多道程序环境下计算程序A和B的CPU利用率，理解CPU调度和进程切换的概念。 这些题目涵盖了计算机科学基础理论，特别是数据结构和操作系统的重要概念，对于备考研究生考试的学生来说，是很好的练习材料。解答这些问题需要扎实的理论基础和编程能力。