数据结构习题集 下载本文

非递归算法,实现求从根结点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生成树高度DFS生成树的高度 D.BFS生成树高度≥DFS生成树的高度

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