《数据结构——C语言描述》习题及答案 耿国华.doc 89页

'第1章绪论习　题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。3.算法的定义与特性。4.算法的时间复杂度。5.数据类型的概念。6.线性结构与非线性结构的差别。7.面向对象程序设计语言的特点。8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。10.抽象数据类型的概念。二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2.算法就是程序。3.在高级语言（如C、或PASCAL）中，指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：　i=1时：1=(1+1)×1/2=(1+12)/2　i=2时：1+2=(1+2)×2/2=(2+22)/2　i=3时：1+2+3=(1+3)×3/2=(3+32)/2…　i=n时：1+2+3+……+n=(1+n)×n/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(12+22+32+……+n2)]/2=[(1+n)n/2+n(n+1)(2n+1)/6]/2 =n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n))=O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]：floatPolyValue(floata[],floatx,intn){……}核心语句：p=1;(x的零次幂)s=0;i从0到n循环s=s+a[i]*p;p=p*x;或：p=x;(x的一次幂)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法，求pn(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(){inti,n;floatx,a[],p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;inext=S;（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;（6）S->next=NULL;（7）Q=P;（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;2.4已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。[提示]：voidinsert(SeqList*L;ElemTypex)<方法1>（1）找出应插入位置i，（2）移位，（3）……<方法2>参P.2292.5写一算法，从顺序表中删除自第i个元素开始的k个元素。[提示]：注意检查i和k的合法性。（集体搬迁，“新房”、“旧房”）<方法1>以待移动元素下标m（“旧房号”）为中心，计算应移入位置（“新房号”）：for(m=i－1+k;m<=L－>last;m++)L－>elem[m－k]=L－>elem[m];<方法2>同时以待移动元素下标m和应移入位置j为中心：<方法3>以应移入位置j为中心，计算待移动元素下标： 2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。[提示]：注意检查mink和maxk的合法性：minknext;while(p!=NULL&&p－>data<=mink){pre=p;p=p－>next;}（2）找到最后一个应删结点的后继s，边找边释放应删结点s=p;while(s!=NULL&&s－>datanext;free(t);}（3）pre－>next=s;2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（2）以单链表作存储结构。[方法1]：在原头结点后重新头插一遍[方法2]：可设三个同步移动的指针p,q,r，将q的后继r改为p2.8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C.[提示]：参P.28例2-1<方法1>voidmerge(LinkListA;LinkListB;LinkList*C){……pa=A－>next;pb=B－>next;*C=A;(*C)－>next=NULL;while(pa!=NULL&&pb!=NULL){if(pa－>data<=pb－>data) {smaller=pa;pa=pa－>next;　smaller－>next=(*C)－>next;/*头插法*/　(*C)－>next=smaller;}else{smaller=pb;pb=pb－>next;　smaller－>next=(*C)－>next;(*C)－>next=smaller;}}while(pa!=NULL){smaller=pa;pa=pa－>next;smaller－>next=(*C)－>next;(*C)－>next=smaller;}while(pb!=NULL){smaller=pb;pb=pb－>next;smaller－>next=(*C)－>next;(*C)－>next=smaller;}<方法2>LinkListmerge(LinkListA;LinkListB){……LinkListC；pa=A－>next;pb=B－>next;C=A;C－>next=NULL;…………returnC; 2.9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。[提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？2.10已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.11设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时；或者C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。[提示]：voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB)2.12将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。[提示]：注明用头指针还是尾指针。2.13建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。[提示]：可将低位放在前面。2.14设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。[提示]：floatPolyValue(Polylistp;floatx){……}实习题1．将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。2．约瑟夫环问题。约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m, 从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。第二章答案 实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如，m的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4，出列顺序为6,1,4,7,2,3,5。【解答】算法如下： typedefstructNode{intpassword;intnum;structNode*next;} Node,*Linklist; voidJosephus(){ LinklistL; Node*p,*r,*q; intm,n,C,j; L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/ if(L==NULL){printf("n链表申请不到空间!");return;} L->next=NULL;  r=L;      printf("请输入数据n的值(n>0):"); scanf("%d",&n); for(j=1;j<=n;j++)                             /*建立链表*/  {       p=(Node*)malloc(sizeof(Node));     　if(p!=NULL)       {              printf("请输入第%d个人的密码:",j);         　　scanf("%d",&C);         p->password=C;         p->num=j;         r->next=p;        r=p;    }  } r->next=L->next;printf("请输入第一个报数上限值m(m>0):"); scanf("%d",&m); printf("*****************************************n"); printf("出列的顺序为:n"); q=L; p=L->next; while(n!=1)                       /*计算出列的顺序*/ {      j=1;      while(jnext;            j++;      }      printf("%d->",p->num);      m=p->password;                /*获得新密码*/       n--;                      q->next=p->next;   /*p出列*/      r=p;      p=p->next;      free(r);   }  printf("%dn",p->num);} 2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,…,an）逆置为(an,an-1,…,a1)。【解答】（1）用一维数组作为存储结构    void invert(SeqList *L, int *num){  int j; ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表作为存储结构  void invert(LinkList L) {Node *p,*q,*r;   if(L->next==NULL) return;         /*链表为空*/   p=L->next;      q=p->next;              p->next=NULL;             /*摘下第一个结点，生成初始逆置表*/while(q!=NULL)            /*从第二个结点起依次头插入当前逆置表*/  {r=q->next; q->next=L->next;L->next=q;q=r; }} 2.11将线性表A=(a1,a2,……am),B=(b1,b2,……bn)合并成线性表C,C=(a1,b1,……am,bm,bm+1,…….bn) 当m<=n时，或C=(a1,b1,……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkList merge(LinkList A, LinkListB, LinkList C){Node *pa,*qa,*pb,*qb,*p; pa=A->next;                   /*pa表示A的当前结点*/ pb=B->next; p=A; /*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/  while(pa!=NULL && pb!=NULL)  /*利用尾插法建立连接之后的链表*/{  qa=pa->next;qb=qb->next; p->next=pa;  /*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;                      pa=qa;pb=qb;}if(pa!=NULL)  p->next=pa;     /*A的长度大于B的长度*/if(pb!=NULL)  p->next=pb;     /*B的长度大于A的长度*/C=A;   return(C);}  第3章限定性线性表—栈和队列习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？123、213、132、231、321（312）⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C[提示]：A、B、C、D、E（输出队首元素A）A、B、C、D、E、A（把队首元素A插入到队尾）B、C、D、E、A（删除队首元素A）C、D、E、A（再次删除队首元素B）C、D、E、A（输出队首元素C）C、D、E、A、C（把队首元素C插入到队尾）D、E、A、C（删除队首元素C）E、A、C（再次删除队首元素D）3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 1.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1　&　序列2’模式的字符序列。其中序列1和序列2　中都不含字符’&’，且序列2　是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。[提示]：（1）边读边入栈，直到&（2）边读边出栈边比较，直到……2.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。[提示]：例：中缀表达式：a+b后缀表达式:ab+中缀表达式：a+b×c后缀表达式:abc×+中缀表达式：a+b×c-d后缀表达式:abc×+d-中缀表达式：a+b×c-d/e后缀表达式:abc×+de/-中缀表达式：a+b×(c-d)-e/f后缀表达式:abcd-×+ef/-·后缀表达式的计算过程：（简便）顺序扫描表达式，（1）如果是操作数，直接入栈；（2）如果是操作符op，则连续退栈两次，得操作数X,Y，计算XopY，并将结果入栈。·如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式，（1）如果是操作数，直接输出；（2）如果是操作符op2，则与栈顶操作符op1比较：如果op2>op1，则op2入栈；如果op2=op1，则脱括号；如果op2top==-1表示栈空。判断栈S满：如果S->top==Stack_Size-1表示栈满。（2）链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果top->next==NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3.4照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E↑F【解答】3.5写一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如‘序列1&序列2’的字符序列。序列1和序列2中都不含‘&’，且序列2是序列1的逆序列。例如，’a+b&b+a’是属于该模式的字符序列，而’1+3&3-1’则不是。【解答】算法如下：intIsHuiWen(){Stack*S; Charch,temp;InitStack(&S);Printf(“n请输入字符序列：”);Ch=getchar();While(ch!=&)/*序列1入栈*/{Push(&S,ch);ch=getchar();}do/*判断序列2是否是序列1的逆序列*/{ch=getchar();Pop(&S,&temp);if(ch!=temp)/*序列2不是序列1的逆序列*/{return(FALSE);printf(“nNO”);}}while(ch!=@&&!IsEmpty(&S))if(ch==@&&IsEmpty(&S)){return(TRUE);printf(“nYES”);}/*序列2是序列1的逆序列*/else{return(FALSE);printf(“nNO”);}}/*IsHuiWen()*/3.8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：intEnterQueue(SeqQueue*Q,QueueElementTypex){/*将元素x入队*/if(Q->front==Q->front&&tag==1)/*队满*/return(FALSE);if(Q->front==Q->front&&tag==0)/*x入队前队空，x入队后重新设置标志*/tag=1;Q->elememt[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE;/*设置队尾指针*/Return(TRUE);}出队算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x){/*删除队头元素，用x返回其值*/if(Q->front==Q->rear&&tag==0)/*队空*/return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE;/*重新设置队头指针*/if(Q->front==Q->rear)tag=0;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE);}编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：voidhanoi(intn,charx,chary,charz){/*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座*/if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A->C)1号搬到CMove(A->B)2号搬到BHanoi(1,C,A,B)move(C->B)1号搬到B Move(A->C)3号搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B->A)1号搬到AMove(B->C)2号搬到CHanoi(1,A,B,C)move(A->C)1号搬到C第4章　串习　题1.设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t),StrCat(sub2,q));[参考答案]StrLength(s)=14;sub1=’IAMA_’;sub2=’_’;StrIndex(s,’A’,4)=6;StrReplace(s,’STUDENT’,q)=’IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))=’IAMAGOODWORKER’;2.编写算法，实现串的基本操作StrReplace(S,T,V)。3.假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)。[说明]：用单链表实现。4.叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5.已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T.6.S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。7.S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。以下算法用定长顺序串： 8.写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。（2）将顺序串r中所有字符按照相反的次序仍存放在r中。（3）从顺序串r中删除其值等于ch的所有字符。（4）从顺序串r1中第index个字符起求出首次与串r2相同的子串的起始位置。（5）从顺序串r中删除所有与串r1相同的子串。9.写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。[提示]：（1）用静态顺序串（2）先移位，后复制10.写算法，实现顺序串的基本操作StrCompare(s,t)。11.写算法，实现顺序串的基本操作StrReplace(&s,t,v)。[提示]：（1）被替换子串定位（相当于第9题中i）（2）被替换子串后面的字符左移或右移（为替换子串准备房间）（3）替换子串入住（复制）（4）重复上述，直到……第四章　答案4.1设s=’IAMASTUDENT’，t=’GOOD’，q=’WORKER’。给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7)sub1=’IAMA’;SubString(sub2,s,7,1)sub2=’’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q);s=’IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’IAMAGOODWORKER’。4.2编写算法，实现串的基本操作StrReplace(S,T,V)。【解答】算法如下：intstrReplace(SStringS,SStringT,SStringV){/*用串V替换S中的所有子串T*/intpos,i;pos=strIndex(S,1,T);/*求S中子串T第一次出现的位置*/if(pos==0)return(0);while(pos!=0)/*用串V替换S中的所有子串T*/ {switch(T.len-V.len){case0:/*串T的长度等于串V的长度*/for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];case>0:/*串T的长度大于串V的长度*/for(i=pos+t.ien;ilen;i--)/*将S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i];前移T.len-V.len个位置*/for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case<0:/*串T的长度小于串V的长度*/if(S->len-T.len+V.len)<=MAXLEN/*插入后串长小于MAXLEN*/{/*将S中子串T后的所有字符后移V.len-T.len个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;}else{/*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN){for(i=MAXLEN-1;i>=pos+T.len;i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else/*串V的部分字符要舍弃*/{for(i=0;ich[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T);/*求S中下一个子串T的位置*/ }/*while()*/return(1);}/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedefstructNode{chardata;structNode*next;}Node,*Lstring;intstrIndex(LstringS,intpos,LstringT)/*从串S的pos序号起，串T第一次出现的位置*/{Node*p,*q,*Ppos;inti=0，,j=0;if(T->next==NULL||S->next==NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&jnext;j++;}if(j!=pos)return(0);while(p!=NULL&&q!=NULL){Ppos=p;/*Ppos指向当前匹配的起始字符*/if(p->data==q->data){p=p->next;q=q->next;}else/*从Ppos指向字符的下一个字符起从新匹配*/{p=Ppos->next;q=T->head->next;i++;}}if(q==NULL)return(pos+i);/*匹配成功*/elsereturn(0);/*失败*/} 第五章数组和广义表习题1.假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：（1）数组A共占用多少字节；（288）（2）数组A的最后一个元素的地址；（1282）（3）按行存储时，元素A36的地址；（1126）（4）按列存储时，元素A36的地址；（1192）[注意]：本章自定义数组的下标从1开始。2．设有三对角矩阵（aij）n×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。i=k/3+1,j=k%3+i-1=k%3+k/3或：i=k/3+1,j=k-2×(k/3)3.假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。[提示]：参考P.28例、P.47例。4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。[提示]：（1）position[k]中为第k列非零元素个数，k=1,2,…,n（2）position[0]=1;（第1列中第一个非零元素的正确位置）（3）position[k]=position[k–1]+position[k],k=1,2,…,n（4）position[k]=position[k–1],k=n,n–1,…,15．写一个在十字链表中删除非零元素aij的算法。[提示]：“删除”两次，释放一次。 6．画出下面广义表的两种存储结构图示：((((a),b)),(((),d),(e,f)))第一种存储结构（自底向上看）11∧11∧1∧0f0e0a1∧11∧1∧1∧11∧0b0d7．求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)参考题8．试设计一个算法，将数组A（0:n-1）中的元素循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。9．假设按低下标优先（以最左的下标为主序）存储整数数组A（1:8,1:2,1:4,1:7）时，第一个元素的字节地址是100，每个整数占4个字节，问元素A(4,2,3,5)的存储地址是什么？10.高下标优先（以最右的下标为主序）存储整数数组A（1:8,1:2,1:4,1:7）时，顺序列出数组A的所有元素。11．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 实习题1．若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。第五章答案5.2三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j(2)i=[k/3]+1,j=[k/3]+k%3（[]取整，%取余）5.4稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/intcol,t,p,q;intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){position[1]=1;for(t=1;t<=A.len;t++)position[A.data[t].col+1]++;/*position[col]存放第col-1列非零元素的个数,即利用pos[col]来记录第col-1列中非零元素的个数*//*求col列中第一个非零元素在B.data[]的位置，存放在position[col]中*/for(col=2;col<=A.n;col++)position[col]=position[col]+position[col-1];for(p=1;pdata[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}}算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){intcol,t,p,q;intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){for(col=1;col<=A.n;col++)position[col]=0;for(t=1;t<=A.len;t++)position[A.data[t].col]++;/*计算每一列的非零元素的个数*///从最后一列起求每一列中第一个非零元素在B.data[]中的位置，//放在position[col]中*/for(col=A.n,t=A.len;col>0;col--){t=t-position[col];position[col]=t+1;}for(p=1;pdata[q].row=A.data[p].col;B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e;Position[col]++;}}}5.6画出下面广义表的两种存储结构图示：((((a),b)),(((),d),(e,f)))【解答】5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];(a,b)（2）TAIL[((a,b),(c,d))];((c,d))（3）TAIL[HEAD[((a,b),(c,d))]];(b)（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)第六章树和二叉树习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？[提示]：参考P.116性质3∵　n=n0+n1+……+nkB=n1+2n2+3n3+……+knkn=B+1∴n0+n1+……+nk=n1+2n2+3n3+……+knk+1∴n0=n2+2n3+……+(k-1)nk+14.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 [提示]：参考P.1485.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？[提示]：[方法1]（1）一个叶子结点，总结点数至多有多少个？结论：可压缩一度结点。（2）满二叉树或完全二叉树具有最少的一度结点（3）可能的最大满二叉树是几层？有多少叶结点？如何增补？25<50<26可能的最大满二叉树是6层有25=32个叶结点假设将其中x个变为2度结点后，总叶结点数目为50则：2x+(32–x)=50得：x=18此时总结点数目=(26–1)+18×2[方法2]假设完全二叉树的最大非叶结点编号为m，则最大叶结点编号为2m+1,(2m+1)-m=50m=49总结点数目=2m+1=99[方法3]由性质3：n0=n2+1即：50=n2+1所以：n2=49令n1=0得：n=n0+n2=996.给出满足下列条件的所有二叉树：（1）前序和中序相同（2）中序和后序相同（3）前序和后序相同[提示]：去异存同。（1）DLR与LDR的相同点：DR，如果无L，则完全相同,如果无LR，…。 （2）LDR与LRD的相同点：LD，如果无R，则完全相同。（3）DLR与LRD的相同点：D，如果无LR，则完全相同。（如果去D，则为空树）7.n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？[提示]：参考P.1198．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。[提示]：（1）先画出对应的二叉树（2）树的后根序列与对应二叉树的中序序列相同9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10（1）请为这8个字母设计哈夫曼编码，（2）求平均编码长度。10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因.[提示]：无右子的“左下端”11.画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。13．编写递归算法：对于二叉树中每一个元素值为x 的结点，删去以它为根的子树，并释放相应的空间。[提示]：[方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放；voidDelSubTree(BiTree*bt,DataTypex){if(*bt!=NULL&&(*bt)->data==x){FreeTree(*bt);*bt=NULL;}elseDelTree(*bt,x)voidDelTree(BiTreebt,DataTypex){if(bt){if(bt->LChild&&bt->LChild->data==x){FreeTree(bt->LChild);bt->LChild=NULL;}if(bt->RChild&&bt->RChild->data==x){FreeTree(bt->RChild);bt->RChild=NULL;}DelTree(bt->LChild,x);DelTree(bt->RChild,x);}}[方法2]：（1）先序查找；（2）直接查看当前根结点（3）用指针参数；[方法3]：（1）先序查找；（2）直接查看当前根结点（3）通过函数值，返回删除后结果；（参示例程序）14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 [提示]：（1）先查看线索，无线索时用下面规律：（2）结点*p在先序序列中的后继为其左子或右子；（3）结点*p在后序序列中的前驱也是其左子或右子。15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题）16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。[提示]：（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。（2）可利用返回值，或全局变量。17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。（参课本）19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。[提示]：可利用任何递归、非递归遍历算法。20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。22.证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23.二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。 实习题1.[问题描述]建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。[基本要求]从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。[测试数据]ABCффDEфGффFффф（其中ф表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。[提示]：（1）参习题6.20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。CFEADBFABCDE图6.344．按凹入表形式打印树形结构，如图6.35所示。[提示]：参P.129例，用先根遍历。 ABDCGFEABEFCGDABCDEFG图6.35第六章答案6.1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3个结点的树具有3个结点的二叉树6.3已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则n=n0+n1+……+nk树中分支数目为B,则B=n1+2n2+3n3+……+knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1即n0+n1+……+nk=n1+2n2+3n3+……+knk+1由上式可得叶子结点数为：n0=n2+2n3+……+(k-1)nk+16.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0=n2+1所以n2=n0–1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=996.6试分别找出满足以下条件的所有二叉树:(1)前序序列与中序序列相同;(2)中序序列与后序序列相同;(3)前序序列与后序序列相同。【解答】 (1)前序与中序相同：空树或缺左子树的单支树；(2)中序与后序相同：空树或缺右子树的单支树；(3)前序与后序相同：空树或只有根结点的二叉树。6.9假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：哈夫曼编码为：I1：11111I5：1100I2：11110I6：10I3：1110I7：01I4：1101I8：006.11画出如下图所示树对应的二叉树。【解答】6.15分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。【解答】（1）找结点的中序前驱结点BiTNode*InPre(BiTNode*p)/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用线索*/else{/*在p的左子树中查找“最右下端”结点*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}return(pre);} （2）找结点的中序后继结点BiTNode*InSucc(BiTNode*p)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/{if(p->Rtag==1)succ=p->RChild;/*直接利用线索*/else{/*在p的右子树中查找“最左下端”结点*/for(q=p->RChild;q->Ltag==0;q=q->LChild);succ=q;}return(succ);}(3)找结点的先序后继结点BiTNode*PreSucc(BiTNode*p)/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/{if(p->Ltag==0)succ=p->LChild;elsesucc=p->RChild;return(succ);}(4)找结点的后序前驱结点BiTNode*SuccPre(BiTNode*p)/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/{if(p->Ltag==1)pre=p->LChild;elsepre=p->RChild;return(pre);}6.21已知二叉树按照二叉链表方式存储，试利用栈的基本操作写出先序遍历非递归形式的算法。【解答】VoidPreOrder(BiTreeroot)/*先序遍历二叉树的非递归算法*/{InitStack(&S);p=root;while(p!=NULL||!IsEmpty(S)) {if(p!=NULL){Visit(p->data);push(&S,p);p=p->Lchild;}else{Pop(&S,&p);p=p->RChild;}}}6.24已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。【解答】算法(一)Voidexchange(BiTreeroot){p=root;if(p->LChild!=NULL||p->RChild!=NULL){temp=p->LChild;p->LChild=p->RChild;p->RChild=temp;exchange(p->LChild);exchange(p->RChild);}}算法(二)Voidexchange(BiTreeroot){p=root; if(p->LChild!=NULL||p->RChild!=NULL){exchange(p->LChild);exchange(p->RChild);temp=p->LChild;p->LChild=p->RChild;p->RChild=temp;}}第七章　图习　题7.1已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）十字链表；（6）强连通分量。142536题2图156243题1图 7.1已知如图所示的无向图，请给出该图的：（1）邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）（2）从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树）（3）从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树）021435768944354336614522图7.31题7.3用图7.27.3已知如图7.31所示的AOE-网，试求：（1）每个事件的最早发生时间和最晚发生时间；（2）每个活动的最早开始时间和最晚开始时间；（3）给出关键路径。654321101521043020152010图7.30题7.4用图7.47.57.6 7.17.2已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。7.5试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v);InsertArc(G,v,w);DeleteVertex(G,v)和DeleteArc(G,v,w)。7.6试对邻接表存储结构重做题6。7.7试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。7.8同上题要求。试基于图的广度优先搜索策略写一算法。7.9试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。7.10采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。[提示]：利用深度搜索，增设一个深度参数，深度超过k则停止对该结点的搜索。7.11下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（A），广度遍历图G所得结点序列为（B）；G的一个拓扑序列是（C）；从结点V1到结点V8的最短路径为（D）；从结点V1到结点V8的关键路径为（E）。其中A、B、C的选择有：①V1,V2,V3,V4,V5,V6,V7,V8②V1,V2,V4,V6,V5,V3,V7,V8③V1,V2,V4,V6,V3,V5,V7,V8④V1,V2,V4,V6,V7,V3,V5,V8⑤V1,V2,V3,V8,V4,V5,V6,V7⑥V1,V2,V3,V8,V4,V5,V7,V6⑦V1,V2,V3,V8,V5,V7,V4,V6D、E的选择有：①V1,V2,V4,V5,V3,V8②V1,V6,V5,V3,V8③V1,V6,V7,V8④V1,V2,V5,V7,V8 16v1v2v5v3v40123431550∧24346311∧78∧412∧238624∧41v6v7v8∧567612∧720∧题12图7.13二叉树的层次遍历。实习题1．分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。2．校园导游程序。用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。3．编程求解关键路径问题。补充题1．将图7.31所示的有向网改为无向网，并要求：（1）用普里姆算法从顶点9开始，手工构造最小生成树。（最小代价连通网）（2）用克鲁斯卡尔算法手工构造最小生成树。（注：可将结点看成电脑，将权值看成电缆代价；也可将结点看成城市，将权值看成电缆代价；还可将结点看成城市，将权值看成修路代价；） 021435768944354336614522图7.31题7.3用图2．将图7.31所示的AOE-网改为AOV-网（去掉权值即可），并给出一个拓扑序列。（要求优先输出编号小的顶点）。参考题1．已知有向图，试基于图的深度优先搜索策略写一算法，求顶点vi到顶点vj的一条简单路径（i≠j）。[提示]：有向图可用邻接表存储，并在表结点中增加一个prior域。第七章答案156243题1图7.1已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）十字链表；（6）强连通分量。　　　　　　 【解答】（1）顶点入度出度1302223124135216237.2已知如图所示的无向图，请给出该图的：（2）深度优先遍历该图所得顶点序列和边的序列；（3）广度优先遍历该图所得顶点序列和边的序列。【解答】（2）深度优先搜索顶点序列：1-2-3-4-5-6边的序列：（1，2）（2，3）（3，4）（4，5）（5，6）深度优先搜索树：（3）广度优先搜索顶点序列：1-2-3-6-5-4边的序列：（1，2）（1，3）（1，6）（1，5）（5，4）深度优先搜索树：注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。7.3【解答】源点终点最短路径路径长度121，3，21931，31541，3，2，42951，3，52961，3，2，4，6447.12【解答】（1）深度遍历：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4，（2）广度遍历：1，2，4，6，3，5，7，8（3）拓扑序列：1，2，4，6，5，3，7，8 （4）最短路径：1，2，5，7，8（5）关键路径：1，6，5，3，87.13【解答】按层遍历二叉树LayerOrder(BiTreeroot){LinkQueueQ;InitQueue(&Q);if(root==NULL)return;EnterQueue(&Q,root);while(!Empty(&Q)){DelQueue(&Q,&p);visite(p->data);if(p->LChild!=NULL)EnterQueue(&Q,p->LChild);if(p->RChild!=NULL)EnterQueue(&Q,p->RChild);}}第八章　查找习　题8.1若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？查找不成功，即表中没有关键字等于给定值K的记录。（1）查找成功，且表中只有一个关键字等于给定值K的记录。（2）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。[提示]：均用顺序查找法。8.2画出对长度为10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。[提示]：根据P.191ASL定义计算平均查找长度。8.2试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。8.3试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。8.4选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。[提示]：平均查找长度参考P.225。012345678910224130015346136711221126ASLsucc=(1×4+2×3+6)/8=2ASLunsucc=(2+1+8+7+6+5+4+3+2+1+1)/11=40/118.5试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）[提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数，（3）确定解决冲突的方法。8.6试编写利用折半查找确定记录所在块的分块查找算法。 8.8试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。[提示]：检验中序遍历序列是否递增有序？[方法1]：用非递归中序遍历算法，设双指针pre,p一旦pre->data>p->data则返回假[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法）一旦pre->data>p->data则返回假[方法3]：用递归（中序或后序）算法（1）空树是（2）单根树是（3）左递归真（4）右递归真（5）左子树的右端小于根（6）右子树的左端大于根8.9编写算法，求出指定结点在给定的二叉排序树中所在的层数。8.10编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。[提示]：（1）假设A<=B，（2）从根开始，左走或右走，直到A在左（或根），B在右（或根）。8.11编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。[提示]：（1）表中已经有x，（2）表中没有x参P.2318.12已知长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。[提示]：画出判定树或排序树，根据P.191ASL定义计算平均查找长度。 8.13含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？[提示]：叶子结点对应空指针。8.14写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。8.15在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(logn)的算法，确定树中第k个结点的位置。实习题一、哈希表设计。为30个人的姓名设计一个哈希表，假设姓名用汉语拼音表示。要求用除留余数法构造哈希函数，用线性探测再散列法处理冲突，平均查找长度的上限为2。二、简单的员工管理系统。每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统的功能包括：（1）查询：按特定条件查找员工。（2）修改：按编号对某个员工的某项信息进行修改。（3）插入：加入新员工的信息。（4）删除：按编号删除已离职的员工的信息。（5）排序：按特定条件对所有员工的信息进行排序。第八章　答案8.2【解答】5ASLsucc=（1+2X2+3X4+4X3）/10=2.98.5【解答】ASLSUCC=(1X4+2X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/118.12【解答】（1）ASLSUCC=(1+2X2+3X3+4X3+5X2+6)/12=3.5（2）　排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep 折半查找ASLSUCC=(1+2X2+3X4+4X5)/12=37/12第九章　内部排序习题9.1以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态：（1）直接插入排序；（2）希尔排序（增量d[1]=5）；（3）快速排序；（4）堆排序；（5）归并排序；（6）基数排序。9.2一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。9.3不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。n=7时在最好情况下需进行多少次比较？请说明理由。对n=7给出一个最好情况的初始排列实例。（保证每个基准记录都是中间记录）9.4假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<a[i+1],则将两者交换；第一趟对所有奇数i,第二趟对所有偶数i，…,依次类推直至整个序列有序为止。（1）这种排序方法的结束条件是什么？（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。（3）写出奇偶交换排序的算法。9.12设计一个用链表表示的直接选择排序算法。（与9.8重）9.13插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。（与9.5重复）9.14一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（与9.7类似）9.15为什么通常使用一维数组作为堆的存放形式？9.16已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1 ）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。9.17试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。9.18在供选择的答案中填入正确答案：（1）排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_。供选择答案①选择排序②快速排序③插入排序④冒泡排序⑤归并排序⑥二分排序⑦哈希排序⑧基数排序（2）一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79（3）下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。A、堆排序B、冒泡排序C、快速排序D、SHELL排序9.19判断正误：（）在一个大堆中，最小元素不一定在最后。（X）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。（X）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。 实习题一、随机生成30个数，试比较直接插入排序、简单选择排序、起泡排序、快速排序、堆排序和希尔排序的时空性能和稳定性。二、统计成绩。给出n个学生的考试成绩表，每条信息由姓名与分数组成。三、按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；四、按名次列出每个学生的姓名与分数。参考答案9.1（1）无序表：顺序查找不成功时，查找长度为n+1；成功时，平均查找长度为1/(n+1)*(1+2+…+(n+1))=(n+2)/2；两者不相同。（2）表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。（3）表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。 9.365283197410ASL=1/10（1+2*2+4*3+3*4）=2.9            9.11   202030502030505220305020305260502030526068683052207060509.14 删除50后 602030526870 删除68后6070203052 9.1922674130 5346 13 01012345678910 ASL=（4*1+2*2+3+6）/8=17/8  9.25intSearch-Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素，ST按关键字自大至小有序，//若找到，则函数值为该元素在表中的位置，否则为0ST.elem[ST.length+1].key=key;for(i=1;ST.elem[i].key>key;++i);if(ST.elem[i].key==key)&&(i<=ST.length)returnielsereturn0;}//Search-Seq 9.31TelemTypeMaxv(BitreeT){//返回二叉排序树T中所有结点的最大值for(p=T;p->rchild;p=p->rchild);returnp->data;}//Maxv TelemTypeMinv(BitreeT){//返回二叉排序树T中所有结点的最小值for(p=T;p->lchild;p=p->lchild);returnp->data;}//Minv StatusIsBST(BitreeT){//判别T是否为二叉排序树if(!T)returnOK;elseif((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)data)))&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))returnOKelsereturnERROR; }//IsBST 9.33StatusOutputGEx(BitreeT,TelemTypex){//从大到小输出给定二叉排序树T中所有值不小于x的数据元素if(T){if(OutputGEx(T->rchild,x))if(T->data>=x){print(T->data);if(OutputGEx(T->lchild,x))returnOK;}elsereturnOK;}elsereturnOK;}//OutputGEx 9.25intSearch_Sq(SSTableST,intkey){//在有序表上顺序查找的算法,监视哨设在高下标端  ST.elem[ST.length+1].key=key;  for(i=1;ST.elem[i].key>key;i++);  if(i>ST.length||ST.elem[i].keyhigh)return0;//查找不到时返回0  mid=(low+high)/2;  if(ST.elem[mid].key==key)returnmid;  elseif(ST.elem[mid].key>key)    returnSearch_Bin_Digui(ST,key,low,mid-1);   elsereturnSearch_Bin_Digui(ST,key,mid+1,high);  }}//Search_Bin_Digui9.27intLocate_Bin(SSTableST,intkey){//折半查找,返回小于或等于待查元素的最后一个结点号  int*r;  r=ST.elem;  if(key=r[ST.length].key)returnST.length;  low=1;high=ST.length;  while(low<=high)  {    mid=(low+high)/2;    if(key>=r[mid].key&&keyL.idx[L.blknum].maxkey)returnERROR;//超过最大元素  low=1;high=L.blknum;  found=0;  while(low<=high&&!found)//折半查找记录所在块号mid  {    mid=(low+high)/2;    if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)      found=1;    elseif(key>L.idx[mid].maxkey)      low=mid+1;    elsehigh=mid-1;  }  i=L.idx[mid].firstloc;//块的下界  j=i+blksize-1;//块的上界  temp=L.elem[i-1];//保存相邻元素  L.elem[i-1]=key;//设置监视哨  for(k=j;L.elem[k]!=key;k--);//顺序查找  L.elem[i-1]=temp;//恢复元素  if(kdata==key)returnL.t;  elseif(L.t->data>key)    for(p=L.h,i=1;p->data!=key;p=p->next,i++);  else    for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);  L.t=p;//更新t指针  returnp;}//Search_CSList分析：由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{            DLNode*pre;          intdata;           DLNode*next; }DLNode;typedefstruct{           DLNode*sp;            intlength;  }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey){　//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功  p=L.sp;  if(p->data>key)  {     while(p->data>key)p=p->pre;    L.sp=p;  }  elseif(p->datadatanext;    L.sp=p;  }  returnp;}//Search_DSList分析：本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT){　//判断二叉树T是否二叉排序树,是则返回1,否则返回0  if(T->lchild&&flag)Is_BSTree(T->lchild);  if(T->datadata;  if(T->rchild&&flag)Is_BSTree(T->rchild);  returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx){//找到二叉排序树T中小于x的最大元素和大于x的最小元素  if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现  if(lastdata>=x)//找到了小于x的最大元素    printf("a=%dn",last);  if(last<=x&&T->data>x)//找到了大于x的最小元素    printf("b=%dn",T->data);  last=T->data;   if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx){//从大到小输出二叉排序树T中所有不小于x的元素  if(T->rchild)Print_NLT(T->rchild,x);  if(T->datadata);  if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx){//删除二叉排序树T中所有不小于x元素结点,并释放空间  if(T->rchild)Delete_NLT(T->rchild,x);  if(T->datalchild;  free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根  if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb){//打印输出后继线索二叉排序树T中所有大于a且小于b的元素  p=T;  while(!p->ltag)p=p->lchild;//找到最小元素  while(p&&p->datadata>a)printf("%dn",p->data);//输出符合条件的元素    if(p->rtag)p=p->rtag;    else    {       p=p->rchild;      while(!p->ltag)p=p->lchild;    }//转到中序后继  }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx){//在后继线索二叉排序树T中插入元素x  if(T->datartag)//T没有右子树时,作为右孩子插入    {      p=T->rchild;      q=(BiThrNode*)malloc(sizeof(BiThrNode));      q->data=x;      T->rchild=q;T->rtag=0;      q->rtag=1;q->rchild=p;//修改原线索    }    elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中  }//if  elseif(T->data>x)  {//插入到左子树中    if(!T->lchild)    {//T没有左子树时,作为左孩子插入      q=(BiThrNode*)malloc(sizeof(BiThrNode));      q->data=x;      T->lchild=q;      q->rtag=1;q->rchild=T;//修改自身的线索    }    elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中  }//if}//BSTree_Insert_Key 9.37StatusBSTree_Delete_key(BiThrTree&T,intx){//在后继线索二叉排序树T中删除元素x  BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继  p=T;last=NULL;//last始终指向当前结点p的前一个(前驱)  while(!p->ltag)p=p->lchild;//找到中序起始元素  while(p)  {    if(p->data==x)//找到了元素x结点    {      pre=last;      ptr=p;    }    elseif(last&&last->data==x)suc=p;//找到了x的后继    if(p->rtag)p=p->rtag;    else    {      p=p->rchild;      while(!p->ltag)p=p->lchild;    }//转到中序后继    last=p;  }//while//借助中序遍历找到元素x及其前驱和后继结点  if(!ptr)returnERROR;//未找到待删结点  Delete_BSTree(ptr);//删除x结点  if(pre&&pre->rtag)    pre->rchild=suc;//修改线索  returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{   q=T;  if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树    T=T->lchild;  elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树    T=T->rchild;  elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树  {    p=T;r=T->lchild;    while(!r->rtag)    {      s=r;      r=r->rchild;//找到结点的前驱r和r的双亲s    }    T->data=r->data;//用r代替T结点    if(s!=T)      s->rchild=r->lchild;    elses->lchild=r->lchild;//重接r的左子树到其双亲结点上    q=r;  }//else  free(q);//删除结点}//Delete_BSTree分析：本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S){　//把二叉排序树S合并到T中  if(S->lchild)　BSTree_Merge(T,S->lchild);  if(S->rchild)　BSTree_Merge(T,S->rchild);//合并子树  Insert_Key(T,S);//插入元素 }//BSTree_MergevoidInsert_Key(Bitree&T,BTNode*S){//把树结点S插入到T的合适位置上  if(S->data>T->data)  {    if(!T->rchild)T->rchild=S;    elseInsert_Key(T->rchild,S);  }  elseif(S->datadata)  {    if(!T->lchild)T->lchild=S;    elseInsert_Key(T->lchild,S);  }  S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系  S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Key分析：这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx){　//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素//全部大于x  if(T->lchild)BSTree_Split(T->lchild,A,B,x);  if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树  if(T->data<=x)Insert_Key(A,T);  elseInsert_Key(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Key(Bitree&T,BTNode*S) {//把树结点S插入到T的合适位置上  if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况  elseif(S->data>T->data)//其余部分与上一题同  {    if(!T->rchild)T->rchild=S;    elseInsert_Key(T->rchild,S);  }  elseif(S->datadata)  {    if(!T->lchild)T->lchild=S;    elseInsert_Key(T->lchild,S);  }  S->lchild=NULL;  S->rchild=NULL;  }//Insert_Key9.40typedefstruct{                intdata;                intbf;                intlsize;//lsize域表示该结点的左子树的结点总数加1                BlcNode*lchild,*rchild;}BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk){//在含lsize域的平衡二叉排序树T中确定第k小的结点指针  if(!T)returnNULL;//k小于1或大于树结点总数  if(T->lsize==k)returnT;//就是这个结点  elseif(T->lsize>k)    returnLocate_BlcTree(T->lchild,k);//在左子树中寻找  else returnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{                enum{LEAF,BRANCH}tag;//结点类型标识                intkeynum;                BPLinkparent;//双亲指针                intkey[MAXCHILD];//关键字                union{                        BPLinkchild[MAXCHILD];//非叶结点的孩子指针                        struct{                                  rectype*info[MAXCHILD];//叶子结点的信息指针                                  BPNode*next;//指向下一个叶子结点的链接                            }leaf;                   }  }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos){//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在//叶子结点中的位置pos  p=T;  while(p.tag==BRANCH)//沿分支向下查找  {    for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树if(i==p->keynum)returnERROR;//关键字太大    p=p->child[i];  }  for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找  if(i==p->keynum)returnERROR;//找不到关键字   ptr=p;pos=i;  returnOK;}//BPTree_Search  9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey){//在Trie树T中插入字符串key,StringType的结构见第四章  q=(TrieNode*)malloc(sizeof(TrieNode));  q->kind=LEAF;  q->lf.k=key;//建叶子结点  klen=key[0];  p=T;i=1;  while(p&&i<=klen&&p->bh.ptr[ord(key[i])])  {    last=p;    p=p->bh.ptr[ord(key[i])];    i++;  }//自上而下查找  if(p->kind==BRANCH)//如果最后落到分支结点(无同义词):  {    p->bh.ptr[ord(key[i])]=q;//直接连上叶子    p->bh.num++;  }  else//如果最后落到叶子结点(有同义词):  {    r=(TrieNode*)malloc(sizeof(TrieNode));//建立新的分支结点    last->bh.ptr[ord(key[i-1])]=r;//用新分支结点取代老叶子结点和上一层的联系    r->kind=BRANCH;r->bh.num=2;    r->bh.ptr[ord(key[i])]=q;    r->bh.ptr[ord(p->lf.k[i])]=p;//新分支结点与新老两个叶子结点相连  }}//TrieTree_Insert_Key分析：当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词, 此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.9.43StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey){　//在Trie树T中删除字符串key  p=T;i=1;  while(p&&p->kind==BRANCH&&i<=key[0])//查找待删除元素  {    last=p;    p=p->bh.ptr[ord(key[i])];    i++;  }  if(p&&p->kind==LEAF&&p->lf.k=key)//找到了待删除元素  {    last->bh.ptr[ord(key[i-1])]=NULL;    free(p);    returnOK;  }  elsereturnERROR;//没找到待删除元素}//TrieTree_Delete_Key9.44voidPrint_Hash(HashTableH){//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法  for(i=1;i<=26;i++)    for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])//线性探测      if(H(H.elem[j].key)==i)printf("%sn",H.elem[j]);}//Print_HashintH(char*s){//求Hash函数  if(s)returns[0]-96;//求关键字第一个字母的字母序号(小写)  else return0;}//H9.45typedef*LNode[MAXSIZE]CHashTable;//链地址Hash表类型StatusBuild_Hash(CHashTable&T,intm){//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突.  if(m<1)returnERROR;  T=malloc(m*sizeof(WORD));//建立表头指针向量  for(i=0;idata=key;q->next=NULL;    n=H(key);    if(!T[n])T[n]=q;//作为链表的第一个结点    else    {      for(p=T[n];p->next;p=p->next);      p->next=q;//插入链表尾部.本算法不考虑排序问题.    }  }//while  returnOK;}//Build_Hash9.46StatusLocate_Hash(HashTableH,introw,intcol,KeyTypekey,int&k){//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k  h=2*(100*(row/10)+col/10);//作者设计的Hash函数  while(H.elem[h].key&&!EQ(H.elem[h].key,key))    h=(h+1)%20000;  if(EQ(H.elem[h].key,key))k=h;  elsek=NULL;}//Locate_Hash 分析：本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).第十章　外部排序习题10.1磁盘平衡归并和磁带平衡归并在时间上有否差别？如果有，差别在何处？如果没有，请说明理由？10.2败者树中的败者指的是什么？若利用败者树求k个数中的最大值，在某次比较中得到a>b，那么谁是败者？败者树与堆有何区别？10.3试问输入文件在哪种状态下，经由置换选择排序法得到的初始归并段长度最长？其最长的长度是多少？10.4假如对一个经由置换选择排序法得到的输出文件再次进行置换选择排序，试问该文件将产生什么变化？10.5设内存有大小为6个记录的区域可供内部排序之用，文件的关键字序列为：（51，49，39，46，38，29，14，61，15，30，1，48，52，3，63，27，4，13，89，24，46，58，33，76）。试列出：用内部排序方法求出的初始归并段；用置换选择排序法得到的初始归并段。10.6假设某文件经内部排序得到100个初始归并段，试问：若要使多路归并三趟完成排序，则应取归并的路数至少为多少？10.10假如操作系统要求一个程序同时可用的输入、输出文件的总数不超过13，则按多路归并至少需几趟可完成排序？如果限定这个趟数，则可取的最低路数是多少？10.11假设一次I/O的物理块大小为150，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4路平衡归并排序时，需进行多少次I/O？10.12手工执行算法k-merge，追踪败者树的变化过程。假设初始归并段如下：（10，15，16，20，31，39，+∞）；（9，18，20，25，36，48，+∞）；（20，22，40，50，67，79，+∞）； （6，15，25，34，42，46，+∞）；（12，37，48，55，+∞）；（84，95，+∞）；10.13已知某文件经过置换选择排序之后，得到长度分别为47，9，39，18，4，12，23和7的八个初始归并段。试用3路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。第十章外部排序10.23voidInsert_Sort1(SqList&L){//监视哨设在高下标端的插入排序算法  k=L.length;  for(i=k-1;i;--i)//从后向前逐个插入排序    if(L.r[i].key>L.r[i+1].key)    {      L.r[k+1].key=L.r[i].key;//监视哨      for(j=i+1;L.r[j].key>L.r[i].key;++j)        L.r[j-1].key=L.r[j].key;//前移      L.r[j-1].key=L.r[k+1].key;//插入    }}//Insert_Sort110.24voidBiInsert_Sort(SqList&L){//二路插入排序的算法  intd[MAXSIZE];//辅助存储  x=L.r.key;d=x;  first=1;final=1;  for(i=2;i<=L.length;i++)  {    if(L.r[i].key>=x)//插入前部     {      for(j=final;d[j]>L.r[i].key;j--)        d[j+1]=d[j];      d[j+1]=L.r[i].key;      final++;    }    else//插入后部    {      for(j=first;d[j]L.r[i];      L.r[i].next=p;    }    p=q;  }//for}//SLInsert_Sort10.26voidBubble_Sort1(inta[],intn){//对包含n个元素的数组a进行改进的冒泡排序  change=n-1;//change指示上一趟冒泡中最后发生交换的元素  while(change)  {    for(c=0,i=0;ia[i+1])      {        a[i]<->a[i+1];        c=i+1;//c指示这一趟冒泡中发生交换的元素      }    change=c;  }//while}//Bubble_Sort110.27voidBubble_Sort2(inta[],intn){//相邻两趟是反方向起泡的冒泡排序算法  low=0;high=n-1;//冒泡的上下界  change=1;  while(lowa[i+1])      {        a[i]<->a[i+1];        change=1;      }    high--;//修改上界    for(i=high;i>low;i--)//从下向上起泡      if(a[i]a[i-1];        change=1;      }    low++;//修改下界  }//while}//Bubble_Sort210.28voidBubble_Sort3(inta[],intn){//对上一题的算法进行化简,循环体中只包含一次冒泡  intb[3];//b[0]为冒泡的下界,b[2]为上界,b[1]无用  d=1;b[0]=0;b[2]=n-1;//d为冒泡方向的标识,1为向上,-1为向下  change=1;  while(b[0]0)//注意这个交换条件      {        a[i]<->a[i+d];        change=1;      }     b[1+d]-=d;//修改边界    d*=-1;//换个方向  }//while}//Bubble_Sort310.29voidOE_Sort(inta[],intn){//奇偶交换排序的算法  change=1;  while(change)  {    change=0;    for(i=1;ia[i+1])      {        a[i]<->a[i+1];        change=1;      }    for(i=0;ia[i+1])      {        a[i]<->a[i+1];        change=1;      }  }//while}//OE_Sort分析：本算法的结束条件是连续两趟比较无交换发生10.30typedefstruct{   intlow;   inthigh;   }boundary;//子序列的上下界类型voidQSort_NotRecurve(intSQList&L) {//快速排序的非递归算法  low=1;high=L.length;  InitStack(S);//S的元素为boundary类型  while(low2)//如果当前子序列长度大于3且尚未排好序    {      pivot=Partition(L,low,high);//进行一趟划分      if(high-pivot>pivot-low)      {        Push(S,{pivot+1,high});//把长的子序列边界入栈        high=pivot-1;//短的子序列留待下次排序      }      else      {        Push(S,{low,pivot-1});        low=pivot+1;      }    }//if    elseif(low=pivotkey)      high--;    L.r[low]=L.r[high];    while(lowL.r[high].key)L.r[low]<->L.r[high];  else//子序列含有三个元素  {    if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1];    if(L.r[low+1].key>L.r[high].key)L.r[low+1]<->L.r[high];    if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1];  }}//Easy_Sort10.31voidDivide(inta[],intn){//把数组a中所有值为负的记录调到非负的记录之前  low=0;high=n-1;  while(low=0)high--;//以0作为虚拟的枢轴记录    a[low]<->a[high];    while(lowa[high];  }}//Divide10.32typedefenum{RED,WHITE,BLUE}color;//三种颜色voidFlag_Arrange(colora[],intn){//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列  i=0;j=0;k=n-1;  while(j<=k)    switch(a[j])    {      caseRED:        a[i]<->a[j];        i++;        j++;        break;      caseWHITE:        j++;        break;      caseBLUE:        a[j]<->a[k];        k--;//这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况    }}//Flag_Arrange分析：这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.10.33voidLinkedList_Select_Sort(LinkedList&L){//单链表上的简单选择排序算法  for(p=L;p->next->next;p=p->next)  {    q=p->next;x=q->data;    for(r=q,s=q;r->next;r=r->next)//在q后面寻找元素值最小的结点      if(r->next->datanext->data;        s=r;      }    if(s!=q)//找到了值比q->data更小的最小结点s->next    {      p->next=s->next;s->next=q;      t=q->next;q->next=p->next->next;      p->next->next=t;    }//交换q和s->next两个结点  }//for}//LinkedList_Select_Sort10.34voidBuild_Heap(Heap&H,intn){//从低下标到高下标逐个插入建堆的算法  for(i=2;iH.r[k].key)        H.r[j]<->H.r[k];      j=k;    }  }//for}//Build_Heap10.35voidTriHeap_Sort(Heap&H){//利用三叉树形式的堆进行排序的算法  for(i=H.length/3;i>0;i--)    Heap_Adjust(H,i,H.length);  for(i=H.length;i>1;i--)   {    　　H.r[1]<->H.r[i];    Heap_Adjust(H,1,i-1);  }}//TriHeap_SortvoidHeap_Adjust(Heap&H,ints,intm){//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆  rc=H.r[s];  for(j=3*s-1;j<=m;j=3*j-1)  {    if(j(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界      Merge(a,start1,end1,start2,end2);//归并    }}//Merge_Sort voidMerge(inta[],ints1,inte1,ints2,inte2){//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]  intb[MAXSIZE];　//设立辅助存储数组b  for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)  {    if(a[i]next,e2=p;p->next;p=e2)    {      for(i=1,q=p;i<=l&&q->next;i++,q=q->next);      e1=q;      for(i=1;i<=l&&q->next;i++,q=q->next);      e2=q;//求出两个待归并子序列的尾指针      if(e1!=e2)LinkedList_Merge(L,p,e1,e2);//归并    }}//LinkedList_Merge_Sort1voidLinkedList_Merge(LinkedList&L,LNode*p,LNode*e1,LNode*e2){//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2  q=p->next;r=e1->next;//q和r为两个子序列的起始位置  while(q!=e1->next&&r!=e2->next)  {    if(q->datadata)//选择关键字较小的那个结点接在p的后面     {      p->next=q;p=q;      q=q->next;    }    else    {      p->next=r;p=r;      r=r->next;    }  }//while  while(q!=e1->next)//接上剩余部分  {    p->next=q;p=q;    q=q->next;  }  while(r!=e2->next)  {    p->next=r;p=r;    r=r->next;  }}//LinkedList_Merge10.38voidLinkedList_Merge_Sort2(LinkedList&L){//初始归并段为最大有序子序列的归并排序,采用链表存储结构  LNode*end[MAXSIZE];//设立一个数组来存储各有序子序列的尾指针  for(p=L->next->next,i=0;p;p=p->next)//求各有序子序列的尾指针    if(!p->next||p->data>p->next->data)end[i++]=p;  while(end[0]->next)//当不止一个子序列时进行两两归并  {    j=0;k=0;//j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置    for(p=L->next,e2=p;p->next;p=e2)//两两归并所有子序列    {      e1=end[j];e2=end[j+1];//确定两个子序列       if(e1->next)LinkedList_Merge(L,p,e1,e2);//归并      end[k++]=e2;//用新序列的尾指针取代原来的尾指针      j+=2;//转到后面两个子序列    }  }//while}//LinkedList_Merge_Sort2voidLinkedList_Merge(LinkedList&L,LNode*p,LNode*e1,LNode*e2){//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2  q=p->next;r=e1->next;  while(q!=e1->next&&r!=e2->next)  {    if(q->datadata)    {      p->next=q;p=q;      q=q->next;    }    else    {      p->next=r;p=r;      r=r->next;    }  }//while  while(q!=e1->next)  {    p->next=q;p=q;    q=q->next;  }  while(r!=e2->next)  {    p->next=r;p=r;    r=r->next;  }}//LinkedList_Merge,与上一题完全相同 10.39voidSL_Merge(inta[],intl1,intl2){//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列  start1=0;start2=l1;//分别表示序列1和序列2的剩余未归并部分的起始位置  for(i=0;ia[i])b[i].gt++;      elseif(a[j]a[min];//与第i个记录交换    c[min]=INFINITY;//修改该记录的c值为无穷大以便下一次选取  }}//Count_Sort10.44voidEnum_Sort(inta[],intn){//对关键字只能取v到w之间任意整数的序列进行排序  intnumber[w+1],pos[w+1];  for(i=0;i1&&change;i--)//对影子序列执行冒泡排序  {    change=0;    for(j=0;jd[j+1].key)      {        d[j]<->d[j+1];        change=1;      }  }//for  for(i=0;i '