发布时间 : 星期五 文章科文学院09z网络数据结构期末复习资料--简答题更新完毕开始阅读
本答案由钱逸敏个人提供，正确性只作参考
0邻接矩阵：????1??1??011010111011101010??1?1??1?0??
邻接表如下图所示：
1234∧2135∧31245∧4135∧5234∧ 19、设有如下图所示的AOE网（其中vi（i=l，2，?，6）表示事件，弧上表示活动的
天数）。
v26v14v48217v311v693v5 （1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。
（1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。 （2）v3事件的最早开始时间是13。
20、如果在1000000个记录中找出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？
采用树形选择排序方法所需的关键字比较次数最少，最多比较次数=999999+?log21000000?=1000019次。
21、假设把n个元素的序列（a1,a2,?an）满足条件ak 不对，例如序列｛3、3、4、2、l｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。 22、设内存有大小为6个记录的缓冲区供内排序使用，文件的关键字序列为｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），试列出： （1）用内排序求出初始归并段； （2）用置换一选择排序求初始归并段。 （1）用内排序求出初始归并段为： 本答案由钱逸敏个人提供，正确性只作参考 归并段1：29,33,38,50,60,70: 归并段2：9,25,28,31,36,43 归并段3：2,18,57,65,80,100: 归并段4：14,17,20,30,78,99. （2）用置换一选择排序求初始归并段为： 归并段1：29,33,38,50,60,70,80,100 归并段2：9,18,25,28,31,36,57,65,78,99; 归并段3：2,14,17,20,30. 23、已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 用链地址法处理冲突的哈希表如下图所示： ASL= 112(1*6+2*4+3*1+4*1)=1.75 24、已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 构造二叉排序树的过程如下图所示。 构造的二叉排序树如下图所示： 25、试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n的查找表来说，三种查找法在查找成功时的查找长度各是多少？ 三种方法对查找的要求分别如下： 本答案由钱逸敏个人提供，正确性只作参考 ? ? ? 顺序查找法：表中元素可以任意存放； 折半查找法：表中元素必须以关键字的大小递增或递减的次序存放： 分块查找法：表中元素每块内的元素可任意存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大于（或小）后一块内任何元素的关键字。 n?12三种方法的平均查找长度分别如下： ? ? 顺序查找法：查找成功的平均查找长度为 ； 折半查找法：查找成功的平均查找长度为log2(n+1)+1； 1n(?s)?1；若用折半确定所2s分块查找法：若用顺序查找确定所在的块，平均查找长度为在块，平均查找长度为log2(ns?1)?s2。 26、设有一个输入数据的序列是{ 46, 25, 78, 62, 12, 80 }，试画出从空树起，逐个输入各个数据而生成的二叉排序树。 如下图所示： 27、给定一个关键字序列｛24，19，32，43，38，6，13，22｝，请写出快速排序第一趟的结果；堆排序时所建的初始堆；然后回答上述两种排序方法中哪一种方法使用的辅助空间最小，在最坏情况下哪种方法的时间复杂度最差？ 快速排序的第一趟结果为｛22,19,13,6,24,38,43,12｝；堆排序时所建立的初始大顶堆如所图所示： 两种排序方法所需辅助空间：堆是O(1)，快速排序是O(logn)，可见堆排序所需辅助空间较少；在最坏情况下两种排序方法所需时间：堆是O(nlogn)，快速排序是O(n2)，所以，可见快速排序时间复杂度最差。 ? 注意：快速排序的平均时排序速度最快，但在最坏情况下不一定比其他排序方法快。 28、设二维数组A[0:10,-5:0]，按行优先顺序存储，每个元素占4个单元，A[0][-5]的存储地址为1000，则A[9][-2]的存储地址为多少？ 依题意A的起始地址为1000，则有： Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。 29、用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访 本答案由钱逸敏个人提供，正确性只作参考 问结点序列。 先画出该二叉树的树形结构。对其进行后序遍历得到后序序列为：HIDJKEBLFGCA。 30、请说明对一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？ 二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。 31、对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。 用Kruskal算法构造最小生成树的过程如下图所示： 32、已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。