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 页 则式子 的值为( )。
相关内容
相关标签