数据结构单元自测题

2 从邻接矩阵A=??010??可以看出,该图共有(1)____个顶点.如果是有向图,该图共有(2)____条弧;如果是无向101??图,则共有(3)____条边.

(1) A) 9 B) 3 C) 6 D) 1 E) 以上答案均不对 (2) A) 5 B) 4 C) 3 D) 2 E) 以上答案均不对 (3) A) 5 B) 4 C) 3 D) 2 E) 以上答案均不对

3 对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表向量的大小为(1)____,所有顶点的邻接表的结点总数为(2)____.

(1) A) n B) n+1 C) n-1 D) n+e (2) A) e/2 B) e C) 2e D) n+e

4 已知一有向图的邻接表存储结构如图6.60所示.则按深度优先遍历算法从顶点V1出发,所得到的顶点序列为(1)____;按广度优先

遍历算法从顶点V1出发,所得到的顶点序列为(2)_____.

A) V1,V2,V3,V5,V4 B)V1,V2,V3,V4,V5 C)V1,V3,V4,V5,V2 D)V1,V3,V2,V4,V5 E)V1,V2,V4,V5,V3 5 给定一无向图G如图6.61所示,下列哪些是由顶点1 1 12 出发的深度优先搜索序列_____.

1 2 A) 1243 B) 1234 C) 1342 D) 1324 E)1423 15 2 3 5 6 图的应用算法有_____.

A) 克鲁斯卡尔算法 B) 哈夫曼算法 C)迪杰斯特拉算法 4 20 3 D) 欧几里得算法 E) 拓扑排序算法 6 10 图6.61 无向图

8 4 5 三 填空题

1 如果含n个顶点的图形成一个环,则它有___棵生成树.

4 9 2 一个非连通无向图,共有28条边,则该图至少有___个顶点.

6 3 具有10个顶点的无向图,边的总数最多为____.

4 对于如图6.62所示的图,用Prim算法从顶点①开始求最小生成树,按次序产生的边为___, 图6.62 无向图 共____条边; 用Dijkstra算法产生的边的次序是_____.(注: 边用( i,j )的形式表示) 5 在有n个顶点的有向图中,每个顶点的度最大可达_____.

V1 6 设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为____. 7克鲁斯卡尔算法的时间复杂度为____,它对___图较为适合.

8 遍历图的过程实质是____.Breadth-first search 遍历图的时间复杂度为____, V3 V2 depth-first search遍历图的的时间复杂度为___,

两者不同之处在于_____,反映在数据结构上的差别是_____. 9 设有向图G如图6.63所示.(1)写出所有的拓扑序列:_____.

V4 (2)添加弧___后,则仅可能有唯一的拓扑序列. 10 遍历图的基本方法有深度优先搜索和广度优先搜索, 图6.63 无向图 其中_____是一个递归过程.

11 若一个连通图中每个边上的权值均不同,则得到的最小生成树是____的.

12 设图G有n个顶点和e条边,则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为____,而用邻接表

表示的图进行深度或广度优先搜索遍历时的时间复杂度为____;图的深度或广度优先搜索遍历时的时间复杂度为____.

13 深度优先搜索遍历类似于树的____遍历, 它所用到的数据结构是___;

广度优先搜索遍历类似于树的____遍历,它所用到的数据结构是_____. 14 一个图的____表示法是唯一的,而___表示法是不唯一的.

15 对无向图,若它有n个顶点e条边,则其邻接表中需要____个结点.其中,____个结点构成邻接表,___个结点构成顶点表 .

16 有n个顶点的有向图,至少需要____条弧才能保证是连通的.

17 求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则

当图的顶点数

为40时,计算时间为___ms.

18 一个连通图的_____是一个极小连通子图.

19 在AOE网中,从源点到汇点路径上各活动的时间总和最长的路径称为____. 20 n个顶点的连通图用邻接矩阵表示时,该矩阵至少有____个非零元素. 21有向图中的结点前驱后继关系的特征是____.

22 Prim算法适用于求____的网的最小生成树;Kruskal算法适用于求_____网的最小生成树. 23 AOV网是_____有向图.

24 有向图的极大强连通子图称为____

