数据结构(习题二).ppt

数 据 结 构,习 题 二,第四部分 树与二叉树,考点一 树的概念,本考点主要考查： 树的基本概念,第四部分 树与二叉树,考点一 树的概念,1. 下列有关树的概念错误的是 ( ) A. 一棵树中只有一个无前驱的结点 B. 一棵树的度为树中各个结点的度数之和 C. 一棵树中，每个结点的度数之和等于结点总数减 1 D. 一棵树中每个结点的度数之和与边的条数相等,【解析】本题考查树的相关概念。 一棵树中只有根结点没有前驱结点， 除根结点之外，每个结点都有一个前驱结点， 即父结点，故而 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. 2h B. 2h-1 C. 2h+1 D. h+1,B,【解析】 高度为 h，而且只有度数为 0 或者 2 的结点，这是什么样的树呢？如下图所示的二叉树就是一棵这样的二叉树。,由图可以观察出，除了第 1 层，其他每一层都是两个结点，故而总共有结点 2 （ h-1）+1=2h-1。,第四部分 树与二叉树,考点二 二叉树二叉树的定义及其主要特征,2. 以下说法错误的是 ( ) A. 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同 B. 二叉树是树的特殊情形 C. 由树转换成二叉树，其根结点的右子树总是空的 D. 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树,【解析】 尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形，故而 B 答案错误。 对于 A 答案，如果二叉树中只有一个根结点，则不管采用什么样的遍历算法，所得访问序列都是一样的。 对于 C 答案，树转换成二叉树时，树的左孩子为树的一个孩子，第二个孩子成为其左孩子的右孩子，第三个孩子（如果存在的话）成为其左孩子的右孩子的右孩子。故而，根结点的右子树总是空的。 二叉树是有序树，其左右孩子有次序之分，即使只有一棵子树也要明确指出该子树是左子树还是右子树。,B,第四部分 树与二叉树,考点二 二叉树二叉树的顺序和链式存储结构,用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中 R1n，结点 Ri若有左孩子，其左孩子的编号为结点 ( ),A. R2i+1 B. R2i C. Ri/2 D. R2i-1,B,【解析】 将完全二叉树存储在数组中 R1n中，结点 Ri若有左孩子，其左孩子的编号为结点 R2i，若有右孩子，则右孩子的编号为结点 R2i+1。故而，本题选择 B 答案。 值得注意的是，一般二叉树的顺序存储，将每个结点与完全二叉树上的结点相对照，然后存储在数组的相应位置中，缺少的结点用“ 0”补齐。,第四部分 树与二叉树,考点二 二叉树二叉树的遍历,1. 该二叉树结点的前序遍历的序列为( ) A. E、 G、 F、 A、 C、 D、 B B. E、 A、 G、 C、 F、 B、 D C. E、 A、 C、 B、 D、 G、 F D. E、 G、 A、 C、 D、 F、 B,C,【解析】 前序遍历首先访问根结点，其次遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，即遍历左右子树时仍然采用前序遍历方法。 对题中的二叉树进行前序遍历，可以得到序列 EACBDGF，故而选择 C答案。,第四部分 树与二叉树,考点二 二叉树二叉树的遍历,2. 该二叉树结点的中序遍历的序列为 ( ) A. A、 B、 C、 D、 E、 G、 F B. E、 A、 G、 C、 F、 B、 D C. E、 A、 C、 B、 D、 G、 F D. B、 D、 C、 A、 F、 G、 E,【解析】 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树，即遍历左右子树时仍然采用中序遍历方法。 对题中的二叉树进行中序遍历，可以得到序列 ABCDEGF，故而选择 A答案。,A,第四部分 树与二叉树,考点二 二叉树二叉树的遍历,3. 该二叉树的按层遍历的序列为 （ ） A. E、 G、 F、 A、 C、 D、 B B. E、 A、 C、 B、 D、 G、 F C. E、 A、 G、 C、 F、 B、 D D. 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-1 B. N2-1 C. N2+N3 D. 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. 60 B. 66 C. 67 D. 50,C,【解析】哈夫曼树的构造过程如下： (1). 根据给定的 n 个权值w1, w2, , wn，构造 n 棵二叉树的集合 F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树; (2). 在 F 中选取根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (3). 从 F 中删去这两棵树，同时将刚生成的新树加入到 F 中; (4). 重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。,由五个分别带权值为 9， 2， 3， 5， 14 的叶子结点构成的一棵哈夫曼树，该哈夫曼树如下图所示。,第四部分 树与二叉树,考点四 树和二叉树的应用哈夫曼树和哈夫曼编码,由上图可知，该哈夫曼树的带权路径长度为 WPS=(2+3) 4 + 5 3 + 9 2 + 14 = 67,第四部分 树与二叉树,考点四 树和二叉树的应用哈夫曼树和哈夫曼编码,2. 设某哈夫曼树中有 199 个结点，则该哈夫曼树中有( )个叶子结点。 A. 99 B. 100 C. 101 D. 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,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 (2). 根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 （ ） A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. 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. 21 B. 26 C. 28 D. 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, V7 B. V1, V3, V5, V6, V4, V2, V7 C. V1, V3, V4, V5, V2, V6, V7 D. 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 中没