數(shù)據(jù)結構試卷及答案

本試卷共本試卷共6頁第黃淮學院2006—2007年第二學期計科系《數(shù)據(jù)結構》期末試卷(A)評分標準及標準答案題號1234567891011121314151617181920答案BBABABDCCCCDBDCACCBD一、選擇題，共20個小題，每小題1分，共20分；本題為單項選擇題，多選或錯選均不能得分。標準答案如下：題號12345678910答案JXXXXJXJXJ二、判斷題(在正確的題后括號內打“J”，在錯誤的題后括號內打“X”，共10個小題，每小題1分，共10分)。標準答案如下：三、應用題(共計55分)1、..10分(1)根結點為A葉子結點為：D,F,J,K,L,M,N(2)樹的度為3；樹的深度為5。(3)結點G的雙親為C結點G祖先為C,A結點G孩子為J,K(4)結點E的子孫為I,M,N結點E的兄弟為D結點E所在的層次為3。2、..8分(2)該二叉樹前序序列：ABEFIJDGH3、(1)六大城市的交通網(wǎng)絡圖..8分(2)最小生成樹6個頂點和5條邊的集合如下：V(G)={Pe,N,Pa,L,T,M}E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)}4、成成成成成成成成成成成成成成成成成成成成成成成成成成成成成成..10分(1)對應的哈夫曼樹這8個字母a,b,c,d,e,f,g,h的哈夫曼編碼分別為：1010，00，10000，1001，11，10001，01，1011（2）其最小的加權路徑長度：WPL=19*2+21*2+32*2+6*4+7*4+10*4+2*5+3*5=38+42+64+24+28+40+10+15=261

希爾排序（增量為5，2，1）的前3趟排序結果：第1趟結果：1327495544938659776第2趟結果：4271349385549659776第3趟結果：4132738起泡排序的前3趟排序結果：494955657697第1趟結果：4493865977613274955第2趟結果：4134938659776274955第3趟結果：41327493865歸并排序（二路歸并）的前3趟排序結果：97764955第1趟結果：3849659713762749455第2趟結果：3849659713274976455第3趟結果：132738496、49657697455..10分5、..9分（1）用線性探查法解決沖突時所構造的散列表：散列地址0123456789101112關鍵字14168275519208479231110比較次數(shù)121431139113(2)在等概率情況下，這種方法的查找成功及查找不成功的平均查找長度(ASL)分別為:ASLsucc=1+2+1+4+3+1+1+3+9+1+1+3)/12=30/12=5/2=2.5ASLunsucc=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7四、算法設計(第1題7分，第2題8分，共計15分)1、linklist*insert(linklist*h,datatypex)/*h是遞增有序單鏈表的頭指針，X為待插入元素*/{linklist*p,*s;p=h;while(p->next!=NULL&&p->next->data>x){p=p->next;}ifp->next==NUll{s=malloc(sizeof(linklist));s->data=x;s->next=NULL;p->next=s;}else{s=malloc(sizeof(linklist));s->data=x;s->next=p->next;p->next=s;}2、2、/*初始值：low=0;high=n-1;*/intBINSEARCH(R,low,high,K)tableR口；keytypeK;intlow,high;{while(low<=high){mid=(low+high)/2;if(K==R[mid].key)returnm