发布时间 : 星期三 文章后4套-答案答应版更新完毕开始阅读
王道模拟试题（五）答案
一、单项选择题
1． D。
【解析】考查栈和队列的区别。栈和队列的逻辑结构都是线性的，都有顺序存储和链式 存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时所包含 的运算都可能不同。插入和删除运算的限定不一样才是栈和队列的最主要区别。
2． A。
【解析】考查出入栈序列和栈深的关系。由于栈的最大深度不能超过 3。故第一个出栈元 素不能是 5 或 4，第二个出栈的元素不能是 5，由此可以排除 B、C、D。
3． A。
【解析】考查栈的应用。设中间计算结果 S1=C/D，S2=(B+C/D)，则扫描过程如下：
扫描字符 A - ( B + C / D 运算数栈（扫描后） A A A A B A B A B C A B C A B C D A B S1 运算符栈（扫描后） 说明 ‘A’入栈 - - ( - ( - ( + - ( + - ( + / - ( + / - ( + - ( + ) - - × - × ‘-’入栈 ‘(’入栈 ‘B’入栈 ‘+’入栈 ‘C’入栈 ‘/’入栈 ‘D’入栈 计算 S1 ‘) ’入栈 计算 S2 ‘×’入栈 ‘E’入栈 ) A B S1 A S2 × E
A S2 A S2 E 扫描到 E 时，运算符栈中的内容依次是“-×”，因此选 A。 4． D。
【解析】考查二叉树的遍历。对于 I，显然任何遍历都相同。对于 II，根结点无右孩子， 此时前序遍历先遍历根结点，中序遍历最后遍历根结点，所以不相同。对于 III，是一棵左单 支树，前序遍历和后序遍历的序列相反。对于 IV，所有结点只有右子树的右单支树，前序遍 历和中序遍历的序列相同。选 D。
5． C。
【解析】考查平衡二叉树的性质与查找操作。设 Nh 表示深度为 h 的平衡二叉树中含有的 最少结点数，有：N0=0，N1=1，N2=2，…，Nh=Nh-1+Nh-2+1，N3=4，N4=7，N5=12，N6=20>15（考
『151』
生应能画出图形）。也就是说，高度为 6 的平衡二叉树最少有 20 个结点，因此 15 个结点的 平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。选项 B 的查找过程 不能构成二叉排序树，错误。选项 A 根本就不包含 28 这个值，错误。
6． A。
【解析】考查完全二叉树性质。完全二叉树第 5 层共有 24=16 个结点。第 6 层最左边有 3 个叶子结点，对应第 5 层最左边 2 个结点，所以第 5 层右边有 16-2=14 个叶子结点，因此共 有 17 个叶子结点。
【另解】画出草图的片段部分进行求解，比较形象且不易出错。
7． B。
【解析】考查无向完全图的性质。n 个结点的无向完全图共有 n(n-1)/2 条边。对于 n+1 个 结点和 n(n-1)/2 边构成的非连通图，仅当 n 个顶点构成完全图、第 n+1 个顶点构成一个孤立 顶点的图；若再增加一条边，则在任何情况下都是连通的。n 个顶点构成的无向图中，边数 ≤n(n-1)/2，将 e=36 代入，有 n≥9，现已知无向图是非连通的，则 n 至少为 10。
8． D。
【解析】考查拓扑序列的性质。选项 D 中的情况是不可能出现的，因此若 G 中有一条 Vj 到 Vi 的路径，则在图的拓扑序列中顶点 Vj 应该在顶点 Vi 之前。以分析中的示例说明：若有 一条 Vj 到 Vi 的路径，说明 Vj 是 Vi 的前驱，则拓扑排序 Vj 应该在 Vi 的前面，显然矛盾。
9． D。
【解析】考查散列表的构造过程。任何散列函数都不可能绝对的避免冲突，因此采用合 理的冲突处理方法，为冲突的关键字寻找下一个“空”位置。将前面各元素分别放入散列表中， 其中 8、9、10 的位置分别存放 25、26、8。元素 59 经过哈希函数计算应该存入位置 59 mod 17 = 8，发生冲突，采用线性探测再散列，依次比较 9、10、11，发现 11 为空，所以将其放 入地址 11 中。各关键字对应的散列地址见下表。
关键字 散列地址 26 9 25 8 72 4 38 4 8 8 18 1 59 8 10．A。
【解析】考查各种排序算法的特点。冒泡排序和选择排序经过两趟排序之后，应该有两 个最大（或最小）元素放在其最终位置；插入排序经过两趟排序之后，前 3 个元素应该是局 部有序的；只有可能是快速排序。
注意：在排序过程中，每一趟都能确定一个元素在其最终位置的有：冒泡排序、简单选择 排序、堆排序、快速排序，其中前三者能形成全局有序的连续子序列，后者能确定枢轴元素的 最终位置。直接插入排序每一趟排序形成的有序子序列只是局部有序的。
11．A。
【解析】考查快速排序的性质。当待排序列有序或接近有序时，快速排序的效率最低。 当每次的枢轴都把表等分为长度相近的二个子表时，速度是最快的。选项 A 第一趟枢轴 21 将表划分为二个子表｛9,17,5｝和｛25,23,30｝，而后对两个子表划分时，枢轴再次地将它们 等分，所以该序列是快速排序的最优情况，速度最快。
『152』
12．A。
【解析】本题考查计算机的性能指标。CPI是一种衡量CPU性能的指标，即执行一条指令 所需的时钟周期数，系统结构、指令集、计算机组织都会影响到CPI。时钟频率不会影响到 CPI，但可以加快指令的执行速度。如一条指令的执行需要10个时钟周期，则执行这条指令时 钟频率为1GHz的CPU比100MHz的CPU要快。
13．B。
【解析】考查不同进制数之间的转换与算术移位运算。对于本类题型，应先将-1088 转换 为 16 位的补码表示，执行算术右移后，再转换为十六进制数。R1 的内容首先为[-1088]补=1111 1011 1100 0000B=FBC0H。算术右移 4 位的结果为 1111 1111 1011 1100B=FFBCH，则此时 R1 中的内容为 FFBCH。
注意：算术移位时保持最高的符号位不变，对于正数（符号位为 0），原码、补码、反码 的算术左移/右移都是添 0；对于负数（符号位为 1），添补规则见下表。
原码 补码 反码
0 左移添 0，右移添 1 1 14．B。
【解析】本题考查机器零。只有当数据发生“上溢”，才会终止运算操作，转去进行溢出处 理，A 错误。规格后化可以判断运算结果是否上溢出（超过表示范围），但和机器零没有关 联，C 错误。定点数中所表示的 0，是实实在在的 0（坐标轴上的），而不是趋近 0 的机器零， D 错误。在各种数码的表示法中，移码相当于真值在坐标轴上整体右移至正区间内，当移码 表示的阶码全 0 时，为阶码表示的最小负数，此时直接认为浮点数是机器零，B 正确。
注意：当浮点运算结果在 0 到最小正数之间（正下溢）或最大负数到 0 之间（负下溢） 时，浮点数值趋于 0，计算机仅将其当做机器零处理。
15．C。
【解析】本题考查 Cache 的性能因素。Cache 的命中率指 CPU 要访问的信息已在 Cache 中 的比率。显然与 Cache 的存取速度无关，而选项 ABD 与 Cache 的命中率都有一定的关系。
16．B。
【解析】本题考查 FIFO 算法。FIFO 算法指淘汰 先进入 的，易知替换顺序为： 走向 c b a 命中否 0 1 2 2 4 2 1 4 2 2 1 4 √ 3 2 3 4 0 0 3 4 2 0 3 2 1 0 1 2 3 3 1 2 2 3 1 2 √ 3 3 1 2 √ 0 3 1 0 1 3 1 0 √ 4 3 4 0 0 1 0 1 0 表中除了标注为命中的，其余均未命中，所以命中率为 4/15=26.7%。
17．A。
【解析】本题考查基址寻址和变址寻址的区别。两者的有效地址都加上了对应寄存器的
『153』
内容，都扩大了指令的寻址范围，I 正确。变址寻址适合处理数组、编制循环程序，II 正确。 基址寻址有利于多道程序设计，III 正确。基址寄存器的内容由操作系统或管理程序确定，在 执行过程中其内容不变，而变址寄存器的内容由用户确定，在执行过程中其内容可变，故 IV 和 V 错误。
注意：基址寻址和变址寻址的真实地址 EA 都是形式地址 A 加上一个寄存器中的内容。
18．C。
【解析】本题考查取指周期完成的操作。CPU 首先需要取指令，取指令阶段的第一个操 作就是将指令地址（程序计数器 PC 中的内容）送往存储器地址寄存器。题干中虽然给出了 一条具体的指令“MOV R0, #100”，实际上 CPU 首先要完成的操作是取指令，与具体指令是 没有关系的。
注意：取指周期完成的微操作序列是公共的操作，与具体指令无关。
19．C。
【解析】考查流水线的时空图。流水线在开始时需要一段建立时间，结束时需要一段排 空时间，设 m 段流水线的各段经过时间均为?t，则需要T0 = m?t的时间建立流水线，之后每 隔?t就可以流出一条指令，完成 n 个任务共需时间T = m?t + (n ? 1)?t。具有三个功能段的 流水线连续执行 10 条指令共需时间 = 3+9 =12。
20．B。
【解析】本题考查总线的定时方式。由题意可知，医生是主模块，护士是从模块。医生 伸出手后（即主模块发出请求信号），等待护士将手术刀递上（主模块等待回答信号），护士 也必须等待医生握紧后才松开收（从模块等待主模块的回答信号），以上整个流程就是异步 通信的全互锁方式。
21．C。
【解析】本题考查外中断方式和 DMA 方式的区别。和中断方式相比，DMA 连接的是高 速设备，其优先级高于中断请求，以防止数据丢失，I 正确。DMA 请求的响应时间可以发生 在每个机器周期结束时，只要 CPU 不占用总线，而中断请求的响应时间只能发生在每条指令 执行完毕，II 错误。通常情况下，DMA 的优先级要高于外中断，所以 DMA 优先级一般要比 非屏蔽中断请求要高，III 错误。如果不开中断，非屏蔽中断（以及内中断）仍可响应，IV 错误。在 DMA 方式的预处理和后处理中，需要 CPU 的干预，只是在传送的过程中不需要 CPU 的干预，V 错误。
注意：中断方式具有对异常时间的处理能力，而 DMA 方式仅局限于完成传送数据块的 能力。
22．B。
【解析】本题考查通道的基本工作过程。通道的基本工作过程：用户程序使用访管指令 进入操作系统管理程序；CPU 通过管理程序组织一个通道程序，并用 I/O 指令启动通道；通 道执行通道指令，完成 I/O 操作；通道程序结束后向 CPU 发中断请求。通道程序放与主存之 中，由 CPU 执行 I/O 指令启动通道，通道执行通道程序。在整个传输过程中，数据传输结束 时，需要中断来处理。
『154』