?1.有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示（當(dāng)出現(xiàn)多個(gè)關(guān)系時(shí)，
對(duì)每個(gè)關(guān)系畫出相應(yīng)的結(jié)構(gòu)圖），并指出它們分別屬于何種結(jié)構(gòu)。
⑴ 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>}
解：⑴是集合結(jié)構(gòu)；⑵是線性結(jié)構(gòu)；⑶⑷是樹型結(jié)構(gòu)；⑸散列結(jié)構(gòu)。只作為參考。
2.設(shè)計(jì)二次多項(xiàng)式ax2+bx+c的一種抽象數(shù)據(jù)類型，假定起名為QIAdratic,
該類型的數(shù)據(jù)部分分為三個(gè)系數(shù)項(xiàng)a、b和c，操作部分為：(請(qǐng)寫出下面每一個(gè)
操作的具體實(shí)現(xiàn))。
⑴ 初始化數(shù)據(jù)成員ab和c(假定用記錄類型Quadratie定義成員)，每個(gè)數(shù)據(jù)成
員的默認(rèn)值為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;
}
⑵ 做兩個(gè)多項(xiàng)式加法,即使對(duì)應(yīng)的系數(shù)相加,并返回相加的結(jié)果。
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;
}
⑶ 根據(jù)給定x的值計(jì)算多項(xiàng)式的值。
float Eval(Quadratic q,float x);
解：
float Eval(Quadratic q,float x)
{
return(q.a*x*x+q.b*x+q.c);
}
⑷ 計(jì)算方程ax2+bx+c=0的兩個(gè)實(shí)數(shù)根，對(duì)于有實(shí)根、無實(shí)根和不是實(shí)根方程
(即a==0)這三種情況要返回不同的整數(shù)值，以便于工作調(diào)用函數(shù)做不同的處理。
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表示)輸出二次多項(xiàng)式，在輸出時(shí)要注意
去掉系數(shù)為0的項(xiàng)，并且當(dāng)b和c的值為負(fù)時(shí)，其前不能出現(xiàn)加號(hào)。
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++函數(shù)描述下列每一個(gè)算法，并分別求出它們的時(shí)間復(fù)雜度。
⑴ 比較同一簡單類型的兩個(gè)數(shù)據(jù)x1和x2的大小，對(duì)于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'<';
}
其時(shí)間復(fù)雜度為O(1)
⑵ 將一個(gè)字符串中的所有字符按相反方的次序重新放置。
解：
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;
}
}
其時(shí)間復(fù)雜度為O(n)
⑶ 求一維double型數(shù)組a[n]中的所有元素之乘積。
解：
double product(double a[],int n)
{
double p=1;
for(int i=0;i<n;i++)
p*=a[i];
return p;
}
其時(shí)間復(fù)雜度為O(n)
⑷ 計(jì)算Σ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;
}
其時(shí)間復(fù)雜度為O(n)
⑸ 假定一維數(shù)組a[n]中的每個(gè)元素值均在[0，200]區(qū)間內(nèi)，分別統(tǒng)計(jì)出落在[0，20)
,[20,50),[50,80),[80,130),[130,200]等各區(qū)間的元素個(gè)數(shù)。
解：
int Count(int a[],int n,int c[5])//用數(shù)組c[5]保存統(tǒng)計(jì)結(jié)果
{
int d[5]={20,50,80,130,201};//用來保存各統(tǒng)計(jì)區(qū)間的上限
int i,j;
for(i=0;i<5;i++)c[i]=0;//給數(shù)組c[5]中的每個(gè)元素賦初值0
for(i=0;i<n;i++)
{
if(a[i]<0||a[i]>200)
return 0;//返回?cái)?shù)值0表示數(shù)組中數(shù)據(jù)有錯(cuò)，統(tǒng)計(jì)失敗
for(j=0;j<5;j++)//查找a[i]所在區(qū)間
if(a[i]<d[j]) break;
c[j]++;//使統(tǒng)計(jì)相應(yīng)區(qū)間的元素增1
}
return 1;//返回?cái)?shù)值1表示統(tǒng)計(jì)成功
}
其時(shí)間復(fù)雜度為O(n)
⑹ 從二維整型數(shù)組a[m][n]中查找出最大元素所在的行、列下標(biāo)。
解：
void find(int a[M][N],int m,int n,int&Lin,int&Col)
//M和N為全局常量，應(yīng)滿足M>=n和N>=n的條件，Lin和Col為引用
//形參，它是對(duì)應(yīng)實(shí)參的別名，其值由實(shí)參帶回
{
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;}
}
其時(shí)間復(fù)雜度為O(m*n)
4.指出下列各算法的功能并求出其時(shí)間復(fù)雜度。
⑴ 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是否是一個(gè)素?cái)?shù)，若是則返回?cái)?shù)值1，否則返回0。該算法的時(shí)間復(fù)雜度為
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;
}
解：
計(jì)算Σi!(上標(biāo)為n，下標(biāo)為i=1)的值，其時(shí)間的復(fù)雜度為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;
}
解：
計(jì)算Σi!的值，時(shí)間復(fù)雜度為O(n2)
⑷ int fun(int n)
{
int i=1,s=1;
while(s<n)
s+=++i;
return i;
}
解：
求出滿足不等式1+2+3...+i≥n的最小i值， 其時(shí)間復(fù)雜度為O(n1/2)。
⑸ void UseFile(ifstream& inp,int c[10])
//假定inp所對(duì)應(yīng)的文件中保存有n個(gè)整數(shù)
{
for(int i=0;i<10;i++)
c[i]=0;
int x;
while(inp>>x){
i=x%10;
c[i]++;
}
}
解：
利用數(shù)組c[10]中的每個(gè)元素c[i]對(duì)應(yīng)統(tǒng)計(jì)出inp所聯(lián)系的整數(shù)文件中個(gè)位值同為i的整數(shù)個(gè)
數(shù)，時(shí)間復(fù)雜度為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;
}
}
解：
打印出一個(gè)具有n行的乘法表，第i行(1≤i≤n)中有n-i+1個(gè)乘法項(xiàng)，每個(gè)乘法項(xiàng)為i與j(
i≤j≤n)的乘積，時(shí)間復(fù)雜度為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;
}
解：
使數(shù)組a[M][N]中的每一個(gè)元素均詳細(xì)以d的值，時(shí)間復(fù)雜度為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]，時(shí)間復(fù)雜度為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;
}
