1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，
对每个关系画出相应的结构图），并指出它们分别属于何种结构。
⑴ A=(K,R)其中
K={a1,a2,a3...,an}
R={}
⑵ B=(K,R)其中
K={a,b,c,d,e,f,g,h}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}
⑶ C=(K,R)其中
K={a,b,c,d,f,g,h}
R={r}
r={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}
⑷ D=(K,R)其中
K={1,2,3,4,5,6}
R={r}
r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}
⑸ E=(K,R)其中
K={48,25,64,57,82,36,75,43}
R={r1,r2,r3}
r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}
r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}
r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>}
解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构。只作为参考。
2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,
该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个
操作的具体实现)。
⑴ 初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成
员的默认值为0。
Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);
解：
Quadratic InitQuadratic(float aa,float bb,float cc)
{
Quadratic q;
q.a=aa;
q.b=bb;
q.c=cc;
return q;
}
⑵ 做两个多项式加法,即使对应的系数相加,并返回相加的结果。
Quadratic Add(Quadratic q1,Quadratic q2);
解：
Quadratic Add(Quadratic q1,Quadratic q2);
{
Quadratic q;
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
return q;
}
⑶ 根据给定x的值计算多项式的值。
float Eval(Quadratic q,float x);
解：
float Eval(Quadratic q,float x)
{
return(q.a*x*x+q.b*x+q.c);
}
⑷ 计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程
(即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。
int Root(Quadratic q,float& r1,float& r2);
解：
int Root(Quadratic q,float& r1,float& r2)
{
if(q.a==0)return -1;
float x=q.b*q.b-4*q.a*q.c;
if(x>=0){
r1=(float)(-q.b+sqrt(x))/(2*q.a);
r2=(float)(-q.b-sqrt(x))/(2*q.a);
return 1;
}
else
return 0;
}
⑸ 按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意
去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
void Print(Quadratic q)
解：
void Print(Quadratic q)
{
if(q.a) cout<<q.a<<"x**2";
if(q.b)
if(q.b>0)
cout<<"+"<<q.b<<"x";
else
cout<<q.b<<"x";
if(q.c)
if(q.c>0)
cout<<"+"<<q.c;
else
cout<<q.c;
cout<<end1;
}
3.用c++函数描述下列每一个算法，并分别求出它们的时间复杂度。
⑴ 比较同一简单类型的两个数据x1和x2的大小，对于x1>x2,x1=x2和x1<x2这三种不同
情况分别返回'>''='和'<'字符。假定简单类型用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<n/2;i++){
char ch;
ch=p[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<n;i++)
p*=a[i];
return p;
}
其时间复杂度为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<n;i++)
{
if(a[i]<0||a[i]>200)
return 0;//返回数值0表示数组中数据有错，统计失败
for(j=0;j<5;j++)//查找a[i]所在区间
if(a[i]<d[j]) break;
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<m;i++)
for(int j=0;j<n;j++)
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<n)
s+=++i;
return i;
}
解：
求出满足不等式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%10;
c[i]++;
}
}
解：
利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个
数，时间复杂度为O(n)
⑹ void mtable(int n)
{
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++)
cout<<i<<"*"<<j<<"="
<<setw(2)<<i*j<<"";
cout<<end1;
}
}
解：
打印出一个具有n行的乘法表，第i行(1≤i≤n)中有n-i+1个乘法项，每个乘法项为i与j(
i≤j≤n)的乘积，时间复杂度为O(n2)。
⑺ void cmatrix(int a[M][N],int d)
//M和N为全局整型常量
{
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
a[i][j]*=d;
}
解：
使数组a[M][N]中的每一个元素均详细以d的值，时间复杂度为O(M*N)
⑻ void matrimult(int a[M][N],int b[N][L],int c[M][L])
//
{
int i,j,k;
for(i=0;i<M;i++)
for(j=0;j<L;j++)
c[i][j]=0;
for(i=0;i<M;i++)
for(j=0;j<L;j++)
for(k=0;k<N;k++)
c[i][j]+=a[i][k]*b[k][j];
}
解：
矩阵相乘，即a[M][N]×b[N][L]→c[M][L]，时间复杂度为O(M×N×L)。
5.题目略
⑴解：
void InitSet(Set& s)
{
for(int i=1;i<=SETSIZE;i++)
s.m[i]=0;
}
⑵解：void InitSet(Set& s,int a[],int n)
{
fot(int i=0;i<n;i++)
s.m[a[i]]=1;
}
⑶解：
Set operator + (Set s1,Set s2)
{
Set s;
InitSet(s);
for(int i=1;i<=SETSIZE;i++)
if((s1.m[i]==1)||s2.m[i]===1))
s.m[i]=1;
return s;
}
⑷解：
Set operator*(Set s1,Set s2)
{
Set s;
InitSet(s);
for(int i=1;i<=SETSIZE;i++)
if((s1.m[i]==1)&&(s2.m[i]==1))
s.m[i]=1;
return s;
⑸解：
Boolean operator＾(int elt,Set s)
{
if(s.m[elt]==1)
return True;
else
return False;
}
⑹解：
void Inisert(Set& s,int n)
{
s.m[n]=1;
}
⑺解：
void Delete(Set& s,int n)
{
s.m[n]=0;
}
⑻解：
ostream& operator<<(ostream& ostr,Set& s)
{
ostr<<'{'
for(int i=1;i<=SETSIZE;i++)
if(s.m[i]==1)
ostr<<i<<',';
ostr<<'}'<<end1;
return ostr;
}
