第第頁共49頁分別用Prim和kruskal算法構(gòu)造最小生成樹。（需標(biāo)示每一步構(gòu)造過程）四、算法設(shè)計（第1題10分，第2,3題各15分，共40分）設(shè)計算法，在不帶頭結(jié)點的單鏈表L上實現(xiàn)刪除data域值為x的所有結(jié)點，返回刪除結(jié)點的個數(shù)；intList_Delete（structLNode*L，KeyTypex）采用鏈?zhǔn)酱鎯崿F(xiàn)棧的操作（數(shù)據(jù)元素類型為ElemType）,包括棧的初始化InitStack、入棧Push、出棧Pop、取棧頂元素Peek、判棧空Empty、清空棧ClearStack以及返回棧中元素個數(shù)GetLen等操作，并作簡單注釋。根據(jù)給定的n個權(quán)值可以構(gòu)造一顆哈夫曼樹。若哈夫曼樹采用順序存儲結(jié)構(gòu),每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)采用如下格式。Typedefstruct{unsignedintweight;//結(jié)點的權(quán)值unsignedintparent,lchild,rchild;//分別存放雙親、左右孩子的下標(biāo)}Huffman;試設(shè)計如下算法CreatHuffman，根據(jù)給定的n個權(quán)值構(gòu)造一顆哈夫曼樹。voidCreatHuffman（HuffmanHT[],intn,intw[]）;其中：HT為構(gòu)造的哈夫曼樹，n表示權(quán)值個數(shù)，w用來存儲所有權(quán)值下圖是根據(jù)權(quán)值7,5，2，4所構(gòu)造出來的哈夫曼樹（-1表示空）。參考答案⑷一、選擇題（10小題，每題2分，共20分）DBACDADCAB二、填空題（10小題，每題2分，共20分）1.關(guān)系和操作2.O（n）3.棧4.15.146.A[2i+2]7.28.隊列9.Dijkstra10.11

三、綜合應(yīng)用題(7小題，每題10分，共70分)3(3)(4)(1)k=2i+j-3(2)i=(k+l)/3+lj=(k+l)/3+(k+l)%3(1).三、綜合應(yīng)用題(7小題，每題10分，共70分)3(3)(4)(1)k=2i+j-3(2)i=(k+l)/3+lj=(k+l)/3+(k+l)%3(1).-'(2)先序中序后序:eadcbjfghi:abcdjefhgi:bcjdahigfe01234567891011121314151617181938202142242526452931332041111111211123.散列函數(shù)H(k)=k%19成功：ASL=14/12=7/6不成功：ASL=(4+3+2+1+6+5+4+3+2+1+2+1+2+1+3+2+1+1+1+1)/20=46/20=2.34.1)4)1)快速排序一趟后的結(jié)果:25351640728761502)堆排序進行升序初始堆:87726150401625353)堆排序1趟以后的結(jié)果:72506135401625874)1趟冒泡排序后的結(jié)果:35406172162550875)1趟歸并排序后的結(jié)果:35406187167225505.(2)7291(3)724531查找成功的平均查找長度:(1+2*2+4*3+6*4)/13=41/13不成功時的平均查找長度:(2*3+12*4)/14=54/14=27/76.(1)事件V1V2V3V4V5V6V7V8V9V10V11最早發(fā)生時間01510655080160190220250270最遲發(fā)生時間0151565205801602052202502702)活動a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14e100015106510801908016050220250190l15051557651659520580160205220250210(3)關(guān)鍵路徑:a1-〉a3-〉a5-〉a9-〉a10-〉a12-〉a134)12四、算法設(shè)計(第1題10分，第2，3題各15分，共40分)1.intList_Delete(structLNode*L,KeyTypex){intc=0;if(L==NULL)return0;p=L;while(p->next){if(p->next->data==x){c++;s=p->next;p->next=s->next;free(s);}elsep=p->next;}if(L->data==x){c++;p=L;L=L->next;free(p);}returnc;}2.typedefstructnode{ElenTypedata;structnode*next;}LinkStack;voidInitStack(LinkStack&L){L=NULL;}voidPush(LinkStack&L,ElemTypex){p=(LinkList*)malloc(sizeof(LinkList));p->data=x;p->next=L;L=p;}voidPop(LinkStack&L,ElemType&x){if(L==NULL)return;p=L;L=L->next;x=p->data;free(p);}voidPeek(LinkStack&L,ElemType&x){if(L==NULL)return;x=L->data;}intEmpty(LinkStackL){returnL==NULL;}voidClearStack(LinkStack&L){while(L){p=L->next;free(L);L=p;}}intGetLen(LinkStackL){inti=0;p=L;while(p){i++;p=p->next;}returni;}3.voidCreatHuffman(HuffmanHT[]，intn，intw[]){for(i=0；i<n；i++){HT[i].lchild=T;HT[i].rchild=T;HT[i].weight=w[i];HT[i].parent=T;}for(i=n；i<2*n-