数据结构习题7---图

这篇具有很好参考价值的文章主要介绍了数据结构习题7---图。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、单选题             

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

             A.1/2            B.  1             C.  2             D.  4 

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

             A.1/2            B.  1             C.  2             D.  4 

(  B  )3. 有8个结点的无向图最多有      条边。

             A.14            B.  28             C.  56             D.  112

(  C  )4. 有8个结点的无向连通图最少有      条边。

             A.5            B.  6             C.  7             D.  8

(  C  )5. 有8个结点的有向完全图有      条边。

             A.14            B.  28             C.  56             D.  112

(  B  )6. 用邻接表表示图进行广度优先遍历时,通常是采用         来实现算法的。

A.栈            B. 队列            C.               D.  

(  A  )7. 用邻接表表示图进行深度优先遍历时,通常是采用         来实现算法的。

A.栈            B. 队列            C.               D.  

(  C  )8. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是

数据结构习题7---图数据结构习题7---图

(  D  )9. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按深度优先遍历的结点序列是

A. 0 2 4 3 1 5 6      B.  0 1 3 5 6 4 2     C.  0 4 2 3 1 6 5   D.  0 1 3 4 2 5 6

B )10. 已知图的邻接矩阵同上题8,根据算法思想,则从顶点0出发,按广度优先遍历的结点序列是

A. 0 2 4 3 6 5 1      B.  0 1 3 6 4 2 5      C.  0 4 2 3 1 5 6   D.  0 1 3 4 2 5 6

(  C  )11. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是

A. 0 2 4 3 1 6 5     B.  0 1 3 5 6 4 2     C.  0 1 2 3 4 6 5   D.  0 1 2 3 4 5 6

(  D  )12. 已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是数据结构习题7---图

数据结构习题7---图 

(  A  )13.  已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是

数据结构习题7---图 

(  A  )14. 深度优先遍历类似于二叉树的

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

(  D  )15. 广度优先遍历类似于二叉树的

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

(  A  )16. 任何一个无向连通图的最小生成树

A.只有一棵     B.  一棵或多棵     C.  一定有多棵    D.  可能不存在

(注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一)

二、填空题

1. 图有 邻接矩阵    邻接表  等存储结构,遍历图有 深度优先遍历   广度优先遍历   等方法。

2. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i   出度   

3. 如果n个顶点的图是一个环,则它有    n    棵生成树。  (以任意一顶点为起点,得到n-1条边)

4.  n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为   O(n2)    

5.  n个顶点e条边的图,若采用邻接表存储,则空间复杂度为    O(n+e)    

6. 设有一稀疏图G,则G采用  邻接表   存储较省空间。

7. 设有一稠密图G,则G采用  邻接矩阵   存储较省空间。

8. 图的逆邻接表存储结构只适用于   有向  图。

9. 已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0  

10. 图的深度优先遍历序列  不是  惟一的。

11.  n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为   O(n2) ;若采用邻接表存储时,该算法的时间复杂度为  O(n+e)    

12. n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为   O(n2)    ;若采用邻接表存储,该算法的时间复杂度为   O(n+e)    

13. 图的BFS生成树的树高比DFS生成树的树高 小或相等     

14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为  O(n2)     ;用克鲁斯卡尔(Kruskal)算法的时间复杂度是   O(elog2e)     

15. 若要求一个稀疏图G的最小生成树,最好用  克鲁斯卡尔(Kruskal)  算法来求解。

16. 若要求一个稠密图G的最小生成树,最好用  普里姆(Prim)   算法来求解。

17. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度   递增   的次序来得到最短路径的。

18.  拓扑排序算法是通过重复选择具有   0   个前驱顶点的过程来完成的。

三、分析求解题

1. 已知如图所示的有向图,请给出该图的:

数据结构习题7---图 数据结构习题7---图

 

  1. 每个顶点的入/出度;
  2. 邻接矩阵;
  3. 邻接表;
  4. 逆邻接表。

 答案:

数据结构习题7---图

2. 请对下图的无向带权图:

数据结构习题7---图 

  1. 写出它的邻接矩阵,并按普里姆算法求其最小生成树;
  2. 写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。

                                                                   

