24．稀疏矩阵一般的压缩存储方法有两种，即 三元组表 和 十字链表 。
25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。
26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ 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__。
13
v1v2v3v4v5v6∧∧v2v3v6∧v5v5∧v4∧v4v6v3∧ 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 = s; s->next = p->next; (× ) 16．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出
14
的结构。（ × ）
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)。（ × ）
四、应用简答题。
1．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（1）A ＝ ｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，
r ＝ ｛
r ＝ ｛
r ＝ ｛（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），
15
（4，5），（4，6）｝
2．简述顺序表和链表存储方式的特点。
答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点（增减结点操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问。另外，每个结点上增加指针域，造出额外存储空间增大。
3．对链表设置头结点的作用是什么？（至少说出两条好处） 答：其好处有：
（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
4．对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列。
5．设有4个元素1、2、3、4依次进栈，而栈的操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序。
6．现有稀疏矩阵A如图所示，要求画出三元组表示法和十字链表表示法： ?1500220?15??0133?000???000?600???
000??000?9100000???0028000????
7．设4维数组的4个下标的范围分别为
[-1，0]，[1，2]，[1，3]，[-2，-1]，请分别按行序和列序列出各元素。
8．有一份电文中共使用5个字符：a，b，c，d，e，它们出现的频率依次为4，7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
a9．有如图所示的二叉树，回答如下问题。
（1） 写出该树的中序遍历序列;
bc（2） 写出该树的先序遍历序列;
（3） 写出该树的后序遍历序列；
d16
eghfi