第6章树和二叉树作业.pdf

《第6章树和二叉树作业.pdf》由会员分享，可在线阅读，更多相关《第6章树和二叉树作业.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.第六章 树和二叉树 2 一、选择题 1.设给定权值总数有 n 个，其哈夫曼树的结点总数为()A不确定 B2n C2n+1 D2n-1 2.在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为个 A4 B5 C6 D7 3.二叉树的第 I 层上最多含有结点数为 A2B21-1 C21D2-1 4.将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三叉树的高度 A4 B5 C6 D7 5.一个具有 1025 个结点的二叉树的高h 为 A11 B10 C11 至 1025 之间 D10 至 1024 之间 6.对

2、二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。理工大学 2000 一、4 2 分 A先序 B中序 C后序 D从根开始按层次遍历 7.在下列存储形式中，哪一个不是树的存储形式？A双亲表示法 B孩子链表表示法.C孩子兄弟表示法 D顺序存储表示法 8.下面的说法中正确的是.1任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；2按二叉树定义，具有三个结点的二叉树共有 6 种。A(1)(2)B(1)C(2)D(1)、(2)都错 9.某二叉树的前序序列和后序序列正好相反，则该二叉树一定

3、是 的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树 10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 A所有的结点均无左孩子B所有的结点均无右孩子 C只有一个叶子结点 D是任意一棵二叉树 11.在完全二叉树中，若一个结点是叶结点，则它没。A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点 12在下列情况中，可称为二叉树的是 A每个结点至多有两棵子树的树 B.哈夫曼树 C每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树 E以上答案都不对 13.线索二叉树是一种结构。A逻辑 B逻辑和存储 C

4、物理 D线性 .14.若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 x 的前驱为()AX 的双亲 BX 的右子树中最左的结点 CX 的左子树中最右结点 DX 的左子树中最右叶结点 15.引入二叉线索树的目的是 A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一 二、判断题 1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。2.对一棵二叉树进行层次遍历时，应借助于一个栈。3.由一棵二叉树的前序序列和后序序列可以唯一确定它。4.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一

5、个，则可以确定这棵二叉树。5.二叉树的遍历只是为了在应用中找到一种线性次序。6.二叉树中序线索化后，不存在空指针域。7.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 8.霍夫曼树的结点个数不能是偶数。题号 1 2 3 4 5 6 7 8 答案 题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 答案 .B A C E D F N P G H J M O L I K 三、应用题 1.试证明，在具有 n(n=1)个结点的 m 次树中，有 n(m-1)+1 个指针是空的。2.将下列由三棵树组成的森林转换为二叉树。只要求给出转换结果 3.已知

6、一个森林的先序序列和后序序列如下，请构造出该森林。先根序列：ABCDEFGHIJKLMNO 后根序列：CDEBFHIJGAMLONK .4.已知一组字符与其权值如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8 请构造相应的哈夫曼树，画出结果哈夫曼树并计算出 WPL。四、算法设计题 1.设计算法返回二叉树 T 的先序序列的最后一个结点的指针，要求采用非递归形式，且不能用栈。.K H F E A B G I C D 2.利用栈的基本操作写出先序遍历二叉树的非递归算法要求进栈的元素最少，并指出下图中二叉树中需进栈的元素。3.编写一个函数或过程判定两棵二叉树是否相似相似只是对比树的形状，不对比结点的数据域，所谓两棵二叉树 s 和 t 相似，即是要么它们都为空或都只有一个结点，要么它们的左右子树都相似。