第6章 树和二叉树自测题
一、填空题
1．树是一种________结构。在树结构中，________结点没有直接前趋。（层次，根）
2．一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。（子孙结点，祖先）
3．二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。（空、只有根结点、根和根的左子树、根和根的右子树、根和根的左右子树）
4．树在计算机内的表示方式有_______、_______、_________。（双亲表示法、孩子表示法、双亲孩子表示法）
5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。（n0=n2+1）
6. 高度为k(k>=1)的二叉树至多有______个结点。(2k-1)
7. 二叉树第i(i>=1)层上至多有______个结点。(2i-1)
8. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。（最大值，完全二叉树）
9．具有n个结点的完全二叉树的高度为______。（log2n）
10. 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：先序中序后序遍历二叉树
(1)若i=1，则结点X是______；若i〉1，则X的双亲PARENT(X)的编号为______。(根结点，[i/2])
(2) 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。（左孩子，右孩子，2i）
(3)若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。（右孩子，2i+1）
11. 二叉树通常有______存储结构和______存储结构两类存储结构。(顺序，链接)
12．具有n个结点的二叉链表中，一共有________个指针域，其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。(2n，n-1，n+1)
13. 一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。(访问根结点、遍历左子树、遍历右子树)
14. 若以N、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。(NLR、LNR、LRN、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历)
15. 在二叉链表中，指针p所指结点为叶结点的条件是______。(结点的左右孩子域均为空指针)
16. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶结点。（12）
17．设根结点的层数为１，具有n个结点的二叉树的最大高度是______。(n)
18. 已知二叉树前序序列为ABDEGCF，中序序列为DBGEACF，则后序序列是____。(DGEBFCA)
19. 若一个二叉树的叶结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。(先(前)序)
20. 先根次序遍历树(森林)等同于按______遍历对应的二叉树；后根次序遍历树(森林)等同于______遍历对应的二叉树。(先，中)
二、单项选择题
1．以下说法错误的是 (    A   )
A. 树型结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树型结构可以表达(组织)更复杂的数据
D．树型结构是一种层次结构
2．以下说法错误的是 (  B    )
A．二叉树可以是空集
B．二叉树的任一结点都有两棵子树
C．二叉树的任一结点最多有两棵子树
D．二叉树中任一结点的两棵子树有次序之分
3．以下说法错误的是 (    D    )
A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B. 在三叉链表上，二叉树的求结点双亲运算很容易实现
C. 在二叉链表上，求结点的左、右孩子等很容易实现
D. 在二叉链表上，求结点的双亲运算很容易实现
4．高度为6的二叉树最多有( B  )个结点   
A．64      B. 63      C. 32      D. 31
5. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为  (  D     )
A. 42    B. 40        C. 21        D. 20
6. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置  (  C     ) 
A．一定不相同    B. 有时不相同    C. 一定相同    D. 无法确定
7. 下列说法正确的是          (  A   )
A．树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B．树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C．树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D．树的后根遍历序列与其对应的二叉树的后根遍历序列相同
8．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ B ）遍历方式就可以得到这棵二叉树所有结点的递增序列。
A．先根    B. 中根    C. 后根    D. 层次
9．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（ D  ）个结点。
A．n1-1    B. n1    C. n1+n2+n3    D. n2+n3+n4
10. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,则它的前序遍历序列是（ D ）
A. acbed        B. deabc          C. decab    D. cedba

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