发布时间 : 星期日 文章数据结构、算法与应用(C++语言描述)》习题参考答案doc更新完毕开始阅读9218270c7e192279168884868762caaedd33ba88
结点所对应字符的哈夫曼码。
15. 请简述树的四种常用表示方式。
双亲表示法：在孩子结点中设置一个指针域记录其双亲结点的存储位置。 孩子表示法：在双亲结点中设置指向孩子结点的指针域来表示一棵树。
孩子双亲表示法：综合了孩子表示法和双亲表示法的特点，既在孩子结点中设置记录双亲结点位置的指针域，又在双亲结点中设置记录孩子结点位置的指针域。
孩子兄弟表示法：又称为二叉链表表示法，与二叉树的二叉链表表示法存储结构完全相同，只是结点中指针域的含义有所不同（一个指针域指向该结点的第一个孩子结点，另一个指针域指向该结点的下一个兄弟结点）。 16. 请简述森林转换为二叉树的具体步骤。
将森林中的每棵树都用二叉链表表示法表示，并将各棵二叉树的根结点看做是兄弟结点，在它们之间加上连线；将结点到第一个孩子结点的连线作为左子树的边，结点到兄弟结点的连线作为右子树的边。
17. 请简述二叉树转化为树或森林的具体步骤。
将一个结点左子树的边作为该结点指向第一个孩子结点的连线，右子树的边作为该结点到兄弟结点的连线；在双亲结点和它的各孩子结点之间加上连线，并删除兄弟结点之间的连线，得到一棵树或一个包含若干棵树的森林。
第6章 图
1. 请简述图的结构特性。
图G由顶点（图中通常将结点称为顶点）的非空有限集合V和边的集合E组成，记为G=(V, E)。每一个顶点偶对就是图中的一条边，所以，E用于表示V上的连接关系。在一个图中，至少要包含一个顶点，但可以没有任何边。
2. 请解释有向图、无向图、弧、弧尾、弧头、顶点的度、顶点的入度、顶点的出度、路径、路径长度、回路、简单回路、连通图、单向连通图、强连通图、子图、连通分量、强连通分量、权、带权图、生成树、最小生成树等基本术语的含义。
有向图、弧、弧尾和弧头：若E(G)中的顶点偶对是有序的，则这些有序偶对就形成了有向边，此时图G称为有向图。其中，有向边也简称为弧。在有向图G中，对于一条从顶点vi到顶点vj的弧，记为
无向图：若E(G)中的顶点偶对是无序的，则这些无序偶对就形成了无向边，此时图G称为无向图。
顶点的度、顶点的入度和顶点的出度：在无向图中，与顶点vi相关联的边的数目称为顶点vi的度。在有向图中，以顶点vi为弧头的弧的数目称为顶点vi的入度；以顶点vi为弧尾的弧的数目称为vi的出度；顶点vi的入度和出度之和称为vi的度。
1n-1路径和路径长度：在图G中，若存在一个顶点序列(v0i,vi, …, vi)，使得对于任意
0≤j n-1列是从顶点v0i到顶点vi的一条路径。一条路径中边的数目称为路径长度。 回路和简单回路：在一条路径中，若组成路径的顶点序列中第一个顶点与最后一个顶点相同，则该路径称为回路（或环）；在一个回路中，若除第一个顶点与最后一个顶点外，其他顶点只出现一次，则该回路称为简单回路（或简单环）。 连通图：无向图G中，若任意两个顶点都是连通的，则称G为连通图。 单向连通图和强连通图：有向图G中，若任意两个顶点都是单向连通的，则称G是单向连通图；若任意两个顶点都是强连通的，则称G为强连通图。 子图：对于图G、G'，若满足V(G')?V(G)且E(G')?E(G)，则G'是G的子图。 连通分量和强连通分量：一个无向图的极大连通子图称为该无向图的连通分量；一个有向图的极大强连通子图称为该有向图的强连通分量。 权和带权图：可以为一个图中的每条边标上一个具有某种意义的实数，该实数就称为是边的权。边上带权的图就称为带权图。 生成树和最小生成树：若无向图G的一个子图G'是一棵包含图G所有顶点的树，则G'称为图G的生成树。在所有形式的生成树中，边上的权之和最小的生成树，称为最小生成树。 3. 请列举可以用图来描述的实际问题。 请参考例6-1和例6-2。 4. 请简述图的基本操作及各操作的含义。 创建图：创建不包含任何顶点和边的空图。 对图作深度优先遍历：类似于树的先序遍历，即从某一个顶点开始访问，访问后将该顶 点去除得到若干子图，对每个子图再依次进行深度优先遍历。 对图作广度优先遍历：类似于树的逐层遍历，即先从某一个顶点开始访问，然后访问与该顶点相邻接且未被访问过的顶点集V1(G)，再访问与V1(G)中顶点相邻接且未被访问过的顶点集V2(G)，重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图，还要从某一个未被访问的顶点开始重复上一过程，直至所有顶点访问完毕。 获取顶点数目：获取图中所包含的顶点的数目。 获取边的数目：获取图中所包含的边的数目。 获取与指定顶点相关联的第一条边：对无向图，获取到与指定顶点相关联的第一条边；对有向图，获取到以指定顶点作为弧尾的第一条弧。不同表示方法获取到的结果会有所不同（邻接矩阵法按顶点编号顺序，邻接压缩表和邻接链表按边的添加顺序）。 获取与指定边有相同关联顶点的下一条边：对无向图，获取到与指定边(nV1,nV2) 有相同关联顶点nV1的下一条边；对有向图，获取到与指定弧 添加一条边：对无向图，向图中添加一条新边；对有向图，向图中添加一条新弧。 获取一个顶点中存储的数据：根据顶点编号获取该顶点中存储的数据。 判断一条边是否存在：对无向图，判断两个顶点nV1和nV2之间是否存在边；对有向图，判断是否存在从顶点nV1到顶点nV2的弧。 设置一条边的权：对无向图，设置指定边(nV1,nV2)上的权；对有向图，设置指定弧 获取一条边的权：对无向图，获取指定边(nV1,nV2)上的权；对有向图，获取指定弧 5. 请简述图的三种常用表示方法。 邻接矩阵法：用矩阵来表示各顶点之间的连接关系。对于有n个顶点的图G=(V, E)，其邻接矩阵A为n*n的方阵，元素A[i][j]（0≤i,j ?wA[i][j]??ij??对无向图存在(vi,vj)?E(G)，对有向图存在?vi,vj??E(G)反之 其中，wij为边(vi, vj)或 邻接压缩表：邻接矩阵的一种压缩表示形式，使用3个顺序表来表示图中顶点之间的连接关系和权。设图中共有n个顶点{v0, v1, …, vn-1}，3个顺序表分别为s、w和h。在s中依次记录与顶点vi（i = 0, 1, …, n-1）相关联的顶点；在w中依次记录s中存储的各条边的权；在h中依次记录与顶点vi相关联的顶点在s中的起始存储位置。 邻接链表：图的一种链式存储结构。每个顶点中设置一个指向链表头的指针，在链表中保存与该顶点相邻接的顶点信息（包括顶点位置及两个顶点形成的边的权）。 6. 请简述图的两种常用遍历方法及每一种遍历方法中结点的访问顺序。 广度优先遍历：类似于树的逐层遍历，即先从某一个顶点开始访问，然后访问与该顶点相邻接且未被访问过的顶点集V1(G)，再访问与V1(G)中顶点相邻接且未被访问过的顶点集V2(G)，重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图，还要从某一个未被访问的顶点开始重复上一过程，直至所有顶点访问完毕。 深度优先遍历：类似于树的先序遍历，即从某一个顶点开始访问，访问后将该顶点去 除得到若干子图，对每个子图再依次进行深度优先遍历。 7. 请列举最小生成树和最短路径可以用于解决什么应用问题。 请参考例6-1和例6-2。 8. 请简述Prim算法的作用和具体步骤。 Prim算法用于最小生成树问题求解。对于有n个顶点的图G=(V, E)，Prim算法从空树T开始，按照以下规则将n个顶点和n-1条边依次添加到树中，形成最小生成树： （a）从某一顶点v0'开始，将该顶点作为树的根结点加入到T中，使得T中的数据元素集合D={v0'}，数据元素关系集合R={}。 （b）对于一个顶点在集合D中、另一个顶点在集合V-D中的那些边，找出权最小的一条边，将该边在集合V-D中的顶点vi（'i=1,2,…,n-1）加入到集合D中，并将顶点间关系 （c）重复上一步骤直至集合D中包括图G中所有n个顶点（此时关系集合R中包括n-1条边）。若在某一步骤中找不到边，则说明图G是一个非连通图或非强连通图，在这种情况下不存在最小生成树。 9. 请简述Kruskal算法的作用和具体步骤。 Kruskal算法用于最小生成树问题求解。对于有n个顶点的图G=(V, E)，Kruskal算法根据图G中所有n个顶点生成一个包括n棵只有根结点的树T（的森林F，并按照ii=0, 1, …, n-1）以下规则森林F中的树合并，形成最小生成树： （a）从边集合E中选取未被访问过且具有最小权的边，置该边状态为已访问。判断该边的两个顶点是否属于不同的树，若属于不同的树则使用该边将两棵树合并为一棵；若属于同一棵树则不做任何处理。 （b）重复上一步骤直至森林F中只剩下一棵树，该树即是图G的最小生成树。若最后森林F中剩下不止一棵树，则说明图G是非连通图或非强连通图，在这种情况下不存在最小生成树。 10. 请简述Dijkstra算法的作用和具体步骤。 Dijkstra算法用于计算从某个顶点到其余各顶点的最短路径。对于有n个顶点的图G=(V, E)，若要计算从顶点v0'到其余各顶点vi'（i=1,2,…,n-1）的最短路径，则其计算步骤为： （a）令集合S为已计算出最短路径的顶点集合（初始时S={v0'}），w(vj', vi')表示从顶点vj'到顶点vi'的边的权（这里为方便计算，令w(vi', vi')=0），D(v0', vi')表示当前计算得到的从顶点v0'到顶点vi'的最短路径长度（初始D(v0', vi')= w(v0', vi')）。 （b）将顶点vm'?argmin(D(v0',vi'))加入到集合S中，并将从顶点v0'到顶点vm'的最短 vi'?V?S路径记录下来。若仍有顶点没有加到集合S中，则对集合V-S中的顶点vi'计算D(v0',vi')?min(D(v0',vj')?w(vj',vi'))。 vj'?S（c）重复上一步骤直至图中所有顶点都加到集合S中。 11. 请简述Floyd算法的作用和具体步骤。 Floyd算法用于计算每一对顶点之间的最短路径。对于有n个顶点的图G=(V, E)，若要计算任意两个顶点vj'和vk'（j,k为[0,n-1]区间上的整数且j≠k）之间的最短路径，则其计算步骤为： （a）令w(vj', vk')表示连接顶点vj'和顶点vk'的边的权（这里为方便计算，令w(vj', vj')=0），D(vj', vk')表示当前计算得到的从顶点vj'到顶点vk'的最短路径长度（初始D(vj', vk')= w(vj', vk')）。 （b）对于图中每一个顶点vi'（i依次取值为0, 1, …, n-1），若D(vj',vk')>D(vj',vi')+D(vi',vk')，则表明路径(vj', …, vi', …, vk')的长度更短，此时令D(vj',vk')=D(vj',vi')+D(vi',vk')并更新从顶点vj'到