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

一、单项选择题

1． 主机甲与主机乙之间已建立一个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 。

2．

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

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

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

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

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

【答案】A

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

3． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。

图

A.4

B.3

C.2

D.1

【答案】B

【解析】拓扑排序的步骤为:

(1)在有向图中选一个没有前驱的顶点并且输出它;

(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。

4． 下面关于B 和B+树的叙述中，不正确的是（ ）

A.B 树和B+树都是平衡的多叉树

B.B 树和B+树都可用于文件的索引结构

C.B 树和B+树都能有效地支持顺序检索

D.B 树和B+树都能有效地支持随机检索

【答案】C

【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件:①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k －1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于:有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。

5． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.

【答案】D

m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】

元素依次进行比较, 比较的次数是m 和n 中的最大值。

6． 用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。

A.94，32，40，90，80，46，21，69

B.32，40，21，46，69，94，90，80

C.21，32，46，40，80，69，90，94

D.90，69，80，46，21，32，94，40

【答案】C

7． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

8． 在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.

A. 数据链路层

B. 传输层

C. 会话层

D. 应用层

【答案】B

【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意. 题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输. 所以本题答案应该是B 项. 在OSI 模型中网络层提供的是主机到主机的通信服务.