【综合文库】
树和二叉树
一、选择题：
1． 以下说法错误的是 ( )
A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种\分支层次\结构 E．任何只含一个结点的集合是一棵树
2．讨论树、森林和二叉树的关系，目的是为了（）
A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树
D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ()
A．有序数据元素 B．无序数据元素
C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9B．11 C．15 D．不确定
6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有699个结点，其中叶子结点的个数是（）
A． 250 B． 350 C．256D．511
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为()
A．不确定B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（）
I I-1I-1I
A．2 B． 2-1 C． 2D．2 -1
10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点
A．2h B．2h-1C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子 C．空D．非空
14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）
A．都不相同B．完全相同
C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。
A．左子结点B．右子结点
C．左子结点和右子结点D．左子结点，右子结点和兄弟结点E．以上答案都不对
16、以下说法错误的是 ()
A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
17.某二叉树先根遍历的结点序列是abdgcefh，中根遍历的结点序列是dgbaechf，则其后根遍历的结点序列是 ( )
A．bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 18.由带权8,5,2,7四个叶子结点构成一棵哈夫曼树，其带权路径长度是（）
A．23 B.37 C.46D.43
19.树的后根遍历序列等同于该树对应的二叉树的（）序列。A. 先根 B.中根C.后根D.按层 20.下列不是完全二叉树的是（）
二、判断题（在各题后填写“√”或“×”） 1. 完全二叉树一定存在度为1的结点。()
2．对于有N个结点的二叉树，其高度为log2n。()
3. 二叉树的遍历只是为了在应用中找到一种线性次序。()
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。()
5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。() 6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 () 7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。() 8. 二叉树只能用二叉链表表示。()
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。() 10．树形结构中元素之间存在一个对多个的关系。() 11．将一棵树转成二叉树，根结点没有左子树。() 12．度为二的树就是二叉树。()
13．霍夫曼树的结点个数不能是偶数。()
14．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()
三、填空题
1．在二叉树中，指针p所指结点为叶子结点的条件是___ ___。
2．深度为k的完全二叉树至少有_______个结点，至多有_______个结点。
3．高度为8的完全二叉树至少有______个叶子结点。
4．树的主要遍历方法有________、________、________等三种。
6．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。
7．二叉树的先序序列和中序序列相同的条件是___ ___。
8．一个无序序列可以通过构造一棵______树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
9．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的____ __序列中的最后一个结点。
10．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
四、应用题
1．树和二叉树之间有什么样的区别与联系？
2．分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3.写出图1的遍历序列。
4.将图2所示的森林转换为二叉树。
5.设某密码电文由8个字母组成，每个字母在电文中出现的频率分别是7,19,2,6,32,3,21,10，试为这8个字母设计哈夫曼编码。
6．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,求其后序遍历的结果，并画出这棵树。
7. 一组关键字为（36，75，83，54，12，67，60，40，92，72），试依次插入结点生成平衡二叉搜索树，并标明插入时所需平衡的类型。
第六章树和二叉树
一、单项选择题 1.A 2.D 3．A 4．C 5．B 6．D 7．E8. D 9．C 10．B 11. C 12．A 13．D 14．B 15．C 16．B17. B 18. A 19．C 20．D 21．B 22. D 23．C
二、判断题（在各题后填写“√”或“×”） 1. 完全二叉树一定存在度为1的结点。×
2. 对于有N个结点的二叉树，其高度为log2n。×
3. 二叉树的遍历只是为了在应用中找到一种线性次序。√
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。×
5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。× 6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列√ 7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√ 8. 二叉树只能用二叉链表表示。×
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。√ 10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。×
11．树形结构中元素之间存在一个对多个的关系。√ 12．将一棵树转成二叉树，根结点没有左子树。× 13．度为二的树就是二叉树。×
查看全文
false