2016年沈阳师范大学软件学院数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
2． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。
I. 撤销部分进程
II. 增加磁盘交换区的容量 III. 提高用户进程的优先级 A. 仅I B. 仅 II C. 仅III D. 仅 I 、II 【答案】A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页 必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）
题，提高用户进程的优先级会使系统的状态更加恶化。
3． 某计算机主存容量为64KB , 其中ROM 区为4KB , 其余为RAM 区，按字节编址。现要用2Kx8位的ROM 芯片和4Kx4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）。
A.1、15
C.1、30 D.2、30 【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB 。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2Kx8位的ROM 芯片，只需/4*2采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用（60）片芯片进行字和位同时扩展便可得60KB 的RAM 区。
4． 下列有关接口的叙述中错误的是：（ ）
A. 状态端口和控制端口可以合用同一寄存器 B.
接口中CPU 可访问寄存器，称为
端口
端口
指令，
C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和
端口共用统一的地址空间，不需要专用的
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
5． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
6． 内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关 B. 内部异常的检测由CPU 内部逻辑实现 C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行 【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
7． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问
C. 仅 1，2 D. 仅 2, 3 【答案】C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
8． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1 B.2 C.3 D.4
【答案】C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
9． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1
个大小为
的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该
报文传输所需的总时间分别为（ ）
A.800ms> 1600ms B.801ms 、1600ms
C.1600ms 、800ms D.1600ms 、801ms 【答案】D
【解析】不进行分组时，发送一个报文的时延是
的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是
在接收端接收此报文件
接收一个报
文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801 ms。
10．向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D