当前位置：文档之家 › 数据结构与算法课件：DS07_图 习题

数据结构与算法课件：DS07_图 习题

  • 格式：pptx
  • 大小：183.61 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

《数据结构与算法 》课件

《数据结构与算法 》课件
人工智能领域中，数据结构对于机器学习、深度学习等算法的效率至关重要。例如，使用决策树、神经网络等数据结构进行分类、预测等任务。
数据结构在人工智能中的优化可以提升算法的效率和准确性，例如通过使用哈希表实现快速特征匹配，提高图像识别速度。
THANK YOU
定义与分类
添加边、删除边、查找路径等。
基本操作
图中的边可以是有方向的，也可以是无方向的。节点之间可以有多种关系，如邻接、相连等。
特性
社交网络、交通网络、路由协议等。
应用场景
05
排序与查找算法
冒泡排序：通过重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
详细描述
链表的优势在于可以动态调整大小，插入和删除操作仅需修改指针，时间复杂度为O(1)。但链表访问特定元素需要从头部遍历，效率较低。
VS
栈和队列是特殊的线性数据结构，它们遵循特定的操作规则。栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。
详细描述
栈用于保存按照后进先出顺序访问的数据元素，常见的操作有压栈、弹栈和查看栈顶元素。队列用于保存按照先进先出顺序访问的数据元素，常见的操作有入队、出队和查看队首元素。
03
线性数据结构
数组是线性数据结构中的基本形式，它以连续的内存空间为基础，用于存储固定长度的同类型元素。
数组具有固定的长度，可以通过索引直接访问任意元素。它适合于需要快速访问数据的场景，但插入和删除操作需要移动大量元素，效率较低。
详细描述
总结词
总结词
链表是一种线性数据结构，它通过指针链接各个节点，节点包含数据和指向下一个节点的指针。

数据结构第7章 图习题

数据结构第7章 图习题

习题7 图7.1 单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，假设采用邻接矩阵表示，那么该矩阵的大小是____。

A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，假设采用邻接表表示，那么表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．一个图如图7.1所示，假设从顶点a出发按深度搜索法进行遍历，那么可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，那么可能得到的一种顶点序列为__②__。

①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b图 7.1 一个无向图11．一有向图的邻接表存储结构如图7.2所示。

图7.2 一个有向图的邻接表存储结构⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

《数据结构与算法 》课件

《数据结构与算法 》课件
自然语言处理
自然语言处理中，数据结构用于表示句子、单词之间的关系，如依 存句法树。
计算机视觉
计算机视觉中的图像处理和识别使用数据结构来存储和操作图像信 息，如链表和二叉树。
算法在计算机科学中的应用
加密算法
加密算法用于保护数据的机密性和完整性，如 RSA算法用于公钥加密。
排序算法
排序算法用于对数据进行排序，如快速排序和归 并排序广泛应用于数据库和搜索引擎中。
归并排序
将两个或两个以上的有序表组合成一个新的有序表。
查找算法
线性查找：从数据结构的一端开始逐 个检查每个元素，直到找到所查找的 元素或检查完所有元素为止。
二分查找：在有序数据结构中查找某 一特定元素，从中间开始比较，如果 中间元素正好是要查找的元素，则搜 索过程结束；如果某一特定元素大于 或者小于中间元素，则在数组大于或 小于中间元素的那一半中查找，而且 跟开始一样从中间元素开始比较。如 果在某一步骤数组为空，则代表找不 到。这种搜索算法每一次比较都使搜 索范围缩小一半。
04
常见算法实现
排序算法
冒泡排序
通过重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复 地进行直到没有再需要交换，也就是说该数列已经排序完成。
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按 此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
数据结构在计算机科学中的应用
1 2
数据库系统
数据结构是数据库系统的基础，用于存储、检索 和管理大量数据。例如，B树和哈希表在数据库 索引中广泛应用。

数据结构与算法(共11张PPT)

数据结构与算法(共11张PPT)

