第6章树和二叉树自测题.doc

《第6章树和二叉树自测题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、__________________________________________________第6章树和二叉树自测题一、填空题1．树是一种________结构。在树结构中，________结点没有直接前趋。（层次，根）2．一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。（子孙结点，祖先）3．二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。（空、只有根结点、根和根的左子树

2、、根和根的右子树、根和根的左右子树）4．树在计算机内的表示方式有_______、_______、_________。（双亲表示法、孩子表示法、双亲孩子表示法）5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。（n0=n2+1）6.高度为k(k>=1)的二叉树至多有______个结点。(2k-1)7.二叉树第i(i>=1)层上至多有______个结点。(2i-1)8.满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。（最大值，完全二叉树）9．具有n个结点

3、的完全二叉树的高度为______。（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.

4、二叉树通常有______存储结构和______存储结构两类存储结构。(顺序，链接)12．具有n个结点的二叉链表中，一共有________个指针域，其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。(2n，n-1，n+1)13.一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。(访问根结点、遍历左子树、遍历右子树)14.若以N、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序

5、有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。(NLR、LNR、LRN、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历)15.在二叉链表中，指针p所指结点为叶结点的条件是______。(结点的左右孩子域均为空指针)16.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶结点。（12）17．设根结点的层数为１，具有n个结点的二叉树的最大高度是______。(n)18.已

6、知二叉树前序序列为ABDEGCF，中序序列为DBGEACF，则后序序列是____。(DGEBFCA)19.若一个二叉树的叶结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。(先(前)序)20.先根次序遍历树(森林)等同于按______遍历对应的二叉树；后根次序遍历树(森林)等同于______遍历对应的二叉树。(先，中)收集于网络，如有侵权请联系管理员删除__________________________________________________二、单项选择题1．以下说法错误

7、的是(A)A.树型结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树型结构可以表达(组织)更复杂的数据D．树型结构是一种层次结构2．以下说法错误的是(B)A．二叉树可以是空集B．二叉树的任一结点都有两棵子树C．二叉树的任一结点最多有两棵子树D．二叉树中任一结点的两棵子树有次序之分3．以下说法错误的是(D)A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求结点双亲运算很容易实现C.在二叉链表上，求结点的左、右孩子等很容易实现D.在二叉链表上，求结点的

8、双亲运算很容易实现4．高度为6的二叉树最多有(B)个结点A．64B.63C.32D.315.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为(D)A.42B.40C.21D.206.任何一棵二叉树的叶结点在其先