有哪些信誉好的足球投注网站- 1、本文档共5页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
1213二學期数据结构评分标准A
2012 ~ _2013_学年第 1 学期 数据结构 课程试卷
标准答案及评分标准 A( √ )/B( ) 卷
专业___计专_____ 班级 ___ 111_____
一、单项选择题：(每小题1.5*20=30分)
1. B 2.D 3. B 4.A 5.B
6.B 7.C 8.D 9.A 10.B
11. A 12. C 13. A 14. B 15. A
16.B? 17. B 18.A 19. C 20. C
二、判断题（每小题1分，10分）
１．× ２．× ３．× ４．× ５．√
６．√ ７．√ ８．√ ９．× １０．×
三、简答题：（共46分）
1.（4分）答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
２．（10分）
解： （1）哈希表如下：（4分）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 01 14 55 27 68 19 20 84 23 11 10 77 （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倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32
（100）
（40） （60）
19 21 32 （28）
（11）
7 10 6 （5）
2 3
4. {50，18，12，61，8，17，87，25}不是堆（2分）
调整为堆的过程为：
61和25交换{50，18，12，25，8，17，87，61}
18和8交换{50，8，12，25，18，17，87，61}
50先和8交换然后和18交换结果为{8，18，12，25，50，17，87，61} （4分）
5.（共8分）
先罗列：f—2—g a—3—c f—3—e a—4—b d—4—h
目前存在(a,b,c) (e,f,g) (d,h) 三个连通分量。 取b—5—d, g—5--d 就把三个连通分量连接起来了。
解法二：先罗列：f—2—g a—3—c f—3—e a—4—b d—4—h
目前存在(a,b,c) (e,f,g) (d,h) 三个连通分量。 取c—5—d, g—5—d 就把三个连通分量连接起来了。
6.（共8分）
解：
先画出判定树如下（注：mid=?(1+12)/2?=6）：（2分）
30
5 63
3 7 42 87
4 24 54 72 95
(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；（2分）
(3) 查找元素90，需依次与30, 63,87, 95等元素比较；（2分）
（4） 所以ASL＝1/12（1*1+2*2+3*4+4*5）＝37/12≈3.08（2分）
四、算法设计题（共14分）
1. （8分）
（1） low=high
(2) mid=(low+high)/2
(3)high=mid-1
(4)low=mid+1
2. （6分）
Status ListOppose_L(LinkList L)
{
LinkList p,q;
p=L-next; //p指向单链表第一个结点
L-next=NULL; //形成空的单链表
while(p){ //采用头插入法将p结点插入到头结点的后面实现逆置
q=p;
p=p-next;
q-next=L-next;
L
文档评论（0）