《数据结构》试卷A参
一、选择题(每小题2分，共计30分)
AACCD BCAAC BCCAA 二、判断题(每小题1 分，共计10分) 对对错错对 对对错错对
三、应用题(每小题10分，共计40分
1、 1）
a e d c b
2）edbca
3）e=1,a=2,d=3,c=4,b=5 2、2、1）（4分）
无向图
2)6(分)
邻接矩阵
3、初始状态：10，2，13，15，12，14 第1趟： ( 2，10，13，15，12，14) 第2趟： 2，(10，12，13，15，14) 第3 趟：2，10 ，(12，14，13，15) 第4趟： 2，10，12，(13，14，15) 第5趟： 2，10，12，13，( 14，15)
2分 2分 2分 2分 2分
第6趟： 2，10，12，13，14，15
4、(1)用拉链法处理冲突构造的散列表如下图所示：(6分)
图3.拉链法解决冲突
(2) 在等概率的情况下，查找成功的平均查找长度： ASLs= （1×7+2×2+3×1）/10=1.4 (4分)
四、算法设计题(共计20分)
1、(1)计算二叉树叶子结点个数。(6分) (2)该二叉树叶子结点个数是4。(4分) 2、（1）jnext （3）q->next（4）q->next （5）p 3、（1）low<=high（2）mid（3）a[mid].key