数据结构习题二课件.ppt

数据结构,习题二,第四部分树与二叉树,考点一树的概念,本考点主要考查：树的基本概念,第四部分树与二叉树,考点一树的概念,1.下列有关树的概念错误的是()A.一棵树中只有一个无前驱的结点B.一棵树的度为树中各个结点的度数之和C.一棵树中，每个结点的度数之和等于结点总数减1D.一棵树中每个结点的度数之和与边的条数相等,【解析】本题考查树的相关概念。一棵树中只有根结点没有前驱结点，除根结点之外，每个结点都有一个前驱结点，即父结点，故而A答案正确。通常我们把一个结点拥有子树的个数称为该结点的度数，所以结点的度数之和等于除根结点外所有结点的个数，即每个结点的度数之和等于结点总数减1，故而C答案正确。结点的度等于该结点子树的个数，而结点与子树之间是以边连接的，所以一棵树中每个结点的度数之和与边的条数相等，D答案正确。一棵树的度等于结点中度数最大的结点的度数，而不是树中各结点的度数之和。故而，B答案错误。,B,第四部分树与二叉树,考点一树的概念,2.有一棵树如右图所示，回答下面的问题：,(1).这棵树的根结点是_.(2).这棵树的叶子结点是_.(3).结点k3的度是_.(4).这棵树的度是_.(5).这棵树的深度是_.(6).结点k3的孩子结点是_.(7).结点k3的父结点是_.,k1,k2,k5,k7,k4,2,3,4,k5,k6,k1,【解析】由图可知，(1).这棵树的根结点是结点k1。(2).这棵树的叶子结点是k2、k5、k7、k4。(3).k3结点有2个孩子结点k5与k6，故而其度为2。(4).树的度等于数中度最大的结点的度数，本题中度数最大的结点为根结点，度数为3。故而，树的度为3。(5).很显然本题的树的层数为4层，第一层（层数我们从1开始算）有结点k1，第二层有结点k2、k3和k4，第三层有结点k5和k6，第四层有结点k7。因而，树的深度为4。(6).k3结点的孩子结点为k5、k6。(7).k3结点的父结点是结点k1。,第四部分树与二叉树,考点一树的概念,第四部分树与二叉树,考点二二叉树,本考点主要考查：二叉树包括：1、二叉树的定义及其主要特征；2、二叉树的顺序存储结构和链式存储结构；3、二叉树的遍历；4、线索二叉树的基本概念和构造。,第四部分树与二叉树,考点二二叉树二叉树的定义及其主要特征,设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）A.2hB.2h-1C.2h+1D.h+1,B,【解析】高度为h，而且只有度数为0或者2的结点，这是什么样的树呢？如下图所示的二叉树就是一棵这样的二叉树。,由图可以观察出，除了第1层，其他每一层都是两个结点，故而总共有结点2（h-1）+1=2h-1。,第四部分树与二叉树,考点二二叉树二叉树的定义及其主要特征,2.以下说法错误的是()A.存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B.二叉树是树的特殊情形C.由树转换成二叉树，其根结点的右子树总是空的D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树,【解析】尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形，故而B答案错误。对于A答案，如果二叉树中只有一个根结点，则不管采用什么样的遍历算法，所得访问序列都是一样的。对于C答案，树转换成二叉树时，树的左孩子为树的一个孩子，第二个孩子成为其左孩子的右孩子，第三个孩子（如果存在的话）成为其左孩子的右孩子的右孩子。故而，根结点的右子树总是空的。二叉树是有序树，其左右孩子有次序之分，即使只有一棵子树也要明确指出该子树是左子树还是右子树。,B,第四部分树与二叉树,考点二二叉树二叉树的顺序和链式存储结构,用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若有左孩子，其左孩子的编号为结点(),A.R2i+1B.R2iC.Ri/2D.R2i-1,B,【解析】将完全二叉树存储在数组中R1n中，结点Ri若有左孩子，其左孩子的编号为结点R2i，若有右孩子，则右孩子的编号为结点R2i+1。故而，本题选择B答案。值得注意的是，一般二叉树的顺序存储，将每个结点与完全二叉树上的结点相对照，然后存储在数组的相应位置中，缺少的结点用“0”补齐。,第四部分树与二叉树,考点二二叉树二叉树的遍历,1.该二叉树结点的前序遍历的序列为()A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B,C,【解析】前序遍历首先访问根结点，其次遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，即遍历左右子树时仍然采用前序遍历方法。对题中的二叉树进行前序遍历，可以得到序列EACBDGF，故而选择C答案。,第四部分树与二叉树,考点二二叉树二叉树的遍历,2.该二叉树结点的中序遍历的序列为()A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.B、D、C、A、F、G、E,【解析】中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树，即遍历左右子树时仍然采用中序遍历方法。对题中的二叉树进行中序遍历，可以得到序列ABCDEGF，故而选择A答案。,A,第四部分树与二叉树,考点二二叉树二叉树的遍历,3.该二叉树的按层遍历的序列为（）A.E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B,C,【解析】层次遍历，也是常见的二叉树遍历算法。层次遍历二叉树，即从上到下，从左到右遍历二叉树的结点。对题中的二叉树进行层次遍历，可以得到序列EAGEFBD，故而选择C答案。,第四部分树与二叉树,考点二二叉树线索二叉树的基本概念和构造,1.引入二叉线索树的目的是()A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一,【解析】引入二叉线索树的目的是有效利用空指针域，提高遍历运算的效率，加快查找结点的前驱或者后继结点的速度，简化遍历算法。对于有n个结点的线索二叉树上含有n+1条线索。,A,2.在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是()A.左子树的最右下结点B.右子树的最右下结点C.左子树的最左下结点D.右子树的最左下结点,第四部分树与二叉树,考点二二叉树线索二叉树的基本概念和构造,【解析】二叉树的线索化说透了就是按照某种遍历算法将结点的线索引向前驱或者后继（若不存在左孩子，则左指针引向该遍历序列的直接前驱结点；若不存在右孩子，则右指针引向该遍历序列的直接后继结点）。若中序遍历时，某结点有右孩子，那么该结点中序遍历的直接后继应该是其右子树的最左下的结点。故而，本题选择D答案。,D,第四部分树与二叉树,考点三树和森林,本考点主要考查：1、树的存储结构；2、森林与二叉树的转换；3、树和森林的遍历。本部分内容的命题形式比较固定，解题方法也比较固定，同学们可以通过掌握一个题的解题方法，而掌握一类题型的解题方法。,第四部分树与二叉树,考点三树和森林,1.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为()A.N1-1B.N2-1C.N2+N3D.N1+N3,A,【解析】本题道理与第1题相同。F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数N1-1。,第四部分树与二叉树,考点四树和二叉树的应用,本考点主要考查：1、二叉排序树；2、平衡二叉树；3、哈夫曼(Huffman)树和哈夫曼编码。前两个知识点结合课本第九章出题，这里主要掌握第三个知识点。,第四部分树与二叉树,考点四树和二叉树的应用哈夫曼树和哈夫曼编码,1.由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为()A.60B.66C.67D.50,C,【解析】哈夫曼树的构造过程如下：(1).根据给定的n个权值w1,w2,wn，构造n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树;(2).在F中选取根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(3).从F中删去这两棵树，同时将刚生成的新树加入到F中;(4).重复(2)和(3)两步，直至F中只含一棵树为止。,2019/12/16,19,可编辑,由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该哈夫曼树如下图所示。,第四部分树与二叉树,考点四树和二叉树的应用哈夫曼树和哈夫曼编码,由上图可知，该哈夫曼树的带权路径长度为WPS=(2+3)4+53+92+14=67,第四部分树与二叉树,考点四树和二叉树的应用哈夫曼树和哈夫曼编码,2.设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。A.99B.100C.101D.102,B,【解析】正如第一题所言，哈夫曼树其实是二叉树的一种。哈夫曼树的特点是没有度为1的结点，根据二叉树的性质可知n0=n2+1。所以，具有n0个叶子结点的二叉树具有n0-1个度为2的结点。当n=199时，n0+n2=199，可知n0=100，n2=99。故而，本题选择B答案。,第五部分图,考点一图的基本概念,本部分考查图的基本概念，包括：1、顶点、边、度、完全图、子图、路径、连通图等基本概念；2、图的顶点集和边集的表示。本考点考查的都是图的基本内容,连通分量指的是（）无向图中的极小连通子图B.无向图中的极大连通子图C.有向图中的极小连通子图D.有向图中的极大连通子图,第五部分图,考点一图的基本概念,B,【解析】本题考查连通分量的基本概念。连通分量是针对无向图而言的，是无向图中的极大连通子图（与极小连通子图进行区别）。如下图左图所示，无向图G有3个连通分量，分别如右图所示。,第五部分图,考点二图的存储及基本操作,本考点考查图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构表示及相应的空间复杂度。,第五部分图,考点二图的存储及基本操作,1.图的邻接矩阵表示法适用于表示（）A.无向图B.有向图C.稠密图D.稀疏图,【解析】常见的图的存储方式有主要有两种：邻接矩阵和邻接表。邻接矩阵属于顺序存储结构，邻接表属于链式存储结构。邻接矩阵易于实现图的操作，但对稀疏图而言尤其浪费空间。故而，邻接矩阵一般用于存储稠密图（邻接表一般适用于稀疏图）。,C,2.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）A.第i行非无穷的元素之和B.第i列非无穷且非0的元素个数C.第i行非无穷且非0的元素个数D.第i行与第i列非无穷且非0的元素之和,第五部分图,考点二图的存储及基本操作,【解析】对于邻接矩阵表示的有向图，第i行表示的是顶点Vi的出度，而第i列表示的是顶点Vi的入度。带权图不同于不带权图，带权图Aij=x表示从Vi到Vj的边的权值为x，而在不带权图中，邻接矩阵中只有0、1两个值，值为1表示从Vi到Vj有边，为0则表示没有边。故而，第i列非无穷且非0元素的元素个数之和，即为顶点A的入度。,B,第五部分图,考点三图的遍历,本考点主要考查图的深度优先、广度优先搜索遍历和层次遍历的过程。请同学们掌握用邻接表和邻接矩阵存储表示下，图的深度优先遍历、广度优先遍历和层次遍历的方法和时间复杂度。,第五部分图,考点三图的遍历,1.已知一有向图的邻接表存储结构如下图所示。,(1).根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2(2).根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2,C,B,第五部分图,考点三图的遍历,【解析】为了说明深度优先遍历和广度优先遍历，我们给出了本题。请同学们多留意遍历方法。(1).从顶点v1出发，发起深度优先遍历，经过v1v3,再v3v4，v4没有后续顶点，转回v3，v3的后续顶点中还有v5没有被遍历过，于是找到v3v5，再由v5v2。因而，得到一个序列v1v3v4v5v2。选择C答案。(2).从顶点v1出发，发起广度优先遍历。因为从v1发出，有一条有向边v1v3。因此，有序列v1v3v2，可有序列v1v3v2v4v5，选择B答案。,第五部分图,考点四图的应用,本考点主要考查图的应用，包括最小生成树、最短路径、拓扑排序和关键路径。本考点特别重要。,第五部分图,考点四图的应用最小生成树,1.已知一个图G如图所示，在该图的最小生成树中各边上数值之和为（）,A.21B.26C.28D.33,B,第五部分图,考点四图的应用最小生成树,【解析】我们可以利用克鲁斯卡尔算法构造最小生成树，过程如图所示。,由图可知，原图的最小生成树各边上的权值之和为2+3+4+7+10=26，故而选择B答案。,第五部分图,考点四图的应用拓扑排序,1.已知有向图G=(V,E),其中V=V1,V2,V3,V4,V5,V6,V7，E=,，G的拓扑序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V5,V6,V4,V2,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7,A,第五部分图,考点四图的应用拓扑排序,【解析】本题考查有向图的拓扑排序方法。本题中的图G如图所示。对图G进行拓扑排序，其中的一个排序过程如图所示。,由图5.24可得到一个拓扑序列为V1、V3、V4、V6、V2、V5、V7。当然，本题的图G的拓扑排序可以得到多个正确的序列，比如V1、V2、V3、V4、V5、V6、V7或V1、V3、V4、V2、V6、V5、V7等等。本题选A。,第五部分图,考点四图的应用拓扑排序,2.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没有弧D.G中有一条从Vj到Vi