第一章
◆1.16② 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。 void Descend(int &x, int &y, int &z)
/* 按从大到小顺序返回x，y和z的值 */ { int t; if(x {t=x;x=y;y=t;} if(x {t=x;x=z;z=t;} if(y {t=y;y=z;z=t;} } 1.17③ 已知k阶裴波那契序列的定义为 f0=0, f1=0, ..., fk-2=0, fk-1=1; fn=fn-1+fn-2+...+fn-k, n=k,k+1,... 试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。要求实现下列函数： Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ { int tempd; int temp[100]; int i,j,sum=0; if(k<2||m<0) return ERROR; if(m else if (m==k-1) f=1; else {for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1; for(i=k;i<=m;i++) { for(j=i-1;j>=i-k;j--) sum=sum+temp[j]; temp[i]=sum; sum=0; } f=temp[m]; } return OK; } 1.18③ 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为项目名称 性别 校名 成绩 得分.编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, */ /* 并以特殊记录 {\（域scorce=0）*/ /* 表示结束 */ { int i = 0; while( result[i].sport ) { switch( result[i].schoolname ) { case 'A': score[0].totalscore+= result[i].score; if( result[i].gender == female ) score[0].femalescore+=result[i].score; else score[0].malescore+=result[i].score; break; case 'B': score[1].totalscore += result[i].score; if( result[i].gender == female ) score[1].femalescore+=result[i].score; else score[1].malescore+= result[i].score; break; case 'C': score[2].totalscore += result[i].score; if( result[i].gender == female ) score[2].femalescore+=result[i].score; else score[2].malescore += result[i].score; break; case 'D': score[3].totalscore+= result[i].score; if( result[i].gender == female ) score[3].femalescore+=result[i].score; else score[3].malescore+=result[i].score; break; case 'E': score[4].totalscore+= result[i].score; if( result[i].gender == female ) score[4].femalescore+=result[i].score; else score[4].malescore+=result[i].score; break; } i++; } } ◆1.19④ 试编写算法，计算i!×2^i的值并存入数组a[0..ARRSIZE-1]的第i-1个分量中 (i=1,2,…,n)。 假设计算机中允许的整数最大值为MAXINT，则当n>ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。 1.19 Status Series(int ARRSIZE, int a[]) /* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ { int i=1; int t=1; a[0]=1;int n; for(n=1;n for(i=0;i if(a[i]>MAXINT) return OVERFLOW; break; } return OK; } ◆1.20④ 试编写算法求一元多项式P(x) = a0 + a1x + a2x^2 + ... + anx^n的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。 1.20 float Polynomial(int n, int a[], float x)/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ { int i; float s=0; for(i=n;i>=0;i--) s=s*x+a[i]; return s; } 第二章 ◆2.11② 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。 2.11 void InsertOrderList(SqList &L, ElemType x)// 在有序的顺序表 L 中保序插入数据元素 x { int j; j=L.length-1; while(L.elem[j]>x) { L.elem[j+1]=L.elem[j]; j--; } L.elem[j+1]=x; L.length++; } ◆2.12③ 设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，则A=B；若A'=空表，而B'≠ 空表，或者两者均不为空表，且A'的首元小于B'的首元，则A int i=0; while((i<=A.length-1)&&(i<=B.length-1)&&(A.elem[i]=B.elem[i])) ++i; if(i==A.length&&i==B.length) return '='; else if(i==A.length&&i!=B.length&&A.elem[i] 2.13② 试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。 实现下列函数： LinkList Locate(LinkList L, ElemType x); // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer pointing node 'x', // otherwise return 'NULL' LinkList Locate(LinkList &L, ElemType x) // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer ha pointing node 'x', // otherwise return 'NULL' { LinkList ha; ha=L->next; while(ha!=NULL&&ha->data!=x) ha=ha->next; if(ha==NULL) return NULL; else return ha; } 2.14② 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 int Length(LinkList L) // Return the length of the linked list // whose head node is pointed by 'L' { LinkList p; int i=0; p=L; while(p->next!=NULL) { p=p->next; i++; } return i; } 2.17② 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 void Insert(LinkList &L, int i, ElemType b) { LinkList p,s; if(!L&&i==1) { L=(LinkList)malloc(sizeof(LNode)); L->data=b; L->next=NULL; } else { if(i==0) { } else if(i==1) { s=(LinkList)malloc(sizeof(LNode)); s->data=b; s->next=L; L=s; } else { p=L; int j=1; while(p&&j p=p->next; j++ ; } s=(LinkList)malloc(sizeof(LNode)); s->data=b; s->next=p->next; p->next=s; } } } 2.18② 同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。 void Delete(LinkList &L, int i) {