25 在一个具有n个顶点的无向完全图中,包含有____条边;在一个具有n个顶点的有向完全图中,包含有____条边.

26 根据图的存储结构进行某种次序的遍历,得到的顶点序列是____的.

27 对含有n个顶点e条边的无向连通图,利用Prim算法生成最小生成树的时间复杂度为_____. 利用Kruskal算法生成最小生成树的时间复杂度为_____.

28 若无向图G的顶点度数最小值大于等于____时,G至少有一条回路. 29 连通分量是无向图中的___连通分量.

30 从源点到汇点长度最长的路径称关键路径,该路径上的活动称____.

四 判断题

1 在n个结点的无向图中,若边数>n-1,则该图必是连通图.

2 若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑有序序列必定存在. 3 已知一有向图的邻接矩阵An×n ,其顶点vi的入度为

?[j,i].

j?1nn 4 已知一有向图的邻接矩阵An×n ,其顶点vi的出度为

?[j,i].

j?1 5 任何AOV网拓扑排序的结果都是唯一的. 6有回路的图不能进行拓扑排序.

m

7 用邻接矩阵A表示图,判定任意两个结点vi和 vj之间是否有长度为m的路径相连,则只要检查A的第i行第j列的元素

是否为0即可.

8 对于一个有向图,除了拓扑排序方法外,还可以通过对有向图进行深度优先遍历的方法来判断有向图中是否有环存在.

9 一个图的广度优先搜索树是唯一的.

10 图的深度优先搜索序列和广度优先搜索序列不是唯一的.

11 有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半. 12 若连通图上各边权值均不相同,则该图的最小生成树是唯一的.

13 无向图的邻接矩阵一定是对称矩阵,且有向图的邻接矩阵一定是非对称矩阵.

14 用邻接矩阵存储一个图时,所占用的存储空间大小只与图中结点的个数有关,而与图的边数无关. 15 邻接表只能用于存储有向图,而邻接矩阵则可以存储有向图和无向图. 16 无向图的邻接矩阵是对称的,因此可只存储邻接矩阵的上(或下)三角阵. 17连通分量是无向图中的极小连通子图.

18强连通分量是有向图中的极大强连通子图.

19 如果连通网中存在相同权值的边,则最小生成树不唯一. 20 用邻接矩阵表示图时,矩阵元素的个数与边的条数有关.

第七章 查找 一 选择题

1 设有一个按各元素的值排好序的线性表且长度大于2,对给定的值K,分别用顺序查找法和二分查找法查找一个与K相等的元素,

比较次数分别是s和b;在查找不成功的情况下,正确的s和b的数量关系是____. A) s=b B) s>b C) s

3 关于杂凑查找说法不正确的有___个. A) 1 B) 2 C) 3 D) 4 (1) 采用链地址解决冲突时,查找一个元素的时间是相同的;

(2) 采用链地址解决冲突时,若规定插入总是在链首,则插入任一个元素的时间是相同的; (3) 采用链地址解决冲突易引起聚集现象; (4) 用哈希法不易产生聚集

4 对有18个元素的有序表作二分(折半)查找,则查找A[3]的比较序列的下标为____. A) 1,2,3 B) 9,5,2,3 C) 9,5,3 D) 9,4,2,3

5 若在线性表中采用折半查找法查找元素,该线性表应该____.

A)元素按值有序 B)采用顺序存储结构 C)元素按值有序且采用顺序存储结构 D)元素按值有序且采用链式存储结构

6 在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与_____量级相当. A) 顺序查找 B) 折半查找 C) 前两者均不正确

8 假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行___次探测. A) k-1 B) k C) k+1 D) k(k+1)/2

9 具有5层结点的AVL树至少有____个结点. A) 10 B) 12 C) 15 D) 17

11 设散列地址空间0~m-1,k为关键字,用P去除k,将余数作为k的散列地址,即h(k)=k%P,为了减少发生冲突的可能性,

一般取P为_____. A)小于m的最大奇数 B)小于m的最大素数 C)小于m的最大偶数 D)小于m的最大合数

