第一章 习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽
（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型
（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作
（9）有限性、输入、可行性 4、（1）A（2）C（3）C
5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定
（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A
B：H、L、I、E、A C：F、M
D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C
3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下：
int Linser(SeqList *L,int X) { int i=0,k;
if(L->last>=MAXSIZE-1)
{ printf(“表已满无法插入”)； return(0); }
while(i<=L->last&&L->elem[i] for(k=L->last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink { p=L; while(p->next-data<=mink) p=p->next; while(q->data return OK; } } 9、算法如下： int Dele(Node *S) { Node *p; P=s->next; If(p= =s) {printf(“只有一个结点，不删除”)； return 0; } else {if((p->next= =s) {s->next=s; free(p); return 1; } Else { while(p->next->next!=s) P=p->next; P->next=s; Free(p); return 1; } } } 第三章 习题答案 2、（1） 3、栈有顺序栈和链栈两种存储结构。 在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。 在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。 5、 #include char ch,temp; SeqStack s; InitStack(&s); scanf(\ while(ch!='@'&&ch!='&') { Push(&s,ch); scanf(\ } while(ch!='@'&&!IsEmpty(&s)) { Pop(&s,&temp); scanf(\ if(ch!=temp) break; } if(!IsEmpty(&s)) printf(\ else { scanf(\ if(ch=='@') printf(\ else printf(\ } } 12、（1）功能：将栈中元素倒置。 （2）功能：删除栈中的e元素。 （3）功能：将队列中的元素倒置。 第四章习题答案 1、StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=’I AM A ’； SubString(sub2,s,7,1)操作结果为sub2=’ ’；StrIndex(s,’A’,4) 操作结果为5； StrReplace(s,’STUDENT’,q) 操作结果为’I AM A WORKER’； StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为’I AM A GOOD WORKER’； 2、 int StrReplace(SString S,Sstring T,SString V) { int i=1; //从串S的第一个字符起查找串T if(StrEmpty(T)) //T是空串 return ERROR; do { i=Index(S,T,i); //结果i为从上一个i之后找到的子串T的位置 if(i) //串S中存在串T { StrDelete(S,i,StrLength(T)); //删除该串T StrInsert(S,i,V); //在原串T的位置插入串V i+=StrLength(V); //在插入的串V后面继续查找串T } }while(i); return OK; } 第五章习题答案 1、（1）数组A共占用48*6=288个字节； （2）数组A的最后一个元素的地址为1282； （3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126 （4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=1192 9、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d） 10、D 第六章 习题答案 1、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5个。 2、略 3、证明：分支数=n1+2n2+…+knk （1） n= n0+n1+…+nk （2） n=分支数+1 （3） ∵ 将（1）（2）代入（3）得 n0= n2+2n3+3n4+…+（k-1）nk+1 4、 注：C结点作为D的右孩子（画图的时候忘记了，不好意思） 5、n0=50，n2=n0-1=49，所以至少有99个结点。 6、（1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树 7、证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。 ∴空域=nk-（n-1）=nk-n+1 8、对应的树如下： 9、（答案不唯一） 哈夫曼树如下图所示： 哈夫曼编码如下： 频率 编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011 11、对应的二叉树如下： 12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。 typedef int ElemType; void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j) if(i>j) i=i/2; else j=j/2; printf(\所查结点的最近公共祖先的下标是%d,值是%d\} 15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。 void Del_Sub(BiTree T) { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); } void Del_Sub_x(BiTree T,int x) { if(T->data==x) Del_Sub(T); 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) 14、略 15、略 第八章 查找 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 (3) 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）归并排序 解：（1）略 （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 （4）略 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、对，错，对