非递归算法，实现求从根结点t到结点p之间的路径。
第六章 图
一、单项选择题
1．下面关于图的存储结构的叙述中正确的是 (1) 。
(1)：A．用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关 B．用邻接矩阵存储图占用空间大小只与图中边数有关，而与顶点数无关 C．用邻接表存储图占用空间大小只与图中顶点数有关，而与边数无关 D．用邻接表存储图占用空大小只与图中边数有关，而与顶点数无关 2．下面关于对图的操作的说法不正确的是 (2) 。 (2)：A:寻找关键路径是关于带权有向图的操作 B．寻找关键路径是关于带权无向图的操作 C．连通图的生成树不一定是惟一的 D．带权无向图的最小生成树不一定是惟一的
3．下面的各种图中，哪个图的邻接矩阵一定是对称的 (3) 。 (3)：A．AOE网 B．AOV网 C．无向图 D．有向图 4．在AOE网中关于关键路径叙述正确的是 (4) 。
(4)：A．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间
B．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所
需的最短时间
C．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所
需的最长时间
D．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所
需的最短时间
5．一个具有n个顶点e条边的图中，所有顶点的度数之和等于 （5）。 (5)：A．n B．2n C．e D．2e 6．具有8个顶点的无向图最多有 (6) 条边。 (6)：A．8 B．28 C．56 D．72 7．具有8个顶点的有向图最多有 (7) 条边。 (7)：A．8 B．28 C．56 D．78 8．深度优先遍历类似于二叉树的 (8) 。
(9)：A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 9．广度优先遍历类似于二叉树的 (9) 。
(9)：A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 10．任一个连通图的生成树 (10) 。
（l0）：A．可能不存在 B．只有一棵 C．一棵或多棵 D．一定有多棵
11
11．下列关于连通图的BFS和DFS生成树高度论述正确的是 （11）。 (11)：A．BFS生成树高度
12．G是一个非连通无向图，共有28条，则该图至少有解 (12) 个顶点。 (12)：A．7 B．8 C．9 D.10 二、判断题
1．一个图的邻接矩阵表示是惟一的。 ( ) 2．一个图的邻接表表示是惟一的。 ( ) 3．无向图的邻接矩阵一定是对称矩阵。 ( ) 4．有向图的邻接矩阵一定是对称矩阵。 ( )
5．有向图用邻接表表示，顶点vi的出度是对应顶点vj链表中结点个数。 ( ) 6．有向图用邻接表表示，顶点vi的度是对应顶点vj链表中结点个数。 ( ) 7．有向图用邻接矩阵表示，删除所有从顶点i出发的弧的方法是，将邻接矩阵的i行全部元素置为0。 ( )
8．若从无向图中任