(b)入队3个元素(c)出队3个元素
(b) d, e, b, g入队
利用一组连续的存储单元(一维数组)依次存放从队 在循环队列中进行出队、入队操作时，队首、队尾指
队列示意图
在非空队列里，队首指针始终指向队头元素，而队
(b) d, e, b, g入队
8
Q.rear
a5
a4
Q.front
(d)入队2个元素
a1, a2, … , an
的指修针改 和是队依列先中进元先素出的Q的变.re原化a则情r 进况行。的，如图所示。
a3
Q.front
a2
a1
首到队尾的各个元素，称为顺序队列。
(c)
d, e出队Q.front
Q.front
◆出队：首先删去front所指的元素，然后将队首指针front+1，并
◆rear所指的单元始终为空(a。)空队列
i
i, j, k入队
(e)
1
2
3
k
r
01
j5
2
front
43
i
b, g出队
(f )
r, p,
p rear
s, t入队
循环队列操作及指针变化情况
入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针 ，故队空和队满时头尾指针均相等。因此，无法通过front=rear来 判断队列“空”还是“满”。解决此问题的方法是：约定入队前，
数据结构与算法
1算法基础 2数据结构
3栈
4队列
5链表 6树和二叉树
7查找
4队列
✓队列的基本概念 ✓队列运算
✓循环队列及其运算
4队列
1.队列的基本概念

数据结构与算法讲义课件

数据结构与算法讲义课件

04
基础算法
排序算法
冒泡排序
通过重复地比较相邻元素并交换位置，使得较大 的元素逐渐向数组尾部移动，最终实现数组序序列的合适位置， 使得已排序序列保持有序，直到所有元素均插入 完毕。
选择排序
每次从未排序的元素中选取最小（或最大）的一 个元素，将其放到已排序序列的末尾，直到所有 元素均排序完毕。
03
算法概述
算法的定义与特性
总结词
算法是解决问题的步骤集合，具有确定 性、有限性、输入和输出。
VS
详细描述
算法是解决问题的明确、具体的步骤集合 ，每个步骤都有确切的含义，不存在歧义 。算法在执行过程中，从开始到结束，是 确定性的，每一步都有确定的输入和输出 。算法在有限的时间内完成执行，无论何 种情况下都能得出结果。算法具有输入和 输出，可以接受外部数据，并对外输出结 果。
快速排序
通过选取一个基准元素，将数组分成两部分，其 中一部分的所有元素都比基准元素小，另一部分 的所有元素都比基准元素大，然后递归地对这两 部分进行快速排序。
查找算法
线性查找
从数组的第一个元素开始，逐个比较 每个元素，直到找到目标元素或遍历 完整个数组。
哈希查找
利用哈希函数将键值转化为数组下标， 然后在相应的数组下标处查找目标元 素。
性是指算法在修改和升级时的难易程度。
算法的分类
总结词
详细描述
根据不同标准可以将算法分为不同类型，如 按照功能、按照应用领域、按照设计方法等。
按照功能可以将算法分为排序算法、搜索算 法、图论算法等。按照应用领域可以将算法 分为计算机视觉算法、自然语言处理算法等。 按照设计方法可以将算法分为分治法、贪心 法、动态规划法等。
树
总结词

数据结构与算法课件：DS07_图 习题

