原创力文档- 1、本文档共5页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
【第PAGE1页共NUMPAGES5页】
华中农业大学本科课程考试试卷答案及评分标准
考试课程与试卷类型：数据结构（期末A）学年学期：2009.2-2009.7考试日期：2009-6
题号
一
二
三
四
五
六
七
总分
得分
评卷人
一、单项选择题（每题2分，共20分）
题号
1
2
3
4
5
6
7
8
9
10
答案
D
B
C
C
A
A
A
D
C
B
二、判断正误：（正确在（）内打√，否则打r。每小题1分，共5分）
(r)（1）(r)（2）(√)（3）(r)（4）(r)（5）
三、填空题.（将答案写在该题（）里。每（）2分，共12分）
1．完全2.平衡3.排序4.深度优先广度优先队列
本题
得分
四、解答题(本题满分44分)。
1．解：（满分9分，每错一个关键字，扣1分）
0
1
2
3
4
5
6
7
8
9
10
K
TA
BA
M
D
CI
X
?
?
TN
I
2．解：（满分9分，其中哈夫曼树占7分，每错一处扣1分；带权路径长度正确再给2分）。
WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2
=207
3.
解：（1）
□，50，15，30，85，12，20，702分
20，50，15，30，85，12，□，70………1分
20，□，15，30，85，12，50，70…………1分
20，12，15，30，85，□，50，70…………1分
20，12，15，30，□，85，50，70………1分
（20，12，15，30，）35,(85,50,70)………1分
（2）
（35），50，15，30，85，12，20，70……1分
（35，50），15，30，85，12，20，70
（15，35，50），30，85，12，20，70……1分
（15，30，35，50），85，12，20，70
（15，30,35,50,85）,12,20,70……1分
(12,15,30,35,50,85),20,70
(12,15,20,30,35,50,85),70……1分
(12,15,20,30,35,50,70,85)……1分
?4、解：（满分7分，每错一步，扣1分）
5、解（满分7分，每错1步扣1.5分）
本题
得分
五、程序填空题：(请阅读下面拓扑排序算法程序，完成填空，将答案写在该题横线上,每空3分，本题满分9分)。
indegree[i]==0p!=NULLp=p->nextarc
本题
得分
六、编程题：(本题满分10分)
.
解法1：
LinkList??merge_1(LinkListLA,LinkListLB)
{?/*此算法将两个采用头指针的循环单链表的首尾连接起来*/
?????Node*p,*q;
??????p=LA;
??????q=LB;……………………..2分
??????while(p->next!=LA)?????p=p->next;???
??????while(q->next!=LB)?????q=q->next;????……….3分
??????q->next=LA;??
??????p->next=LB->next;…………4分
??????free(LB);
return(LA);
}………………………..1分
解法2：
LinkList??merge_2（LinkListRA,LinkListRB）
{?/*此算法将两个采用尾指针的循环链表首尾连接起来*/
?????Node*p;
??????p=RA->next;…………………2分
??????RA->next=RB->next->next;
??????free(RB->next);………………4分
??????RB->nex
文档评论（0）