天津商业大学 计算机科学与技术专业 高职升本 课件4.ppt

综合练习四 一 单选题 1 设二叉树的第1层为根结点 则第i层最多有 1 个结点 深度为k的二叉树最多有 2 个结点 对任一棵二叉树T 如果其叶结点数为n0 度数为1的结点数为n1 度数为2的结点数为n2 则n0 3 1 A 2iB 2i 1C 2i 1D 2i 1 2 A 2k 1B 2k 1C 2k 1D 2k 3 A n2 1B n1 1C n 1D n1 n2参考答案 1 C2 B 3 A 一 单选题 2 在一棵二叉树中 若一个结点是叶结点 则它没有 A 左子结点B 右子结点C 左子结点和右子结点D 左子结点 右子结点和兄弟结点答案 C 一 单选题 3 在二叉树结点的先序序列 中序序列和后序序列中 所有叶结点的先后顺序 A 都不相同B 完全相同C 先序和中序相同 而与后序不同D 中序和后序相同 而与先序不同答案B 一 单选题 4 由3个结点可以构造出 种不同的二叉树 A 2B 3C 4D 5D5 带权路径长度最短的二叉树称为 A 赫夫曼树B 诺伊曼树C 线索二叉树D B 树A 一 单选题 6 树结构最适合用来表示 A 元素间具有分支 层次关系的数据B 有序数据C 元素间没有关联的数据D 无序数据A 一 单选题 7 深度为k的二叉树所含叶子的个数最多为 A 2k 1B 2k 1C kD 2k参考答案 B8 设有一棵n个叶结点的哈夫曼树 其树中总结点数是 A 2n 1B n n 1 C nD n 1参考答案 A9 具有10个叶结点的二叉树中有 个度为2的结点 P124A 8B 9C 10D ll参考答案 B 一 单选题 10 一个具有1025个结点的二叉树的高h为 P124A 11B 10C 11至1025之间D 10至1024之间参考答案 C11 在线索二叉树中 t所指结点没有左子树的必要条件是 P132A t left NULLB t ltag 1且t left NULLC t ltag 1D 以上都不对参考答案 C 一 单选题 12 由权值3 8 6 5 2的叶子结点生成一棵赫夫曼树 它的带权路径长度为 A 48B 72C 53D 24 WPL 2 3 3 3 5 2 8 2 6 2 53参考答案 C 一 单选题 13 已知某二叉树的后序遍历是dabec 中序序列是debac 则它的先序序列是 A acbedB deabcC decabD cedba 参考答案 D 一 单选题 14 线索二叉树是一种 结构 A 逻辑B 存储C 线性存储D 逻辑存储B15 深度为5的二叉树最多有 结点 A 32B 31C 16D 10B 二 多选题 1 下列关于哈夫曼树的叙述中 正确的是 A 哈夫曼树是一棵二叉树 因此 它的结点的度可以是0 1或2B 具有n个权值的哈夫曼树共有2n 1个结点C 哈夫曼树根结点的权值等于所有叶结点的权值之和D 具有n个权值的哈夫曼树含有n 1个非叶结点参考答案 BCD 二 多选题 2 下面的说法中 正确的是 A 任何一棵二叉树的叶子结点在三种遍历中的相对次序不变B 按二叉树定义 具有三个结点的二叉树共有6种C 用二叉树的前序遍历和中序遍历可以导出该树的后序遍历D 完全二叉树一定存在度为1的结点参考答案 AC 二 多选题 3 在下述结论中 正确的是 A 只有一个结点的二叉树的度为0B 二叉树的度为2C 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树 D 二叉树的左右子树可任意交换 参考答案 AC 二 多选题 4 一棵完全二叉树上有1001个结点 其中叶子结点的个数是错误的是 A 500B 254C 505D 以上答案都不对参考答案 ABC 最大层有490 1001 511个结点 次最大层有11 511 1001 2 个结点 二 多选题 5 关于二叉树 下面说法正确的是 p124A 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B 在三叉链表上 二叉树的求双亲操作很容易实现C 在二叉链表上 求根以及左 右孩子等操作很容易实现D 在二叉链表上 求双亲的时间性能很好参考答案 ABC 三 判断题 1 用二叉链表存储有n个结点的二叉树 结点的2n个指针中 只利用了n 1个指针 其余n 1个是空指针 P1262 树是一种线性数据结构 3 用一维数组存储二叉树 总是以先序遍历的顺序存储各结点 正确 四 填空题 1 假设二叉树的第1层为根结点 则具有n个结点的二叉树的最大高度是 答案 n2 带权结点A B C D的权值分别为8 6 1 5 则B结点的哈夫曼编码 二进制 为 权值小的叶结点为左子树 答案 10 0 0 0 1 1 1 四 填空题 3 设森林F由n棵树组成 它的第一棵树 第二棵树 第n棵树分别有t1 t2 tn个结点 则与森林F对应的二叉树中 根结点的左子树有个结点 答案 t1 1 t1为根节点的二叉树节点数减一个根节点 四 填空题 4 在树中 一个结点的直接子结点的个数称为该结点的 答案 度5 已知完全二叉树的第七层有10个结点 则整个二叉树有 个结点 答案 73 26 1 10 6 若叶结点A只有三个兄弟 不包括A本身 并且B是A的双亲结点 则B的度是 答案 四 填空题 7 将一棵有50个结点的完全二叉树从根结点开始 由根向下 每一层从左至右 顺序地存储在一个一维数组b 51 中 并从b 1 开始存放 这棵二叉树最下面一层上最左边一个结点存储在数组元素中 答案 b 32 8 假定一棵二叉树的结点数为18 则它的最小深度为 最大深度为 P124答案 518 四 填空题 9 对于具有30个结点的完全二叉树 若一个结点的编号为5 则它的左孩子的编号为 右孩子的结点为 双亲结点结点的编号为 124参考答案 10112 四 填空题 10 设森林中有4棵树 结点个数分别为n1 n2 n3 n4 当把森林转换成一棵二叉树后 根结点的右子树上有 结点 参考答案 n2 n3 n4 五 简答题 1 简要回答树和二叉树之间有什么区别和联系 参考答案 区别 对子树要求不同 二叉树任一结点都有两棵子树 且两棵子树之间有次序关系 二叉树即使一结点只有一棵非空子树 仍需区别是左子树还是右子树 二叉树上任一结点的度定义为该结点的孩子数 树的度定义为结点拥有子树的数目 二叉树与树有相似之处 但并非树的特例 属两种不同的数据结构 联系 逻辑结构相同 都是树形结构 五 简答题 2 已知一棵二叉树如下 请分别写出按先序 中序 后序和层次遍历时得到的结点序列 参考答案 先序 ABDGCEFH中序 DGBAECHF后序 GDBEHFCA层次 ABCDEFGH 六 应用题 1 假设用于通信的电文由字符集 A B C D E F G 中的字母构成 它们出现的频率依次为10 9 2 7 8 6 3 试画出对应的哈夫曼树 并计算它的WPL值 六 应用题 1 答案 WPL 2 4 3 4 6 3 7 3 8 3 9 2 10 2 121 六 应用题 2 试画出下图所示森林对应的二叉树 六 应用题 森林中第一棵树对应的二叉树 六 应用题 森林中第二棵树对应的二叉树 六 应用题 森林中第三棵树对应的二叉树 六 应用题 2 参考答案 六 应用题 3 已知二叉树的中序和后序序列分别如下 请构造出该二叉树 中序序列 CBEDAFIGH后序序列 CEDBIFHGA 六 应用题 4 已知二叉树的中序和后序序列分别如下 请构造出该二叉树 中序序列 BDFHGIJECA后序序列 HJIGFEDCBA 六 应用题 有一份电文中共使用6个字符 a b c d e f 它们的出现频率依次为2 3 4 7 8 9 试构造一棵哈夫曼树 计算其加权路径长度WPL和字符c的编码 要求将频率小的结点出现在左子树上 叶结点权值小的为左子树 六 应用题 参考答案 WPL 7 2 8 2 9 2 4 3 2 4 3 4 80c的编码为110 七 编程题 一棵n个节点的完全二叉树以一维数组作为存储结构 请编写非递归算法实现对该二叉树的前序遍历 用C语言实现 给定结构说明如下 函数首部为 Preorder intn chara 前序遍历由数组a存储的具有n个节点的完全二叉树 参考答案 Preorder intn chara ints n inttop 1 inti 1 if n 0 ret