资源描述：
《南昌航空大学数据结构复习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、南昌航空大学期末考试（计算机科学与技术）数据结构复习资料计算题一.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。二叉树自画！二．试列出如下图中全部可能的拓扑排序序列。解：全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364三．已知哈希表地址空
2、间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度以及查找因子。解：哈希表及查找各关键字要比较的次数如下所示：ASL=(4×1+1×2+1×4+2×5)=2.5a=8/9四．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。解：五．设有序列：w={23,24,27,80,28}，试给出哈夫曼树；哈夫曼树如下图所示：六：已知一棵二叉树的先序序
3、列与中序序列分别如下，试画出此二叉树。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。七．（本题8分）对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。解：用Kruskal算法构造最小生成树的过程如下图所示：八．给出一组关键字29、18、25、47、58、12、51、1
4、0，写出归并排序方法进行排序时的变化过程。解：(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,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
5、,33,65,33,56,48,92,86,70}（2）是小根堆。十一．设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，弧上表示活动的天数）。找出所有的关键路径。解：所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。十二.对给定的有7个顶点的有向图的邻接矩阵如下：（l）画出该有向图；（2）若将图看成是AOE-网，画出关键路径。解：（1）由邻接矩阵所画的有向图如下图所示：（2）关键路径如下图所示：
