2017年北京师范大学教育学部894程序设计与数据结构考研强化模拟题
● 摘要
一、填空题
1． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2） 4． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
5．
=_____
【答案】5 6． 假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
第 2 页，共 46 页
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
对应的前缀式为_____，若
则后缀式
的
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
平均查找次数为
7． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
8． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
9． 设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
10．建立索引文件的目的是_____。
【答案】提高查找速度
11．已知二维数组
为1000的连续存储区域时
，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
12．在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
二、判断题
13．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
14．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性
第 3 页，共 46 页
质。
15．倒排文件是对次关键字建立索引。（ ）
【答案】√
，将所有具有相同【解析】倒排文件是对每一个次关键字项建立次关键字索引（称为倒排表）次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
16．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
17．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
18．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】√
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
19．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】√
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
20．两个长度不相同的串有可能相等。（ ）
【答案】
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
21．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
22．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易増加闲置空间的碎片。
（ ） 【答案】√
【解析】最佳适配法：将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给
第 4 页，共 46 页