历年真题分类整理

A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3) 11.如图所示有向图的一个拓扑序列是( )

A.ABCDEF B.FCBEAD C.FEDCBA D.DAEBCF 28．已知无向图G的邻接表如图所示，

(1)画出该无向图；(2)画出该图的广度优先生成森林。

22．求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目正相关。11．若非．连通无向图G含有21条边，则G的顶点个数至少为（ ） A．7 B．8 C．21 D．22

12．如图所示的有向图的拓扑序列是（ ）

A．c，d，b，a，e B．c，a，d，b，e C．c，d，e，a，b D．c，a，b，d，e 27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。 13

请回答下列问题：

(1)请画出对应的图G。(2)画出图G的邻接表存储结构。

22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。

11．对下面有向图给出了四种可能的拓扑序列，其中错误．．

的是（ ）

A．1，5，2，6，3，4 B．1，5，6，2，3，4 C．5，1，6，3，4，2 D．5，1，2，6，4，3 12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）

A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6 C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v4

29.请回答下列问题：

(1)英文缩写DAG的中文含义是什么？ (2)请给出下面DAG图的全部拓扑排序。

21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。 9.在图G中求两个结点之间的最短路径可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法

14

10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18

11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7

27.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵；

(2)从结点A出发，写出该图的深度优先遍历序列。

22.一个有n个顶点的无向连通图，最少有________________条边。 9.下列叙述中错误的是（ ）

A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程

10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={，，，，}，图G的拓扑序列是（ ）

A.V1,V2,V3,V4 B.V1,V3,V2,V4 C.V1,V3,V4,V2 D.V1,V2,V4,V3 11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ） A.e B.2e C.n-2e D.n-1

10.在带权图的最短路径问题中，路径长度是指（ ）

A.路径上的顶点数 B.路径上的边数 C.路径上的顶点数与边数之和 D.路径上各边的权值之和 29.已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。

15

2

2

5.无向完全图G有n个结点，则它的边的总数为（ ） A.n

2

B.n(n-1) C.n(n-1)/2 D.(n-1)

7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是（ ） ．．．A.acfdeb B.aebdfc C.aedfbc D.aefdbc

八、排序

返回

29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。 （1） （2）

23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。

11.对长度为n的关键字序列进行堆排序的空间复杂度为（ ） A. O（log2n） B. O（1） C. O（n） D. O（n*log2n）

12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）

A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序

27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。 (1)写出排序过程中前两趟的划分结果； (2)快速排序是否是稳定的排序方法? (1) (2)

23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。 12.下列关键字序列中，构成大根堆的是( )

16