《ch6习题及标准答案》由会员分享，可在线阅读，更多相关《ch6习题及标准答案（11页珍藏版）》请在金锄头文库上搜索。
1、习题6解答判断题：1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。( )2.二叉树就是结点度为2的树。( )( (哈工大2000年研究生试题)3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。 ( ) (陕西省1998年自考试题)4.当k1时，高度为k的二叉树至多有个结点。( )5.完全二叉树的某结点若无左孩子，则它必是叶结点。 ()(中科院软件所1997年研究生试题)6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。( )7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后
2、一个结点。( )8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。() (哈工大2000年研究生试题)9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。()10.将一棵树转换成二叉树后，根结点没有左子树，( )(北邮1999年研究生试题。)11.由树转换成二叉树，其根结点的右子树总是空的。()12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。( )13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( )14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。( )15.霍夫曼树一定是满二叉树。( )16.树的
3、度是树内各结点的度之和。( )17.由二叉树的结点构成的集合可以是空集合。()18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( )选择题：19.树最适合用来表示( C )。 A有序数据元素 B. 无序数据元素 C元素之间具有分支层次关系的数据 D. 元素之间无联系的数据20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( D )。A. 4 B. 5 C. 1 D. 321.下列有关二叉树的说法正确的是( B )。(南京理工大学2000年研究生试题。)A二叉树的度为2 B. 一棵二叉树度可以小于2C二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为222.
4、以下说法错误的是( B )。 A二叉树可以是空集 B. 二叉树的任一结点都可以有两棵子树 C二叉树与树具有相同的树形结构 D. 二叉树中任一结点的两棵子树有次序之分23.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( B )个。A15 B. 16 C. 17 D.4724. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R1.n中，结点Ri若有左子女，则左子女是结点( B )。 AR2i+1 B. R2i C. Ri/2 D. R2i-1(参见严蔚敏(c语言版)数据结构P.124 125,二叉树的性质,性质5)25.设a、b为一棵二叉树上的两个结点。在中
5、序遍历时，a在b前面的条件是( B )。Aa在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙26.以下说法正确的是( C )。A 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。B 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。C 在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(提示：后继结点应为遍历右子树时访问的第一个结点，该后继结点或为叶子结点，则其无子女；或为仅有右子树，则其也是最多只能有一个子女；若有两个子女，则它本身已不是后继。
6、)D 在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点。27.以下说法错误的是( B )。A存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。 B. 二叉树是树的特殊情形。 C. 由树转换成二叉树，其根结点的右子树总是空的。 D. 在二叉树只有一棵子树的情况与也要明确指出该子树是左子树还是右子树。28.将下图的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向( C )。AA，D B. B，C C. D，A D. C，AABDCXEY29.在N个结点的线索二叉树中，线索的数目为( C )。AN-1 B. N C. N+1 D. 2N(参见严蔚敏(c语言版)数
7、据结构P.126 & P.132)30.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有( D )个结点。(全国2001年自考题)A13 B. 12 C. 26 D. 25(参见严蔚敏(c语言版)数据结构P.147)31.下面几个符号串编码集合中，不是前缀编码的是( B )。A0，10，110，1111 B. 11，10，001，101，0001C00，010，0110，1000 D. b，c，aa，ac，aba，abb，abc32.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( D )。A. 23 B. 37 C. 46 D. 4433.树的基本遍历策略可
8、分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论( A )是正确的。 A树的先根遍历序列与其对应的二叉树先序遍历序列相同。 B. 树的后序遍历序列与其对应的二叉树后序遍历序列相同。 C. 树的先根遍历序列与其对应的二叉树中序遍历序列相同。 D. 以上都不对34.在一棵具有n个结点的二叉树第i层上，最多具有( C )个结点。 A B. C. D. (参见严蔚敏(c语言版)数据结构P.123)35.给定一个整数集合3，5，6，9，12，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。（ C ）填
9、空题：36.具有n个结点的二叉树，采用二叉链表存储，共有 n+1 个空链域。(重庆大学2000年研究生试题)37.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为 2n 个，其中 n-1 个用于链接孩子结点， n+1 个空闲着。38.二叉树的线索化实质是将二叉链表中的_空指针_改为_线索_。(陕西省1998年自考题)39.一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为 n-(n-1)/k 。40.在下图所示的树中，结点H的祖先为 A、D、G 。ABDEFGCHI41.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是 借
10、用二叉树的有关算法实现树的有关操作 。42.对于一个具有n个结点的二叉树，当它为一棵 完全 二叉树时具有最小高度，即为 ，当它为一棵单支树具有 最大 高度，即为 n 。(注：树的深度有时称为高度，不同的体系所用的名词可能会有差别。)43.设只包含根结点的二叉树高度为0，则高度为k的二叉树最大结点数为 2k+1-1 ，最小结点数为 k+1 。(提示：请注意，这里关于树的高度的定义与通常的高度定义有不同！)44. 8层完全二叉树至少有 128 个结点，拥有100个结点的完全二叉树的最大层数为 7 。(西南交大2000年研究生试题。)45.二叉树通常有 顺序 存储结构和 链式 存储结构。46.二叉树
11、有不同的链式存储结构，其中最常用的是 二叉链表 与 三叉链表 。47.一棵左右子树均不空的二叉树在先序线索化后，其空指针域有 1 个。48.线索二叉树的左线索指向其 前驱 ，右线索指向其 后继 。(哈工大2000年研究生试题)49.用树的孩子兄弟表示法存储，可以将一棵树转换成 二叉树 。(重庆大学2000年研究生试题)50.遍历一棵二叉树包括访问 根结点 、遍历 左子树 和遍历 右子树 三个方面。51.已知树的广义表形式为ABE，F，C，DG（H，I），则该树的度为_3_，从根开始的前序遍历所得序列为_A、B、E、F、C、D、G、H、I_.52.森林定义为 m(m=0)棵互不相交的树 的集合。
12、简答题53.分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？(1) 二叉树是一种特殊的树；(2) 度为2的树是一棵二叉树；(3) 度为2的有序树是一棵二叉树。一、3个结点的树二、3个结点的二叉树(注：由此可以看出两个问题。1. 二叉树与树的重要区别:(1)二叉树的一个结点至多有两个子树，树则不然。(2)二叉树的一个结点的子树有左右之分，而树则没有此要求。2. 度为2的树有两个分支,没有左、右之分；一棵二叉树也可以有两个分支,但有左、右之分,且左、右不能交换。)54.对于如图所示的森林，要求：(1)将其转换为相应的二叉树；(2)写出该森林的先序遍历序列和中序遍历序列。ABCDEFGIHJKL（1）相应二叉树ABGDCEFHKIJL（2）该森林的先序遍历序列：A、B、D、E、F、C、G、H、I、J、K、L该森林的中序遍历序列：D、E、F、B、C、A、H、I、J、G、L、K55.设有一段正文是由字符集A,B,C,D,E,F组成的，正文长度为100个字符，其中每个字符要正文中出现的次数分别为17,12,5,28,35,3。若采用哈夫曼编码对这段正文进行压缩存储，请完成如下的工作：(1)构造哈夫曼树(规定权值较小的结点为左子树)；
