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

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

2、順序表中的元素個(gè)數(shù)for (i=L-elemnum-1;i=0 & L-dataix;i-) L-datai+1=L-datai; /從后往前比較并移動(dòng)元素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 時(shí)+%

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

4、+n= n+0+ n-1=2n-102012000nn0 012m201m3012m012m1GFBCHKJEDAIHBGIKLCEFJABCFDEGHIJ10a1010ceb1d哈夫曼編碼樹(shù)0 B C BD B B 每個(gè)頂點(diǎn)入度和出度：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)/以鄰接表為存儲(chǔ)結(jié)構(gòu)，判斷vi和vj之間是否有路徑，若有返回1，否則返回0EdgeNode visitedi=TRUE； /標(biāo)記vi已訪問(wèn)p=G-adjlisti.firstedge； vi邊表的頭指針while(p)/依次搜索vi的鄰接點(diǎn)k=p-adjvexif（!visitedp-adjvex)/若vk尚未被訪問(wèn)if (p-adjvex=j)return 1;else ruturn PATHDFS(g，p-adjvex,j);/則以Vk為出發(fā)點(diǎn)向縱深搜索p=p-

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

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

8、P0=-1; /* 0號(hào)頂點(diǎn) 無(wú)前驅(qū)頂點(diǎn) ，用-1表示 */for(i=1;in;i+) finali=0;Di= INFINITY ;Pi=0; /* Pi存放i號(hào)頂點(diǎn)的前驅(qū)頂點(diǎn) */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 答：等概率情況下，查找成功的平均查找長(zhǎng)度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失敗時(shí)，最多的關(guān)鍵字比較次樹(shù)不超過(guò)判定樹(shù)的深度，此處為 Apr Aug Dec FebJune July Se