发布时间 : 星期五 文章数据结构习题册更新完毕开始阅读2b2a7704e45c3b3567ec8b91
10. 在下图所示的有向图7.12中： V1 V2 V3 V4 图7.12
（1） 该图是强连通图吗？ （2）请给出每个顶点的度、入度和出度。 （3）给出其邻接矩阵、邻接表及逆邻接表。
11. DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种
遍历？画出以顶点v1为初始源点遍历图7.13所示的有向图所得到的DFS和BFS生成森林。 V 3 V1 V4 V2 V5 V6 V8 V7 图7.13
12. 对图7.14所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。
10 4 6
5 15 4 30 10 4 15 10 图7.14
2 20 2 1 3
13. 已知如图7.16所示的AOE网。求：
（1）每项活动的最早开始时间和最晚开始时间； （2）完成此工程最少需要多少单位时间； （3）关键活动与关键路径。
e3=3 5 2 e8=1
e1=3 e4=2
4 6 1 e7=2 e5=4
e2=2 e6=3 3
图7.16
14. 已知带权连通图，G（V,E）的邻接表如图7.17所示。试画出该图，并分别从顶点1开始的深度优先和
广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为
顶点号 边上的权值 指针
17
2 8 2 1 8 3 1 10 4 1 11 5 2 13 图 7.17 1 3 3 2 3 10 3 3 4 4 ∧ 11 5 ∧ 13 4 ∧ 4 5 ∧ 7 4 ∧ 7 ?0?115. 已知某图G的邻接矩阵为 ??0??1101001011?0??，顶点集合为{v1,v2,v3,v4} 1??0?（1）由邻接矩阵画出相应的图G；
（2）如果要使用此图成为完全图还要增加哪几条边。
16. 对于图7.19所示的AOE网络，计算各事件（顶点）的ve(vi)和vl(vj)和活动（边）的e(ai)和l(ai)函数值；
列出各条关键路径和关键活动。 a7=6 A
a1=1 a2=6 D a12=5 B a8=2 a 9=7 C E a11 =8 a20=10 W a 16 =8 a 17 =4 a13=11 a 3=3 a4=4 F V a5=3 G a6=1 I a10=6 a=12 a 18 =4 22H J a14 =10 a19=9 a15=6 a=9 21K 图7.19
第九章：查找复习题
一、 选择题
1、顺序查找一个共有n个元素的线性表，其时间复杂度为（ ），折半查找一个具有n个元素的有序表，其时间复杂度为（ ）。
A、O(n) B、O(log2n) C、O(n2) D、O(nlog2n)
2、在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。 A、n B、[log2n] C、[log2(n+1)] D、「log2(n+1)
3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（ ） A、n B、n/2 C、(n+1)/2 D、(n-1)/2
4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高度大于等于2）。
A、小于 B、大于 C、等于 D、大于等于
18
5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（ ）。
A、1 B、2 C、3 D、4
6、对线性表进行折半查找时，要求线性表必须（ ）。
A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序
7、顺序查找法适合于存储结构为（ ）的查找表。
A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储
8、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。 A、10 B、25 C、6 D、625
9、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。
A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（ ）。 A、相同 B、不相同
11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1
12、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。
A、4次 B、5次 C、7次 D、10次
13、设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。 A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数D、小于m的最大合数。 14、长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（ ）
A、24/10 B、 24/11 C、39/10 D、39/11
15、在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ）
A、n+1 B、1 C、n D、n-1
16、设哈希函数为H(key)=key%7,一组关键字为(37，21，9，20，30，19和46)，哈希表T的地址空间为0..6,用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（ ） A、 0 1 2 3 4 5 6
21 20 21 46 21 19 20 37 37 37 9 30 9 9 37 21 46 30 30 46 30 19 46 19 19 20 20 9 B、 0 1 2 3 4 5 6 C、 0 1 2 3 4 5 6 D、 0 1 2 3 4 5 6 17、设有一个用线性探测法解决冲突得到的哈希表：
T: 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 哈希函数为H(key)=key,若要查找元素14，探测的次数是（ ） A、 3 B、 6 C、7 D、9 18、在哈希函数H(key)=key%m 中，一般来讲，m应取（ ）
A、奇数 B、偶数 C、 素数 D、充分大的数 19、分块查找的时间性能（ ）
19
A、低于二分查找 B、高于顺序查找而低于二分查找 C、高于顺序查找 D、低于顺序查找而高于二分查找 20、以下说法错误的是（ ）
A、哈希法存储的基本思想是由关键字的值决定数据的存储地址 B、哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是哈希法的一个重要参数，它反映哈希表的装填程度
D、哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21、以下说法正确的是（ ）
A、前序遍历二叉排序树的结点就可以得到排好序的结点序列
B、任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C、对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的
D、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要
22、已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（ ） A、将该元素所在的存储单元清空 B、将该元素用一个特殊的符号代替
C、将与该元素有相同Hash地址的后继元素顺次前移一个位置 D、用与该元素有相同Hash地址的最后插入表中的元素替代
23、设哈希表长为M=14，哈希函数H（key）=key。表中已有4个结点：
ADDR(15)=4 ADDR(38)=5 ADDR(61)=6 ADDR(84)=7
其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（ ） A、3 B、8 C、9 D、10
24、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（ ）
A、32/12 B、35/12 C、37/12 D、39/12
25、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应（ ）个结点最佳。
A、25 B、10 C、6 D、625
26、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（ ）查找方法。
A、分块 B、顺序 C、折半 D、散列 27、深度为6的AVL树至少有（ ）个结点。
A、10 B、12 C、20 D、21 28、哈希表的平均查找长度（ ）
A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关 29、若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为（ ）
A、(d+1)%m B、(d-1)%m C、(d+4)%m D、(d-4)%m
30、有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列哪个输入序列（ ）
A、45，12，49，6，40，56，32 B、40，12，6，32，49，45，56 C、6，12，32，40，45，49，56 D、32，12，6，40，45，56，49
31、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）
A、n B、log2n C、(h+1)/2 D、h
二、 判断题
20