二学期数据结构评分标准A

1、2012 _2013_学年第 1 学期 数据结构 课程试卷标准答案及评分标准 A( )/B( ) 卷 专业_计专_ 班级 _ 111_一、单项选择题：(每小题1.5*20=30分)1. B 2.D 3. B 4.A 5.B6.B 7.C 8.D 9.A 10.B11. A 12. C 13. A 14. B 15. A16.B  17. B 18.A 19. C 20. C二、判断题（每小题1分，10分）× × × × × ×三、简答题：（共46分）1.（4分）答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。

2、数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。（10分）解： （1）哈希表如下：（4分）012345678910111213141516011455276819208423111077（2） 查找27,首先要与H(27)=27%13=1号单元内容比较，与01冲突;然后用线性探测再散列处理冲突，与14，55，27相比较，一共比较了4次，查找成功（2分）（3）查找87,首先要与H(87)=87%13=9号单元内容比较，但因为9号单元为空（应当有空标记），所以应当只比较这一次即可。（2分）（4）ASL=23/12 (2分)3. （共10分）哈夫曼编码先将概率放大100倍，以方便

3、构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.104. 50，18，12，61，8，17，87，25不是堆（2分）调整为堆的过程为：61和25交换50，18，12，2

4、5，8，17，87，6118和8交换50，8，12，25，18，17，87，6150先和8交换然后和18交换结果为8，18，12，25，50，17，87，61 （4分）5.（共8分）先罗列：f2g a3c f3e a4b d4h 目前存在(a,b,c) (e,f,g) (d,h) 三个连通分量。 取b5d, g5-d 就把三个连通分量连接起来了。解法二：先罗列：f2g a3c f3e a4b d4h 目前存在(a,b,c) (e,f,g) (d,h) 三个连通分量。 取c5d, g5d 就把三个连通分量连接起来了。6.（共8分）解：（1） 先画出判定树如下（注：mid=ë(1+12)

5、/2û=6）：（2分）305 633 7 42 87 4 24 54 72 95(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；（2分）(3) 查找元素90，需依次与30, 63,87, 95等元素比较；（2分）（4） 所以ASL1/12（1*1+2*2+3*4+4*5）37/123.08（2分）四、算法设计题（共14分）1. （8分） （1） low<=high (2) mid=(low+high)/2 (3)high=mid-1 (4)low=mid+12. （6分）Status ListOppose_L(LinkList &L)LinkList p,q;p=L->next; /p指向单链表第一个结点L->next=NULL; /形成空的单链表while(p) /采用头