《南昌航空大学数据结构复习资料》由会员分享，可在线阅读，更多相关《南昌航空大学数据结构复习资料（7页珍藏版）》请在金锄头文库上搜索。
1、南昌航空大学期末考试(计算机科学与技术)数据结构复习资料计算题一. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出 空格处的内容，并画出该二叉树。先序序列：_B_F_ICEH_ G中序序列：D_KFIA_EJC后序序列：_K_FBHJ_G_A解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。二叉树自画！二. 试列出如下图中全部可能的拓扑排序序列。解：全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、 512364三. 已知哈希表地址空间为0.8，哈希函数为H (key)二key%
2、7，采用线性探测再散列处 理冲突，将数据序列100,20,21,35,3,78,99,45依次存入此哈希表中，列出插入时的比较 次数，并求出在等概率下的平均查找长度以及查找因子。解：哈希表及查找各关键字要比较的次数如下所示：后掛上；L117456711):)3冷芋比较次数11141ASL二1 (4X1+1 X2+1 X4+2X5) =8a=8/9四. 已知关键字序列23, 13, 5, 28, 14, 25，试构造二叉排序树。解:IL：VI五. 设有序列：w二23,24,27,80,28，试给出哈夫曼树;哈夫曼树如下图所示:六：已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序
3、列：ABCDEFGHIJ中序序列：CBEDAGHFJI解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部 分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右 孩子结点，由类似的方法可确定其他结点，如下图所示。七. （本题8分）对于如下图所示的G,用Kruska I算法构造最小生成树，要求图示出每一步的变化情况。解：用Kruskal算法构造最小生成树的过程如下图所示: ()(tj(=)八. 给出一组关键字29、18、25、47、58、12、51、10,写出归并排序方法进行排序 时的变化过程。解:(18,29)(25,47)(12,58)(1
4、0,51)(18,25,29,47)(10,12,51,58)(10,12,18,25,29,47,51,58)九. 三、(本题8分)请画出如下图所示的邻接表。解：邻接表如下图所示:十判断以下序列是否是小根堆如果不是，将它调整为小根堆。（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 解：（1）不是小根堆。调整为：12,24,33,65,33,56,48,92,86,70（2）是小根堆。十一.设有如下图所示的AOE网（其中vi （i = l, 2,，6）表示事件，弧上表示活动 的天数）。找出所有的关键路径。解：所有的关键路径有：v1Tv2Tv3Tv5Tv6，以及v1Tv4Tv6。十二. 对给定的有7个顶点的有向图的邻接矩阵如下：（l ）画出该有向图；（2）若将图看成是AOE-网，画出关键路径。g252ggggg2gg8gggg135ggggg5ggggggg39gggggg5ggggggg解：（1）由邻接矩阵所画的有向图如下图所示：2）关键路径如下图所示：
