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

一、选择题

1． 下列关于图的叙述中，正确的是（ ）。

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间

III. 若有向图中存在拓扑序列，则该图不存在回路

A. 仅 II

B. 仅 I 、II

C. 仅III

D. 仅 I 、III

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项I 错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项II 错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项III 正确。

2． 下列调整中，不可能导致饥饿现象的是（ ）

A. 时间片转移

B. 静态优先及调度

C. 非抢占式作业优先

D. 抢占式短作业优先

【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

3． 在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。

【答案】D

【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于

上。

4． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。

A. 建立在TCP 之上的控制连接

B. 建立在TCP 之上的数据连接

C. 建立在UDP 之上的控制连接

D. 建立在UDP 之上的数据连接

【答案】A

【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。

5． 下列网络设备中，能够抑制广播风暴的是（ ）。

中继器

集线器

网桥

路由器

A.

仅

和

B.

仅

C.

仅

D. 仅 和 的结点

【答案】D

【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。

6． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。

A.CSMA

B.CDMA

C.CSMA/CD

D.CSMA/CA

【答案】D

【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当

客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。

7． 可以用（ ）定义一个完整的数据结构。

A. 数据元素

B. 数据对象

C. 数据关系

D 抽象数据类型

【答案】D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。

8． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。

A. 每次分区后，先处理较短的部分

B. 每次分区后，先处理较长的部分

C. 与算法每次分区后的处理顺序无关

D. 以上三者都不对

【答案】A

【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为

9． 以下说法错误的是（ ）。

（2）在相同的规模n 下，复杂度整个f 的最大深度为递归深度。 （1）算法原地工作的含义是指不需要任何额外的辅助空间 的算法在时间上总是优于复杂度的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A. （1）

B. （1）, （2）

C. （1）, （4）

D. （3）

【答案】A

【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。