2017年辽宁石油化工大学计算机与通信工程学院951数据结构考研冲刺密押题
● 摘要
一、填空题
1． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
存放还没有转换过的结点，它的栈顶指针为
。
（1）
{（2）
If （ （3） ）
}
}} 【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
2． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9
3． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
4． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
5． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。 6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
7． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
8． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
9． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
10．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
；
（“图有回路”）
二、算法设计题
11．已知一具有n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非
递归算法。该二叉链表的 链结点结构为（lchild ，data , rchild ）, 其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域 （当孩子结点不存在时，相应指针域为空，用nil 表示）。
【答案】算法如下：
//由二叉树的中序序列IN[]和后序序列POSTt[]建立二叉树
分别是中序序列和后序序列第一和最后元素的下标，初始调用时
，
为栈，容量足够大
//初始化
//取出栈顶数据
//在中序序列中查等于
的结点