数据结构c语言版期末考试复习试题[1]

A56BE3G115F 24C3D19．给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。

13425

图 一个无向图G20．使用普里姆算法构造出如图所示的图G的一棵最小生成树。

21

1615552342364656

图 一个无向图G21．使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。

16234725181225815107543620图 一个无向图G

22．设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。 中序：1 4 3 5 6 2 后序：4 6 5 3 2 1

22

23．设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。 24．设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。

123465725．设有如图所示的一棵树，请将其转化为二叉树。

1214458101226．下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题： （1）画出相应的AOE图；

36711913 23

（2）给出各事件的最早发生时间和最晚发生时间； （3）找出关键路径，并指明完成该工程所需最短时间；

（4）若把AOE网视为AOV网，给出其一个拓扑序列的例子。 工序A 代号 时间 15 先驱－ 工作 B C D E F G H I J K L M M 10 50 8 15 40 90 15 80 60 15 30 20 40 － A,B B C,D B E G,I E I F,I H,J,K L G

27．某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。

AFBGED

28．求如下AOE图的关键路径，要求给出求解过程。

24

C