本試卷共本試卷共6頁第黃淮學(xué)院2006—2007年第二學(xué)期計科系《數(shù)據(jù)結(jié)構(gòu)》期末試卷(A)評分標(biāo)準(zhǔn)及標(biāo)準(zhǔn)答案題號1234567891011121314151617181920答案BBABABDCCCCDBDCACCBD一、選擇題，共20個小題，每小題1分，共20分；本題為單項選擇題，多選或錯選均不能得分。標(biāo)準(zhǔn)答案如下：題號12345678910答案JXXXXJXJXJ二、判斷題(在正確的題后括號內(nèi)打“J”，在錯誤的題后括號內(nèi)打“X”，共10個小題，每小題1分，共10分)。標(biāo)準(zhǔn)答案如下：三、應(yīng)用題(共計55分)1、..10分(1)根結(jié)點為A葉子結(jié)點為：D,F,J,K,L,M,N(2)樹的度為3；樹的深度為5。(3)結(jié)點G的雙親為C結(jié)點G祖先為C,A結(jié)點G孩子為J,K(4)結(jié)點E的子孫為I,M,N結(jié)點E的兄弟為D結(jié)點E所在的層次為3。2、..8分(2)該二叉樹前序序列：ABEFIJDGH3、(1)六大城市的交通網(wǎng)絡(luò)圖..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)對應(yīng)的哈夫曼樹這8個字母a,b,c,d,e,f,g,h的哈夫曼編碼分別為：1010，00，10000，1001，11，10001，01，1011（2）其最小的加權(quán)路徑長度：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趟排序結(jié)果：第1趟結(jié)果：1327495544938659776第2趟結(jié)果：4271349385549659776第3趟結(jié)果：4132738起泡排序的前3趟排序結(jié)果：494955657697第1趟結(jié)果：4493865977613274955第2趟結(jié)果：4134938659776274955第3趟結(jié)果：41327493865歸并排序（二路歸并）的前3趟排序結(jié)果：97764955第1趟結(jié)果：3849659713762749455第2趟結(jié)果：3849659713274976455第3趟結(jié)果：132738496、49657697455..10分5、..9分（1）用線性探查法解決沖突時所構(gòu)造的散列表：散列地址0123456789101112關(guān)鍵字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四、算法設(shè)計(第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