数据结构第6章课后习题答案(上)

简介: 数据结构第6章课后习题答案

1.选择题

1)在一个图中,所有顶点的度数之和等于图的边数的(   )倍。

 A1/2            B1             C2             D4

答案:C

2)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(   )倍。

 A1/2            B1             C2             D4

答案:B

解释:有向图所有顶点入度之和等于所有顶点出度之和。

3)具有n个顶点的有向图最多有(   )条边。

An              Bn(n-1)         Cn(n+1)        Dn2

答案:B

解释:有向图的边有方向之分,即为从n个顶点中选取2个顶点有序排列,结果为n(n-1)

4n个顶点的连通图用邻接距阵表示时,该距阵至少有   个非零元素。

An              B2(n-1)         Cn/2           Dn2

答案:B

5G是一个非连通无向图,共有28条边,则该图至少有   个顶点。

A7              B8             C9             D10

答案:C

解释:8个顶点的无向图最多有8*7/2=28条边,再添加一个点即构成非连通无向图,故至少有9个顶点。

6若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点,则该图一定是   图。

A非连通        B连通          C强连通        D有向

答案:B

解释:即从该无向图任意一个顶点出发有到各个顶点的路径,所以该无向图是连通图。

7)下面( )算法适合构造一个稠密图G的最小生成树。

A Prim算法      BKruskal算法   CFloyd算法     DDijkstra算法

答案:A

解释:Prim算法适合构造一个稠密图G的最小生成树,Kruskal算法适合构造一个稀疏图G的最小生成树。

8)用邻接表表示图进行广度优先遍历时,通常借助(   )来实现算法。

A.栈            B. 队列            C.              D.图

答案:B

解释:广度优先遍历通常借助队列来实现算法,深度优先遍历通常借助栈来实现算法。

9)用邻接表表示图进行深度优先遍历时,通常借助(   )来实现算法。

A.栈            B. 队列            C.              D.图

答案:A

解释:广度优先遍历通常借助队列来实现算法,深度优先遍历通常借助栈来实现算法。

10)深度优先遍历类似于二叉树的(   )。

A.先序遍历      B.中序遍历        C.后序遍历      D.层次遍历

答案:A

11)广度优先遍历类似于二叉树的(   )。

A.先序遍历      B.中序遍历        C.后序遍历       D.层次遍历

答案:D

12图的BFS生成树的树高比DFS生成树的树高(   )。

A.小            B相等            C小或相等       D大或相等

答案:C

解释:对于一些特殊的图,比如只有一个顶点的图,其BFS生成树的树高和DFS生成树的树高相等。一般的图,根据图的BFS生成树和DFS树的算法思想,BFS生成树的树高比DFS生成树的树高小。

(13)已知图的邻接矩阵如图6.30所示,则从顶点v0出发按深度优先遍历的结果是(    )。

 图6.30  邻接矩阵

(14)已知图的邻接表如图6.31所示,则从顶点v0出发按广度优先遍历的结果是(    ),按深度优先遍历的结果是(    )。

图6.31  邻接表

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

答案:DD

15下面   方法可以判断出一个有向图是否有环。

A深度优先遍历      B拓扑排序      C求最短路径     D求关键路径

答案:B

2.应用

(1)已知图6.32所示的有向图,请给出:

① 每个顶点的入度和出度;    

② 邻接矩阵;

③ 邻接表;

④ 逆邻接表。            

答案:

(2)已知如图6.33所示的无向网,请给出:

邻接矩阵;    

邻接表;

最小生成树

答案:

(3)已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

(4)有向网如图6.35所示,试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径,完成表6.9。

表6.9

D

终点

i=1

i=2

i=3

i=4

i=5

i=6

b

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

15

(a,b)

c

2

(a,c)

d

12

(a,d)

12

(a,d)

11

(a,c,f,d)

11

(a,c,f,d)

e

10

(a,c,e)

10

(a,c,e)

f

6

(a,c,f)

g

16

(a,c,f,g)

16

(a,c,f,g)

14

(a,c,f,d,g)

S

终点集

{a,c}

{a,c,f}

{a,c,f,e}

{a,c,f,e,d}

{a,c,f,e,d,g}

{a,c,f,e,d,g,b}

目录
相关文章
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
43 2
|
6月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
79 1
|
6月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
48 1
|
6月前
|
机器学习/深度学习
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
42 1
|
6月前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
39 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
38 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
38 0
|
6月前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
36 0