a[i][j]=i*j;
AO(m2)BO(n2)CO(m*n)DO(m+n)
5.执行下面程序段时,执行S语句的次数为(D)。
for(inti=1;i<=n;i++)
for(intj=1;j<=i;j++)
S;
An2Bn2/2Cn(n+1)Dn(n+1)/2
6.下面算法的时间复杂度为(B)。
intf(unsignedintn){
if(n==0||n==1)return1;
Elsereturnn*f(n-1);
}
AO
(1)BO(n)CO(n2)DO(n!
)
二、填空题
1.数据的逻辑结构被除数分为集合结构、线性结构、树型结构和图形结构四种。
2.数据的存储结构被分为顺序结构、结构、索引结构和散列结构四种。
3.在线性结构、树型结构和图形结构中,前驱和后继结点之间分别存在着1对1、1对N和
M对N的关系。
4.一种抽象数据类型包括数据和操作两个部分。
5.当一个形参类型的长度较大时,应最好说明为引用,以节省参数值的传输时间和存储参数的空间。
6.当需要用一个形参访问对应的实参时,则该形参应说明为引用。
7.在函数中对引用形参的修改就是对相应实参的修改,对值(或赋值)形参的修改只局限在该
函数的部,不会反映到对应的实参上。
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第1/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
8.当需要进行标准I/O操作时,则应在程序文件中包含iostream.h头文件,当需要进行文件I/O操作时,
则应在程序文件中包含fstream.h头文件。
9.在包含有stdlib.h头文件的程序文件中,使用rand()%21能够产生0-20之间的一个随机数。
10.一个记录r理论上占有的存储空间的大小等于所有域的长度之和,实际上占有的存储空间的大小即
记录长度为sizeof(r)。
11.一个数组a所占有的存储空间的大小即数组长度为sizeof(a),下标为i的元数a[i]的存储地址为a+1,
或者为(char*)a+i*sizeof(a[i])。
12.函数重载要求参数类型、参数个数或排列顺序有所不同。
13.对于双目操作符,其重载函数带有2个参数,其中至少有一个为用户自定义的类型。
14.若对象ra和rb中至少有一个属于用户定义的类型,则执行ra==rb时,需要调用等于号(==)重载函数,该函数第一个参数应与ra,的类型相同,第二个参数应与rb的类型相同。
15.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为O(n),输出一个二维数组b[m][n]中所有元素值的时间复杂度为O(m*n)。
16.在下面程序段中,s=s+p语句的执行次数为n,p*=j语句的执行次数为n(n+1)/2,该程序段的时间复杂度为O(n2)。
inti=0,s=0;
while(++i<=n){
intp=1;
for(intj=1;j<=i;j++)P*=j;
s=s+p;
}
17.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为O(n)。
18.从一个数组a[7]中顺序查找元素时,假定查找第一个元素a[0]的概率为1/3,查找第二个元素a[1]的概率为1/4,查找其余元素的概率均相同,则在查找成功时同元素的平均比较次数为35/12。
三、普通题
1.有下列几种用二元组表示的数据结构,试画出它们分别对应的图形表示(当出现多个关系时,
对每个关系画出相应的结构图),并指出它们分别属于何种结构。
⑴A=(K,R)其中
K={a1,a2,a3...,an}
R={}
⑵B=(K,R)其中
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第2/10页)[2010-3-1622:
06:
17]
(第二版)
file:
///D|/上架商品/数据结构实用教程
课后答案(徐孝凯著)清华大学/第一章绪论.txt
K={a,b,c,d,e,f,g,h}
R={r}r={,,,,,,}
⑶C=(K,R)其中
K={a,b,c,d,f,g,h}
R={r}r={,,,,,,}
⑷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。
QuadratiCInitQuadratiC(floataa=0,floatbb=0,floatCC=0);
解:
QuadratiCInitQuadratiC(floataa,floatbb,floatCC)
{QuadratiCq;
q.a=aa;
q.b=bb;
q.C=CC;
returnq;
}
⑵做两个多项式加法,即使对应的系数相加,并返回相加的结果。
QuadratiCAdd(QuadratiCq1,QuadratiCq2);
解:
QuadratiCAdd(QuadratiCq1,QuadratiCq2);
{
QuadratiCq;
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第3/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
returnq;
}
⑶根据给定x的值计算多项式的值。
floatEval(Quadraticq,floatx);
解:
floatEval(Quadraticq,floatx)
{
return(q.a*x*x+q.b*x+q.c);
}
⑷计算方程ax2+bx+c=0的两个实数根,对于有实根、无实根和不是实根方程
(即a==0)这三种情况要返回不同的整数值,以便于工作调用函数做不同的处理。
intRoot(Quadraticq,float&r1,float&r2);
解:
intRoot(Quadraticq,float&r1,float&r2)
{
if(q.a==0)return-1;
floatx=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);
return1;
}
elsereturn0;
}
⑸按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式,在输出时要注意去掉系数为0的项,并且当b和c的值为负时,其前不能出现加号。
voidPrint(Quadraticq)
解:
voidPrint(Quadraticq)
{
if(q.a)cout<if(q.b)if(q.b>0)
cout<<"+"<else
cout<if(q.c)
if(q.c>0)cout<<"+"<else
cout<cout<}
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第4/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
3.用C++函数描述下列每一个算法,并分别求出它们的时间复杂度。
⑴比较同一简单类型的两个数据x1和x2的大小,对于x1>x2,x1=x2和x1''='和'<'字符。
假定简单类型用SimpleType表示,它可通过typedef
语句定义为任一简单类型。
解:
CharCompare(SimpleTypex1,SimpleTypex2)
{
if(x1>x2)return'>';
elseif(x1==x2)return'=';
elsereturn'<';
}
其时间复杂度为O
(1)
⑵将一个字符串中的所有字符按相反方的次序重新放置。
解:
voidReverse(Char*p)
{
intn=strlen(p);
for(inti=0;iCharCh;
Ch=p[i]p[i]=p[n-i-1];
p[n-i-1]=Ch;
}
}
其时间复杂度为O(n)
⑶求一维double型数组a[n]中的所有元素之乘积。
解:
doubleproduCt(doublea[],intn)
{
doublep=1;
for(inti=0;ip*=a[i];
returnp;
}
其时间复杂度为O(n)
⑷计算刀ni=0xi/i+1的值。
解:
doubleAccumulate(doublex,intn)
{
doublep=1,s=1;
for(inti=1;i<=n;i++){
p*=x;
s+=p/(i+1);
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第5/10页)[2010-3-1622:
06:
17]
数据结构实用教程(第二版)
file:
///D|/上架商品/
课后答案(徐孝凯著)清华大学/第一章绪论.txt}
returns;
}其时间复杂度为O(n)
⑸假定一维数组a[n]中的每个元素值均在[0,200]区间,分别统计出落在[0,20)
[20,50),[50,80),[80,130),[130,200]等各区间的元素个数。
解:
用数组c[5]保存统计结果用来保存各统计区间的上限给数组c[5]中的每个元素赋初值0
if(a[i]<0||a[i]>200)
return0;//返回数值0表示数组中数据有错,统计失败
if(a[i]c[j]++;//使统计相应区间的元素增1
}
return1;//返回数值1表示统计成功
}
其时间复杂度为O(n)
⑹从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。
解:
voidfind(inta[M][N],intm,intn,int&Lin,int&Col)
//M和N为全局常量,应满足皿>=门和N>=n的条件,Lin和Col为引用
//形参,它是对应实参的别名,其值由实参带回
{
Lin=0;Col=0;
for(inti=0;ifor(intj=0;jif(a[i][j]>a[Lin][Col]){Lin=i;Col=j;}
}
其时间复杂度为O(m*n)
4.指出下列各算法的功能并求出其时间复杂度。
⑴intprime(intn)
{
inti=2;
intx=(int)sqrt(n);
while(i<=x){
if(n%i==0)break;
i++;
}
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第6/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
if(i>x)
return1;
else
return0;
}
解:
判断n是否是一个素数,若是则返回数值1,否则返回0。
该算法的时间复杂度为
O(n1/2)。
⑵intsum1(intn)
{
intp=1,s=0;
for(inti=1;i<=n;i++){
p*=i;
s+=p;
}
returns;
}
解:
计算刀i!
(上标为n,下标为i=1)的值,其时间的复杂度为0(n)。
⑶intsum2(intn)
{
ints=0;
for(inti=1;i<=n;i++){
intp=1;
for(intj=1;j<=i;j++)
p*=j;
s+=p;
}
returns;
}
解:
计算刀i!
的值,时间复杂度为0(n2)
⑷intfun(intn)
{
inti=1,s=1;
while(ss+=++i;
returni;
}解:
求出满足不等式1+2+3...+i>n的最小i值,其时间复杂度为0(n1/2)。
⑸voidUseFile(ifstream&inp,intc[10])
//假定inp所对应的文件中保存有n个整数
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第7/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
{
for(inti=0;i<10;i++)
c[i]=0;
intx;
while(inp>>x){
i=x%10;
c[i]++;
}
}
解:
利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个
数,时间复杂度为0(n)
⑹voidmtable(intn)
{
for(inti=1;i<=n;i++){
for(intj=i;j<=n;j++)
cout<
<(2)<
cout<}
}
解:
打印出一个具有n行的乘法表,第i行(1
与j(
iwjwn)的乘积,时间复杂度为0(n2)。
⑺voidcmatrix(inta[M][N],intd)
//M和N为全局整型常量
{
for(inti=0;ifor(intj=0;ja[i][j]*=d;
}
解:
使数组a[M][N]中的每一个元素均详细以d的值,时间复杂度为0(M*N)
⑻voidmatrimult(inta[M][N],intb[N][L],intc[M][L])
//
{
inti,j,k;
for(i=0;ifor(j=0;jc[i][j]=0;
for(i=0;ifor(j=0;jfor(k=0;kfile:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第8/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
}
解:
矩阵相乘,即a[M][N]Xb[N][L]tc[M][L],时间复杂度为O(MXNXL)。
5.题目略
⑴解:
voidInitSet(Set&s)
{
for(inti=1;i<=SETSIZE;i++)
s.m[i]=0;
}
⑵解:
voidInitSet(Set&s,inta[],intn)
{
fot(inti=0;is.m[a[i]]=1;
}
⑶解:
Setoperator+(Sets1,Sets2)
{
Sets;
InitSet(s);
for(inti=1;i<=SETSIZE;i++)
if((s1.m[i]==1)||s2.m[i]===1))
s.m[i]=1;
returns;
}
⑷解:
Setoperator*(Sets1,Sets2)
{
Sets;
InitSet(s);
for(inti=1;i<=SETSIZE;i++)
if((s1.m[i]==1)&&(s2.m[i]==1))
s.m[i]=1;
returns;
⑸解:
Booleanoperator人(intelt,Sets)
{
if(s.m[elt]==1)
returnTrue;
else
file:
///D|/上架商品...教程(第二版)课后答案(徐孝凯
著)清华大学/第一章绪论.txt(第9/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第一章绪论.txt
returnFalse;
}
⑹解:
voidInisert(Set&s,intn)
{
s.m[n]=1;
}
⑺解:
voidDelete(Set&s,intn)
{
s.m[n]=0;
}
⑻解:
ostream&operator<<(ostream&ostr,Set&s){ostr<<'{'
for(inti=1;i<=SETSIZE;i++)
if(s.m[i]==1)
ostr<
}
类别:
数据结构
上架商品...程(第二版)课后答案(徐孝凯著)
第10/10页)[2010-3-1622:
06:
17]
file:
///D|/上架商品/数据结构实用教程(第二版)
课后答案(徐孝凯著)清华大学/第二章线性表.txt习题二
一、单选题
1.在一个长度为n的顺序存储的线性表中,向第i个元素(1
时,
需要从年向前依次移B个元素。
An-iBn-i+1Cn-i-1Di
2.在一个长度为n的顺序存储的线性表中,删除第i个元素(1
前移A个元素。
3.在一个长度为n的线性表中顺序查找值为x的元素时,查找成功的平均查找长度(即x同元素
的平均比较次数,假定查找每个元素的概率都相等)为C。
AnBn/2C(n+1)/2D(n-1)/2
4.在一个单链表HL中,若要向表头插入一个自由指针p指向的结点,则执行B。
AHL=p;p->next=HL;Bp=next=HL;HL=p;
Cp->next=HL;p=HL;Dp->next=HL->next;HL->next=p;
5.在一个单链表HL中,若要在指针q所指结点的后面插入一个自由指针p所指向的结点,
则执行
D。
Aq->next=p->next;p->next=q;Bp->next=q->next;q=p;
Cq->next=p->next;p->next=qDp->next=q->next;q->next=p;
6.在一个单链表HL中,若要删除由指针q所指向结点的后继结点,则执行C。
Ap=q->next;p->next=q->next;Bp=q->next;q->next=p;
Cp=q->next;q->next;q->next=q;Dq->next=q=->Next->next;q->next=q;
二、填空题
1.在线性表的单存储结构中,每个结点包含有两个域,一个叫值,另一个叫指针域。
2.在下面数组a中存储着一个线性表,表头指针为a[0].next,则该线性表为(38,56,25,