2017年兰州交通大学电子与信息工程学院828数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
2． 已知程序如下：
{
}
{
}
程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。
A. B. C. D.
【答案】A
【解析】函数S （intn ）是一个递归函数：①当实际参数小于等于零时则返回0, 并终止递归；
，并将S （n-1）的结果加上n 作为返回值。程序从②当实际参数大于零时则递归调用S （n-1）
main （ ）函数开始，首先调用main （ ）函数；在main （ ）函数中调用S （1）
；由于函数S （1）的函数时，将main （ ）函数的上下文保存到栈中，并进入函数S （1）
；在S 实际参数大于零，需要调用S （0）, 故将S （1）函数的上下文保存到栈中，进入S （0）
（0）中，实际参数小于等于零，递归终止。
3． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
4． 若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。
图 电子邮件发送接收示意图
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 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。
因此题中1，2, 3阶段分别使用的应用层协议可以是SMTP ，SMTP , POP3, 因此答案是D 。SMTP 采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。
5． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
：
_
则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为
768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
6． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表
B. 广度优先搜索网
C. 前序（根）遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
7． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。
8． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
相关内容
相关标签