数据结构答案《考试必备》

⑸ 按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意 去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。 void Print(Quadratic q) 解：

void Print(Quadratic q) {

if(q.a) cout<

if(q.b>0)

cout<<\ else

cout<0)

cout<<\ else

cout<

3.用c++函数描述下列每一个算法，并分别求出它们的时间复杂度。 ⑴ 比较同一简单类型的两个数据x1和x2的大小，对于x1>x2,x1=x2和x1''='和'<'字符。假定简单类型用SimpleType表示，它可通过typedef 语句定义为任一简单类型。 解：

char compare(SimpleType x1,SimpleType x2) {

if(x1>x2) return'>';

else if(x1==x2) return '='; else return'<'; }

其时间复杂度为O(1) ⑵ 将一个字符串中的所有字符按相反方的次序重新放置。 解：

void Reverse(char*p) {

int n=strlen(p);

for(int i=0;i

p[i]=p[n-i-1]; p[n-i-1]=ch; }

}

其时间复杂度为O(n) ⑶ 求一维double型数组a[n]中的所有元素之乘积。 解：

double product(double a[],int n) {

double p=1;

for(int i=0;i

其时间复杂度为O(n) ⑷ 计算∑ni=0xi/i+1的值。 解：

double Accumulate(double x,int n) {

double p=1,s=1;

for(int i=1;i<=n;i++){ p*=x;

s+=p/(i+1); }

return s; }

其时间复杂度为O(n) ⑸ 假定一维数组a[n]中的每个元素值均在[0，200]区间内，分别统计出落在[0，20) ,[20,50),[50,80),[80,130),[130,200]等各区间的元素个数。 解：

int Count(int a[],int n,int c[5])//用数组c[5]保存统计结果 {

int d[5]={20,50,80,130,201};//用来保存各统计区间的上限 int i,j;

for(i=0;i<5;i++)c[i]=0;//给数组c[5]中的每个元素赋初值0 for(i=0;i

if(a[i]<0||a[i]>200)

return 0;//返回数值0表示数组中数据有错，统计失败 for(j=0;j<5;j++)//查找a[i]所在区间 if(a[i]

c[j]++;//使统计相应区间的元素增1 }

return 1;//返回数值1表示统计成功

}

其时间复杂度为O(n) ⑹ 从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。 解：

void find(int a[M][N],int m,int n,int&Lin,int&Col)

//M和N为全局常量，应满足M>=n和N>=n的条件，Lin和Col为引用 //形参，它是对应实参的别名，其值由实参带回 {

Lin=0;Col=0;

for(int i=0;i

if(a[i][j]>a[Lin][Col]){Lin=i;Col=j;} }

其时间复杂度为O(m*n)

4.指出下列各算法的功能并求出其时间复杂度。 ⑴ int prime(int n) {

int i=2;

int x=(int)sqrt(n); while(i<=x){

if(n%i==0)break; i++; } if(i>x) return 1; else

return 0; } 解：

判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为 O(n1/2)。 ⑵ int sum1(int n) {

int p=1,s=0;

for(int i=1;i<=n;i++){ p*=i; s+=p; }

return s; } 解：

计算∑i!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。 ⑶ int sum2(int n) {

int s=0;

for(int i=1;i<=n;i++){ int p=1;

for(int j=1;j<=i;j++) p*=j; s+=p; }

return s; } 解：

计算∑i!的值，时间复杂度为O(n2) ⑷ int fun(int n) {

int i=1,s=1; while(s

求出满足不等式1+2+3...+i≥n的最小i值， 其时间复杂度为O(n1/2)。 ⑸ void UseFile(ifstream& inp,int c[10])

//假定inp所对应的文件中保存有n个整数 {

for(int i=0;i<10;i++) c[i]=0; int x;

while(inp>>x){ i=x; c[i]++; } } 解：

利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个

数，时间复杂度为O(n) ⑹ void mtable(int n) {