2017年北京理工大学计算机学院889数据结构[专业硕士]考研强化模拟题
● 摘要
一、填空题
1． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】 2． 假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
第 2 页，共 64 页
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
4． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
存放还没有转换过的结点，它的栈顶指针为
。
（1）
{（2）
If （ （3） ）
}
}} 【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
5． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
6． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
第 3 页，共 64 页
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
7． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
8． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。
9． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为一个元素时，此时堆的元素个数最少，元素个数为
10．数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
当最后一层只有
二、选择题
11．若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵 B. 稀疏矩阵 C. 三角矩阵 D. —般矩阵 【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在 图中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
第 4 页，共 64 页