南昌航空大学期末考试（计算机科学与技术）南昌航空大学期末考试（计算机科学与技术）数据结构复习资料
计算题一一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。二叉树自画！二．试列出如下图中全部可能的拓扑排序序列。
1234
5
6
1523634、152634、156234、561234、516234、512634、解：全部可能的拓扑排序序列为：512364三．已知哈希表地址空间为08，哈希函数为Hkeykey7，采用线性探测再散列处理冲突，将数据序列1002021353789945依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度以及查找因子。解：哈希表及查找各关键字要比较的次数如下所示：
ASL14×11×21×42×525
8
a89四．已知关键字序列23，13，5，28，14，25，试构造二叉排序树。解：
五．设有序列：w2324278028，试给出哈夫曼树；
1
f哈夫曼树如下图所示：
六：已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。
七．（本题8分）（对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。
解：用Kruskal算法构造最小生成树的过程如下图所示：
八．给出一组关键字29、18、25、47、58、12、51、10，写出归并排序方法进行排序时的变化过程。解：l82925471258l051
l825294710125158l012182529475158
九．三、本题8分）三（本题（请画出如下图所示的邻接表。
2
f解：邻接表如下图所示：
12345211123323345454∧∧∧∧5∧
十．判断以下序列是否是小根堆如果不是，将它调整为小根堆。（1）12703365245648928633（2）0523202840382961357647100解：（1）不是小根堆。调整为：12243365335648928670（2）是小根堆。十一．设有如下图所示的AOE网（其中vi（il，2，…，6）表示事件，弧上表示活动的天数）。
v26v14v48217v311v693v5
找出所有的关键路径。解：所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。十二对给定的有7个r