资源描述：
《数据结构课后习题(第7章)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计科系2011级网络工程1班、计算机科学与技术2班《算法与数据结构》课后习题（第7章）【课后习题】第7章图2011级（）班学号：姓名：A题号一二三四五总分得分一、判断题（如果正确，在对应位置写T，否则写F。每题0.5分，共5分)123456789101.图G由两个集合V（G）和E（G）所组成，其中顶点集V（G）不能为空集，而边集E(G)可以为空集。2.一般情况下，对于稠密图G，采用邻接表存储比采用邻接矩阵存储节省省空间。3.生成树是一个连通图的极小连通子图，它含有图中全部n个顶点，但只有n-1条边。4.从不同顶点出发进行DFS或BFS，得到的生成树不同，即：
2、图的生成树不惟一。但具有n的结点，n-1条边的连通图其生成树是唯一的。5.求最小生成树的算法有Prim（普里姆）算法和Dijkstra（迪杰斯特拉算法）。6.“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。7.整个工程完成的时间为：从有向图的源点到汇点的最短路径长度。8.有n个顶点的无向连通图至少有n-1条边,有n个顶点的强连通图至少有n条边。9.若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系,则这样的有向图叫做用顶点表示活动的网络，简称AOV网。10.十字链表是无向图的另一种链式结构。二、单项选择（请将正确答案
3、的代号填写在下表对应题号下面。每题1分，共30分)题号123456789101112131415答案 题号161718192021222324252627282930答案 1.在一个图中，所有顶点的度数之和等于图的边数的()倍。第10页共10页计科系2011级网络工程1班、计算机科学与技术2班《算法与数据结构》课后习题（第7章）A).1/2B)1C)2D).41.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A)1/2 B)1 C)2 D)42.若用邻接矩阵表示一
4、个有向图，则其中每一列包含的″1″的个数为（）。A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目3.图的邻接矩阵表示法适用于表示（）。A．无向图B．有向图C．稠密图D．稀疏图4.任何一个无向连通图的最小生成树（）。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在5.一个有n个顶点的无向图最多有（）条边。A.n B.n(n-1) C.n(n-1)/2 D.2n6.具有4个顶点的有向完全图有（）条边。A.6 B.12 C.16 D.207.n个顶
5、点e条边的带权无向连通图的最小生成树包含（）个顶点A.n-1 B.n C.n/2 D.n+18.在一个具有n个顶点的无向图中，要连通全部顶点至少需要()条边。A.n B.n+1 C.n-1 D.n/29.对于一个具有n个顶点e条边的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A.n B.n*e C.n+e D.n*n10.对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则该邻接表包含（）个边结点。A.e B.2e C.n+e D.n211.已知一有向图的邻接表
6、存储结构如图2所示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是()。A.v1,v2,v3,v5,v4 B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2 D.v1,v4,v3,v5,v2第10页共10页计科系2011级网络工程1班、计算机科学与技术2班《算法与数据结构》课后习题（第7章）1.已知一有向图的邻接表存储结构如图2所示。根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是()。A.v1,v2,v3,v4,v5 B.v1,v3,v2,v4,v5C.v1,v2,v
7、3,v5,v4 D.v1,v4,v3,v5,v22.采用邻接表存储的图的深度优先遍历算法类似于二叉树的()。A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历3.采用邻接表存储的图的广度优先遍历算法类似于二叉树的()。A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历4.关键路径是AOE网络中()。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路 D.最短的回路5.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应
8、邻接表中该顶点单链表中的结点数为()。A.k1
