非递归算法，实现求从根结点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．若从无向图中任一顶点出发，进行一次深度优先搜索，就可以访问图中所有顶点，则该图一定是连通的。 ( )
9．在非连通图的遍历过程中，调用深度优先搜索算法的次数等于图中连通分量的个数。 ( )
10．具有n个顶点的有向强连通图的邻接矩阵中至少有n个小于∞的非零元素。 ( )
11．一个连通图的生成树是一个极小连通子图。 ( ) 12．在有数值相同的权值存在时，带权连通图的最小生成树可能不惟一。 ( ) 13．在AOE网中仅存在一条关键路径。 ( ) 14．若在有向图的邻接矩阵中，主对角线以下的元素均为0，则该图一定存在拓扑有序序列。 ( ) 15．若图C的邻接表表示时，表中有奇数个边结点，则该图一定是有向图。 ( ) 16．在AOE网中，任何一个关键活动提前完成，整个工程都会提前完成。 ( ) 17．图的深度优先遍历序列一定是惟一的。 ( ) 18．有向无环图的拓扑有序序列一定是惟一的。 ( ) 19．拓扑排序输出的顶点个数小于图中的顶点个数，则该图一定存在环。 ( ) 三、填空题
1．在一个具有n个顶点的完全无向图和完全有向图中分别包含有 (1) 和 (2) 条边。 2．具有n个顶点的连通图至少具有 (3) 条边。
3．具有n个顶点e条边的有向图和无向图用邻接表表示，则邻接表的边结点个数分别为（4）和 （5） 条。
12
4．在有向图的邻接表和逆邻接表中，每个顶点链表中链接着该顶点的所有 （6） 和 （7）结点。
5．若n个顶点的连通图是一个环，则它有 (8) 棵生成树。 6．图的逆邻接表存储结构只适用于 (9) 。
7．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度是 （10） ，广度优先算法的时间复杂度是 （11） 。
8．n个顶点e条边的图，采用邻接表存储，广度优先遍历算法的时间复杂度是 （12） ，深度优先遍历算法的时间复杂度是 （13） 。
9．若要求一个稀疏图的最小生成树，最好用 (14) 算法求解。 10．若要求一个稠密图的最小生成树，最好用 （15） 算法求解。 四、应用题
1．已知图C=(V，E)，其中V={a，b，c，d，e}，E={(a，b)，{a，c}，{a，d}，(b，c)，(d，c)，(b，e)，(c，e)，（d，e）}要求： (1)画出图G；
(2)给出图G的邻接矩阵； (3)给出图G的邻接表；
(4)给出图G的所有拓扑有序序列。 2．已知带权无向图的邻接表见下图，要求： 0 1
2 3 4 5 6
(1)画出图G。
(2)各画一棵从顶点a出发的深度优先生成树和广度优先生成树。 (3)给出用prim算法从顶点a出发构造最少生成树的过程。 (4)给出用Kruscal算法构造最小生成树的过程。 3．已知带权有向图如右图所示，要求：
(1)给出图G的邻接矩阵； (2)给出图G的一个拓扑有序序列；
(3)求从顶点a出发到其余各顶点的最短路径。 4．已知带权有向图G见下图，图中边上的权值
13
a b c d e f g 1 0 1 0 0 0 2 9 9 2 3 2 8 8 3 2 3 2 3 1 3 3 2 7 7 4 3 9 4 5 6 4 5 4 4 2 3 8 4 4 4 1 ^ ^ 5 8 ^ 6 6 6 5 9 1 5 5 ^ ^ ^ ^ 为完成活动ai需要的天数，要求：
(1)求每项活动的最早和最晚开工时间；
(2)完成此项工程最少需要多少天； (3)给出图G的关键路径。
四、算法题
1.编写根据无向图G的邻接表，判断图G是否连通的算法。 2．编写根据有向图的邻接表，分别设计实现以下要求的算法： (1)求出图G中每个顶点的出度；
(2)求出图G中出度最大的一个顶点，输出该顶点编号； (3)计算图G中出度为0的顶点数； (4)判断图G中是否存在边〈i，j〉。
第七章 查找
一、单项选择题
1．在长度为n的线性表中进行顺序查找，在等概率的情况下，查找成功的平均查找长度是 (1) 。
(1)：A．n B．n(n+1)／2 C．(n-1)／2 D．(n+1)／2
2．在长度为n的顺序表中进行顺序查找，查找失败时需与键值比较次数是 (2) 。 (2)：A．n B．1 C．n-1 D．n+l
3．对线性表进行顺序查找时，要求线性表的存储结构是 （3） 。 (3)：A．倒排表 B．索引表 C．顺序表或链表 D．散列表 4．对线性表用二分法查找时要求线性表必须是 （4） 。
(4)：A．顺序表 B．单链表 C．顺序存储的有序表 D．散列表
5．在有序表A[80]上进行二分法查找，查找失败时，需对键值进行最多比较次数是 （5） 。
(5)：A．20 B．40 C．10 D．7
6．在长度为n的有序顺序表中，采用二分法查找，在等概率的情况下，查找成功的平均查找长度是 （6）。
(6)：A. O(n) B．O(nlog2n) C．O(n) D．O(log2n)
7．设顺序表为{4，6，12，32，40，42，50，60，72，78，80，90，98}，用二分法查找
14
2
72，需要进行的比较次数是 (7) 。 (7)：A．2 B．3 C．4 D．5
8．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是 (8) 。
(8)：A．顺序查找 B．二分法查找 C．分块查找 D．都不行
9．在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值 (9) 。
(9)：A．一定都是同义词 B．一定都不是同义词 C．不一定是同义词 D．无任何关系
10．在查找过程中，若同时还要做插入、删除操作，这种查找称为 (10) 。 (10)：A．静态查找 B．动态查找 C．内部查找D． 外部查找 二、填空题
1．在有序表A[30]上进行二分查找，则需要对键值进行4次、5次比较查找成功的记录个数分别为 (1) 、 (2) ，在等概率的情况下，查找成功的平均查找长度是 (3) 。 2．散列法存储的基本思想是由 (4) ，确定记录的存储地址。
3．对一棵二叉排序树进行 (5) 遍历，可以得到一个键值从小到大次序排列的有序序列。 4．对有序表A[80]进行二分查找，则对应的判定树高度为 (6) ．，判定树前6层的结点个数为 (7) ，最高一层的结点个数是 (8) ，查找给定值K，最多与键值比较 (9) 次。 5．对于表长为n的线性表要进行顺序查找，则平均时间复杂度为 (10) ，若采用二分查找，则平均时间复杂度为 (11) 。
6．在散列表中，装填因子。值越大，则插入记录时发生冲突的可能性 (12) 。 7．在散列表的查找过程中与给定值K进行比较的次数取决于 (13) 、 (14) 和 (15)。 8．在使用分块查找时，除表本身外，尚需建立一个 (16) ，用来存放每一块中最高键值及 (17) 。
9．若表中有10000个记录，采用分块查找时，用顺序查找确定记录所在的块，则分成 (18)块最好，每块的最佳长度 (19) ，在这种情况下，查找成功的平均检索长度为 (20) 。 10．用n个键值构造一棵二叉排序树，最低高度是 (21) 。
11．设有散列函数H和键值k1、k2，若k1≠k2，且H(k1)= H(k2)，则称k1、k2是 (22)。 12．设有n个键值互为同义词，若用线性探查法处理冲突，把这n个键值存于表长为m(m>n)的散列表中，至少要进行 (23) 次探查。
13.高度为6的平衡二叉排序树，其每个分支结点的平衡因子均为0，则该二叉树共有 (24)个结点。
14．m阶B-树，除根结点外的分支结点最多有 (25) 棵子树，最少有 (26) 棵子树，最多有 (27) 个键值，最少有 (28) 个键值。
15．m阶B+树，除根结点外的每个结点最多有 (29) 棵子树值，最少有 (30) 棵子树。 三、应用题
1．画出对长度为13的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的
15