2018年江苏省培养单位苏州纳米技术与纳米仿生研究所866计算机原理之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 由3个结点可以构造出多少种不同的有向树？（ ）
A.2
B.3
C.4
D.5
【答案】A
【解析】满足以下条件的有向图称为有向树:①有且仅有一个结点的入度为0；②除树根外结点的入度为1；③从树根到任一结点有一有向通路。
2． 排序过程中, 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中, 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序
Ⅱ. 希尔排序
Ⅲ. 快速排序
Ⅳ. 堆排
Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序, 每一趟排序结束时将确定最大(或最小) 关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
3． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。
4． 下列选项中, 不能改善磁盘设备性能的是（ ）。
A. 重排请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
【答案】B 。
【解析】
磁盘
的一个瓶颈。“重排性能主要是指其读写速度。相对而言,
磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞
性能, 后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘
而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘性能的提升没有什么帮助, 是不能改善磁盘设备性能的, 故答案为B 。
5． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.A VL 树
D. 堆
【答案】D
【解析】堆的定义:
n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :
(1)
(2)
且且或
满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
6． 若用户1与用户2之间发送和接收电子邮件的过程如题40图所示, 则图中①、②、③阶段分别使用的应用层协议可以是（ ）。
图 电子邮件发送接收示意图
A.SMTP 、SMTP 、SMTP
B.POP3、SMTP 、POP3
C.POP3、SMTP 、SMTP
D.SMTP 、SMTP 、POP3
【答案】D 。
【解析】题中电子邮件的工作过程如下:
①用户1调用用户代理来编辑要发送的邮件, 用户代理用SMTP 将邮件传送给用户1的发送端邮件服务器。
②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中, 等待发送。 ③运行在发送端邮件服务器的SMTP 客户进程, 发现在邮件缓存中有待发送的邮件, 就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP 服务器进程发起TCP 连接建立。当TCP 连接建立后, SMTP 客户进程开始向远程的SMTP 服务器发送邮件。当所有的待发邮件发完了, SMTP 就关闭所建立的TCP 连接。
④运行在接收端邮件服务器中的SMTP 服务器进程收到邮件后, 将邮件放人收信人的用户邮箱中, 等待收信人在他方便时进行读取。收信人在打算收信时, 调用用户代理, 使用POP 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回(如果邮箱中有来信的话) 。
SMTP 因此题中1, 2, 3阶段分别使用的应用层协议可以是SMTP , SMTP , POP3, 因此答案是D 。
采用“推”的通信方式, 用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式, 用于用户从目的邮件服务器上读取邮件。
7． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移
24空间，因此最大段长为2B.