anyview数据结构题目与答案.doc

感谢欧浩宇提供答案，仅供学习参考。 第一章 1.【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/ void Descend(int a, int b, int c) /* 通过交换，令 a = b = c */ { int t; if(ab) {t=b,b=a,a=t;} if(ac) {t=c,c=a,a=t;} if(bc) {t=b,b=c,c=t;} } 2./********** 【题目】试编写算法求一元多项式 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 p=a[n];//一次 for(int i=n-1;i=0;i--)//n次 p=a[i]+x*p; return p;//时间复杂度T(n)=O(n) } 3./********** 【题目】已知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 */ { int i; long temp; int a[1000]; if(k=1||m0){return ERROR;} for(i=0;ik-1;i++){a[i]=0;} a[i]=1; a[k]=1; for(temp=1,i=k+1;i=m;++i){ if(tempMAXINT) return ERROR; temp=temp-a[i-k-1]+a[i-1]; a[i]=temp; } f=a[m]; return OK; } 4./********** 【题目】试编写算法，计算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 x=0; for(int i=0;in;i++) { int JC=1,SUM=1; for(int j=i+1;j0;j--) { JC*=j;SUM*=2; } a[i]=JC*SUM; if(a[i]MAXINT){ return OVERFLOW;x++;} } if(x==0) return OK; } 5./********** 【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛， 各院校的单项成绩均以存入计算机并构成一张表，表中每一行 的形式为： 项目名称 性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体 总分，并输出。 **********/ void Scores(ResultType *result