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

一、选择题

1．

对

（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

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

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

答:A

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

2． 下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。

I. 指令格式规整且长度一致

II. 指令和数据按边界对齐存放

III. 只有Load / Store指令才能对操作数进行存储访问

A. 仅

B. 仅

C. 仅

D.

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

【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。

3． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。

A.7KB

B.8KB

C.9KB

D.16KB

答:C

【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。

4． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

答:C

【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。

5． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）

A.5

B.6

C.8

D.9

答:C 【解析】所以至少需要8位才能表示完130个地址。

6． 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。

A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数

答:B

【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。

7． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗

口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。

A.10KB

B.12KB

C.14KB

D.15KB