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

一、单项选择题

1． 用有向无环图描述表达式

A.5

B.6

C.8

D.9

【答案】A ，至少需要顶点的数目为（ ）。

，6条边【解析】一共5个结点

2． 下面关于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 项错误。

3． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。

A. 分块

B. 顺序

C. 折半

D. 哈希

【答案】A

【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。

4． 数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。

A.1

B.2

C.3

D.4

【答案】B

【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。

5． 5个字符有如下4种编码方案, 不是前缀编码的是（ ）

A.01, 0000, 0001, 001, 1

B.011, 000, 001, 010, 1

C.000, 001, 010, 011, 100

D.0, 100, 110, 1110, 1100

【答案】D

【解析】在一个字符集中, 任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符„0‟, 右分支表示字符„1‟, 则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中, 编码110是编码1100的前缀, 故不符合前缀编码的定义

6． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. B. C. D.

【答案】C

【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。

7．

参考模型的网络层提供的是（ ）。

A. 无连接不可靠的数据报服务

B. 无连接可靠的数据报服务

C. 有连接不可靠的虚电路服务

D. 有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。

8． 下列关于IP 路由器功能的描述中, 正确的是（ ）。

Ⅰ. 运行路由协议, 设置路由表;

Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;

Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失;

Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。

A. 仅Ⅲ、Ⅳ

B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅱ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】C 。

【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不

保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。

9． 已知循环队列存储在一维数组中, 且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在

的值分别是（ ）。

A.0, 0

B.0, n-1

C.n-1, 0

D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执

行, 则初始时front 的值为0、rear 的值为n-1。

10．若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。

A. 对称矩阵

B. 稀疏矩阵

C. 三角矩阵

D. —般矩阵

【答案】C

【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图

中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。

处, 则初始时front 和rear