一、单选题（每题2分，共20分）
1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B
二、填空题（每空1分，共26分）
1. 联系 树（或树结构）
2. 单 （子）表
3. O(n) O(1)
4. p->next=HS;HS=p HS=HS->next
5. 先进后出 先进先出
6. 行 列
7. k-1
8. 2.625
9. 邻接矩阵 邻接表 边集数组
10. 2 1
11. O(n) O(nlog2n) O(n)
图9
12. 哈夫曼树 带权路径长度
13. 稠密 稀疏
三、运算题（每题6分，共24分）
1.(1) 3 X * Y 2 H *- / 1 +
（2） 2 X Y 3 + * +
2. 先序： a,b,c,d,e,f；中序： c,b,a,e,d,f
后序： c,b,e,f,d,a；按层： a,b,d,c,e,f
3.（1）该图的图形如图9示：
（2）深度优先遍历序列为：abdce
广度优先遍历序列为：abedc
4. 普里姆：(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20
四、阅读算法（每题7分，共14分）
1.15 22 8 5 2 10
2. 该函数的功能是：
求：
五、算法填空（共8分，每一空2分）
BST->data left right false
六、编写算法（8分）
递归算法 ：
int halfsearch(SSTable *a, KeyType k,int low,int high)
{
if (low>high)
return 0;
else
{
int mid=(low+high)/2
if EQ(k,a[mid].key) return mid;
else if LT(k,a[mid].key) return halfsearch(a,k,low,mid-1);
else return halfsearch(a,k,mid+1,high);
}
}下载本文
