①2h ②2h-1 ③2h-1 ④2h+1-1
二、判断题
三、填空题 （附答：
1、 分支层次、根、直接前趋 2、 子孙、祖先
3、 空、只含根、非空左子树、非空右子树、非空左右子树 4、 2i-1 5、 2k-1 6、 n2+1
7、 最大值、完全 8、 floor(log2n)+1
9、23 10、6 11、16
3、前趋 前趋 后趋 后趋
4、线性 5、线性 长度 表长 6、空表
12、0（1） 13、0 14、head->next==NULL 15、上溢 16、28 17、每个数据元素是一个字符 ）
1、 树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2、 一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________
3、 一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______
的二叉树、同时有______的二叉树五种基本形态。 4、 二叉树第i(i>=1)层上至多有______个结点。 5、 深度为k(k>=1)的二叉树至多有______个结点。
6、 对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
7、 满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。
8、 具有n个结点的完全二叉树的深度为______。 9. 如果一棵树有6个度为1的结点，有5个度为2的结点，有2个度为3的结
点，其余结点均为叶子，则该树的结点总数为_______。 10. 某完全二叉树有39个结点，计算其深度为_______。 11. 深度为5的完全二叉树，结点个数最少为______。
3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.
4.所有结点按1对1的邻接关系构成的整体就是______结构。
5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______.
6.表长为O的线性表称为______
12. 下面语句段执行的时间复杂度是________。
int i,j,n,s=0;
cin>>n; //这里用n表示问题的规模 for (i=1;i<=10;i++)
for (j=1;j<=10;j++)
s+=i+j;
13. 访问长度为n的顺序表第i个元素，需要移动的元素个数为_______。 14. 带头结点的单链表head为空的判断条件是 。 15. 当栈满时再执行进栈操作，会产生 。
16. 设某循环队列的排头front值为17，队尾rear值为15，保存队列元素的数组
下标定义为30，则该循环队列中有______个元素。 17. 串是一种特殊的线性表，其特殊性在于---------。