admin 管理员组文章数量: 1184232
2024年3月20日发(作者：nativebinding官网)
第6章 树和二叉树自测题
一、填空题
1．树是一种________结构。在树结构中，________结点没有直接前趋。（层次，根）
2．一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称
A是B的________。（子孙结点，祖先）
3．二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉
树、同时有______的二叉树五种基本形态。（空、只有根结点、根和根的左子树、根和根的
右子树、根和根的左右子树）
4．树在计算机内的表示方式有_______、_______、_________。（双亲表示法、孩子表示
法、双亲孩子表示法）
5．对任何二叉树，若度为2的节点数为n
2
，则叶子数n
0
=______。（n
0
=n
2
+1）
6. 高度为k(k>=1)的二叉树至多有______个结点。(2
k
-1)
7. 二叉树第i(i>=1)层上至多有______个结点。(2
i-1
)
8. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______
二叉树，但反之不然。（最大值，完全二叉树）
9．具有n个结点的完全二叉树的高度为______。（log
2
n）
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、先根（或前序）遍历、中根（或中序）遍历、后
根（或后序）遍历)
版权声明：本文标题：第6章树和二叉树自测题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710947294a580915.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论