2018年中国海洋大学信息科学与工程学院807数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
2． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.
A.LRN
B.NRL
C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径：
①先上后下的按层次遍历；
②先左(子树) 后右(子树) 的遍历；
③先右(子树) 后左(子树) 的遍历.
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.
3． 某设备中断请求的相应和处理时间为100ns , 每400ns 发出一次中断请求, 中断相应所容许的最长延迟时间为50ns , 则在该设备持续工作过程中CPU 用于该设备的
分比至少是（ ） A. B. C. D.
【答案】B
【解析】每400ns 响应一次中断并且用100ns 进行处理, 所以该设备的时间占用CPU 时间百分比为100/400=25%, 中断响应容许的延迟时间对此没有影响, 属于干扰条件。
4． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知平衡因子为0的分支结点为3个叶子结点, 故答案为D 。
时间占整个CPU 时间百
图
5． 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤. 设浮点数的阶码
7和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位). 若有两个数X ＝2×29/32，Y
5＝2×5/8，则用浮点加法计算X ＋Y 的最终结果是（ ）.
A.001111100010
B.001110100010
C.010000010001
D. 发生溢出
【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步.X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐. 因此将Y 对阶后得到：Y ＝2×5/32，然后将尾数相加，得到尾数之和为：34/32.因为这是两7
个同号数相加，尾数大于1，则需要右规，阶码加1. 由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在之间. 而阶码本身等于7，再加1就等于8. 因此，最终结果发生溢出.
6． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
7． 下列选项中, 不会引起指令流水线阻塞的是（ ）。
A. 数据旁路(转发)
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式, 相邻或相近的两条指令可能会因为存在某种关联, 后一条指令不能按照原指定的时钟周期运行, 从而使流水线断流。有三种相关可能引起指令流水线阻塞:
①结构相关, 又称资源相关;
②数据相关;
③控制相关, 又称指令相关, 主要由转移指令引起。
8． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
9． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