数据结构第六章树和二叉树习题 (1)
第六章树和二叉树
一、选择题
1. 在下述结论中，正确的是（）
①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右
子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
2．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点
个数是（）
A．9 B．11 C．15 D．不确定
3．具有10个叶结点的二叉树中有（）个度为2的结点。
A．8 B．9 C．10 D．ll
4. 有关二叉树下列说法正确的是（）
A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为
2
5．二叉树的第I层上最多含有结点数为（）
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
6. 一个具有1025个结点的二叉树的高h为（）
A．11 B．10 C．11至1025之间 D．10至1024之
间
7．一棵具有 n个结点的完全二叉树的树高度（深度）是（）
A．nlog
2n B．log
2
n C．?log
2
n?|+1 D．不确定
8．深度为h的满m叉树的第k层有（）个结点。(1= A．2k B．2k-1 C．2k -1 D．2k-1-1 11. 一棵树高为K的完全二叉树至少有（）个结点。 A．2k–1 B. 2k-1–1 C. 2k-1 D. 2k 12. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非 空 13．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右 孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可 采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按 层次遍历 14．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 15．在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示 法 16．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。 A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 17．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序 遍历的结果为（）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 18．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前 序遍历是（）。 A．acbed B．decab C．deabc D．cedba 19. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序 列是： A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上 面的都不对 20．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：（） A、 E B、 F C、 G D、 H 21．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 22. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一23．下述编码中哪一个不是前缀码（）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 24．下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 二、判断题 1. 二叉树是度为2的有序树。 2. 完全二叉树一定存在度为1的结点。 n。 3. 对于有N个结点的二叉树，其高度为log 2 4．深度为K的二叉树中结点总数≤2k-1。 5. 二叉树的遍历结果不是唯一的. 6．由一棵二叉树的前序序列和后序序列可以唯一确定它。 7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 8. 二叉树只能用二叉链表表示。 9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。 10．树形结构中元素之间存在一个对多个的关系。 11．在二叉树的第i层上至少有2i-1个结点(i>=1)。 12．将一棵树转成二叉树，根结点没有左子树。 三、填空题 1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。 3．具有256个结点的完全二叉树的深度为______。 4．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。5．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。