数据结构练习2-10答案[1].pdf

1 数据结构练习数据结构练习 二二 参考参考答案答案 一 填空题 1 若一棵树的括号表示为 A B E F C G H I J K L D M N 则该树的度为 1 4 树的深度为 2 4 树中叶子结点的个数为 3 8 2 一棵满二叉树中有 m 个叶子 n 个结点 深度为 h 请写出 m n h 之间 关系的表达式 4 n 2h 1 m 2h 1 n n0 n2 2m 1 3 一棵二叉树中如果有 n 个叶子结点 则这棵树上最少有 5 2n 1 个结点 一棵深度为 k 的完全二叉树中最少有 2k 1 6 个结点 最多有 7 2k 1 个 结点 4 具有 n 个结点的二叉树 当它是一棵 8 完全 二叉树时具有最小高度 9 log2n 1 当它为一棵单支树时具有高度 10 n 5 对具有n个结点的完全二叉树按照层次从上到下 每一层从左到右的次序对 所有结点进行编号 编号为i的结点的双亲结点的编号为 11 i 2 左孩子的编号为 2i 右孩子的编号为 2i 1 6 若具有n个结点的二叉树采用二叉链表存储结构 则该链表中有 2n 个指 针域 其中有 n 1 个指针域用于链接孩子结点 n 1 个指针域空闲存 放着NULL 7 二叉树的遍历方式通常有 先序 中序 后序 和 层序 四种 8 已知二叉树的前序遍历序列为ABDCEFG 中序遍历序列为DBCAFEG 其 后序遍历序列为 DCBFGEA 9 已知某完全二叉树采用顺序存储结构 结点的存放次序为 A B C D E F G H I J 该完全二叉树的后序序列为 HIDJEBFGCA 10 若具有n个结点的非空二叉树有n0个叶结点 则该二叉树有 n0 1 个度为 2的结点 n 2n0 1 个度为1的结点 11 任何非空树中有且仅有一个结点没有前驱结点 该结点就是树的 根 度为k的树中第i层最多有 ki 1 个结点 i 1 深度为h的k叉树最 多有 k0 k1 kh 1 个结点 12 非空二叉树一共有 4 种基本形态 第i层最多有 2i 1 个结点 13 在一棵完全二叉树中 编号 i 和编号 j 的两个结点处于同一层的条件是 log2i log2j 14 有 n 个顶点的强连通图至少有 7 n 弧 有 n 个顶点的连通图至少有 8 n 1 边 15 设无向图 G 的顶点数为 n 图 G 最少有 12 0 边 最多有 13 n n 1 2 条边 若边数为 e 用邻接矩阵表示图 求每一顶点度的时间复杂性为 14 2 O n2 若用邻接表表示图 访问一个顶点的所有邻接顶点的时间复杂性 为 15 O e 一个有 n 个顶点的有向图中 最少有 16 0 弧 最多有 17 n n 1 弧 二 选择题 1 树型结构最适合用来描述 A 有序的数据元素 B 无序的数据元素 C 数据元素之间具有层次关系的数据 D 数据元素之间没有关系的数据 2 对于一棵具有n个结点 度为4的树而言 A 树的深度最多是n 4 B 树的深度最多是n 3 C 第i层上最多有4 i 1 个结点 3 二叉树为空 意味着二叉树 A 由一些未赋值的空结点组成 B 根结点无子树 C 不存在 D 没有结点 4 按照二叉树的定义 具有3个结点的二叉树有 种形态 不考虑数据信息的 组合情况 A 2 B 3 C 4 D 5 5 若一棵二叉树具有 10 个度为 2 的结点 5 个度为 1 的结点 则度为 0 的结 点个数为 A 9 B 11 C 15 D 不确定 6 一个具有 1025 个结点的二叉树的高 h 为 A 11 B 10 C 11 1025 D 12 1024 7 若二叉树的前序序列与后序序列的次序正好相反 则该二叉树一定是 树 A 空或仅有一个结点 B 其分支结点无左子树 C 其分支结点无右子树 D 其分支结点的度都为1 8 任何一棵非空二叉树中的叶结点在前序遍历 中序遍历与后序遍历中的相 对位置 A 都会发生改变 B 不会发生改变 C 有可能会发生改变 D 部分会发生改变 9 如图所示的二叉树 T2 是由森林 T1 转换而来 的二叉树 那么森林 T1 有 个叶子结点 A 4 B 5 C 6 D 7 10 设 n m 为一棵二叉树上的两个结点 在中 序遍历时 n 在 m 前的条件是 A n 在 m 右方 B n 是 m 祖先 C n 在 m 左方 D n 是 m 子孙 11 一棵二叉树的先序遍历序列为 ABCDEFG A BE C D FH GJI 3 它的中序遍历序列可能是 A CABDEFG B ABCDEFG C DACEFBG D ADCFEGB 12 引入线索二叉树的目的是 A 加快查找结点的前驱或后继结点的速度 C 为了能方便找到双亲 B 为了能在二叉树中方便插入和删除 D 使二叉树的遍历结果唯一 13 线索二叉树是一种 结构 A 逻辑 B 逻辑和存储 C 物理 D 线性 14 判断线索二叉树中 p 结点有右孩子结点的条件是 A p NULL B P rchild NULL C p rtag 0 D p rtag 1 15 n 个结点的线索二叉树上含有的线索数为 A 2n B n 1 C n 1 D n 16 根据使用频率为 5 个字符设计的哈夫曼编码不可能是 A 000 001 010 011 1 B 0000 0001 001 01 1 C 000 001 01 10 11 D 00 100 101 110 111 18 设有 13 个值 用它们组成一棵哈夫曼树 则该哈夫曼树共有 个结点 A 13 B 12 C 26 D 25 19 在一个图中 所有顶点的度数之和等于所有边数的 倍 A 1 2 B 1 C 2 D 4 20 一个具有n个顶点的无向图最多有 条边 A n n 1 2 B n n 1 C n n 1 2 D n2 21 一个具有n个顶点的有向图最多有 条边 A n n 1 2 B n n 1 C n n 1 2 D n2 22 在一个具有n个顶点的无向图中 要连通全部顶点至少需要 条边 A n B n 1 C n 1 D 2n 23 具有n个顶点的连通图的生成树一定有 条边 A n B n 1 C n 1 D 2n 24 若一个非连通的无向图最多有28条边 则该无向图至少有 个项点 A 6 B 7 C 8 D 9 25 在带权图中 两个顶点之间的路径长度是 A 路径上的顶点数目 B 路径上的边的数目 C 路径上顶点和边的数目 D 路径上所有边上的权值之和 26 若具有n个顶点的元向图采用邻接矩阵存储方法 该邻接矩阵一定为一个 A 一般矩阵 B 对称矩阵 C 对角矩阵 D 稀疏矩阵 27 若图的邻接矩阵中主对角线上的元素均为0 其余元素全为1 则可以断定 4 该图一定 A 是无向图 B 是有向图 C 是完全图 D 不是带权图 28 有向图的邻接表的第i个链表中的边结点数目是第i个顶点的 A 度数 B 出度 C 人数 D 边数 29 若某图的邻接表中的边结点数目为奇数 则该图 A 一定有奇数个顶点 B 一定有偶数个顶点 C 一定是有向图 D 可能是无向图 30 若某图的邻接表中的边结点数目为偶数 则该图 A 一定是无向图 B 可能是有向图 C 可能是无向图 也可能是有向图 D 一定有偶数个顶点 31 若无向图有k条边 则相应的邻接表中就有 个边结点 A k 1 B k C 2k D k2 32 若有向图有k条边 则相应的邻接表中就有 个边结点 A k 1 B k C 2k D k2 33 对于一个不带权的无向图的邻接矩阵而言 A 矩阵中非零元素的数目等于图中边的数目 B 矩阵中非全零的行的数目等于图中顶点的数目 C 第i行的非零元素的数目与第i列的非零元素的数目相等 D 第i行与第i列的非零元素的总数等于第i个顶点的度数 34 导致图的遍历序列不惟一的因素有 A 出发点不同 遍历方法不同 B 出发点不同 存储结构不同 C 遍历方法不同 存储结构不同 D 出发点不同 存储结构不同 遍历方法不同 35 若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的 所有顶点 则该图一定是一个 图 A 非连通 B 连通 C 强连通 D 完全 36 可以进行拓扑排序的图一定是 A 连通图 B 带权连通图 C 无回路的图 D 无回路的有向图 37 已知某有向图G V E 其中V v1 v2 v3 v4 v5 v6 E G的拓扑序列 是 A v3 v1 v4 v5 v2 v6 B v3 v4 v1 v5 v2 v6 C v1 v3 v4 v5 v2 v6 D v1 v4 v3 v5 v2 v6 38 下面关于AOE网的叙述中 不正确的是 A 若所有关键活动都提前完成 则整个工程一定能够提前完成 B 即使所有非关键活动都未按时完成 整个工程仍有可能按时完成 5 C 任何一个关键活动的延期完成 都会导致整个工程的延期完成 D 任何一个关键活动的提前完成 都会导致整个工程的提前完成 39 无向图的邻接矩阵是一个 A 对称矩阵 B 零矩阵 C 上三角矩阵 D 对角矩阵 40 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点 则该图一定是 A 完全图 B 连通图 C 有回路 D 一棵树 41 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 算法 A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 42 一个无向连通图的生成树是含有该连通图的全部顶点的 A 极小连通子图 B 极小子图 C 极大连通子图 D 极大子图 43 任何一个无向连通图 最小生成树 A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在 44 求最短路径的 Dijkstra 算法的时间复杂度为 A O n B O n e C O n2 D O n3 45 求最短路径的 Floyd 算法的时间复杂度为 A O n B O ne C O n2 D O n3 45 2 有向网 G 用邻接矩阵 A 存储 则顶点 i 的入度等于 A 中 A 第 i 行非 的元素之和 C 第 i 列非 的元素之和 B 第 i 行非 且非 0 的元素个数 D 第 i 列非 且非 0 的元素个数 46 关键路径是事件结点网中 A 从起点到终点的最长路径 B 从起点到终点的最短路径 C 最长的回路 D 最短的回路 47 已知一个有向图如右图所示 则从顶点 a 出发进行深 度优先遍历不可能得到的 DFS 序列为 A adbefc B adcefb C adcbfe D adefcb 三 判断题 1 在树型结构中 每一个结点最多只有一个前驱结点 但可以有多个后继结 点 2 在树型结构中 每一个结点不能没有前驱结点 3 在度为k的树中 至少有一个度为k的结点 4 在度为k的树中 每个结点最多有k 1个兄弟结点 5 度为2的树是二叉树 6 二叉树的度一定为2 7 在非空完全二叉树中 只有最下面一层的结点为叶结点 8 在完全二叉树中 没有左孩子的结点一定是叶结点 6 9 在完全二叉树中 没有右孩子的结点一定是叶结点 10 在结点数目一定的前提下 各种形态的二叉树中 完全二叉树具有最小深 度 11 满二叉树一定是完全二叉树 12 满二叉树中的每个结点的度不是0就是2 13 在所有深度相同的二叉树中 满二叉树具有最大结点数目 14 具有n个结点的非空二叉树一定有n 1个分支 15 n个结点的二叉树采用二叉链表结构 链表中有n 1个存放NULL指针域 16 由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树 17 由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树 18 由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树 19 实现二叉树的按层次遍历算法时需要用到队列结构 20 实现二叉树的遍历算法时不需要用到堆栈结构 21 线索二叉树对应的二叉链表中不存在空的指针域 22 给定一组权值 构造出来的哈夫曼树是唯一的 23 哈夫曼树中不存在度为1的结点 24 在哈夫曼树中 权值相同的叶结点都在同一层上 25 没有顶点的图称为空图 26 图的度是图中所有顶点的度的最大值 27 边上带权值的图称为网 络 28 图中一个顶点的度应该是它的出度与人度之和 29 n个顶点的无向图最多有n n 1 条边 30 在有向图中 所有顶点的人度之和等于所有顶点的出度之和 31 在无向图中 若顶点i到顶点j有路径 则这两个顶点之间是连通的 32 在有向图中 若顶点i到顶点j有路径 则这两个顶点之间是连通的 33 连通图的最小生成树是惟一的 34 邻接矩阵主要用来表示顶点之间的关系 35 若表示某图的邻接矩阵不是对称矩阵 则该图一定是有向图 36 若表示某图的邻接矩阵中出现了全零行或者全零列 则该图一定是非连 通图或者非强连通图 37 对于同一个有向图 邻接表中的边结点数目与逆邻接表中边结点数目相 等 38 无向图的邻接表中边结点数目一定为偶数 39 邻接表中边结点数目为奇数的图一定是有向图 40 邻接表中边结点数目为偶数的图一定是无向图 41 对图进行广度优先搜索的过程中要用到队列 7 42 对图进行深度优先搜索的过程中要用到堆找 43 带权连通图的最小生成树是惟一的 44 最短路径一定是简单路径 45 求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向 网络 46 若AOV网中存在拓扑序列 则一般情况下 拓扑序列不是惟一的 47 关键路径是由权值最大的边构成的 48 给定的AOE网的关键路径一定是惟一的 四 简答题 1 已知森林的先序遍历序列为 ABDJCEFHK 中序序列为 DJBAECHKF 请 画出该森林 2 若一棵度为 4 的树中度为 1 2 3 4 的结点个数分别为 4 3 2 2 则 该树叶子结点的个数是多少 总结点个数是多少 14 25 3 一棵度为2的树与一棵二叉树有什么区别 将树转化为二叉树的基本目的是 什么 可以采用二叉树的结构并利用已有的算法解决树的有关问题 4 已知一棵完全二叉树共有 892 个结点 试求 1 树的高度 10 2 叶子结点数 446 3 单支结点数 1 4 最后一个非终端结点的序号 446 5 画出二叉树的后序前驱线索 6 一文件中只出现 9 种字符 a b c d e f g h 它们出现的频率分 别为 8 9 3 5 6 4 2 1 请根据书上算法画出相应的哈夫曼树 叶子 结点用相应字母表示 左子树的权小于右子树的权 给出哈夫曼编码 并计 算其带权的路径长度 WPL 7 已知某二叉树的中序遍历序列为CBGEAFHD 后序遍历序列为 CGEBHFDA 请画出该二叉树的前序线索二叉树的二叉链表结构的表示 8 已知按前序遍历二叉树的结果为ABC 试问 有几种不同的二叉树可以得到 这一遍历结果 5 8 9 将图所示的树林转换为一棵二叉树 10 分别写出如图所示的树的前序遍历序列与后序遍历序列 题9 题10 11 已知某树林转化为二叉树后所对应的顺序存储结构为 A B H C E I J D F G 请画出该树林 5 请写出用普里姆算法对下图求最小生成