数据结构与算法课件：DS07_图 习题

}
return 1;
}
void EulerCycle(AdjList g)
{ int flag=degree(g);
if(!flag)
{ printf(“无解\n”); exit(0);}
dfs(1);
} 2020/9/28
18
算法举例
在有向图G中，如果r到G中的每个结点都有路径可 达，则称结点r为G的根结点。编写一个算法判断有向 图G是否有根，若有，则打印出所有根结点的值。
【2010年全国硕士研究生入学统一考试计算机学科专业基础综合】
C 6*(6-1)/2+1
6 2020/9/28
自测题
设图如右所示，在下面的5个序列中，符合深度优先遍历的序列 有多少？（ ）
aebdfc A．5个 B．4个 C．3个 D．2个
acfdeb
aedfcb aefdcb
a
b
e
aefdbc
c
【哈尔滨工业大学2004二.3(1分)】
【北京工业大学1999一.1(2分)】
【北方交通大学1999一.7(3分）】
B
11
2020/9/28
自测题
下列有关图的说法错误的是（ ）
A. 在有向图中，出度为0的结点称为叶子。 B. 用邻接矩阵表示图，容易判断任意两个结点之间
是否有边相连，并求得各结点的度。
void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)
∥将图的邻接表表示转换为邻接矩阵表示
{ for(i=0;i<n;i++) ∥设图有n个顶点，邻接矩阵初始化
for(j=0;j<n;j++) gm[i][j]=0;

DS07-图

scanf ("%d，%d，%d"，&i，&j，&w)； ga->edges[i][j] = w； ga->edges[j][i] = w；
}
}
算法分析
该算法的执行时间是O(n+n2+e)，由于e< n2， 所以算法的时间复杂度为O(n2)。
邻接表 (Adjacency List)表示法 ▪无向图的邻接表
▪ 无向图的邻接矩阵是对称的，有向图的邻接矩阵 一般情况下是不对称的。
▪ 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度， 统计第 j 列 1 的个数可得顶点 j 的入度。
▪ 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。ቤተ መጻሕፍቲ ባይዱ
网络的邻接矩阵
W (i, j),
A.Edge
▪图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。
▪强连通图与强连通分量 在有向图中, 若对于每一 对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子 图叫做强连通分量。
表头结点 data first
表结点 vertex next
v1
v2
v3
v4
scanf("%c",&(ga->vexs[i]))；/*输入顶点信息*/ for (i = 0；i<ga->n；i++) /*邻接矩阵初始化*/
for (j = 0；j<ga->n；j++) ga->edges[i][j] = 0；

数据结构与算法课件：DS07_图15-16

(complete graph)，完全图显然具有最大的边数
❖ 有向完全图:n个顶点的有向图最大边数是n(n-1) ❖ 无向完全图:n个顶点的无向图最大边数是n(n-1)/2
7.1 图的定义和术语
A
A
B
A
A
B
B
CC
DB
（a）无向完全图
CC
D
（b）有向完全图
❖ 邻接点:若(vi,vj)是一条无向边，则称vi和vj互为~ ❖ 关联:vi和vj互为邻接点，称边(vi,vj)关联于顶点vi和vj ❖ 顶点的度：
v0
v1
v0
v1
v3
v2
v4
(a) 无向图G1
v2
v3
(b) 有向图G2
7.1 图的定义和术语
通常用n表示图中顶点的数目，用e表示边或弧的数 目。无向图中e的取值范围是从0到n(n - 1)/2，有向 图中e的取值范围是从0到n(n - 1)
边数相对较少的图称为稀疏图(sparse graph) 边数相对较多的图称为稠密图(dense graph) 任何两顶点间都有边相关联的图称为完全图
1736年欧拉将陆地作顶点，将桥作边，从而将这个实 际问题抽象成图的模型。
“一笔画问题”：当两个顶点的度为奇数，其余顶点 的度为偶数时，可以从一个奇数顶点出发，经过每条 边一次，最后到达另一奇数顶点。
“欧拉回路问题”：只有所有的顶点的度都是偶数， 才能从一个顶点出发，经过每条边一次，最后回这个 顶点。
v0
v1
v3
v2
v4
(a) 无向图G1
v0
v1
v0
v1
v0
v1
v3
v2
v3
(b) 有向图G2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

