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

一、单项选择题

1． 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 （ ）

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为

2． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

3． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107

B.108

C.214

D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。

4． 某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息“＜netl ，16＞”，则能得出的结论是（ ）.

A.R2可以经过R1到达netl ，跳数为17

B.R2可以到达netl ，跳数为16

C.R1可以经过R2到达netl ，跳数为17

D.R1不能经过R2到达netl

【答案】D

【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，因此RIP 协议里规定16为路由不可达，答案为D.

5． 某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机

A.

C.

D. 和和 B.{2, 3}和{1} 和

{1}

向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）

【答案】B

【解析】

第一次交换机没有

这个数据报源MAC 地址的信息的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了所以只用从1端口转发。

6． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。

7． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:

①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。

然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:

A. 左子树为空, 右子树为cd ;

b. 左子树为c , 右子树为d ;

c. 左子树为cd , 右子树为空。

按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。

8． 下面关于求关键路径的说法不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的

B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D. 关键活动一' 定位于关键路径上

【答案】C

【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。

9． 两台主机之间的数据链路层采用后退N 帧协议(GBN)传输数据, 数据传输速率为16kbps , 单向传播时延为270ms , 数据帧长度范围是字节, 接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高, 帧序号的比特数至少为（ ）。

A.5