《数据结构及其应用》笔记含答案 第六章_图

第 6 章图课后习题讲解1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

删除40 删除70 删除60struct node { int data;struct node *lchild, *rchild;};typedef struct node NODE;NODE *create_tree(a,i,j)int a[ ],i,j;{NODE *p;int k;if(i>j) return(NULL);k=(i+j)/2;p=(NODE *)malloc(sizeof(NODE));p->data=a[k];p->lchild=create_tree(a,i,k-1);p->rchild=create_tree(a,k+1,j);return(p);}6. 3int check(root)NODE *root;{int x;if(root==NULL)return(0);if(root->data<root->rchild->data&&root->data>root->lchild->data) {x=check(root->rchild);if(!x) return(check(root->lchild));}return(1);}6. 4int height(root)NODE *root;{int h,k;if(root==NULL)return(-1);else if(root->lchild==NULL&&root->rchild==NULL)return(0);elseh=height(root->lchild);k=height(root->rchild);if(h>k)return(h+1);elsereturn(k+1);}}6. 5#include “math.h”int check_beltree(root)NODE *root;{int a;if(root==NULL)return(1);if(check_beltree(root->lchild)==0||check_beltree(root->rchild)==0) return(0);a=abs(height(root->rchild)-height(root->lchild)); //上题函数if(a<=1)return(1);}6．76．8结点k1 k2 k3 k4 k5结点值10 30 50 70 90相对使用频率（pi）p1 p2 p3 p4 p55 6 3 7 4外部结点使用频率(qi) q0 q1 q2 q3 q4 q54 2 1 2 3 4 本题的分析与计算，请参考“习题6.8”（Excel表），最后结果为：。

第1章概论1.数据、数据元素、数据结构、数据类型的含义分别是什么数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。

数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。

数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。

数据类型包含取值范围和基本运算等概念。

2.什么是数据的逻辑结构什么是数据的物理结构数据的逻辑结构与物理结构的区别和联系是什么逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。

数据的逻辑结构包含下面两个方面的信息：①数据元素的信息；②各数据元素之间的关系。

物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。

数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。

采用不同的存储结构，其数据处理的效率是不同的。

因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。

3.数据结构的主要操作包括哪些对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：创建：建立一个数据结构；清除：清除一个数据结构；插入：在数据结构中增加新的结点；删除：把指定的结点从数据结构中删除；访问：对数据结构中的结点进行访问；更新：改变指定结点的值或改变指定的某些结点之间的关系；查找：在数据结构中查找满足一定条件的结点；排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。

4.什么是抽象数据类型如何定义抽象数据类型抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。

数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。

下面是一些关于栈的应用场景。

1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。

1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。

通过使用栈，我们可以很方便地进行算术运算。

1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。

将数据依次压入栈中，然后再逐个弹出即可。

2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。

下面是一些关于队列的实现和应用。

2.1 数组实现队列队列可以使用数组来实现。

我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。

2.2 链表实现队列队列还可以使用链表来实现。

我们可以使用一个指针指向队列的头部，并在尾部添加新元素。

通过移动指针来实现出队操作。

2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。

在BFS中，我们需要按照层级来访问节点。

使用队列可以帮助我们按照顺序存储和访问节点。

3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。

下面是一些关于树的遍历和应用的介绍。

3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。

通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。

3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。

通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。

3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。

这种结构可以用于高效地进行数据查找。

4. 图的表示与遍历图是由节点和边组成的一种数据结构。

下面是一些关于图的表示和遍历的说明。

4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。

使用一个二维数组来表示节点之间的连接关系。

图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为( )。