数据结构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