二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。 16．下列程序段的时间复杂度为_______。
i=0；s=0；
while（s<n）
{i++；
s=s+i；
}
17．数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种。
18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动_______个元素。
19．在单链表中，插入一个新结点需修改_______个指针。
20．在队列结构中，允许插入的一端称为_______。
21．稀疏矩阵采用的压缩存储方法是_______。
22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和_______操作。
23．有m个叶结点的哈夫曼树所具有的结点数为_______。
24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_______。
25．在一棵树中，_______结点没有前驱结点。
26．一个具有n个顶点的有向完全图的弧数是_______。
27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。
28．选择排序的平均时间复杂度为_______。
三、应用题(本大题共5小题，每小题6分，共30分)29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）
30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。
31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。
32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优
先搜索顶点序列。
题32图
33．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.编写计算二叉树中叶子结点数目的算法。
35.开散列表的类型定义如下：
typedef struct tagnode
{keytype key;
struct tagnode*next;
}*pointer,node;
typedef pointer openhash［n］;
试写出开散列表上的查找算法。
