树与二叉树
树与二叉树
P133，13、一棵完全二叉树上有1001个节点，其中叶节点的个数是（）
250
500
254
501
1001=511+490,511=255+256,490/2=245,256-245=11,11+490=501
用补足的想法更简便
P133，14、若一棵完全二叉树有768个节点，则该二叉树中叶子节点的个数是（）
257
258
384
385
768=511+257,511=255+256,257/2=128.5=>129,256-129=127,127+257=384
P133，16、一棵有124个叶子节点的完全二叉树，最多有（）个节点
247
248
249
250
247与248都能构成完全二叉树，所以选更大的，所以注意要验证所有情况
仅仅知道叶节点的数目不能完全确定一棵完全二叉树
比如有3个叶节点的完全二叉树，度为1的节点可能有1个也可能有0个
P133，19、假定一棵三叉树的节点数为50，则它的最小高度为（）
3
4
5
6
计算公式应该重新推，新的计算公式因该是S=(3^h-1)/2，当h=5时，S>=50
P126，3、树的路径长度是从树根到每个叶子节点的路径长度的（）
总和
最小值
最大值
平均值
P146，5、在二叉树中有两个节点m和n，若m是n的祖先，则使用（）可以找到从m到n 的路径
先序遍历
中序遍历
后序遍历
层序遍历
后序遍历回退时访问父节点，于是在后序遍历时，遍历到n，开始记录每次回退的节点，直到遍历到m为止，这样得到的序列反转，就是m到n的路径
P148，23、线索二叉树是一种（）结构
逻辑
逻辑和存储
物理
线性
线索二叉树是加上线索后的链表结构，是一种存储结构，所以是一种物理结构
P148，24、n个节点的线索二叉树上含有的线索数为（）
2n
n-1
n+1
n
总数有n+1个，n个节点总共有2n个指针域，其中n-1个用来构成树，则剩下的n+1个用来作为线索
P149，32、若X是后序线索二叉树中的叶节点，且X存在左兄弟节点Y，则X的右线索指向的是（）
X的父节点
以Y为根的子树的最左下节点
X的左兄弟节点Y
以Y为根的子树的最右下节点
后序线索二叉树的右线索指向父节点，左线索指向前驱节点
P149，35、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）
空或者只有一个节点
高度等于其节点数
任一节点无左孩子
任一节点无右孩子
即所有节点只有一个孩子，C和D都不全面
P175，10、若T1是由有序树T转换而来的二叉树，则T中节点的后根序列就是T1中节点的（）序列
先序
中序
后序
层序
P176，15、若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根序列相同的是（）
先序遍历
中序遍历
后序遍历
层序遍历
P193，25、一棵哈夫曼树由215个节点，对其进行哈夫曼编码，共能得到（）个不同的码字
107
108
214
215
215=108+107，其中n_0=108,n_2=107
P194，32、已知字符集{a,b,c,d,e,f}出现的频率为{6,3,8,2,10,4}，则对应的哈夫曼编码可能是（）
00,1011,01,1010,11,100
00,100,110,000,0010,01
10,1011,11,0011,00,010
0011,10,11,0010,01,000
注意编码与字符对应顺序不要搞错
P194，33、从AVL树T1中删除节点v后得到AVL树T2，再插入v得到T3，下列关于T1，T3的说法正确的是（）
若v是T1的叶节点，则T1和T3可能不同
若v不是T1的叶节点，则T1一定与T3不相同
若v不是T1的叶节点，则T1一定与T3相同
第二个选项的反例
森林的先根遍历序列相当于对应的二叉树的先序遍历序列
森林的后根遍历序列相当于对应的二叉树的中序遍历序列