数据结构课后习题部分参考答案

1、数据结构课后习题部分参考答案 ? )n)2)23算法思想：P 1n0语句：;a ;i) 因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后，插入该位置后面即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。算法如下：void InsertIncreaseList1(seqlist *L,datatype x)int i;if (L-elemnum=maxsize) printf(overflow); / L-elemnum 中存放当前

2、顺序表中的元素个数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森林中既无孩子又无右兄弟的结点在二叉树中是叶结点。5AEHG6. 用反证法证明。假设结点数大于1的哈夫曼树存在节点A度为1，那么A的孩子lchild的权值和A相同.(叙述叙述)=此树的WPL并非最小.那么此树就不是哈夫曼树.=假设错误.=结点数大于1的哈夫曼树不存在度为1的结点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)/以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0EdgeNode visitedi=TRUE； /标记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为出发点向纵深搜索p=p-

6、next； /找vi的下一邻接点return 0;/PATHDFSint BFS(ALGraph *G，int i,int j)/以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0int CirQueue /须将队列定义中DataType改为intEdgeNode InitQueue(&Q)；/队列初始化visitedi=TRUE；EnQueue(&Q，i)；/viwhile(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)； /相当于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号顶点 无前驱顶点 ，用-1表示 */for(i=1;in;i+) finali=0;Di= INFINITY ;Pi=0; /* Pi存放i号顶点的前驱顶点 */s=G-adjlist0.firstedge;while (s!=NULL) Ds-adjvex=s-weight; s=s-next; for(i=1;in; i+) /*重复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查找失败时，最多的关键字比较次树不超过判定树的深度，此处为 Apr Aug Dec FebJune July Se