当前位置：问答库＞考研试题

一、选择题

1． 对（ ）。

A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

2． 某主机的IP 地址为

组，则目的地址可以是（ ）。

A. B. C. D. 【答案】D 。

【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1, 这里77的二进制是

子网掩码252的二进制是

由此可以看到77的前6位作为子网位，后四

位作为主机位，由此可以知道其广播地址是也就是因此答案是D 。

3． 已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。

A.3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C.3，8，12，5，20，15，22，28，19

第 2 页，共 27 页

个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是

子网掩码为若该主机向其所在子网发送广播分

D.3，12，5，8，28，20，15，22，19 【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。

第 3 页，共 27 页

4． 在子网

A.0 B.1 C.2 D.4

【答案】C

中，能接收目的地址为的IP 分组的最大主机数是（ ）。

【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，

这里

显然是其广播地址，因此答案是C 。

5．

循环两列放在一维数组

中，endl 指向队头元素，end2指向队尾元素的后一个位置。

个元素。初始时为空，下列判断

假设队列两端均可进行入队和出队操作，队列中最多能容纳队空和队满的条件中，正确的是（ ）

A. 队空：B. 队空：C. 队空：D. 队空：【答案】A

队满：队满：

队满：队满：

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

6． 下列选项中，描述浮点数操作速度指标的是（ ）。

A.MIPS B.CPI C.IPC

D.MFLOPS 【答案】D

【解析】

表示每秒执行多少百万次浮点运算，

MIPS 表示每秒执行多少百万条指令。对于一个给定的程序，

定义为

这里所说的指令一般是指加、减运算这类短指令。

就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，造

成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。

每个时钟周期执行的指令数。

第 4 页，共 27 页

用来描述计算机的浮点运算速度，适用于衡量处理机的性能。