n2＋1 。
27．在有n个结点的二叉链表中，空链域的个数为__n＋1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点。 29．深度为5的二叉树至多有 31 个结点。
30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 69 。
31．某二叉树的前序遍历序列是abdgcefh，中序序列是dgbaechf，其后序序列为 gdbehfca 。
32．线索二叉树的左线索指向其 遍历序列中的前驱 ，右线索指向其遍历序列中的后继 。
33．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找法 。
34．在分块索引查找方法中，首先查找 索引表 ，然后查找相应的 块表 。
35．一个无序序列可以通过构造一棵 二叉排序 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
36．具有10个顶点的无向图，边的总数最多为__45__。
37．已知图G的邻接表如图所示，其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4_，其从顶点v1出发的广度优先搜索序列为_v1v2v5v4v3v6__。
38．索引是为了加快检索速度而引进的一种数据结构。一个索引隶属于某个数据记录集，它由若干索引项组成，索引项的结构为 关键字 和 关键字对应记录的地址 。
39．Prim 算法生成一个最小生成树每一步选择都要满足 边的总数不超过n－1 ，
当前选择的边的权值是候选边中最小的 ， 选中的边加入树中不产生回路 三项原则。
40．在一棵m阶B树中，除根结点外，每个结点最多有 m 棵子树，最少有 m/2 棵子树。
三、判断题。
1．在决定选取何种存储结构时，一般不考虑各结点的值如何。（√） 2．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（√ ） 3．抽象数据类型与计算机内部表示和实现无关。（√ ）
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ × ）
5．线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（ × ）
6．对任何数据结构链式存储结构一定优于顺序存储结构。（ × ） 7．顺序存储方式只能用于存储线性结构。（ × ） 8．集合与线性表的区别在于是否按关键字排序。（ × ） 9．线性表中每个元素都有一个直接前驱和一个直接后继。（ × ） 10．线性表就是顺序存储的表。（ × ）
11．取线性表的第i个元素的时间同i的大小有关。（ × ） 12．循环链表不是线性表。（ × ）
13．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。（ √ ）
14．双向链表可随机访问任一结点。（× ）
15．在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面 ：p－＞ next； （× ）
16．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（ × ）
17． 串是一种特殊的线性表，其特殊性体现在可以顺序存储。（ × ） 18．长度为1的串等价于一个字符型常量。（× ） 19．空串和空白串是相同的。（×）
20．数组元素的下标值越大，存取时间越长。（× ）
21．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存
储空间大小只与图中结点个数有关，而与图的边数无关。（√ ） 22．一个广义表的表头总是一个广义表。（× ） 23．一个广义表的表尾总是一个广义表。（ √ ）
24．广义表（（（ a ）， b）， c ） 的表头是（（ a ）， b），表尾是（ c ）。（ √ ）
25．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（ √ ）
26．度为2的有序树是二叉树。（ × ）
27．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（ √ ）
28．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×） 29．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（ × ）
30．在哈夫曼树中，权值最小的结点离根结点最近。（× ） 31．强连通图的各顶点间均可达。（ √ ）
32．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（ × ）
33．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（√ ）
34．在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（√ ） 35．拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。（× ）
36．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ × ） 37．对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。（× ）
38．散列法存储的思想是由关键字值决定数据的存储地址。（√ ） 39．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（× ）
40．具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳
的。（ √）
41．直接选择排序算法在最好情况下的时间复杂度为O（n）。（ × ）
2015年数据结构期末考试题及答案
