一、填空题

1． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】

【解析】叶子节点的左右孩子都不存在。

2． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。

【答案】23; 100CH

3． 在一棵m 阶

的个数是_____。 【答案】

最少 【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是

4．

=_____

【答案】5

5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

6． 模式串的next 函数值序列为_____。

【答案】01122312

7． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是

中序序列是

前庁序列是_____。 【答案】

前序是

。

第 2 页，共 67 页 树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字.

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的 【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的

8． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

二、选择题

9． —个具有1025个结点的二叉树的高h 为（ ）。

A.11

B.10

C.11至1025之间

D.10至1024之间

【答案】C

【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。

10．—次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）

A. 并行传输

B 串行传输

C. 突发

D. 同步

【答案】C

【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式

11．主机甲与主机乙之间已建立一个TCP 连接，主机甲向主机乙发送了 3个连续的TCP 段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（ ）。

A.300

B.500

C.1200

D.1400

【答案】B

【解析】本题考查TCP 的确认机制，TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的序号为200, 这里主机乙仅 正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500, 因此答案是B 。

第 3 页，共 67 页

12．

对

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

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

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

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

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

【答案】A

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

13．某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）

A.-32768〜+32767

B.-32767〜+32768

C.-65536〜+65535

D.-65535〜+65536

【答案】A

【解析】寄存器个数

指令编址方式如下所示：

16位补码取值范围为-32768〜+32767，所以偏移量取值范围为-32768〜+32767

14．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。

A.257

B.258

C.384

D.385

【答案】C

【解析】由

：

_则和

__可知

，

即显然

384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个

第 4 页，共 67 页 偏移量有32-8-4-4=16位