六 树
1．一棵具有 n个结点的完全二叉树的树高度（深度）是（⎣log2n ⎦+1）
2．有关二叉树下列说法正确的是（一棵二叉树的度可以小于完全二叉树算法2）
每个结点至多有两颗子树，即二叉树中不存在度大于2的节点。           
3．二叉树的第I层上最多含有结点数为（2I-1）

4．在下述结论中，正确的是（①④）

①只有一个结点的二叉树的度为0；
②二叉树的度为2； 
③二叉树的左右子树可任意交换；
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
5．由3 个结点可以构造出多少种不同的二叉树？（5）
6．引入二叉线索树的目的是（加快查结点的前驱或后继的速度）
7．有n个叶子的哈夫曼树的结点总数为（2n-1）
8．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（只有一个叶子结点）
9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（501）   
若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。因此，叶子结点数为1001-500=501。故答案为D。
11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（CEDBA）
A）ACBED    B）DECAB    C）DEABC    D）CEDBA
12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（11）
13．利用二叉链表存储树时，根结点的右指针是（空）
14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（M2+M3）
当森林转化为对应的二叉树时，二叉树的根结点及其左子树是由森林的第一棵树转化而来，二叉树的右子树是由森林的其余树转化而来。
15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（X的左子树中最右结点）
中序遍历二叉树时，结点的后继为遍历右子树时访问的第一个结点，即右子树中最左下的结点。左子树最右下的节点为前驱。
16．n个结点的线索二叉树上含有的线索数为（n+l）
17．在一棵高度为k的满二叉树中，结点总数为（2k-1）
18．一棵树高为K的完全二叉树至少有（2k-1 ）个结点
七．图
1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（O(n+e)）
2．设无向图的顶点个数为n，则该图最多有（n(n-1)/2）条边。
3．连通分量指的是（无向图中的极大连通子图）
4．n个结点的完全有向图含有边的数目（n*（n-1））
5．关键路径是（AOE网中从源点到汇点的最长路径）
6．有向图中一个顶点的度是该顶点的（入度与出度之和）
7．有e条边的无向图，若用邻接表存储，表中有（2e）边结点。
8．实现图的广度优先搜索算法需使用的辅助数据结构为（队列）
9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（栈）
10．存储无向图的邻接矩阵一定是一个（对称矩阵）
11．在一个有向图中所有顶点的入度之和等于出度之和的（1）倍
12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（O(n+e)　）
13．下列关于AOE网的叙述中，不正确的是（任何一个关键活动提前完成，那么整个工程将会提前完成）
14．具有10个顶点的无向图至少有多少条边才能保证连通（9
15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（n2-2e）
九．查
1．顺序查法适合于存储结构为（顺序存储或链接存储　）的线性表。
2．下面哪些操作不属于静态查表（插入一个数据元素）
3．下面描述不正确的是（经常进行插入和删除操作时可以采用二分查）
4．散列查时，解决冲突的方法有（链地址法）
5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查的平均查长度为（O(n)）
6．对长度为4的顺序表进行查，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查任一个元素的平均查长度为（9/4）
ASL=4*(1/8)+3*(1/4)+2*(3/8)+1*(1/4)=9/4
7．静态查表与动态查表二者的根本差别在于（施加在其上的操作不同  ）
8．若查表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查的平均检索长度是（O(log2n)）
9．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查，搜索到R[4]的关
键码等于给定值，此时元素比较顺序依次为（R[7]，R[3]，R[5]，R[4]）。
10．设有一个长度为100的已排好序的表，用二分查进行查，若查不成功，至少比较（8）次。
二分查不成功时和给定值进行比较的关键字个数最多不超过二叉判定树的深度。100个元素查表的判定树深为8（64<100<128）。
11．请指出在顺序表{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查关键码12需做（4  ）次关键码比较。
12．从具有 n 个结点的二叉排序树中查一个元素时，在最坏情况下的时间复杂度为 (  O (log 2 n)    ) 。
13．分块查时确定块的查可以用顺序查，也可以用（二分查），而在块中只能是（顺序查）
14．采用分块查时，若线性表中共有625个元素，查每个元素的概率相同，假设采用顺序查来确定结点所在的块时，每块应分（  25      ）个结点最佳。
15．采用分块查法（块长为s，以二分查确定块）查长度为n的线性表时，每个元素的平均查长度为（  log2 (n/s+1)+s/2 ）
16．对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（小于）
17．若二叉排序树中关键字互不相同，则下面命题中不正确的是（最小元和最大元一定是叶子）
18．设二叉排序树中关键字由1至1000的整数构成，现要查关键字为363的结点，下述关键字序列（  ）不可能是在二叉排序树上查到的序列?  925, 202, 911, 240, 912, 245, 363
19．在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。插入后的散列表应该如（  ）所示。