12 设散列表的长m=14,散列函数h(k)=k,表中已有4个记录(如图7.61所示),如果用二次探测散列来处理冲突,则关键字

为49的记录其存储地址是_____. A) 8 B) 3 C) 5 D) 9

0 1 2 3 4 5 6 7 8 9 10 11 12 13

15 38 61 84 图7.61 散列表

13 从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为_____.

2

A) O(n) B) O(1) C) O(log2n) D) O(n)

14 在采用线性探测法处理冲突的闭散列表上，假定装填因子α的值为0.5,则查找任一元素的平均查找长度为____.

A) 1 B) 1.5 C) 2 D) 2.5

15在采用链接法处理冲突的开散列表上，假定装填因子α的值为4,则查找任一元素的平均查找长度为____. A) 3 B) 3.5 C) 4 D) 2.5 17 以下说法错误的是______.

A) 散列表存储的基本思想是由关键码值决定数据的存储地址

B) 散列表的结点中只包含数据元素自身的信息,不包含任何指针 C) 装填因子是散列法的一个重要参数,它反映了散列表的装填程度

D) 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法

18 设有一个用线性探测法解决冲突得到的散列表如图7.62所示: 散列函数为H(k)=k,若要查找元素14 ,探测的次数是___. A) 8 B) 9 C) 3 D) 6 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 图7.62 散列表

19 设散列函数为H(k)=k%7,一组关键码为23,14,9,6,30,12,18,散列表T的地址空间为0~6,用线性探测法解决冲突,依次将这组

关键码插入T中,则得到的散列表为____. 0 1 2 3 4 5 6

0 1 2 3 4 5 6 A) B) 14 6 23 9 18 30 12 14 18 23 9 30 12 6

C) D) 0 1 2 3 4 5 6

0 1 2 3 4 5 6

6 23 30 14 18 12 9

14 12 9 23 30 18 6

20 散列表的平均查找长度_______.

A) 与处理冲突方法有关而与表的长度无关 B) 与处理冲突方法无关而与表的长度有关 C) 与处理冲突方法有关而与表的长度有关 D) 与处理冲突方法无关而与表的长度无关 21 在采用线性探测法处理冲突所构成的闭散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些

位置上的键值是_____. A) 一定都是同义词 B) 一定都不是同义词 C) 都不同 D) 不一定都是同义词

+

22 m路B树是一棵(1)_____,其结点中关键字最多为(2)______个,最少为(3)____个. (1) A) m路平衡查找树 B) m路平衡索引树 C) m路Ptrie树 D) m路键树

(2) E) m-1 F) m G) m+1 H) ?m2?1? (3) I) ?m2? J)?m2?1?

23 在构造哈希表的过程中,不可避免地会出现冲突,通常解决它的方法有______.

A)平方取中法 B)开放地址法 C)随机探查法 D) 再哈希法 E)拉链分散法(链地址法) 24 散列函数是指定关键字与存储地址间的映射关系,常用的构造方法有_______.

A)自身函数(直接定址)法 B)折叠函数法 C)平方取中法 D) 链接表法 E)除留余数法 25 如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用的查找方法是____. A)分块查找 B)顺序查找 C)折半查找 D)基于属性查找

26 有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择

下面哪个序列输入_____.

A) 45,24,53,12,37,96,30 B) 37,24,12,30,53,45,96 C) 12,24,30,37,45,53,96 D) 30,24,12,37,45,96,53

27 利用逐点插入法建立序列{50,72,43,85,75,20,35,45,65,30}对应的二叉排序树以后,查找元素35要进行___元素之间的比较.

A) 4次 B) 5次 C) 7次 D) 10次

28 在非空m阶B-树上,除根结点以外的所有其他非终端结点______.

A)至少有?m/2?棵子树 B)至多有?m/2?棵子树 C)至少有?m/2?棵子树 D)至多有?m/2?棵子树 29 在顺序表(n足够大)中进行顺序查找,其查找不成功的平均长度是_____. A) (n+1)/2 B) n/2+1 C) n D) n+1

30 采用二分检索方法检索长度为n的有序表,检索每个元素时的平均比较次数与对应的判定树高度(设高度≥2)相比较为____.