2018年仲恺农业工程学院食品安全与智能控制810数据结构(自)考研核心题库
● 摘要
一、单项选择题
1． 已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。 A. B. C. D.
【答案】A 拓扑序列的条件:若在顶
点
能被称为必须排
【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列
是图中的边(即从顶点。
到有一条路径) ，则在序列中顶点
之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
2． 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3, 这些资源总数分别为18、6、22。
时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。
表 资源分配情况表
A.P0, P2, P4, P1, P3 B.P1, P0, P3, P4, P2 C.P2, P1, P0, P3, P4 D.P3, P4, P2, P1, P0P0 【答案】D 。
【解析】典型的死锁避免算法、银行家算法的应用。分析一下下表, 可以看到, P3, P4, P2, P1, P0运行是可以的。
表
本题也可以排除法,
时刻可用资源是R1, R2, R3分别为2, 3, 3, 此时刻, P0需要R1, R2, R3
分别为2, 3, 7, 故排除A , P1需要R1, R2, R3分别为1, 3, 3, P2还需要资源R1, R2, R3分别为0, 0, 6, 故C 排除, P3需要R1, R2, R3分别为2, 2, 1。所以正确答案在B , D 之间。
看B 选项, P1之后的可用资源R1, R2, R3分别变为6, 3, 6, 而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。
3． 已知一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，则该完全二叉树的结点个数最多是（ ）.
A.39 B.52 C.111 D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层. 题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度. 根据题意，一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，可知此二叉树的高度是6或7. 题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7. 由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是目中二叉树的第6层结点数是
. 又根据二叉树的性质1可知，题
个结点，已知有8个叶子结点，那么其余32﹣8＝24个结点
均为分支结点，这些结点在第7层上最多有48个子结点(即叶子结点). 所以此二叉树的结点数最多 可达
4． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13 B.14 C.15 D.16
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有: A. 左子树为空, 右子树为cd ; b. 左子树为c , 右子树为d ; c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
5． 某CPU 主频为, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ）
A. B. C. D. 【答案】C
【解析】采用4级流水线执行100条指令, 在执行过程中共用CPU 的主频是
, 也就是说每秒钟有
条指令/秒,
故答案为C 。
6． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
7． 下列调整中, 不可能导致饥饿现象的是（ ）
A. 时间片转移 B. 静态优先及调度 C. 非抢占式作业优先 D. 抢占式短作业优先
条指令/秒 条指令/秒 条指令/秒 条指令/秒
个时钟周期。
个时钟周期。流水线的吞吐率为