解:设起点为a。可以直接由原始图画出最小生成树,而且最小生成树只有一种(类)!

邻接矩阵为:                                         数据结构习题7---图

PRIM算法(横向变化):                                                            

V

b

c

d

e

f

g

h

U

V-U

Vex

lowcost

a

4

a

3

a

a

a

a

a

{a}

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

Vex

lowcost

a

4

0

c

5

a

a

a

c

5

{a,c}

{b, d,e,f,g,h}

Vex

lowcost

0

0

c

5

b

9

a

a

c

5

{a,c,b}

{d,e,f,g,h}

Vex

lowcost

0

0

0

d

7

d

6

d

5

d

4

{a,c,b,d }

{e,f,g,h}

Vex

lowcost

0

0

0

d

7

d

6

d

5

0

{a,c,b,d ,h }

{e,f,g }

Vex

lowcost

0

0

0

d

7

g

2

0

0

{a,c,b,d ,h ,g}

{ f,e }

Vex

lowcost

0

0

0

f

3

0

0

0

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

{e }

Vex

lowcost

0

0

0

0

0

0

0

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

{ }

邻接表为:

a

b

4

c

3

b

a

4

c

5

d

5

e

9

^

c

a

3

b

5

d

5

h

5

^

d

b

5

c

5

e

7

f

6

g

5

h

4^

e

b

9

d

7

f

3

^

f

d

6

e

3

g

2

^

g

d

5

f

2

h

6

^

h

c

5

d

4

g

6

^

数据结构习题7---图

先罗列:f---2---g    a3--c   f3—e   a4---b   d—4—h     

(a,b,c)   (e,f,g)   (d,h)   b—5—d,  g—5--d  就把三个连通分量连接起来了。

3. 已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

数据结构习题7---图

4. 试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。

数据结构习题7---图

解:最短路径为:(a,c,f,e,d,g,b

数据结构习题7---图


5.给定下列网G:

      数据结构习题7---图

(1) 试着找出网G的最小生成树,画出其逻辑结构图;

(2) 用两种不同的表示法画出网G的存储结构图;

(3) 用C语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型。

解:1 )最小生成树可直接画出,如右图所示。

数据结构习题7---图

 

(2)可用邻接矩阵和邻接表来描述:

数据结构习题7---图数据结构习题7---图

邻接表为:

a

b

12

e

4

^

b

a

12

c

20

e

8

f

9

^

c

b

20

d

15

g

12

^

d

c

15

g

10

^

e

a

4

b

8

f

6

^

f

b

9

e

6

^

g

c

12

d

10

五、算法设计题

1. 编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解:Status Build_AdjList(ALGraph &G)  //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表

{

  InitALGraph(G);

  scanf("%d",&v);

  if(v<0) return ERROR; //顶点数不能为负

  G.vexnum=v;

  scanf("%d",&a);

  if(a<0) return ERROR; //边数不能为负

  G.arcnum=a;

  for(m=0;m<v;m++)

    G.vertices[m].data=getchar(); //输入各顶点的符号

  for(m=1;m<=a;m++)

  {

    t=getchar();h=getchar(); //t为弧尾,h为弧头

    if((i=LocateVex(G,t))<0) return ERROR;

    if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到

    p=(ArcNode*)malloc(sizeof(ArcNode));

    if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;

    else

    {

      for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);

      q->nextarc=p;

    }

    p->adjvex=j;p->nextarc=NULL;

  }//while

  return OK;

}//Build_AdjList

2. 试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w) ,即删除一条边的操作。(如果要删除所有从第i个顶点出发的边呢?  提示: 将邻接矩阵的第i行全部置0  )

解://本题中的图G均为有向无权图。

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)

  {

  if((i=LocateVex(G,v))<0) return ERROR;

  if((j=LocateVex(G,w))<0) return ERROR;

  if(G.arcs[i][j].adj)

  {

    G.arcs[i][j].adj=0;

    G.arcnum--;

  }

  return OK;

}//Delete_Arc

3. 试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(ij)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0 

{

  if(i==j) return 1; //i就是j

  else

  {

    visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc)

    {

      k=p->adjvex;

      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

    }//for

  }//else

}//exist_path_DFS

