2017年广工AnyView数据结构第1_5章答案及解析.doc

..WORD完美格式.. ..专业知识编辑整理.. /********** 【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/ void Descend(int a, int b, int c) /* 通过交换，令 a = b = c */ { if(c=bb=a) return; else { if(ab) swap(a,b); if(ac) swap(a,c); if(bc) swap(b,c); } } void swap(int a,int b) { int temp; temp=a; a=b; b=a; } /********** 【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n 的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/ float Polynomial(int n, int a[], float x) /* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ { float answer =a[0]; float temp= 1.0; for(int i=1;i=n;i++) { temp*=x; answer+=a[i]*temp; } return answer; } /********** 【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,... 试编写求k阶裴波那契序列的第m项值的函数算法， k和m均以值调用的形式在函数参数表中出现。 **********/ Status Fibonacci(int k, int m, int f) /* 求k阶斐波那契序列的第m项的值f */ { if(k=1||m0) return ERROR; else if(m==k-1) f=1; else if(m==0) f=0; else { int i,j,sum; int *t; t=(int*)malloc(m*sizeof(int)); for(i=0;i=k-2;i++) t[i]=0; t[k-1]=1; for(i=k;i=m;i++) { sum=0; for(j=i-k;j=i;j++) sum+=t[j]; t[i]=sum; } f=t[m]; } return OK; } /********** 【题目】试编写算法，计算i!×2^i的值并存入数组 a[0..n-1]的第i-1个分量中 (i=1,2,…,n)。假设计 算机中允许的整数最大值为MAXINT，则当对某个k (1≤k≤n)使k!×2^kMAXINT时，应按出错处理。注意 选择你认为较好的出错处理方法。 **********/ Status Series(int a[], int n) /* 求i!*2^i序列的值并依次存入长度为n的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */ { int t=1,p=1; for(int i=1;i=n;i++) { t*=i; p*=2; a[i-1]=t*p; if(a[i-1]MAXINT) return ERROR; } return OK; } /********** 【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛， 各院校的单项成绩均以存入计算机并构成一张表，表中每一行 的形式为： 项目名称 性别 校名