第1章的绪论知识题参备考资料答案解析Word下载.docx
《第1章的绪论知识题参备考资料答案解析Word下载.docx》由会员分享，可在线阅读，更多相关《第1章的绪论知识题参备考资料答案解析Word下载.docx（12页珍藏版）》请在冰点文库上搜索。
顺序存储结构示意图如下：
链式存储结构示意图如下：
5．设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。
图1.9第5题的逻辑结构图
它的二元组定义形式为B=（D，R），其中D={k1,k2,k3,k4,k5,k6,k7,k8,k9}，R=<
k1,k3>
<
k1,k8>
k2,k3>
<
k2,k4>
k2,k5>
k3,k9>
k4,k6>
k4,k7>
k5,k6>
k8,k9>
k9,k7>
}。
6．设有函数f（n）=3n2-n+4，请证明f（n）=O（n2）。
证明：
因为存在c=6，N=1，对所有的n≥N，0≤3n2-n+4≤6×
n2都是恒成立的，所以由书P16的定义可得f（n）=O（n2）。
7．请比较下列函数的增长率，并按增长率递增的顺序排列下列函数：
（1）2100
（2）（3/2）n（3）（4/3）n（4）nn（5）n2/3（6）n3/2（7）n!
（8）
（9）n（10）log2n（11）1/log2n（12）log2（log2n）（13）nlog2n（14）nlog2n
按增长率递增的排列顺序是:
1/log2n<
2100
log2（log2n）<
log2n<
n1/2
n2/3
n
nlog2n
n3/2
nlog2n<
（4/3）n
（3/2）n
n!
nn
8．试确定下列程序段中有标记符号“*”的语句行的语句频度（其中n为正整数）。
⑴i=1;
k=0;
while（i<
=n-1）{
k+=10*i;
//*
i++;
i++;
}
⑵i=1;
do{
k+=10*i;
}while（i<
=n-1）;
⑶i=1;
k=0;
while（i<
=n-1）{
i++;
k+=10*i;
⑷k=0;
for（i=1;
i<
=n;
i++）{
for（j=1;
j<
=i;
j++）
k++;
⑸i=1;
j=0;
while（i+j<
=n）{
if（i>
j）j++;
elsei++;
⑹x=n;
y=0;
//n是不小于1的常数
while（x>
=（y+1）*（y+1））{
y++;
⑺x=91;
y=100;
while（y>
0）{
if（x>
100）{x-=10;
y--;
}//*
elsex++;
⑻a=1;
m=1;
while（a<
n）
{
m+=a;
a*=3;
}
指定语句行的语句频度分别为：
（1）n-1
（2）当n≤1时语句频yac为1，当n>
1时语句频度为n-1
（3）n-1
（4）n（n+1）/2
（5）n
（6）
取整
（7）1100
（8）log3n
二、算法设计题
1．有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法，并分析算法的时间复杂度。
voidmax（double[]a）{
doublemax=a[0];
//初始化最大值为数组中的第一个元素
intindex=0;
//
for（inti=0;
i<
a.length;
if（max<
a[i]）{
max=a[i];
index=i;
}
}
System.out.println（"
最大的实数为：
"
+max+"
\n其在数组中的下标为：
+index）;
此算法的时间复杂度为O（n），其中n为数组的长度。
2．试编写一个求一元多项式
的值Pn（x0）的算法，并确定算法中每一条语句的执行次数和整个算法的时间复杂度。
输入是ai（i=0,1,2,…,n-1）和x0，输出为Pn（x0）。
0doublegetPolynomialResult（double[]a,doublex）{//a是多项式中系数数组
1doubleresult=0;
2doublepowX=1;
//临时变量，用于减少计算x幂的计算次数
3for（inti=0;
4result+=a[i]*powX;
5powX*=x;
6}
7returnresult;
8}
语句1~7的执行次数分别是:
1、1、a.length+1、a.length、a.length、1、1
此算法的时间复杂度为O（a.length），其中a.length也是多项式中的项数。
三、上机实践题
1．编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的Java程序。
packagech01Exercise;
publicclassExercise1_3_1{
publicint[]bubbleSort（int[]a）{//a为待排序的整数数组
intn=a.length;
booleanisExchange=true;
//交换标志
for（inti=0;
n-1&
&
isExchange;
i++）{//最多做n-1趟排序
isExchange=false;
for（intj=0;
j<
n-i-1;
j++）{//对当前无序区进行排序
if（a[j]>
a[j+1]）{//交换数据元素
inttemp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
isExchange=true;
//发生了交换，故将交换标志置为真
}
}
if（!
isExchange）
break;
//本趟排序未发生交换，提前终止算法
}
returna;
publicstaticvoidmain（String[]args）{
int[]values={49,38,65,97,76,13,27,49};
排序前数组中数据元素：
4938659776132749"
）;
System.out.print（"
排序后数组中数据元素：
Exercise1_3_1e=newExercise1_3_1（）;
values=e.bubbleSort（values）;
values.length;
i++）
System.out.print（values[i]+"
"
运行结果:
2．设计一个复数类，要求：
（1）在复数内部用双精度浮点数定义其实部和虚部。
（2）实现3个构造函数：
第1个构造函数没有参数；
第2个构造函数将双精度浮点数赋给复数的实部，虚部为0；
第3个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。
（3）编写获取和修改复数的实部和虚部的成员函数。
（4）编写实现复数的减法、乘法运算的成员函数。
设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。
//复数类
classComplex{
privatedoublereal;
//实部
privatedoubleimag;
//虚部
//无参构造函数
publicComplex（）{
this（0,0）;
//带一个参数的构造函数
publicComplex（doublereal）{
this（real,0）;
//带两个参数的构造函数
publicComplex（doublereal,doubleimag）{
this.real=real;
this.imag=imag;
publicdoublegetReal（）{
returnreal;
publicvoidsetReal（doublereal）{
publicdoublegetImag（）{
returnimag;
publicvoidsetImag（doubleimag）{
publicvoidadd（ComplexZ）{
if（Z!
=null）{
real+=Z.getReal（）;
imag+=Z.getImag（）;
//计算与另一复数的差,其中Z是减数
publicvoidminus（ComplexZ）{
real-=Z.getReal（）;
imag-=Z.getImag（）;
//计算与另一复数的乘积,其中Z是乘数
publicvoidmultiply（ComplexZ）{
doubletemp=（real*Z.getReal（）-imag*Z.getImag（））;
imag=（real*Z.getImag（）+imag*Z.getReal（））;
real=temp;
//测试类
publicclassExercise1_3_2{
Complexc1=newComplex（2,3）;
修改前c1的实部为：
+c1.getReal（）+"
虚部为：
+
c1.getImag（））;
c1.setReal
（1）;
c1.setImag
（2）;
修改后c1的实部为：
Complexc2=newComplex（4,5）;
c1.add（c2）;
执行加法运算后c1的实部为：
+c1.getImag（））;
c1.minus（c2）;
执行减法运算后c1的实部为：
c1.multiply（c2）;
执行乘法运算后c1的实部为：
升级会员 