3、 从空堆开始依次向最小堆中插入线性表（28，12，49，16，34，72，30，25，13）中的每一个元素，要求以线性表的形式给出每插入一个元素后堆的状态。再从堆中依次删除元素二个元素后堆的线性表表示。
第 29 页 共 49 页
第 30 页 共 49 页
《数据结构》作业4
得 分：
教师签名： 第七章 图
一、 填空题
1、 在一个图中，所有顶点的度数之和等于所有边数的___________倍。
2、 在一个具有n个顶点的无向完全图中，包含有_____________条边，在一个具有n个顶点的有向完全图中，包含有____________条边。
3、 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 表示图的三种存储结构分别是____________________、______________________和_____________________。
4、 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为___________。 5、 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为___________和____________条。
6、 在有向图的邻接表和逆邻接表中，每个顶点的邻接表分别链接着该顶点的所有 _____________和_____________结点。
7、 对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为___________和_____________条。
8、 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和 边集数组表示时，求任一顶点度数的时间复杂度依次为__________、__________和_______________。
9、 假定一个图具有n个顶点和e条边，当分别采用邻接矩阵、邻接表和边集数组
第 31 页 共 49 页
表示时，其相应的空间复杂度分另为__________、_________和_______________。 10、 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为________________， 对用邻接表表示的图进行任一种遍历时，其时间复杂度为_________________。 11、 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 __________和___________。
12、 假定用一维数组d[n]存储一个AOV网中用于拓扑排序的顶点入度， 则值为0的元素被链接成为一个_______________。
13、 图的二元组定义可叙述为：图由非空______________和______________所组成。 14、 采用邻接矩阵表示图，便于查找图中任一条边或边上的权。如要查找边( i , j )或， 则只要查找邻接矩阵中第______行第_______列的元素是否为一个有效值即可。
15、 图中的每个结点可以有_________个前驱结点和_________个后继结点。 16、 对图的遍历包括___________________和___________________这两种不同的访问顶点次序。
17、 AOV网是一个______________图。
二、 应用题
1、已知一个图G所对应的邻接矩阵表示如下所示，图中9个顶点分别为：V0，V1，V2，V3，V4，V5，V6，V7，V8请按照教材上给定的dfs1和bfs1算法，写出对图G从顶点V0出发得到的深度优先搜索遍历、广度优先搜索遍历的顶点序列。
0 1 2 3 4 5 6 7 8
?0?1??1??1?0??0?0??0??01010100001100010001000010000100001000011000100000100000000010010??0?0??0?0??0?0??1??0?0 1 2 3 4 5 6 7 8
第 32 页 共 49 页
相关推荐：
loading