数据结构第六章练习题

精品文档 2016 全新精品资料 全程指导写作 独家原创 1 / 18 数据结构第六章练习题 1. 填空题 设无向图 G 中顶点数为 n，则图 G 至少有条边，至多有条边；若 G 为有向图，则至少有条边，至多有条边。 0， n/2， 0， n 图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 任何连通图的连通分量只有一个，即是。 其自身 图的存储结构主要有两种，分别是和。 邻接矩阵，邻接表 这是最常用的两种存储结构，此外 ，还有十字链表、邻接多重表、边集数组等。 已知无向图 G 的顶点数为 n，边数为 e，其邻接表表示的空间复杂度为。 在无向图的邻接表中，顶点表有 n 个结点，边表有 2有 n+2e 个结点，其空间复杂度为 =。 已知一个有向图的邻接矩阵表示，计算第 j 个顶点的入度的方法是。 求第 j 列的所有元素之和 精品文档 2016 全新精品资料 全程指导写作 独家原创 2 / 18 有向图 G 用邻接矩阵 Ann存储，其第 i 行的所有元素之和等于顶点 i 的。 出度 图的深度优先遍历类似于 树的遍历，它所用到的数据结构是；图的广度优先遍历类似于树的遍历，它所用到的数据结构是。 前序，栈，层序，队列 对于含有 n 个顶点 e 条边的连通图，利用 法求最小生成树的时间复杂度为，利用 ， 法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树； 法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 如果一个有向图不存在，则该图的全部顶点可以排列成一个拓扑序列。 回路 在一个有向图中，若存在弧、，则在其拓扑序列中，顶点 相对次序为。 由顶点 成的图进行拓扑排序。 2. 选择题 精品文档 2016 全新精品资料 全程指导写作 独家原创 3 / 18 在一个无向图中，所有顶点的度数之和等于所有边数的倍。 A 1/B 1 C D C 设无向图中含有 n 个顶点 e 条边，则 。 n 个顶点的强连通图至少有条边，其形状是。 A n B n+1 C n E 无回路 F 有回路 G 环状 H 树状 A， G 含 n 个顶点的连通图中的任意一条简单路径，其长度不可能超过。 A 1 B n/C n C 若超过 路径中必存在重复的顶点。 对于一个具有 n 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是。 A n B C 图的生成树， n 个顶点的生成树有条边。 A 唯一 B 不唯一 C 唯一性不能确定 D n E n +1 F ， F 精品文档 2016 全新精品资料 全程指导写作 独家原创 4 / 18 设无向图 G=和 G = ，如果 G 是 G 的生成树，则下面的说法中错误的是。 连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。 G 是一个非连通无向图，共有 28 条边，则该图至少有个顶点。 A B C D D n 个顶点的无向图中，边数 en/2 ，将 e=28 代入，有n8 ，现已 知无向图非连通，则 n=9。 最小生成树指的是 。 A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 C 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用。 A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 D 精品文档 2016 全新精品资料 全程指导写作 独家原创 5 / 18 当有向图中无回路 时，从某顶点出发进行深度优先遍历时，出栈的顺序即为逆向的拓扑序列。 下面关于工程计划的 的叙述中，不正确的是 ? A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 B 中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时 提高在几条关键路径上的关键活动。 3. 判断题 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。 精品文档 2016 全新精品资料 全程指导写作 独家原创 6 / 18 对。邻接矩阵的空间复杂度为，与边的个数无关。 图 G 的生成树是该图的一个极小连通子图 错。必须包含全部顶点。 无向图的邻接矩阵一定是对称的，有向图 的邻接矩阵一定是不对称的 错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。 错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。 在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧。 错。只能说明从顶点 a 到顶点 b 有一条路径。 第 6 章 树和二叉树 棵度为 2 的树与一棵二叉树有何区别？ 答：度为 2 的树的结点没有顺序之分，二叉树的结点有顺序。 个结点的树和 3 个结点的二叉树的所有不同形态。 k 的树中有 度为 1 的结点， 的结点， ， 度为 k 的结点，问该树中有多少个叶子结点？答： 2016 全新精品资料 全程指导写作 独家原创 7 / 18 个。 n 和 m 为二叉树中两结点，用 1、 0 或 #填写下表： 注：如果离 a 和 b 最近的共同祖先 p 存在，且 a 在 p 的左子树中， b 在 p 的右子树中，则称 a 在 b 的左方。 它们在先序遍历和中序遍历时，得到的节点访问序列相同； 它们在后序遍历和中序遍历时，得到的结点访问序列相同； 它们在先序遍历和后序遍历时，得到的节点访问序列相同。 序序列和后序序列。 棵二叉树的先序序列： 序序列： 画出二叉树并写出它的后序序列。 一棵二叉树的后序序列： 中序序列： 精品文档 2016 全新精品资料 全程指导写作 独家原创 8 / 18 出二叉树并写出它的先序序列。 下是一棵二叉树的三种遍历序列，请填空并画出此二叉树。 先序序列： E 序序列： I C 后序序列： H A 别画出和下列二叉树对应的树。 出下列森林对应的二叉树，并写出森林的两种遍历序列。 6 12 假设用于通信的电文仅由 8 个字母组成，字母 在电文中出现的频率分别为 为这 8 个字母设计哈夫曼编码。 断题 二叉树中每个结点的两棵子树是有序的。 二叉树中每个结点有两棵非空子树或有两棵空子树。 完全二叉树中的所有结点，如果不存在非空左子树，则也不存在非空右 子树。 对于一棵非空二叉树，它的根结点作为第一层，则它的第 i 层上最多能有 2i 1 个结点。 用二叉链表法存储包含 n 个结点的二叉树，结点的2 n+1个为空指针。 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。 精品文档 2016 全新精品资料 全程指导写作 独家原创 9 / 18 具有 3 个结点的二叉树有 种形态，具有 3 个结点的树 有 种形态。 一棵深度为 6 的满二叉树有 个分支结点和 个叶子。 一棵具有 257 个结点的完全二叉树，它的深度为 。 设一棵完全二叉树有 700个结点，则共有 个叶子结点。 设一棵完全二叉树具有 1000个结点，则此完全二叉树有 个叶子 结点，有 个度为 2 的结点，有 个结点只有非空左子树， ） 有 个 结点只有非空右子树。 设高为 h 的二叉树只有度为 0 和 2 的结点，则此类二叉树的结点数至少 为，至多为。 一棵有 124 个叶子结点的完全二叉树，最多有 个结点。 在深度为 5 的满二叉树中，叶子结点有 个。 有 n 的二叉树有 棵。 设树 T 的度为 4，其中度为 1， 2， 3， 4 的结点个数分别， 2， 1， 1，则 T 中的叶子结点数为 。 第六章树和二叉树 习 题 一、选择题 精品文档 2016 全新精品资料 全程指导写作 独家原创 10 / 18 1有一 “ 遗传 ” 关系 ：设 x 是 y 的父亲，则 x 可以把它的属性遗传给 y。表示该遗传关系最适合的数据结构为。 C 图 2树最合适用来表示。 B 元素之间具有分支层次关系的数据 C 无序数据元素 3树 B 的层号表示为 2b， 3d， 3e， 2c，对应于下面选择的。 A. 2c) B. a,c) C. a,c)D. a,c) h 的完全二叉树至少有个结点，至多有个结点。 编号为 f 的结点存在右孩子，则右子结点的编号为。 .i+l a， d)， f)，则该二叉树的高度为 。 的二叉树至多有个结点。 1D. 10 精品文档 2016 全新精品资料 全程指导写作 独家原创 11 / 18 分支结点数为 15，单分支结点数 为 30个，则叶子结点数为个。 A. 1B. 1C. ，是完全二叉树，是满二叉树。 示的二叉树中： A 结点是 B 根结点但不是分支结点 C 根结点也是分支结点 J 结点是 B根结点但不是分支结点 C 根结点也是分支结点 F 结点的兄弟结点是 空 结点的双亲结点是 的深度为 结点的深度为 结点所在的层是 5 个结点的完全二叉树中，该树的深精品文档 2016 全新精品资料 全程指导写作 独家原创 12 / 18 度为。 2. 一棵有 124 个叶结点的完全二叉树，最多有个结点。 A 24B 24C 24D 250 1?n中，结点 Ri若 有左子树，则左子树是结点。 A. R2i+l B. R2i C.Ri/2 D. R2结点的右边。 15一棵度为 m 的树中，有 度为 1 的结点，有度为 2 的结点 ?，有 度为 m 的结点，则该树的叶结点数为。 A. n1+.+. .+1 D. 序遍历精品文档 2016 全新精品资料 全程指导写作 独家原创 13 / 18 序列是 的前序遍历序列 是。 A. . . . 指针域等于所有非空指针域数加。 B逻辑和存储 C物理 ， 7， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为。 是哈夫曼树，具有 5 个叶结点，树 T 的高度最高可以是。 、填空题 n 个结点的树，该树中所有结点的度数之和为 _。 根结点没有 _结点，其余每个结点有且只有 _个前驱 结点：叶子结点没有 _结点，其余每个结点可以有_后继结点。 示，回答下面的问题。 精品文档 2016 全新精品资料 全程指导写作 独家原创 14 / 18 这棵树的根点是 _；叶子结点是 _；结点 _；结点 子女是 _；结点 _；这棵树的度为_；这棵树的深度是 _。 ， C， D)，则该树的度为 _，树的深度为 _，终端结点的个数为 _，单分支结点的个数为 _，双分支结点的个数为 _， 3 分支结点的个数为 _， C 结点的双亲结点为 _，其孩子结点为_。 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上的每个结点都有 k 棵非空子树。 如果按层次顺序从 1 开始对全部结点编号，则： 第 i 层结点数目是 _。 编号为 n 的结点的双亲结点的编号是 _。 编号为 n 的结点的第 i 个孩子结点的编号是 _。 编号为 n 的结点有右兄弟的条件是 _：其右兄弟的编号是 _。 6前序遍历一棵树相当于 _树中对应的二叉树，后序遍历一棵树则相当于树中对应的二叉树。 7二叉树的遍历分为 _ ，树与森林的遍历包括精品文档 2016 全新精品资料 全程指导写作 独家原创 15 / 18 _。 8一棵二叉树的第 i 层最多有 _个结点；一棵有 _ 个叶子和 _个非终端结点。 定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点为 _个。 10在一棵二叉树中，第五层上的结点数最多为 _。 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 _个，其中 _个用于链接孩子结点， _个空闲着。 二叉树的根是_。 与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是 _ _ ，结点最少的二叉树为 _。 在前序遍历中结点 E 的直接前驱为 _ ，后序遍历中结点 B 的直接后继是 _。 序序列为该二叉树结点的前序序列为 _，该二叉树对应的森林包括 _棵树。 示。 精品文档 2016 全新精品资料 全程指导写作 独家原创 16 / 18 则后序遍历该二叉树时结点访问的顺序为 _。 18.由 n 个权值构成的哈夫曼树共有 _个结点。 ， 9， 6， 2， 5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为 _。 是一个森 林， B 是由 F 转换得到的二叉树， _个。 _ ，树的存储结构分为_。 三、判断题 1树中任意结点的子树不必是有序的。 2树可以看成特殊的无向图。 3可以使用双链表表示树型结构。 4顺序存储方式只能用于存储线性结构。 5完全二叉树的某结 点若无左孩子，则必是叶结点。 6在叶子数目和权值相同的所有二叉树中，最优二叉树 一定是完全二叉树。 7由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树。 8二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。 9二叉树的前序和后序遍历序列能惟一确定这棵二叉精品文档 2016 全新精品资料 全程指导写作 独家原创 17 / 18 树。 线索若不为空，则一定指向其父结点。 四、算法和操作题 1假定一棵二叉树广义表表示为 a