數(shù)據(jù)結(jié)構(gòu)課后習(xí)題部分參考答案

1、數(shù)據(jù)結(jié)構(gòu)課后習(xí)題部分參考答案 ? )n)2)23算法思想：P 1n0語句：;a ;i) 因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點（設(shè)為i位置元素）開始向前尋找到第一個小于或等于x的元素位置i后，插入該位置后面即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個小于或等于x的元素位置i時，插入x的位置i+1也空出來了。算法如下：void InsertIncreaseList1(seqlist *L,datatype x)int i;if (L-elemnum=maxsize) printf(overflow); / L-elemnum 中存放當(dāng)前

2、順序表中的元素個數(shù)for (i=L-elemnum-1;i=0 & L-dataix;i-) L-datai+1=L-datai; /從后往前比較并移動元素L-datai+1=x;L-elemnum+;void InsertIncreaseList2(seqlist *L,datatype x)int i,j;if (L-elemnum=maxsize) printf(overflow);i=0;while(ielemnum-1)&(L-dataielemnum-1;j=i;j-) L-dataj+1=L-dataj; /騰位置L-datai=x; /插入L-elemnum+;同111 時+%

3、。t0i,( 001;1;()()010C C B BC B D A 220A1B2C3D4E5F9G12H（2）ABHG（3）ABHG3（1）01AB-10CGFEDIHJKMN0112224556710111224ABCGFEDIHJKMN678101112（3）ABN4ABFJECGDHI森林中既無孩子又無右兄弟的結(jié)點在二叉樹中是葉結(jié)點。5AEHG6. 用反證法證明。假設(shè)結(jié)點數(shù)大于1的哈夫曼樹存在節(jié)點A度為1，那么A的孩子lchild的權(quán)值和A相同.(敘述敘述)=此樹的WPL并非最小.那么此樹就不是哈夫曼樹.=假設(shè)錯誤.=結(jié)點數(shù)大于1的哈夫曼樹不存在度為1的結(jié)點7.n=n+1,n=n+n

4、+n= n+0+ n-1=2n-102012000nn0 012m201m3012m012m1GFBCHKJEDAIHBGIKLCEFJABCFDEGHIJ10a1010ceb1d哈夫曼編碼樹0 B C BD B B 每個頂點入度和出度：ID(v1)=2ID(v2)=2ID(v3)=1ID(v4)=3ID(v5)=2ID(v6)=1鄰接矩陣：OD(v1)=1OD(v2)=2OD(v3)=3OD(v4)=0OD(v5)=3OD(v6)=2000100100000100010010010101100100100鄰接表：1234565124 25 01100001100000010000010001

5、10110001001001001000110356 56 int PATHDFS(ALGraph *G，int i,int j)/以鄰接表為存儲結(jié)構(gòu)，判斷vi和vj之間是否有路徑，若有返回1，否則返回0EdgeNode visitedi=TRUE； /標(biāo)記vi已訪問p=G-adjlisti.firstedge； vi邊表的頭指針while(p)/依次搜索vi的鄰接點k=p-adjvexif（!visitedp-adjvex)/若vk尚未被訪問if (p-adjvex=j)return 1;else ruturn PATHDFS(g，p-adjvex,j);/則以Vk為出發(fā)點向縱深搜索p=p-

6、next； /找vi的下一鄰接點return 0;/PATHDFSint BFS(ALGraph *G，int i,int j)/以鄰接表為存儲結(jié)構(gòu)，判斷vi和vj之間是否有路徑，若有返回1，否則返回0int CirQueue /須將隊列定義中DataType改為intEdgeNode InitQueue(&Q)；/隊列初始化visitedi=TRUE；EnQueue(&Q，i)；/viwhile(!QueueEmpty(&Q)/隊非空則執(zhí)行i=DeQueue(&Q)； /相當(dāng)于vi出隊p=G-adjlisti.firstedge； vi的邊表頭指針while(p)/依次搜索vi的鄰接點vk(

7、令p-adjvex=k)if(!visitedp-adjvex) /若vk未訪問過if (p-adjvex=j)return 1;elsevisitedP-adjvex=TRUE；EnQueue(&Q，p-adjvex)；/訪問過的vk人隊p=p-next；/找vi的下一鄰接點/endwhile/endwhilereturn 0;/end of pathBFSvoid ShortestPath(ALGraph *G,int P ,int D ) int finalMaxVerNum,i,j,k,min;EdgeNode *s;final0=1; /* 初始時集合S中只有0號頂點 */D0=0;

8、P0=-1; /* 0號頂點 無前驅(qū)頂點 ，用-1表示 */for(i=1;in;i+) finali=0;Di= INFINITY ;Pi=0; /* Pi存放i號頂點的前驅(qū)頂點 */s=G-adjlist0.firstedge;while (s!=NULL) Ds-adjvex=s-weight; s=s-next; for(i=1;in; i+) /*重復(fù)G-n-1次*/ min=INFINITY;for(k=0;kn;k+)if(finalk=0&Dkadjlistj.firstedge;while (s!=NULL)if(finals-adjvex=0)& (Dj+ s-weightadjvex) Ds-adjvex= Dj+ s-weight; Ps-adjvex=j; s=s-next;B BCCCDCDDDC D B 2 答：等概率情況下，查找成功的平均查找長度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失敗時，最多的關(guān)鍵字比較次樹不超過判定樹的深度，此處為 Apr Aug Dec FebJune July Se