《数据结构》习题汇编07-第七章-图-试题.doc

第七章图试题

一、单项选择题

在无向图中定义顶点得度为与它相关联得()得数目。

A、顶点 B、边 C、权 D、权值

在无向图中定义顶点vi与vj之间得路径为从vi到达vj得一个()。

A、顶点序列 B、边序列 C、权值总与 D、边得条数

图得简单路径就是指()不重复得路径。

A、权值 B、顶点 C、边 D、边与顶点均

设无向图得顶点个数为n,则该图最多有()条边。

A、n1 B、n(n1)/2 C、n(n+1)/2 D、n(n1)

n个顶点得连通图至少有()条边。

A、n1 B、n C、n+1 D、0

在一个无向图中,所有顶点得度数之与等于所有边数得()倍。

A、3 B、2 C、1 D、1/2

若采用邻接矩阵法存储一个n个顶点得无向图,则该邻接矩阵就是一个()。

A、上三角矩阵 B、稀疏矩阵 C、对角矩阵 D、对称矩阵

图得深度优先有哪些信誉好的足球投注网站类似于树得()次序遍历。

A、先根 B、中根 C、后根 D、层次

图得广度优先有哪些信誉好的足球投注网站类似于树得()次序遍历。

A、先根 B、中根 C、后根 D、层次

在用Kruskal算法求解带权连通图得最小(代价)生成树时,通常采用一个()辅助结构,判断一条边得两个端点就是否在同一个连通分量上。

A、位向量 B、堆 C、并查集 D、生成树顶点集合

在用Kruskal算法求解带权连通图得最小(代价)生成树时,选择权值最小得边得原则就是该边不能在图中构成()。

A、重边 B、有向环 C、回路 D、权值重复得边

在用Dijkstra算法求解带权有向图得最短路径问题时,要求图中每条边所带得权值必须就是()。

A、非零 B、非整 C、非负 D、非正

在一个连通图中进行深度优先有哪些信誉好的足球投注网站得到一棵深度优先生成树,树根结点就是关节点得充要条件就是它至少有()子女。

A、1 B、2 C、3 D、0

设有向图有n个顶点与e条边,采用邻接表作为其存储表示,在进行拓扑排序时,总得计算时间为()。

A、O(nlog2e) B、O(n+e) C、O(ne) D、O(n2)

设有向图有n个顶点与e条边,采用邻接矩阵作为其存储表示,在进行拓扑排序时,总得计算时间为()。

A、O(nlog2e) B、O(n+e) C、O(ne) D、O(n2)

设G1=(V1,E1)与G2=(V2,E2)为两个图,如果V1?V2,E1?E2,则称()。

A、G1就是G2得子图 B、G2就是G1得子图

C、G1就是G2得连通分量 D、G2就是G1得连通分量

有向图得一个顶点得度为该顶点得()。

A、入度 B、出度

C、入度与出度之与 D、(入度﹢出度))／2

一个连通图得生成树就是包含图中所有顶点得一个()子图。

A、极小 B、连通 C、极小连通 D、无环

n(n＞1)个顶点得强连通图中至少含有()条有向边。

A、n1 B、n n(n1)/2 D、n(n1)

在一个带权连通图G中,权值最小得边一定包含在G得()生成树中。

A、某个最小 B、任何最小 C、广度优先 D、深度优先

对于具有e条边得无向图,它得邻接表中有()个边结点。

A、e1 B、e C、2(e1) D、2e

对于如图所示得带权有向图,从顶点1到顶点5得最短路径为()。

A、1,4,5 B、1,2,3,5 C、1,4,3,5 D、1,2,4,3,5

1

1

2

61

3

81

9

5

5

4

1

2

3

具有n个顶点得有向无环图最多可包含()条有向边。

A、n1 B、n C、n(n1)/2 D、n(n1)

一个有n个顶点与n条边得无向图一定就是()。

A、连通得 B、不连通得 C、无环得 D、有环得

在n个顶点得有向