2018年燕山大学信息科学与工程学院811数据结构考研核心题库
● 摘要
一、填空题
1． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
2． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何
置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素
成_____，若
【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边
中，其下标值最大的分支结点为_____。 3． 设有N 个结点的完全二叉树顺序存放在向量
【答案】
【解析】最大的分支结点是最后一个叶子结点的父结点。
4． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
5． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
6． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
二、判断题
7． 二叉树是一般树的特殊情形。（ ）
【答案】×
【解析】树与二叉树是两种不同的树形结构，二叉树中的孩子结点有着严格左右之分的。
8． 不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
【解析】对于一个带权连通无向图G=(V，E) , 生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
9． 一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
【答案】 √
【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。
10．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
11．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。
12．通常使用队列来处理函数或过程的调用。（ ）
【答案】 ×
【解析】经常使用栈来处理函数或过程的调用。
三、读写算法题
13．设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
14．已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。
【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素 结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点
f
从结点c 的双亲结点直到根结点，
路径上所有结点均为祖先结点
逆序输出，最老的祖先最后输出
结束
15．以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标