二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.下列程序段的时间复杂度为____________。
for(i=1；i<=n；i++)
for(j=1；j<=n；j++)
for(k=1；k<=n；k++)
s=i+j+k；
17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。
18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点____________的。
19.在栈结构中，允许插入的一端称为____________。
20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动____________个元素。
21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为____________。
22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是____________。
23.一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为____________。
24.对于一棵满二叉树，若有m个叶子，则树中结点数为____________。
25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。
26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。
27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为____________。
28.堆排序需____________个记录大小的辅助存储空间。

三、应用题(本大题共5小题，每小题6分，共30分)
29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈)
30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该
二叉树。
31.题31图中二叉排序树的各结点的值为32～40，标出各结点的值。

题31图
32.下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。

33.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。

四、算法设计题(本大题共2小题，每小题7分，共14分)
34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。
35.试写出直接插入排序算法。