集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#
数据结构树和二叉树习题及答案

习题六  树和二叉树
一、单项选择题
1．以下说法错误的是 (    )
A．树形结构的特点是一个结点可以有多个直接前趋
B．线性结构中的一个结点至多只有一个直接后继
C．树形结构可以表达(组织)更复杂的数据
D．树(及一切树形结构)是一种"分支层次"结构
E．任何只含一个结点的集合是一棵树
2．下列说法中正确的是 (    )
A．任何一棵二叉树中至少有一个结点的度为2
B．任何一棵二叉树中每个结点的度都为2
C．任何一棵二叉树中的度肯定等于2
D．任何一棵二叉树中的度可以小于2
3．讨论树、森林和二叉树的关系，目的是为了（    ）
A．借助二叉树上的运算方法去实现对树的一些运算
B．将树、森林按二叉树的存储方式进行存储
C．将树、森林转换成二叉树
D．体现一种技巧，没有什么实际意义
4．树最适合用来表示 (    )
A．有序数据元素                                B．无序数据元素
C．元素之间具有分支层次关系的数据              D．元素之间无联系的数据
5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（  ）
A．9            B．11        C．15      D．不确定
6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（    ）。
A．M1          B．M1+M2      C．M3          D．M2+M3
先序中序后序遍历二叉树7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（    ）
A． 250  B． 500    C．254    D．505      E．以上答案都不对   
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为(    )
A．不确定        B．2n        C．2n+1        D．2n-1
9．二叉树的第I层上最多含有结点数为（   ）
A．2I         B． 2I-1-1          C． 2I-1            D．2I -1
10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(    )结点
A．2h    B．2h-1        C．2h+1        D．h+1   
11. 利用二叉链表存储树，则根结点的右指针是（    ）。
A．指向最左孩子        B．指向最右孩子        C．空        D．非空
12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（    ）。
A．CBEFDA      B． FEDCBA      C． CBEDFA      D．不定   
13．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,  它的前序遍历是（    ）。
A．acbed      B．decab    C．deabc      D．cedba   
14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（    ）
A．都不相同                            B．完全相同 
C．先序和中序相同，而与后序不同        D．中序和后序相同，而与先序不同 
15．在完全二叉树中，若一个结点是叶结点，则它没（    ）。
A．左子结点                B．右子结点　 
C．左子结点和右子结点      D．左子结点，右子结点和兄弟结点
16．在下列情况中，可称为二叉树的是（    ）
A．每个结点至多有两棵子树的树   
B. 哈夫曼树   
C．每个结点至多有两棵子树的有序树 
D. 每个结点只有一棵右子树       
E．以上答案都不对 
17. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：(    )。
A. 0            B. 1        C. 2          D. 不确定
18. 引入二叉线索树的目的是（    ）
A．加快查结点的前驱或后继的速度  B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的到双亲            D．使二叉树的遍历结果唯一
19．n个结点的线索二叉树上含有的线索数为（    ）
A．2n      B．n－l      C．n＋l        D．n
20．由3 个结点可以构造出多少种不同的二叉树（    ）
A．2      B．3        C．4        D．5 
21．下面几个符号串编码集合中，不是前缀编码的是（    ）。
A．{0,10,110,1111}            B．{11,10,001,101,0001}   
C．{00,010,0110,1000}        D．{b,c,aa,ac,aba,abb,abc}
22. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（    ）
A．A[2i](2i<=n)             B．A[2i+1](2i+1<=n) 
C．A[i-2]                     D．条件不充分，无法确定
23、以下说法错误的是 (    )
A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。