《878试卷数据结构和操作系统部分答案(交流版).pdf》由会员分享，可在线阅读，更多相关《878试卷数据结构和操作系统部分答案(交流版).pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、878 计算机专业基础综合答案（交流版）计算机专业基础综合答案（交流版）第一部分：数据结构第一部分：数据结构 一、一、单项选择题单项选择题 1、A 由于链表不带头结点，所以 A 即可完成在第一个元素之前插入新节点，并更改链表指针。B、D 选项先进行 h=t 操作，结果链表和 h、t 都丧失联系；C 选项其实是用新节点替换链表首节点。(=应为=)2、C 第一个出栈元素为 4，则可断定在 4 之前入栈的所有元素，在 4 入栈后都还按后进先出的原则压在栈中，且在 4 之后入栈的所有元素，在 4 出栈之前尚未入栈。所以在栈顶元素 4 出栈后，栈中由栈底到栈顶依次为 1、2、3，因此在 1、2、3、4四
2、个元素中 1 最后出栈。由于元素 5 可能在 1 出栈之前入栈，也可能在 1 出栈之后入栈，所以最后出栈的元素可能是 1，也可能是 5。3、B 假设二叉树根节点为 P，左子树根节点为 L，右子树根节点为 R，则前序遍历序列为 P(L)前(R)前，中序遍历序列为(L)中P(R)中，按题意 P(L)前(R)前=(R)中逆P(L)中逆，故(R)中逆为空（即根节点无右子树）且(L)前=(L)中逆，同理 P 的左子树 L 无右子树。以 L 为根节点递推下去可知任一节点无右子树。4、C 用数组存储完全二叉树时，节点 i(1i=n)的双亲节点为i/2,故下标为 17 的节点的祖先节点下标为 8、4、2、1；
3、下标为 19 的节点其祖先下标依次为 9、4、2、1，因此最近的公共祖先下标为 4。5、D 如下图所示，森林中树的个数为 4 个，最大的树含有节点数目为 9 个12345678910111213141516137152511498166131214森林F10 6、B 一棵 m 阶 B 树的根节点可以有 2 到 m 棵子树。7、B 设高度为 h的 AVL 节点数至少为 N(h)，则 N(h+2)=N(h+1)+N(h)+1；初始时 N(0)=1，N(1)=2，故 N(2)=4,N(3)=7,N(4)=12,N(5)=20,N(6)=33。故该 AVL 树的高度至多为 5。8、C 经过编码，a 的
4、编码为 10（2bit）,b 的编码为 110（3bit），c 编码为 0（1bit）d、e 编码分别为 1110、1111（各 4bit）；故总位数为 2*3+3*2+1*5+4*1+4*1=25bit 112012401123510701 9、C 边存在，故 A 错；存在故 B 错；存在故 D 错。10、A 第 i 列值全为，则第 i 个顶点的入度为 0。在 AOE 网中，只有一个顶点入度为0，即为源点。表示实际工程计划的 AOE 网应该是无环的，并且存在唯一的入度为 0 的开始顶点和唯一的出度为 0 的完成顶点。11、C 简单选择排序和冒泡排序都会首先使待排序序列的最值就位，经过 i 轮
5、简单插入排序后，序列的前 i+1 个元素(或后 i+1 个)将有序，而其它 n-i-1 个均未移动。堆排序经过第一轮排序后，n/2和n是有序的，即 r3和 r6应有序，而其它元素均未移动。题中的处理结果直接看好像是以 46 为枢轴进行快速排序的。但如果以 46 为枢轴进行一轮快速排序，结果是（38、40、46、56、84、79），只能推测是以 56 为枢轴记录进行一轮快速排序的，但究竟具体排过程如何进行才能得到题目中的结果，我现在还没搞清楚，望高手指点。（题我没有抄错）12、D 第一个元素 46 和第五个元素 38 交换，84 和 79、56 和 13、40 和 27 交换。二、分析题二、分析
6、题 1、二叉排序树的插入过程如下图所示：插入27201530252015302527危机节点危机节点，平衡因子平衡因子2，LR型型，先左旋或右旋先左旋或右旋先左旋20153025272015302527后右旋插入26201530252726危机节点，平衡因子-2 RL型，先右旋后左旋先右旋201530252726后左旋153025272026插入1415302527202614危机节点，平衡因子2 LL型，右单旋转处理1530252720 2614右单旋2、（1）该查找树判别函数是不正确的。此函数的判别依据是：根节点的数值大于其左子树根节点的数值而小于其右子树的数值。而符合此条件的二叉树并不一
7、定是二叉排序树，如下图。正确的判别方法是根据二叉排序树的定义或其中序遍历有序的特性来进行的，即根节点的数值大于其左子树的最大值（即其中序遍历前驱节点的数值）而又小于其右子树的最小值（即其中序遍历后继结点的数值）。（下图表示的二叉树能通过函数 IsSearchTree 的测试，但它不是二叉排序树。）20153025（2）该最小堆判别函数是正确的。3、该邻接矩阵所表示的无向图入下所示。13245601710816141222182524（1）G 的最小生成树代价值为 82，其最小生成树的 n-1 条边为红线所示。（2）从顶点 0 深度优先遍历的结果序列为：0、1、2、3、4、5、6；图的存储结构一
8、旦确定，其遍历序列也就唯一。（3）节点的扩展顺序为 0、6、5、1、2、3、4。4、（1）按序列顺序插入关键字之后的哈希表如下图所示:No 0 1 2 3 4 5 6 7 8 9 10 11 12 Key 7 72 33 59 48 36 46 25 collision count 4 2 0 1 0 0 3 0（2）、在查找成功的情况下，查找过程中比较的次数为冲突次数加 1。ASL succ =（5+3+1+2+1+1+4+1）/8=18/8（3）、对于关键字 8，其探测序列为：8、9、7、12、4；当探测到 4 时，由于该位置上关键字为空，故断定查找不成功。第三部分：操作系统第三部分：操作
9、系统 一、单项选择题一、单项选择题 1、C 2、C 3、D 4、A 在使用 FIFO 作为页面替换算法时，进程的缺页率随着驻留集的增大可能减小也可能增大。5、D 根据条件，系统中有 3 个进程正在使用该类资源，有 2 个进程因为等待该类资源而阻塞。（题目中的问法实在让人困惑！选择 D 只是个人看法）6、D 首先，只有一个进程是不会引起死锁的，排除 A。选项 B 的情况下，系统能同时满足 2 个进程的最大需求。C、D 之间选择依据是：若 n*(w-1)+1m 并不能断定选项 D 的情况下一定会发生死锁。死锁的发生只是可能！二、分析题二、分析题 1、该题目的类型是用信号量实现进程间的前驱后继关系。
10、P1P2P3P4P5e12e13e45e25e35 Semaphore e12,e13,e25,e35,e45;e12=e13=e25=e35=e45=0;void P1()operation V(e12);V(e13);void P2()P(e12);operation V(e25);void P3()P(e13);operation V(e35);void P4()operation V(e45);void P5()P(e25);P(e35);P(e45);operation 2、见教科书。附：附：本试题答案（部分）由王道 xiaosheng 整理，旨在供报考 2011 年 ZJU MSE 的同学参考和交流使用。限于自己的水平，错误和疏漏之处在所难免，望各位同学审查并指出。如果你有更好的想法，或者对该部分试题及答案有疑惑之处，你可以按以下方式和我联系： QQ625309175 或在王道下载页直接指出！计算机组成原理和网络部分的答案尚未录入。如果你将这两部分的答案整理完毕，你也可以将其上传到王道 MSE 版块。谢谢你的支持！