题1

(10’)编写程序，判断两个单向链表所表示的线性表是否等价。两个线性表等价是指：两个线性表长度相同、数据相同且数据存放的顺序一致。
具体要求：
（1）假设链表的结点结构、结点的型以及位置的型定义如下：

typedef int elementtype;
struct celltype{
   
	elementtype element;
	celltype *next;
}; 
typedef celltype *LIST;
typedef celltype *position;

（2）定义函数int equal(LIST L1, LIST L2)，判断L1与L2是否等价，如果等价，函数返回1，否则返回0。
（3）假设两个线性表的长度分别是m和n，试分析函数equal的时间复杂度。

参考答案

题2


具体要求：
（1）画出该图，并写出该图的矩阵表示。
（2）写出该图的一个拓扑序列。
（3）写出拓扑排序算法的基本步骤。
（4）编写函数void topSort(MTGraph g, int ret[])，求图g的一个拓扑序列，结果放在参数ret中。其中MTGraph为邻接矩阵表示的图结构，定义如下：

typedef struct {
   
    char vexlist [9]; 	//顶点表
    int edge[9][9];
    int n, e;
}MTGraph;

假设已定义一个数据类型为整型的队列queue及其相关操作：将一个元素加入队列void push(queue &q, int v)；删除队头元素void pop(queue &q)；判断队列是否为空int empty(queue q)，队列为空返回1，否则返回0。

参考答案


题3

(10’)已知二叉树的中根序列是BHCIAEDGF，后根序列是HICBEGFDA，画出此二叉树以及该二叉树的先序线索二叉树。
具体要求：
（1）根据给定的中根序列和后根序列，画出此二叉树。
（2）写出该二叉树的先根序列。
（3）简要说明线索二叉树中哪些是线索，并简要说明线索二叉树中线索的指向规则（以先序线索二叉树为例说明）。
（4）画出由（1）得到的二叉树的先序线索二叉树（带头结点）。

参考答案

题4

(15’)给定叶子结点的权值集合{10, 4, 8, 9, 7, 12, 16, 23}，构造相应的哈夫曼（霍夫曼）树，并计算其带权路径长度。
具体要求：
（1）简要说明哈夫曼树构造步骤。
（2）对于给定的数据，构造哈夫曼树，要求画出构造的每一步中间过程。
（3）根据构造的哈夫曼树，计算其带权路径长度。

参考答案

题5

(15’)下图是一个无向带权图，利用Kruskal算法求其最小生成树。

具体要求：
（1）简要说明Kruskal算法的基本思想，重点说明什么情况下某条边会被加入到生成树中，并说明在实现时用什么方法判断。
（2）画出利用Kruskal算法求给定图的最小生成树的过程，要求画出每添加一条边的中间图，并注明加入和舍弃某条边的理由。

参考答案

题6

(15’)给定数据集S={25, 12, 17, 8, 3, 29, 32, 23, 27, 36, 22}，要求利用该数据集生成一棵AVL树。
具体要求：
（1）什么是平衡因子？简要说明在插入一个数据时，如何找到第一个不平衡点。
（2）有哪四种旋转类型？画出四种旋转类型的图形样式。
（3）画图说明LR旋转的旋转方法。
（4）根据给定的数据集S，从第一个数据开始，依次将给定的数据加入到AVL树中，要求画出每步所产生的中间AVL树，如果需要旋转，请指明旋转类型。

参考答案

题7

(15’)给定如下图所示三阶B-树：

（1）对于三阶B-树，说明根节点中关键字数量的限定范围。
（2）对于三阶B-树，说明非根结点中关键字数量的限定范围。
（3）对于三阶B-树，当插入一个数据时，什么时候需要分裂一个结点？简要说明如何对一个结点进行分裂。
（4）试画出依次插入12、25和85后得到的B-树。如果需要分裂，说明是如何分裂的。

参考答案