2009數(shù)據(jù)結(jié)構(gòu)期末A答案

【第1頁共5頁】華中農(nóng)業(yè)大學(xué)本科課程考試試卷答案及評分標(biāo)準(zhǔn)考試課程與試卷類型：數(shù)據(jù)結(jié)構(gòu)（期末A）學(xué)年學(xué)期：2009.2-2009.7考試日期：2009-6題號(hào)一二三四五六七總分得分評卷人一、單項(xiàng)選擇題（每題2分，共20分）題號(hào)12345678910答案DBCCAAADCB二、判斷正誤：（正確在（）內(nèi)打√，否則打r。每小題1分，共5分）(r)（1）(r)（2）(√)（3）(r)（4）(r)（5）三、填空題.（將答案寫在該題（）里。每（）2分，共12分）1．完全2.平衡3.排序4.深度優(yōu)先廣度優(yōu)先隊(duì)列本題得分四、解答題(本題滿分44分)。1．解：（滿分9分，每錯(cuò)一個(gè)關(guān)鍵字，扣1分）012345678910KTABAMDCIX

TNI2．解：（滿分9分，其中哈夫曼樹占7分，每錯(cuò)一處扣1分；帶權(quán)路徑長度正確再給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分，每錯(cuò)一步，扣1分）5、解（滿分7分，每錯(cuò)1步扣1.5分）本題得分五、程序填空題：(請閱讀下面拓?fù)渑判蛩惴ǔ绦?，完成填空，將答案寫在該題橫線上,每空3分，本題滿分9分)。indegree[i]==0p!=NULLp=p->nextarc本題得分六、編程題：(本題滿分10分).解法1：LinkList

merge_1(LinkListLA,LinkListLB){

/*此算法將兩個(gè)采用頭指針的循環(huán)單鏈表的首尾連接起來*/

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）{

/*此算法將兩個(gè)采用尾指針的循環(huán)鏈表首尾連接起來*/

Node*p;

p=RA->next;…………………2分

RA->next=RB->next->next;

free(RB->next);……………