第5章 图
一、选择题
1. 图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2. 设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2
2
C． n(n+1)/2 D．0 E．n
3. 一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn； 4. n个结点的完全有向图含有边的数目（ ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
5. 一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n
6. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所
有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 7. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点
序列是( )。
A．逆拓扑有序 B．拓扑有序 C．无序的 8. 无向图G是 一个连通图，有9条边，则该图至少有（ ）个顶点。
A．4 B．5 C．6 D．7 9. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 10. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 11. 无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
12. 下面哪些方法可以判断出一个有向图是否有环（回路）： （ ）
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
13. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n)
14. 当各边上的权值( )时，广度优先遍历算法可用来解决单源最短路径问题。
A．均相等 B．均互不相等 C．不一定相等 15. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
16. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
（ ）。
A．存在 B．不存在
17. 一个有向无环图的拓扑排序序列（ ）是唯一的。
A．一定 B．不一定
18. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
（ ）。
A．G中有弧
C．G中没有弧
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 20. 下面关于求关键路径的说法不正确的是（ ）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
21. 下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
二、综合应用题
1. 请计算下图中的强连通分量的个数
2. 考虑下图：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，
画出G的深度优先生成树和广度优先生成树。
3. 在什么情况下，Prim算法与Kruskual算法生成不同的MST？
? 在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不
同的MST。
4. 考虑下图：根据普利姆(Prim) 和Kruskal算法分别求它的最小生成树。 V0 6 5
1
5 5 V1 V3
V2
6 4 3 2 6
V4 V5
5. 已知一图如下图所示：
（1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序；
（3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；
（4）．求V1结点到各点的最短距离。
第6章 查找
一、选择题
1. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找
一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储
3. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但
前者比后者的查找速度( ) 。
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 4. 折半查找的时间复杂性为（ ）
2
A. O（n） B. O（n） C. O（nlogn） D. O（logn） 5. 当采用分块查找时，数据的组织方式为 ( )。
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6. 二叉排序树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找
失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:
A. 相同的 B.不同的
8. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)
9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链
地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。
A．1 B. 2 C. 3 D. 4
10. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链
表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 11. 关于哈希查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是
相同的
（3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
12. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9 13. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要
进行多少次探测？( )。
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
14. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 15. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会
二、综合应用题
1、如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。
2、在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？ 3、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 4、一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。
5、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树
(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;
(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 6、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。
（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363
7、有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是多少？
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(3)在线全文阅读。
相关推荐：