发布时间 : 星期六 文章数据结构c语言版期末考试 - 图文更新完毕开始阅读
17．对有五个顶点{v1,v2,v3,v4,v5}的图的邻接矩阵如图所示，解答下列问题： （1）画出逻辑图。
（2）画出该逻辑结构的邻接表。
（3）基于邻接矩阵写出图的深度、广度优先遍历序列。
?010030?10? ??0???? ????60020??
???10?0? ??? ????500??
18．如图所示，解答如下问题：
（1）写出从定点A出发，深度和广度优先遍历方法遍历该图的顶点序列。 （2）根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构造过程。
A56BE3G115F4C32D 21
19．给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。
13425
图 一个无向图G
20．使用普里姆算法构造出如图所示的图G的一棵最小生成树。
1615552342364656图 一个无向图G
21．使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。
16234725181225815107543620图 一个无向图G
22．设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。
22
中序：1 4 3 5 6 2 后序：4 6 5 3 2 1
23．设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。
24．设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。
1234657
25．设有如图所示的一棵树，请将其转化为二叉树。
1214458101213911673 26．下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题： （1）画出相应的AOE图；
（2）给出各事件的最早发生时间和最晚发生时间； （3）找出关键路径，并指明完成该工程所需最短时间； （4）若把AOE网视为AOV网，给出其一个拓扑序列的例子。 工序A 代号 B C D E F G H I J K L M M 时间 15 10 50 8 15 40 90 15 80 60 15 30 20 40 23
先驱－ － A,B B 工作 C,D B E G,I E I F,I H,J,K L G
27．某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。
AFBGED
28．求如下AOE图的关键路径，要求给出求解过程。
24
C