d
【南京理工大学 2000 一.20 （1.5分）】 D
2020/9/28
f
7
自测题
下面哪一方法可以判断出一个有向图是否 有环（回路）：
A. 深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
【东北大学 2000 4.2（4分）】 AB
8 2020/9/28
自测题
在有向图G的拓扑序列中，若顶点Vi在顶点 Vj之前，则下列情形不可能出现的是（ ）。
void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)
∥将图的邻接表表示转换为邻接矩阵表示
{ for(i=0;i<n;i++) ∥设图有n个顶点，邻接矩阵初始化
for(j=0;j<n;j++) gm[i][j]=0;
for(i=0;i<n;i++)∥取第一邻接点,填邻接矩阵元素值,并求下一邻接点
【哈尔滨工业大学2004二.3(1分)】
【北京工业大学1999一.1(2分)】
【北方交通大学1999一.7(3分）】
B
11
2020/9/28
自测题
下列有关图的说法错误的是（ ）
A. 在有向图中，出度为0的结点称为叶子。 B. 用邻接矩阵表示图，容易判断任意两个结点之间
是否有边相连，并求得各结点的度。
C. 按深度方向遍历图和先根次序遍历树类似，得到 的结果是唯一的。
D. 若有向图G中从结点Vi到结点Vj有一条路径，则在 图G的结点的线性序列中结点Vi必在结点Vj之前的话 ，则称为一个拓扑序列。
C
12 2020/9/28
算法举例 略 给出以十字链表作存储结构，建立图的算
。 法，输入(i,j,v)其中i,j为顶点号，v为权值
B
10 2020/9/28
自测题略
下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动若提前完成，那么整个工程将会提前完成
void CreatOrthList(OrthList g)∥建立有向图的十字链表存储结构 {int i,j,v; ∥假定权值为整型
scanf("%d",&n); for(i=0,i<n;i++) ∥建立顶点向量
{scanf(&g[i].vertex); g[i].firstin=null; g[i].firstout=null;}
图习题主要内容
1. 基础知识 2. 算法设计
7.7 图知识点总结
7.1 图的基本概念 7.2 图的抽象数据类型 7.3 图的存储结构 7.4 图的周游（深度、广度、拓扑） 7.5 最短路径问题 7.6 最小生成树
自测题
7. 下列关于无向连通图特性的叙述中，正确的是 Ⅰ. 所有顶点的度之和为偶数 Ⅱ. 边数大于顶点个数减1 Ⅲ. 至少有一个顶点的度为1 A. 只有Ⅰ B. 只有Ⅱ C. Ⅰ和Ⅱ D. Ⅰ和Ⅲ
【2009年全国硕士研究生入学计算机学科专业基础综合试题】
A
3 2020/9/28
5. 对有n个结点、e条边且使用邻接表存储的有向图进 行广度优先遍历，其算法时间复杂度是
A. O(n) B. O(e) C. O(n+e) D. O(nxe)
【2012年全国硕士研究生入学统一考试计算机学科专业基础综合】
值域
p->headlink=g[j].firstin; g[j].firstin=p;
p->tailink=g[i].firstout; g[i].firstout=p;
2020/9/28scanf("%d%d%d",&i,&j,&v);
13
算法举例 写出从图的邻接表表示转换成邻接矩阵表示的算
法。【南开大学 1998 四(16分)】【天津大学 1999 五】
C
自测题
G是一个非连通无向图，共有28条边，则该图 至少有______个顶点。
【西安电子科技大学2001软件 一.8 （2分）】 9 8*(8-1)/2+1
5 2020/9/28
自测题
7.若无向图G=（V.E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是
A. 6 B. 15 C. 16 D. 21
{ p=gl[i]. firstarc;
while(p!=null)
{ gm[i][p->adjvex]=1;
p=p->next;
}
2}0∥20f/o9/2r8}∥算法结束
14
算法举例
设在4地（A，B，C，D）之间架设有6座桥，如图所示：
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。
（1）试就以上图形说明：此问题有解的条件是什么？ （5分）
A．G中有弧<Vi，Vj> B．G中有一条从Vi到Vj的路径 C．G中没有弧<Vi,Vj> D．G中有一条从Vj到Vi的路径
D
9 2020/9/28
自测题 略
关键路径是AOE网中( )
A. 从始点到终点的最短路径 B. 从始点到终点的最长路径数最少的路径
（2）设图中的顶点数为n,试用C或PASCAL描述与求解此问题有关
的数据结构并编写一个算法，找出满足要求的一条回路。（10分）
【20清20华/9/2大8 学2001一(15分)】
15
（1）只有所有的顶点的度都是偶数，才能有解。
（2）[题目分析]以邻接表作为存储结构，因顶点间有重边 ，可用边的编号作该边的权值，其结构定义如下：
【2010年全国硕士研究生入学统一考试计算机学科专业基础综合】
C 6*(6-1)/2+1
6 2020/9/28
自测题
设图如右所示，在下面的5个序列中，符合深度优先遍历的序列 有多少？（ ）
aebdfc A．5个 B．4个 C．3个 D．2个
acfdeb
aedfcb aefdcb
a
b
e
aefdbc
c
scanf("%d%d%d",&i,&j,&v);
while(i && j && v) ∥当输入i,j,v之一为0时,结束算法运行
{p=(OrArcNode *)malloc(sizeof(OrArcNode)); ∥申请结
点
p->headvex=j; p->tailvex=i; p->weight=v; ∥弧结点中权