当前位置:问答库>考研试题

2017年中国海洋大学基础教学中心教育系938数据结构与程序设计之数据结构考研仿真模拟题

  摘要

一、选择题

1. 对于栈操作数据的原则是( )。

A. 先进先出

B. 后进先出

C. 后进后出

D. 不分顺序

【答案】B

【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则,栈限定在表尾进行插入和删除。

2. 在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是( )。

A. 直接插入排序

B. 起泡排序

C. 简单选择排序

D. 快速排序

【答案】A

【解析】当待排序列基本有序时,对冒泡排序来说,若最大关键字位于序列首部,则每趟排序仅能使其“下沉”一个位置,要使其下沉到底部仍需趟排序,也即时间复杂度仍为而对简单选择排序来说,其比较次数与待排序列的初始状态无关;归并排序要求待排序列已经部分有序,而部分有序的含义是待排序列由若干有序的子序列组成,即每个子序列必须有序,并且其时

;直接插入排序在待排序列基本有序时,每趟的比较次数大为降低,也即间复杂度为0(nlog2n )

n-1趟,

比较的时间复杂度由降至

3. ARP 协议的功能是( )。

A. 根据IP 地址查询MAC 地址

B. 根据MAC 地址查询IP 地址

C. 根据域名查询IP ±也址

D. 根据IP 地址查询域名

【答案】A 。

【解析】ARP 协议是网络层协议,因此只能和传输层和数据链路层有关系,从这一点出发,域名是应用层的范畴,选项C 和D 是不正确的,根据MAC 地址查询IP 地址是RARP 协议的功

第 2 页,共 58 页

能,因此进而得出正确答案是A 。

4. 对同一待排序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是( )。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

【答案】D 。

【解析】折半插入排序所需附加存储空间和直接插入排序相同,从时间上比较,折半插入排序仅减少了关键字间的比较次数,

而记录的移动次数不变。折半插入排序的时间复杂度仍为

所以两者之间的不同只可能是元素之间的比较次数。

5. 对如下所示的有向图进行拓扑排序,得到的拓扑序列可能是( ) A. B. C. D.

【答案】D

【解析】拓扑排序方法如下:

(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它;

(2)从图中删去该顶点,并且删去从该顶点发出的全部有向边;

(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止。

对于此有向图进行拓扑排序所有序列为:和所以选D

6. 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是( )。

A. 直接插入排序

B. 起泡排序

C. 基数排序

D. 快速排序

【答案】C

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

第 3 页,共 58 页

7. FTP 客户和服务器间传递FTP 命令时,使用的连接是( )。

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

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

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

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

【答案】A

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

8. 下列关于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 码内容

9. 广义表【答案】D

head 操作就是得到广义表中第一个的原子。【解析】操作就是得到除第一个原子外剩下元

素构成的表。也就是toil 得到的元素需要在外层再加一个( )。

第 4 页,共 58 页 则式子 的值为( )。