科文学院09z网络数据结构期末复习资料
三、简答题
1、已知一个6⨯5稀疏矩阵如下所示，试：
（1）写出它的三元组线性表；
（2）给出三元组线性表的顺序存储表示。
（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))
（2）三元组线性表的顺序存储表示如下所示：
2、求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？
求网的最小生成树可使用Prim算法，时间复杂度为O(n2)，此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。
3、对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序的，试写出：
（1）从顶点v1出发进行深度优先搜索所得到的深度优先生成树；
（2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。
（1）DFS：v1 v2 v3 v4 v5
（2）BFS：v2 v3 v4 v5 v1
4、已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序的，试给出得到的拓扑排序的序列。
拓扑排序为： 4  3  6  5  7  2  1
5、对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。
所构造的堆如下图所示：
6、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。
先序序列：BFICEHG
中序序列：DKFIAEJC
后序序列：KFBHJGA
在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。
7、设有序列：w={23,24,27,80,28}，试给出：
（1）二叉排序树；
（2）哈夫曼树；
（3）平衡二叉树；
（4）对于增量d=2按降序执行一遍希尔排序的结果。
（1）二叉排序树如下图所示：
（2）哈夫曼树如下图所示：
（3）平衡二叉树如下图所示：
（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23
8、有关键字序列{7,23,6,9,17,19,21,22,5}，Hash函数为H(key)=key % 5，采用链地址法处理冲突，试构造哈希表。
哈希表如下图所示：
9、假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。
先序： a,b,c,d,e,f
中序： c,b,a,e,d,f
后序： c,b,e,f,d,a
按层： a,b,d,c,e,f
10、已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示：
（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
【解答】
（1）该图的图形如下图所示：
（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。
11、树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？
树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。
12、设有数组A[-1:3,0:6,-2:3]，按行为主序存放在2000开始的连续空间中，如元素的长度是5，试计算出A[1,1,1]的存储位置。
A[1,1,1]的存储位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。
13、试列出如下图中全部可能的拓扑排序序列。
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
14、已知哈希表地址空间为先序中序后序遍历二叉树0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查长度。
哈希表及查各关键字要比较的次数如下所示：
ASL=(4×1+1×2+1×4+2×5)=2.5
15、设有一个输入数据的序列是 {46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
16、试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：
波兰式表示：*+a/bc-d*ef
中缀表示：a+b/c*d-e*f
逆波兰式表示：abc/+def*-*
17、已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};       
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
用克鲁斯卡尔算法得到的最小生成树为： 
(1,2)3,(4,6)4, (1,3)5,(1,4)8,(2,5)10,  (4,7)20
18、请画出如下图所示的邻接矩阵和邻接表。
邻接矩阵：
邻接表如下图所示：
19、设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，弧上表示活动的天数）。
（1）出所有的关键路径。
（2）v3事件的最早开始时间是多少。
（1）出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。
（2）v3事件的最早开始时间是13。
20、如果在1000000个记录中出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？
采用树形选择排序方法所需的关键字比较次数最少，最多比较次数=999999+=1000019次。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。