2009年《數(shù)據(jù)結(jié)構(gòu)》試卷B答案

你一定要堅強，即使受過傷，流過淚，也能咬牙走下去。因為，人生，就是你一個人的人生。==============================================================================年月日第頁共頁命運如同手中的掌紋，無論多曲折，終掌握在自己手中==============================================================西華大學課程考試參考答案（B卷）第1頁共3頁裝訂線課程名稱：數(shù)據(jù)結(jié)構(gòu)考試時間：110分鐘課程代碼：8401801試卷總分：100分一、單項選擇題參考答案及評分標準：（本大題共20個小題，每小題2分，共40分）評分標準：選對一題得2分，不選或選錯得0分。1-5：ABDBB6-10：CABDC11-15：BABCB16-20：CABCC二、算法理解題參考答案及評分標準：（本大題共3個小題，第1、2小題各7分，第3小題6分，共20分）評分標準：請根據(jù)各解答步驟酌情給分。1.解答：構(gòu)造過程各圖（略），最后結(jié)果為：2.解：設(shè)權(quán)w=(5,10,15,30,40)，可構(gòu)造一棵赫夫曼樹如下圖所示。所得赫夫曼編碼為：A:1110B:1111C:110D:10E:03.解：（1）

希爾排序第一趟（增量d=5）排序后170、087、275、061、426、503、897、512、653、908第二趟（增量d=3）排序后061、087、275、170、426、503、897、512、653、908第三趟（增量d=1）排序后061、087、170、275、426、503、512、653、897、908（2）

基數(shù)排序第一趟排序后170、061、512、503、653、275、426、087、897、908第一趟排序后503、908、512、426、653、061、170、275、087、897第三趟排序后061、087、170、275、426、503、512、653、897、908三、算法設(shè)計題參考答案及評分標準：（本大題共4個小題，每小題10分，共40分）評分標準：請根據(jù)編程情況酌情給分。1.參考答案示例：LinkListDelete(LinkListL）∥L是帶頭結(jié)點的單鏈表，本算法刪除其最小值結(jié)點。p=L->next；∥p是鏈表的工作指針pre=L；∥pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)。q=p；∥q指向數(shù)據(jù)域最小值結(jié)點，初始假定是首元結(jié)點while（p->next!=NULL）{if（p->next->data<q->data）{pre=p；q=p->next；}∥找到新的最小值結(jié)點p=p->next；}pre->next=q->next；∥將最小值結(jié)點從鏈表上去掉free（q）；∥釋放最小值結(jié)點空間}∥Delete2.參考答案示例：intBTreeEqual(BiTNode*T1,BiTNode*T2){//判斷兩棵二叉樹是否相等，若相等則返回1否則返回0。if(T1==NULL&&T2==NULL)return1;elseif(T1==NULL||T2==NULL)return0; elseif((T1->data==T2->data)&&BTreeEqual(T1->lchild,T2->lchild)&& BTreeEqual(T1->rchild,T2->rchild))return1;elsereturn0;//若根結(jié)點值不等或左、右子樹對應不等則兩棵樹不等}//BTreeEqual3.參考答案示例：intvisited[]=0;//全局變量，訪問數(shù)組初始化intPath_BFS(ALGraphG,intvi,intvj){//以鄰接表為存儲結(jié)構(gòu)的有向圖G，廣度優(yōu)先判斷G中vi到vj間是否有通路。//返回1或0表示有或無。假設(shè)頂點的信息就是頂點編號。visited[vi]=1;InitQueue(Q);

EnQueue(Q,vi);while(!QueueEmpty(Q)){DeQueue(Q,k);

for(p=G.vertices[k].firstarc;p;p=p->nextarc)

{

if(p->adjvex==vj)return1;

else{if(!visited[p->adjvex]){visited[p->adjvex]=1;EnQueue(Q,p->adjvex);}

}//endelse

}//endfor

}//endwhile

return0;}//Path_BFS4.參考答案示例：intPartition(SqList&L,intlow,inthigh){//快速排序的一趟劃分算法。L.r[0]=L.r[low];//用子表的第一個記錄作基準記錄pivotkey=L.r[low].key;//基準記錄關(guān)鍵字while(low<high){//從表的兩端交替地向中間掃描while(low<high&&L.r[high].key>=pivotkey)high--;L.r[low]=L.r[high];while(low<high&&L.r[low].ke