数据结构C语言描述耿国华习题及答案 - 图文(2)

else

{if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); } } 22、

int Width(BiTree bt)

{if (bt==NULL) return (0); else

{BiTree p,Q[50];

int front=1,rear=1,last=1; int temp=0, maxw=0; Q[rear]=bt; while(front<=last)

{p=Q[front++]; temp++;

if (p->lchild!=NULL) Q[++rear]=p->lchild; if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear;

if(temp>maxw) maxw=temp; temp=0;} }

return (maxw); } }

第七章 习题答案 1、（1）顶点1的入度为3，出度为0； 顶点2的入度为2，出度为2； 顶点3的入度为1，出度为2； 顶点4的入度为1，出度为3； 顶点5的入度为2，出度为1； 顶点6的入度为2，出度为3； （2）邻接矩阵如下： 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 （3）邻接表

（4）逆邻接表

2、答案不唯一

（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6 边的序列为：（1，2）（2，3）（3，4）（4，5）（5，6） （3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4 边的序列为：（1，5）（1，6）（1，3）（1，2）（5，4） 3、（1）每个事件的最早发生时间：ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16, ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23 每个事件的最晚发生时间:： vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15, vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0 （2）每个活动的最早开始时间：e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,

e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21

每个活动的最迟开始时间：

l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21 （3）关键路径如下图所示：

4、顶点1到其余顶点的最短路经为： 1-〉3最短路经为1，3；长度为15 1-〉2最短路经为1，3，2；长度为19 1-〉5最短路经为1，3，5；长度为25 1-〉4最短路经为1，3，2，4；长度为29 1-〉6最短路经为1，3，2，4，6；长度为44 13、A(7)B(3)C(2)D(11)E(8) 第八章 查找

1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

解：ASL=(1+2*2+4*3+3*4)/10=2.9 5、解：（1）插入完成后的二叉排序树如下： ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 (2)ASL=(1+282+3*4+4*5)=37/12 12、解：哈希表构造如下：

56 10 1 2 3 4 7 8 9 0 1 2 4305436 2 1 0 1 3 6 7 H(22)=(22*3)=0 H(41)=(41*3)=2 H(53)=(53*3)=5 H(46)=(46*3)=6

H(30)=(30*3)=2 与(41)冲突 H1(30)=(2+1)=3

H(13)=(13*3)=6 与46冲突 H1(13)=(6+1)=7

H(01)=(01*3)=3 与30冲突 H1(01)=(3+1)=4

H(67)=(67*3)=3 与30冲突 H1(67)=(3+1)=4 与01冲突 H2(67)=(3+2)=5 与53冲突 H3(67)=(3+3)=6 与46冲突

H4(67)=(3+4)=7 与13冲突 H5(67)=(3+5)=8

ASLsucc=(1*4+2*3+6)/8=2

ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8 第九章 排序

1、以关键字序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟派结束时的关键字状态。 （1）直接插入排序（2）希尔排序（增量序列为5，3，1） （3）快速排序 （4）堆排序（5）归并排序 解：

（2）增量为5的排序结果：170，087，275，061，426，503，897，512，653，908 增量为3的排序结果：061，087，275，170，426，503，897，512，653，908 增量为1的排序结果：061，087，170，275，426，503，512，653，897，908 （3）一次划分后：{426 087 275 061 170}503{897 908 653 512} 分别进行：{170 087 275 061}426 503 {512 653} 897 {908} {061 087}170{275}426 503 512 {653} 897 908 061 087 170 275 426 503 512 653 897 908 7、已知一组关键字：（40，27，28，12，15，50，7），要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。 解：初始状态：40 27 28 12 15 50 7 一次划分：{7 27 28 12 15} 40 {50} 依次划分：7 {27 28 12 15} 40 50 7 {15 12} 27 {28} 40 50 7 12 15 27 28 40 50 16、（1）A3 B1 C4 D2 E7 (2)C (3)C 17、对，错，对