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

一、选择题

1． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n） 【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）

2． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下：

则并发执行进程

和

时产生的情况是（ ）。

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象 B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象 C. 能保证进程互斥进入临界区，会出现“饥饿”现象 D. 能保证进程互斥进入临界区，不会出现“饥饿”现象 【答案】D

【解析】这是皮特森算法（Peterson ’S Algorithm ）的实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量turn , 表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。先到先人，后到等待，从而完成临界区访问的要求。

3． n 个顶点的无向图的邻接表最多有（ ）个表结点。

A.IT B.n （n-l ） C.n （n+l） D.n （n-l ）/2

【答案】B

【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n-1个结点连接，从而会产生n （n-l ）个表结点。

4． TCP/IP参考模型的网络层提供的是（ ）。

A. 无连接不可靠的数据报服务 B. 无连接可靠的数据报服务 C. 有连接不可靠的虚电路服务 D. 有连接可靠的虚电路服务 【答案】A

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

5． 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：

第一趟：2，12，16, 5，10，88

第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序 【答案】A

【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”

序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”

6． 下列关于SMTP 协议的叙述中，正确的是（ ）

I. 只支持传输7比特ASCII 码内容 II. 支持在邮件服务器之间发送邮件 III. 支持从用户代理向邮件服务器发送邮件 IV . 支持从邮件服务器向用户代理发送邮件

A. 仅 I 、II 和 III B. 仅 I 、II 和 IV C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV 【答案】A

【解析】根据下图可知，SMTP 协议支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASCII 码内容

7． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）

A .10 Mbps B. 20 Mbps C.80 Mbps D.100 Mbps 【答案】C

【解析】

8． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。

A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序 【答案】C

【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。

9． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。

A.0 B.1 C.2