2019计算机考研真题解析：数据结构、操作系统等

本资源是一份2019年全国硕士研究生招生考试计算机科学与技术学科的计算机学科专业基础综合试题，涵盖了数据结构、操作系统、计算机组成原理和计算机网络等多个科目，共计40道多项选择题，总分80分。以下是部分题目及知识点详解： 1. 时间复杂度分析： - 题目询问程序段的时间复杂度，其中while循环条件是n大于等于(x+1)的平方，每次循环增加x，这表明循环次数与n的对数成正比。因此，正确答案是A. O(logn)。 2. 树的遍历： - 考查二叉树遍历与原树遍历的关系。后根遍历的特点是从根节点开始，先访问子树的最远节点，然后回溯。对于任何一棵树转化而来的二叉树，后根遍历顺序与原树的后序遍历相同。所以，正确答案是C. 后序遍历。 3. 哈夫曼树的结点数量与符号数量关系： - 题目提到通过哈夫曼编码法对互不相同的n个符号进行编码，生成的哈夫曼树有115个结点。由于哈夫曼树总是构建得比符号数量多一个，即n+1个结点，解得n=115-1=114。选项中没有提供这个数值，但根据题意推断，n的值应该是114，但这不是题目给出的选项之一。 4. 平衡二叉树操作： - 删除和插入操作对平衡二叉树的影响。删除叶结点u后，可能不改变平衡状态；但若u不是叶结点，删除操作一定会破坏平衡，因此必然导致新树T'与原树T不同。选项C正确，指出仅I和II正确。 5. AOE网络时间分析： - 该问题考查工程网络图的基本概念。活动d的最早开始时间和最迟开始时间通常与依赖关系有关。具体时间取决于其他活动的完成情况，图中未提供足够的信息来确定，因此需要根据网络图的具体结构分析，选项中没有提供答案。 6. 表达式表示与图论： - 题目涉及有向无环图(DAG)表示表达式，对于表达式(x+y)*((x+y)/x)，至少需要的顶点数量取决于如何构建最小的图来表达运算关系。通常，乘法和除法分别对应两条有向边，因此至少需要5个顶点（分别代表x、y、两个括号以及最终结果）。选项A是最少可能的顶点数量。 7. 排序算法选择： - 除了算法的时空效率，选择排序算法时还需要考虑数据的特性，如数据的分布（选项I）、排序的稳定性（选项皿），以及数据的存储方式（选项II）和初始状态（选项IV）。正确答案是B，因为稳定性是排序算法的一个重要特性，其他因素也会影响性能。 8. 散列表冲突处理： - 题目描述了线性探测再散列方法处理散列冲突。当散列表大小为11且初始为空，散列函数为key % 7，插入序列给出，插入过程中的冲突处理可能导致查找失败，但具体查找“失”（可能是查找失败或冲突引起的元素位置不在预期）的信息未在题干中提供。 以上是部分题目及其相关知识点的解析，完整的40道题目需要逐一分析才能得出详细答案。这份真题资源对准备计算机考研的学生来说非常有价值，可以帮助他们了解考试形式和重点知识点。