2009数据结构期末A答案

【第1页共5页】华中农业大学本科课程考试试卷答案及评分标准考试课程与试卷类型：数据结构（期末A）学年学期：2009.2-2009.7考试日期：2009-6题号一二三四五六七总分得分评卷人一、单项选择题（每题2分，共20分）题号12345678910答案DBCCAAADCB二、判断正误：（正确在（）内打√，否则打r。每小题1分，共5分）(r)（1）(r)（2）(√)（3）(r)（4）(r)（5）三、填空题.（将答案写在该题（）里。每（）2分，共12分）1．完全2.平衡3.排序4.深度优先广度优先队列本题得分四、解答题(本题满分44分)。1．解：（满分9分，每错一个关键字，扣1分）012345678910KTABAMDCIX

TNI2．解：（满分9分，其中哈夫曼树占7分，每错一处扣1分；带权路径长度正确再给2分）。WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2=2073.解：（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);……………