《数据结构》-数据结构试卷第六章.docx

《数据结构》期末复****题及参考答案- 第6章树和二叉树
一、选择题
1、在二叉树的第I层(I≥1)上最多含有结点数为( )
A. 2I B. 2I-1-1 C. 2I-1 D. 2I -1
2、深度为6的二叉树最多有( )个结点

3、一棵树高为K的完全二叉树至少有( )个结点
–1 -1 –1 -1 k
4、有关二叉树下列说法正确的是( )
A. 二叉树的度为2 B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2

5、n个结点的线索二叉树上含有的线索数为( )
A. 2n B. n-l C. n+l D. n
6、线性表和树的结构区别在于( )
,后继数量相同 ,后继数量不同

7、已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为ABC*+DE/-,则其前缀形式为( )
A.-A+B*C/DE B. -A+B*CD/E C.-+*ABC/DE D. -+A*BC/DE
8、设有一表示算术表达式的二叉树(见下图),
E
F
D
G
A
B
/
+
+
*
-
C
*
它所表示的算术表达式是( )
A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G)
C. (A*B+C)/(D*E+(F-G)) D. A*B+C/D*E+F-G
9、一棵具有 n个结点的完全二叉树的树高度(深度)(符号表示取不大于x的最大整数)是( )
A. B. C. D.
10、利用二叉链表存储树,则根结点的右指针是( )。

11、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( )。
B. FEDCBA C. CBEDFA
12、某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E 则前序序列是:
,G,F,A,C,D,B ,A,C,B,D,G,F ,A,G,C,F,B,D
13、若前序遍历二叉树的结果为序列A、B、C,则有_________棵不同的二叉树可以得到这一结果。
A. 3 B. 4 C. 5 D. 6

14、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 则它的前序遍历是( )。
A. acbed B. decab C. deabc D. cedba
15、线索二叉树是一种( )结构。

二、填空题
1、对于任意一棵二叉树,如果其叶子结点数为N0,度为1的结点数为N1,度为2的结点数为N2,则N0=___ N2 + 1_________。
2、具有256个结点的完全二叉树的深度为___9___。
3、一个深度为4的二叉树,其结点至少有 4 个,至多有 15 个:
4、深度为H 的完全二叉树至少有_ 2H-1__个结点;至多有 2H-1_个结点;H和结点总数N之间的关系是 H=ëlog2Nû+1。
5、若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,N个结点的二叉树共有__2N__个指针域,其中有_N-1__个指针域是存放了地址,有__N+1_____个指针是空指针。
6、设一棵赫夫曼树有6个叶子结点,权值分别为3、4、7、14、15、20,则根结点的权值是__63____
7、已知二叉树的先序遍历次序是 abdcef,中序遍历次序是 bdaecf,则它的后序遍历次序是: dbefca 。
8、对一棵完全二叉树,设一个结点的编号为i,若它的左孩子结点存在,则其编号为 2i ;若右孩子结点存在,则其编号为 2i+1 ;而双亲结点的编号为ë û 。
9、赫夫曼树是带权路径长度最小的二叉树,又称最优二叉树,路径上权值较大的结点离根较近。
10、下面程序段的功能是建立二叉树的算法,请在下划线处填上正确的内容。
typedef struct node
{ int data;
struct node *lchild;_
struct node *rchild __;
} BiTNode, *BiTree;
void createBitree(BiTree &T)
{ scanf(“%c”, &ch);
if(ch=='#') T=NULL