解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int level=1;//递归进行的层数

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

  if(i==j) return 1; //i就是j

  else

  {

    visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc,level--)

    { level++;

      k=p->adjvex;

      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

  }//else

if (level==1)  return 0;

}//exist_path_DFS

附加题:【严题集7.27④】采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

(注1:一条路径为简单路径指的是其顶点序列中不含有重现的顶点。

2:此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。)

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G

的顶点i到j是否存在长度为k的简单路径

{

{

  if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

  else if(k>0)

  {

    visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc)

    {

      l=p->adjvex;

      if(!visited[l])

        if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一

    }//for

    visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中

  }//else

  return 0; //没找到

}//exist_path_len文章来源地址https://www.toymoban.com/news/detail-460180.html

到了这里,关于数据结构习题7---图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构习题集

    目录 第一章 绪论 一 选择题。  二 填空题。 第二章.线性表 一 选择题。 二 填空题。 第三章.栈、队列 一 选择题。 二 填空题。 第六章.树与二叉树 一 选择题。 二 填空题。 三 简答题。 第七章.图 一 选择题。 二 填空题。 三 简答题。 第九章.查找 一 选择题。 二

    2024年02月07日
    浏览(53)
  • 数据结构习题9---查找

    一、填空题 1 .   在数据的存放无规律而言的线性表中进行检索的最佳方法是    顺序查找(线性查找)    。 2 . 线性有序表( a 1 , a 2 , a 3 ,…, a 256 ) 是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索   

    2024年02月09日
    浏览(65)
  • 【数据结构】复习题(一)

    一、选择题 1.组成数据的基本单位是()。 A. 数据项 B.数据类型 C.数据元素 D.数据变量 2.设数据结构A={D,R},其中D={1,2,3,4},R={r},r={1,2,2,3, 3,4,4,1},则数据结构A是()。 A.线性结构 B.树型结构 C.图型结构 D.集合 3.数组的逻辑结构不同于下列()的逻辑结构。 A.线性表 B.栈 C.队列 D.树 4.二

    2024年02月04日
    浏览(45)
  • 数据结构习题24/12/24

    这道题目可以考虑,如果前缀是一样的长度,那么只需要两个链表同时向后检索,直到找到一样的元素为止。所以应该先找到两个链表的长度,然后将较长的一个链表的多出来的前缀部分删掉,也就不去看这一部分。因为后缀都是一样的,所以长度的差异只可能来自前缀。

    2024年02月04日
    浏览(44)
  • 【数据结构】——图的相关习题

    1、具有n个顶点的有向完全图有()条弧边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n(n+1) 解析: (B) 若一个有向图中,若每个顶点都有互相相反的两条弧连接,则称为有向完全图,在一个含有n个顶点的有向完全图中,共有 n(n-1) 条弧。 例如,含有4个顶点的有向完全图

    2024年02月05日
    浏览(50)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第二弹)

     朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录   前言: 一、

    2024年02月10日
    浏览(88)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录 前言: 一、 二、

    2024年02月10日
    浏览(40)
  • 【数据结构】第二章课后练习题——线性结构

    1、线性表是 一个有限序列,可以为空 2、链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用 单循环链表 存储方式最节省运算时间 3、若某线性表中最常用的操作实在最后一个元素之后插入一个元素和删除第一个元素,则采用 仅有尾结点的

    2024年02月07日
    浏览(59)
  • 【数据结构】——栈、队列的相关习题

    1、栈和队列都是()。 A、顺序存储的线性结构 B、链式存储的非线性结构 C、限制存取点的线性结构 D、限制存取点的非线性结构 解析: (C) 栈 是一种只允许在一端进行插入或删除操作的线性表,它是一种特殊的线性表,它与队列具有相同的逻辑结构,都属于 线性结构

    2024年02月12日
    浏览(39)
  • 【数据结构】——排序算法的相关习题

    1、直接插入排序 1、对n个元素进行直接插入排序,需要进行()趟处理。 A、n B、n+1 C、n-1 D、2n 解析: (C) 直接插入排序是将要排序的序列按照的大小插入至已排好序的子序列中,一直进行直到整个序列有序,所以对n个元素进行直接插入排序,一共插入元素n-1次,

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包