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

一、选择题

1． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）

A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C

【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

2． 最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。

A.

B.

C.

D. 【答案】B

【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采

用

来判定队满，其中

3． 下列说法不正确的是（ ）。

A. 图的遍历是从给定的源点出发每个顶点仅被访问一次 B. 遍历的基本方法有两种：深度遍历和广度遍历 C. 图的深度遍历不适用于有向图 D. 图的深度遍历是一个递归过程 【答案】C

【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的

表示队列的长度。

所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。

4． 执行完下列语句段后，f 值为（ ）。

A.2 B.4 C.8

D. 无限递归 【答案】B

【解析】该程序使用了递归调用，由题知，所以结果为4。

5． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A. 顺序表 B. 双链表

C. 带头结点的双循环链表 D. 单循环链表 【答案】A

【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。

6． 设哈希表

长哈希函

数表中已有4个结点

：

其余地址为空，如用二次探测

再哈希法解决冲突，关键字为49的结点的地址是（ ）。

【答案】D

【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：

仍然发生冲突。

仍然发生冲突。

不再发生冲突。

计算后得地址：4，5，6，7。49计算后

7． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。

A.1000 B.2000 C.3000 D.4000 【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，=2000字节，于是此时发送方的发送窗口为min{4000, 2000）由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节，正确选项为A 。

8． 在’

A.PPP B.IP C.UDP D.TCP

体系结构中，直接为ICMP 提供服务的协议是（ ）。

【答案】B 。

【解析】首先明确ICMP 是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层，在网络层上面，所以显然错误，而PPP 协议是广域网数据链路层协议，直接为网络层，也就是IP 层提供服务，ICMP 协议是封装在网络层，因此PPP 不能直接为ICMP 提供服务，ICMP 报文直接封装在IP 分组中，故答案是B 。

9． 用直接插入排序方法对下面4个序列进行排序，

（由小到大）元素比较次数最少的是（ ）。

【答案】C

10．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）

A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94

【答案】C

【解析】基数排序有两种：最低位优先和最高位优先。

最低位优先的过程

先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。