数据结构作业系统_第一章答案.doc
【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构作业系统_第一章答案.精品文档.1.16 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。要求实现下列函数：void Descend(int &x, int &y, int &z); /* 按从大到小顺序返回x，y和z的值 */void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值 */ if(x<y)int t=x;x=y;y=t; if(x<z)int t=x;x=z;z=t; if(y<z)int 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，则返回OK；*/* 否则（比如，参数k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int tmpk=k; int tmpm=0; int curPos=k; int *tmpResults; if(k<2 | m<0)return ERROR; if(m=0)f=0;return OK; if(m<k-1)f=0;return OK; if(m=k-1)f=1;return OK; /初始化表 tmpResults=(int *)malloc(k*sizeof(int); while(tmpm<k-1) *(tmpResults+tmpm)=0; tmpm+; /while *(tmpResults+tmpm)=1; tmpm=k; /初始化结束 do tmpk=k; f=0; while(tmpk-) f+=*(tmpResults+tmpk); if(f<*(tmpResults+tmpk)return ERROR; if(curPos=k)curPos=1; else curPos+; *(tmpResults+curPos-1)=f; while(tmpm+<m); free(tmpResults); return OK;1.18 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为 项目名称 性别 校名 成绩 得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。要求实现下列函数：void Scores(ResultType *result, ScoreType *score); /* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 "", male, ' ', "", 0 （域scorce=0）*/* 表示结束 */相关数据类型定义如下：typedef enum female,male Sex;typedef struct char *sport; / 项目名称 Sex gender; / 性别（女：female；男：male） char schoolname; / 校名为'A','B','C','D'或'E' char *result; / 成绩 int score; / 得分（7,5,4,3,2或1） ResultType;typedef struct int malescore; / 男子总分 int femalescore; / 女子总分 int totalscore; / 男女团体总分 ScoreType;void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 "", male, ' ', "", 0 （域scorce=0）*/* 表示结束 */int i=0,j; while(resulti.sport!=NULL)switch(resulti.schoolname)case'A':score0.totalscore+=resulti.score;if(resulti.gender=female)score0.femalescore+=resulti.score;elsescore0.malescore+=resulti.score;break;case'B':score1.totalscore+=resulti.score;if(resulti.gender=female)score1.femalescore+=resulti.score; else score1.malescore+=resulti.score;break; case'C':score2.totalscore+=resulti.score; if(resulti.gender=female)score2.femalescore+=resulti.score; else score2.malescore+=resulti.score;break; case'D':score3.totalscore+=resulti.score; if(resulti.gender=female)score3.femalescore+=resulti.score; else score3.malescore+=resulti.score;break; case'E':score4.totalscore+=resulti.score; if(resulti.gender=female)score4.femalescore+=resulti.score; else score4.malescore+=resulti.score;break; i+; 1.19 试编写算法，计算i!×2i的值并存入数组a0.ARRSIZE-1的第i-1个分量中 (i=1,2,n)。假设计算机中允许的整数最大值为MAXINT，则当n>ARRSIZE或对某个k(1kn)使k!×2k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。要求实现下列函数：Status Series(int ARRSIZE, int a);/* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ int i=1,j; int n1=1,n2=2; while(i<=ARRSIZE) n1=1;n2=2; j=i; while(j>1) n1*=j; n2*=2; j-; if(n1*n2)>MAXINT) return OVERFLOW; ai-1=n1*n2; i+; if(i>ARRSIZE+1) return OVERFLOW; else return OK; 1.20 试编写算法求一元多项式 P(x) = a0 + a1x + a2x2 + . + anxn的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。要求实现下列函数：float Polynomial(int n, int a, float x0);/* 求一元多项式的值P(x0)。 */* 数组a的元素ai为i次项的系数，i=0,1,.,n */float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ int i=0,j; float xx=0,num; while(i<=n) j=i;num=1; while(j>=1) num*=x; j-; xx+=ai*num; i+; return xx;
