2018年电子科技大学电子科学技术研究院820计算机专业基础之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 在单链表中设置头结点的作用是_____。
【答案】方便运算
2． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
3． 模式串
【答案】01122312
4． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
5． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
。 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺的next 函数值序列为_____。
二、单项选择题
6． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、
传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。
7． 若用户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采用“拉”的通信方式, 用于用户从目的邮件服务器上读取邮件。
8． 已知循环队列存储在一维数组中, 且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在
的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
处, 则初始时front 和rear
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执
行, 则初始时front 的值为0、rear 的值为n-1。
9． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
10．对进行基数排序，一趟排序的结果是:（ ）
A. 05， 46， 13， 55， 94， 17， 42 B.
C. 42，13， 94，05， 55， 46，17
D. 05，13， 46，55，17，42，94
【答案】C
【解析】基数排序有两种:最低位优先和最高位优先。
①最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
②以r 为基数的最低位优先排序的过程 假设线性表由结点序列
成，
其中
分配:开始时，把
收集:把
线性表。
11．若需在
（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:
表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是