2017年华北电力大学(北京)控制与计算机工程学院842数据结构与操作系统之数据结构考研强化模拟题
● 摘要
一、填空题
1．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
2． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
表示，两栈顶指针为
则
3． 当两个栈共享一存储区时，栈利用一维数组当栈1空时，
【答案】
为_____，栈2空时
，
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
4． 应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
〔始顶点号，终顶点号，权值）
（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在〈limits •h>中
//图的顶点数，应由用户定义
//用二维数组作为邻接矩阵表示
//生成树的边结点
//边的起点与终点
//边上的权值
//最小生成树定义
//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点
//初始化最小生成树
T
//依次求MST 的候选边
//遍历当前候选边集合
//选具有最小权值的候选边
//图不连通，出错处理
//修改候选边集合
【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图
，是N
上最小生成树边的集合。算法从属于
为止。
5．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
E T 开始，重复执行下述操作：在所有u 属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
7． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
8． 实现字符串拷贝的函数strcpy 为：
【答案】
9． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
10．从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
11．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
12．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、选择题
13．设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构 B. 队列
C. 线性表的链式存储结构 D. 栈