12.设图的邻接链表如题12图所示，则该图的边的数目是（ ）

题12图

A.4 B.5 C.10 D.20 23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的______。 30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。

35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。 Void deledge（ALGraph *G，int i，int j） { EdgeNode *p，*q；

p=G→adjlist［i］.firstedge；

if（p→adjvex==j）{ G→adjlist［i］.firstedge=p→next；free（p）；} else

{ while（p→next→adjvex != j && p→next）

（1）________；

if（p→next!=NULL）{q=p→next；（2）________；free（q）；} }

p=G→adjlist［j］.firstedge；

if（p→adjvex==i）{ G→adlist［j］.firstedge=p→next；free（q）；} else

{ while（p→next→adjvex!=i&&p→next）

（3）________；

if（p→next!=NULL）{q=p→next；（4）________；free（q）；} } }

9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历

10.具有n个顶点的无向图，若要连通全部顶点，至少需要（ ）

21

A.（n-1）条边 B. n条边 C. n(n-1)条边 D. n(n-1)/2条边 24.若一个完全无向图具有n条边，则该图的顶点个数为________________。 30.试用Prim算法构造题30图的最小生成树，要求分步给出构造过程。

9.具有10个顶点的有向完全图应具有( ) A.20条弧 B.50条弧C.90条弧 D.100条弧 10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为( ) A.V1V2V3V5V4V6 B.V1V2V3V5V6V4 C.V1V5V2V3V6V4 D.V1V3V6V4V5V2 24.对于n个顶点的生成树，其边的个数为__________ 。 31．试给出题31图的邻接矩阵和邻接表表示。

8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )

题8图 题10图 9.下面关于生成树的描述中，不正确的是( )

A.生成树是树的一种表现形式 B.生成树一定是连通的 C.生成树一定不含有环 D.若生成树顶点个数为n，则其边数一定为n-1

10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是( A v1v2v3v4v5 B v1v2v3v5v4 C v1v4v3v5v2 D v1v3v4v5v2 24.图主要采用___________两种存储结构存放。

30．试用prim算法构造下图的最小生成树，要求分步给出构造过程。

) 22

题31图

9.在一个无向图中，所有顶点的度数之和等于边数的（ ） A.1倍 B.2倍 C.3倍 D.4倍

10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历

24.若图的邻接矩阵是一个对称矩阵，则该图一定是一个___________。

30．若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按广度优先搜索所产生的一棵生成树。

8．邻接表是图的一种（ ）

A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ） A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 B．n C．(n+1)/2 D．n+1

22．顶点数为n、边数为n(n-1)/2的无向图称为__________。

31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）

23

第六章 查找 真题

8.对线性表进行二分查找时，要求线性表必须( )

A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列

27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为____________。

7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ ）A.1 B.2 C.3 D.4 12.用n个值构造一棵二叉排序树，它的最大高度为（ ） A.n/2 B. n C. n+1 D.log2n 27.顺序查找算法的平均查找长度为______。

31.题31图中二叉排序树的各结点的值为1～9，标出各结点的值。

13.二分查找算法的时间复杂度是（ ）A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n) 14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） A.4 B.5 C.6 D.7

25.假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。 12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ） A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列

13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（ ）A.1 B.2 C.4 D.8

32.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 13.闭散列表中由于散列到同一个地址而引起的―堆积‖现象，是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表―溢出‖引起的 24.在一棵二叉排序树上按_________遍历得到的结点序列是一个有序序列。

25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。 31.设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。

24