算法与数据结构（C 语言版）（冯广慧第2版）课后习题答案 第1-4章

习题答案1选择题ADDACC填空题（1）树形结构、（2）图形结构（1）确定性、（2）输出（1）时间复杂度、（2）空间复杂度（1）1:1、（2）1:n、（3）n:n判断题1-4错错对对习题答案2选择1-10：ADBACABDAD填空1、（a）元素的存储位置（b）指针2、p->next!=NULL3、L->next==L或L->prior==L或L->prior==L&&L->next==L…或L->next==L->next…..（a）O(1)（b）O(n)判断1-6：对错错错错错四、应用1、在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。2、选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。3、链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。4、参见2.6节5、单循环链表往往只设尾指针而不设头指针，用一个指向尾结点的尾指针来标识单循环链表，好处是既方便查找表尾结点又方便查找头结点，因为通过尾结点的指针域很容易找到头结点。若使用头指针查找表尾结点需要从头遍历链表，时间复杂度是O(n)。五、算法设计题1、SeqListRearrange(SeqLista){ inti,j,t; i=0;j=a.Last-1;//i,j为工作指针(下标) t=a.data[0];//暂存枢轴元素。 while(i<j) { while(i<j&&a.data[j]>=0)j--; //j指针前移找小于0的元素 if(i<j)a.data[i++]=a.data[j]; //将负数前移 while(i<j&&a.data[i]<0)i++;//i指针后移找大于等于0的元素 if(i<j)a.data[j--]=a.data[i]; //正数后移 } a.data[i]=t; //将原第一元素放到最终位置 returna;}2、(1)LinkedListDelSame（LinkedListla）{ pre=la->next； ∥pre是p所指向的前驱结点的指针 p=pre->next； ∥p是工作指针，设链表中至少有一个结点 while（p） if（p->data==pre->data）∥相同元素值,释放结点{u=p；pre->next=p->next;p=p->next；free（u）；} else {pre=p；p=p->next；} ∥元素值不同 returnla;}(2)算法时间复杂度O(n)3、DLinkedListDInsert(DLinkedListla,ElemTypex){ p=la->next; ∥p指向第一元素 ∥MaxElemType是和x同类型的机器最大值，用做监视哨 la->data=MaxElemType; while(p->data<x) ∥寻找插入位置 p=p->next

; s=(DLNode*)malloc(sizeof(DLNode));∥申请结点空间 s->data=x; s->prior=p->prior; ∥将插入结点链入链表 s->next=p; p->prior->next=s; p->prior=s;}4、（1）①分别求出str1和str2所指的两个链表的长度m和n；②将两个链表以表尾对齐：即长的链表将指针移到|m-n+1|,短链表的指针指向链表的第一个字母；=3\*GB3③两个链表进行模式匹配：对应字母比较，从最后遇到两个链表结点值相等，直至到表尾对应结点值都相等为止。要注意处理虽然首次遇到对应结点值相等，但有后续结点值不等的情况,即在匹配中，并非一遇到对应字母相等，就结论后边是共同后缀。（2）求用单链表表示的两个单词的共同后缀的算法typedefstructNode{ ElemTypedata;structNode*next;}LNode,*LinkedList；intListLength(LNode*la){//求链表la的长度inti=0;LNode*p=la->next; //p指向链表的第一个元素结点while(p){i++; //元素个数加1p=p->next; //链表指针后移}returni; //返回链表的长度}LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分别是单词以单链表存储的头指针，本算法返回两个单词共同后缀的起始位置p=null; //p指向两个链表共同后缀的起始位置m=ListLength(str1);n=ListLength(str2); //求链表str1和str2的长度if(m>n){ s=str1->next; //s指向长链表的第一个元素 q=srt2->next; //q指向短链表的第一个元素 len=m-n+1; //两个链表开始比较时，长链表应移到的位置}else{ s=str2->next; //s指向长链表的第一个元素 q=srt1->next; //q指向短链表的第一个元素 len=n-m+1; //两个链表比较时，长链表应移到的位置}i=1;while(i<len){i++;s=s->next;} //长链表要移到两个链表尾部对齐的位置while(s){while(s&&s->data!=q->data)//对应字母不等，后移指针 { s=s->next;q=q->next;}p=s; //p指向两个链表共同后缀的起始位置while(s&&s->data==q->data)//如对应字母相等，后移指针{ s=s->next;q=q->next;}}returnp; //返回两个链表共同后缀的起始位置}（3）算法中求了两个链表的长度，接着将长链表的指针移到两链表的比较处，进行对应元素的比较，记住可能共同后缀的开始位置，直到链表尾。总的时间复杂度为O(m+n)。5、(1)算法思想：定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。(2)节点的数据结构定义如下：typedefstructNode{Intdata;StructNode*next;}Node;(3)inta[n];//全局数组标志节点的绝对值的值是否出现过voidDeleteABSEqualNode(Node*head){ memset(a,0,n);//初始化为0 if(head==NULL)returnNULL; Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p->data)]==1) //如果此绝对值已经在数组中出现过，则删除 { r->next=p->next;deletep;p=r->next;} else//否则，将数组中对应的元素置1 { a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍历一次链表，所以时间复杂度为O(n)因为申请大小为n的数组，所以空间复杂度为O(n)（n为节点绝对值的最大值）。6、(1)算法思想由于数组中有n个整数，则未出现的最小的正整数一定在1到n+1的范围，假如：数组a为[1,2,3,4]，则最小正整数为5，也就是n+1。如果数组中介于1到n之间的正整数个数不足n个，则未出现的最小的正整数的范围是1到n。设置一个辅助数组b,大小为n+2,初始值全部为0，然后对a[i]进行遍历，如果0<a[i]<=n+1，则将b[a[i]]赋值为1，接下来遍历b数组，遇到的第一个满足b[i]==0的就退出，i就是数组a中未出现过的最小正整数(2)代码实现intfindMissMin(intA[],intn){int*B=newint[n]; //创建动态数组memset(B,0,n*sizeof(int)); //赋初值inti;for(i=0;i<n;++i){ if(A[i]>0&&A[i]<n){//仅处理A中范围在1~n的元素B[A[i]-1]++;}}for(i=0;i<n;++i){if(B[i]==0)break;}delete[]B;returni+1;}(3)算法的时间复杂度为O(n);空间复杂度为O(n)。7、(1)算法思想①首先寻找单链表的中心结点，使用两个指针p、q，每次p走一步，q走两步，当q到链表尾时，p正好在链表中心的位置。②将链表后半段利用头插法逆置。③从单链表前后两段中依次各取一个结点，并重新排列。(2)代码实现voidrealign(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL){ //寻找中间结点p=p->next; //p向后移动一个结点q=q->next;if(q->next!=NULL)q=q->next;//q向后移动两个结点}q=p->next; //p指向中间结点，q指向p后面的结点p->next=NULL;while(q!=NULL){ //从q开始逆置后半段r=q->next;q->next=p->next; //p是中间结点，每次新结点插入在p之后p->next=q;q=r;}s=h->next; //s指向前半部分的第一个结点q=p->next; //q指向后半部分的第一个结点p->next=NULL; //分成2个单链表while(q!=NULL){ //归并单链表r=q->next;q->next=s->next; //将q指向的结点插入到s指向结点的后面s->next=q;s=q->next;q=r;}}时间复杂度为O(n)习题答案3一、选择题1-5B、B、D、B、B6-10B、A、D、BD、C、二、填空题1、先进后出，先进先出2、23.12.3*2-4/34.5*7/++108.9/+3、假溢出4、rear=(rear+1)%ns=newLnode(x)；s->next=r->next；r->next=s；r=s5、O(1),O(n),O(1),O(1)三、判断题对错对对对四、应用题三个：CDEBA，CDBEA，CDBAE435612不可以321，325641可以，154623不可以432，135426可以Rear=4和front=2队列为满的条件：(rear+1)%MaxSize==front队列为空的条件:front==rear5、(1)A*B*C(2)(A+B)*C-D(3)A*B+C/(D-E)(4)(A+B)*D+E/(F+A*D)+C(1)ABC** (2)AB+C*D- (3)AB*CDE-/+ (4)AB+D*EFAD*+/C+五、算法设计题1、#definemaxsize100//两栈共享顺序存储空间所能达到的最多元素数#defineElemTypeint∥假设元素类型为整型typedefstruct{ ElemTypestack[maxsize];∥栈空间 inttop[2];∥top为两个栈顶指针}stk;stks;∥s是如上定义的结构类型变量，//为全局变量入栈操作：intpush(inti,intx)∥入栈。i=0表示左栈s1，i=1表示右栈s2，x是入栈元素。入栈成功返回1，否则返回0{ if(i<0||i>1){printf(“栈号输入不对\n”);exit(0);} if(s.top[1]-s.top[0]==1){printf(“栈已满\n”);return(0);} switch(i) {case0:s.stack[++s.top[0]]=x;return(1);break; case1:s.stack[--s.top[1]]=x;return(1); }}∥push退栈操作:ElemTypepop(inti)∥退栈算法。i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1{ if(i<0||i>1){printf(“栈号输入错误\n”)；exit(0);} switch(i) {case0:if(s.top[0]==-1){printf(“栈空\n”)；return（-1）；} elsereturn(s.stack[s.top[0]--]); case1:if(s.top[1]==maxsize){printf(“栈空\n”);return(-1);} elsereturn(s.stack[s.top[1]++]);}∥switch}∥算法结束判断栈空intEmpty();{return(S.top[0]==-1&&S.top[1]==m);}2、（1）初始化SeQueueQueueInit(SeQueueQ){//初始化队列 Q.front=Q.rear=0;Q.tag=0; returnQ;}（2）入队SeQueueQueueIn(SeQueueQ,inte){//入队列 if((Q.tag==1)&&(Q.rear==Q.front)) printf("队列已满\n");

else{Q.rear=(Q.rear+1)%m; Q.data[Q.rear]=e;if(Q.tag==0)Q.tag=1;//队列已不空 } returnQ;}(3)出队ElemTypeQueueOut(SeQueueQ){//出队列 if(Q.tag==0){printf("队列为空\n");exit(0);}

else { Q.front=(Q.front+1)%m; e=Q.data[Q.front]; if(Q.front==Q.rear)Q.tag=0;//空队列 } return(e);}3、（1）循环队列的定义typedefstruct{ ElemTypeQ[m];∥循环队列占m个存储单元 intrear,length;∥rear指向队尾元素,length为元素个数}SeQueue;(2)初始化SeQueueQueueInit(SeQueuecq)∥cq为循环队列，本算法进行队列初始化{ cq.rear=0; cq.length=0; returncq;}(3)入队SeQueueQueueIn(SeQueuecq，ElemTypex)∥cq是以如上定义的循环队列，本算法将元素x入队{ if(cq.length==m)return(0);∥队满 else {cq.rear=(cq.rear+1)%m;∥计算插入元素位置 cq.Q[cq.rear]=x;∥将元素x入队列 cq.length++;∥修改队列长度 } return(cq);}（4）出队ElemTypeQueueOut(SeQueuecq)∥cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素{ if(cq.length==0)return(0);∥队空 else {intfront=(cq.rear-cq.length+1+m)%m; ∥出队元素位置 cq.length--;∥修改队列长度

return(cq.Q[front]);∥返回对头元素 }}4、（1）递归intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}∥算法结束（2）非递归intAckerman(intm,intn){intakm[M][N];intI,j;for(j=0;j<N;j++)akm[0][j];=j+1;for(i=1;i<m;i++){akm[i][0]=akm[i-1][1];for(j=1;j<N;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}∥算法结束5、intsympthy(charstr[],chars[]){inti=0,j,n;while(str[i]!=‘\0’)i++;//查字符个数n=i;for(i=0;i<n/2;i++)s[i]=str[i];//前一半字符入栈j=i-1;if(n%2==1)i++;//n为奇数时中间字符不用比较while(i<n&&str[i]==s[j])//比较字符串是否是回文{i++;j--;}if(i==n)printf(“字符串是回文\n”)；elseprintf(“字符串不是回文\n”)；}6、VoidPermute(intS[],intj,intn)∥对S[j]――S[n-1]中的n-j个元素进行全排列，j的初值为0{ inti,temp; if(j==n-1)//只有一个元素 {for(i=0;i<n;i++)printf(“%5d”,S[i]);printf(“\n”);} else for(i=j;i<n;i++)//j位置元素固定，求j+1到n的全排列{temp=S[j];S[j]=S[i];S[i]=temp;Permute(S,j+1,n);temp=S[j];S[j]=S[i];S[i]=temp;}习题答案4一、选择题1-6B、A、B、D、C、B二、填空题1．字符2.O(m+n)3．-100112014．-10-10-1310三、判断题对对错错四、应用题1、空串：当串的长度n=0时，串中没有任何字符，称为空串，如S=“”；空格串：由空格字符组成的串，称为空格串，如S=“”子串：串中任意个连续的字符组成的子序列被称为该串的子串。空串是任意串的子串；任意串S都是S自身的子串。主串：包含子串的串又被称为该子串的主串。2、KMP的特点是主串无需回溯，主串指针一直往后移动，只有子串指针回溯，大大减少算法的比较次数和回溯次数。3、五、算法设计题1、[题目分析]设字符串存于字符数组X中，若转换后的数是负数，字符串的第一个字符必为'-'转换过程如下：将取出的数字字符减去字符零（'0'）的ASCII值，变成数；先前取出的数乘上10加上本次转换的数形成部分结果；如此一个字符一个字符的转换，直到字符串结束，得到结果。longatoi(char*X){longnum=0; //结果整数初始化inti=1; //i为数组下标if(X==NULL){cout<<"PointerisNULL\n";return0;}if(X[0]!='-')num=X[0]-'0'; //如是正数，x[0]是数字字符while(X[i]!='\0') //当字符串未到尾，进行数的转换num=10*num+(X[i++]-'0'); //先前取出的数乘上10加上本次转换的数形成部分结果if(X[0]=='-')return(-num); //负数elsereturn(num); //返回正数}2、（1）//求重复子串的长度intrptSubLen(char*p,char*q){ intlen=0;while(*p&&*q){if(*p==*q){ ++len;p++,q++;}elsebreak;}returnlen;}（2）//求最长重复子串voidlongestRepeatSub(char*arr,intsize,int&maxLen,int&maxIndex){inti,j,len;maxLen=0; //记录最长重复子串的长度maxIndex=-1; //记录最长重复子串的下标for(i=0;i<size;++i){for(j=i+1;j<size;++j){len=rptSubLen(&arr[i],&arr[j]);if(len>maxLen){maxLen=len;maxIndex=i;}}}if(maxLen==0)return;i=maxIndex;cout<<"Thelongestrepeatsubstring：";while(maxLen--)cout<<arr[i++];cout<<endl;}3、//利用4.2.1节已经给定的顺序存储结构的串的类型定义StringString&String::replace(intpos,intnum,constString&t){Stringtemp(*this); inti=0,j=0;if(pos<1||num<0){ //参数错误return*this;}curLen+=t.curLen-j; delete[]str; str=newchar[curLen+1]; assert(str!='\0'); while(i<pos-1) //拷贝原串前pos-1个元素str[i]=temp.str[i++];while(j<t.curLen) //拷贝t串str[i++]=t.str[j++];j=pos+num-1;while(temp.str[j]!='\0') //拷贝原串从第pos+num个到串尾的元素str[i++]=temp.str[j++];str[i]='\0';return*this;}4、voidInvertStore(charA[]){∥字符串逆序存储的递