2017年中国农业科学院农业信息所808数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5
B.7
C.8
D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有个关键字，高度为2的阶B 树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
2． 下列选项中，降低进程优先级的合理时机是（ ）。
A. 进程的时间片用完
B. 进程刚完成1/0, 进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪状态转为运行态
【答案】A
【解析】进程时间片用完可以降低其优先级，完成的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是
，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）
先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有
，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）
会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。
3． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出 则z 的机器数为（ ）
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
4． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4
=20MB/s。 字节信息, 则总线带宽是4B ÷
5．
对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。
6． 计算机开后，操作系统最终被加载到（ ）
A.BIOS
B.ROM
C.EPROM
D.RAM
【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区，这段区城是RAM ，故答案选D 。
7．
已知操作符包括的后缀表达式将中缀表达式转换为等价
时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
A.5
B.7
C.8
D.11
【答案】A 。
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）
。表达式
所列：
产生后缀表达式的过程如下表
通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
8． 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156