二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。
17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_________。
18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_________和_________。
19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_________和_________。
20.在栈结构中，允许插入的一端称为_________;在队列结构中，允许插入的一端称为_________。
21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_________。
22.深度为k的二叉树至多有_________个结点，最少有_________个结点。
23.设有一稠密图G，则G采用_________存储结构较省空间。设有一稀疏图G，则G采用_________存储结构较省空间。
24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_________个元素结点。
25.假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。
26.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中_________特别适应磁带存储器，也适应磁盘存储器。
27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是_________。
28.冒泡排序最好的时间复杂度为_________，平均时间复杂度为_________，是一种稳定的排序算法。

三、应用题(本大题共5小题，每小题6分，共30分)
29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。
30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。
 
题30图
31.已知某图的邻接表存储结构如题31图所示：
 
题31图
(1)画出该图。
(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
32.假定采用H(k)=kmod7计算散列地址，引用线性探测的开放定址法解决冲突，试在0~6的散列地址空间中，对关键字序列(38，25，74，63，52，48)构造散列表，并求出等概率情况下查找成功的平均查找长度。
33.用快速排序法对数据序列(49，38，65，97，16，53，134，27，39)进行排序，写出其第一趟排序的全过程。

四、算法设计题(本大题共2小题，每小题7分，共14分)
34.完善下列折半插入排序算法。
Voidbinasort(structnoder[MAXSIZE]，int n)
　　{for(i=2;i<=n;i++){
　　　　r[0]=r[i];low=1;high=i-1;
　　　　while(low<=high){
　　　　　　mid=(1)_________;
　　　　　　if(r[0].key　　　　　　　　high=(2)_________;
　　　　　　elselow=(3)_________;
　　　　}
　　　　for(j=i-1;j>=low;j--)
　　　　(4)_________;
　　　　r[low]=r[0];
　　}
}
35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。
Voidlevel(BSTreeroot，p) 
　　{intlevel=0;
　　　　if(!root)
　　　　　　(1)_________;
　　　　else{
　　　　　　level++;
　　　　　　while(root—>key!=p—>key){
　　　　　　　　if(root—>keykey)
　　　　　　　　　　(2)_________;
　　　　　　　　else
　　　　　　　　　　(3)_________;
　　　　　　　　level++;
　　　　　　}
　　　　　　(4)_________;
　　　　}
　　}