四、综合题
l．请写出如图7-1所示无向图的邻接矩阵和邻接表两种存储结构。
邻接矩阵如图B-5所示。
?0?0??0??0?0A???0?0??1?0??0?100000100?010000001??001000001??010100000?001010000??000001010?000010100??000001010?000010100???110000000?
图B-5
邻接表如图B-6所示。
datafirstarcadjvexdatanext1234567891023434761622343476162810105698783810105698783^^^^^^^9^^9^55^1212^^ 图B-6
2．依据无向图7-1，请写出：
（1）从顶点1出发图的深度优先搜索序列。 （2）从顶点回出发图广度优先搜索的序列。 （3）写出图的深度优先搜索算法。
（4）写出图的广度优先搜索算法。
（1）从顶点1出发图的深度优先搜索序列为： 1→8→7→6→9→5→4→3→2→10
（2）从顶点1出发图广度优先搜索的序列为： 1→8→2→7→9→10→3→6→4→5
（3）图的深度优先搜索算法参考例题7-1的内容。 （4）图的广度优先搜索算法参考例题7.2节内容。
3．使用Prim算法，依据无向图7-2做以下问题；
图7-2
（l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法。
（1）使用Prim算法，构造该图的最小生成树的过程如图B-7所示。
190206507570511041201082580530367548310026012（a）12067554583650752120（b）2834（c）1206507554583650751002120（d）100210834（e）12065075548255100210365075120（f）1002103082543（g）（h）
图B-7
4．使用Kruskal算法，依据无向图7-2做以下问题： （l）写出构造该图的最小生成树的过程。
(2) 写出相应的构造最小生成树算法的形式描述。
（1）使用Kruskal算法，构造该图的最小生成树的过程如图B-8所示。
100190206507570526010301212082536755838011044（a）121067554583675120（b）210834（c）1206755482552103675120（d）2108254303（e）1205067554825521030365075120（f）1002103082543（g）（h）
图B-8
5． 假设图采用邻接表表示，写出一个从顶点v0对图按深度优先搜索遍历的非递归算法。 6．有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点v到顶点w的路径中长度为len的简单路径。
7．以邻接表作为存储结构，编写一个算法，利用深度优先搜索法，求出在无向图中通过给定点w的简单回路的算法。
第九章
一、选择题
1.顺序查找方法适合于存储结构为（ ）的线性表
A.散列存储 B.索引存储 C.散列存储或索引存储 D.顺序存储或链接存储 2.对线性表进行二分查找的时候，要求线性表必须（ ）。
A.以顺序存储方式 B.以链接存储方式
C.以顺序存储方式，且数据元素有序 D.以链接存储方式，且数据元素有序
3. 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）查找方法。 A.顺序 B.分块 C.折半 D.散列 4. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( ) 。
A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式
5. 在线性表的存储结构中,（ ）查找、插入和删除速度慢，但顺序存储和随机存取第i个元素速度快。 A.顺序表 B.链接表 C.散列表 D.索引表 6. 在( )上查找和存取速度快,但插入和删除速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 7. 在( )上查找、插入和删除速度快,但不能进行顺序存取。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 8. 在( )上插入、删除和顺序存取速度快,但查找速度慢。
A.顺序表 B.链接表 C.顺序有序表 D.散列表
9. 采用顺序查找方法查找长度为n的线性表,查找每个元素的平均比较次数为( ) A. n B. n/2 C. (n+1)/2 D.(n-1)/2 10.顺序查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 11.折半查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 12.己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素55需要比较( )次。 A.1 B.2 C.3 D.4
13.已知一个有序表为(11,22,33,44,55,66,77,88,99), 则顺序查找元素 55 需要比较( )次。 A.3 B.4 C.5 D.6 14.顺序查找法与二分查找法对存储结构的要求是( ) 。 A. 顺序查找与二分查找均只是适用于顺序表
B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表 C. 顺序查找只是适用于顺序表 D. 二分查找适用于顺序表
15.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插到集合中。这种方式主要适合于( ) 。 A.静态查找表 B. 动态查找表 C.静态查找表与动态查找表 D. 两种表都不适合 16.若用二分查找取得的中间位置元素关键字值大于被查找值，则说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至( ) 。