第1章的绪论习题参考答案.doc

习题一参考答案
一、概念题
1. 试述下列各组概念：
⑴ 数据、数据元素、数据项
⑵ 数据结构、数据的逻辑结构、数据的存储结构
⑶ 数据类型、数据操作
⑷ 算法、算法的时间复杂度、算法的空间复杂度
参考答案: 略

2．试述数据结构研究的3个方面的内容。
参考答案:
数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。

3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。
参考答案:
集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。
线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。
树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。
图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,…,an}，
R={<ai,ai+1>| i=1,2,…，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。
参考答案:
顺序存储结构示意图如下：

链式存储结构示意图如下：

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++;i++;
　　　}
　⑵ i=1; k=0;
　　　do {
　　　　 k +=10 * i; //*
　　　　　 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++ ; //*
　　　　　 else i++ ;
　　　}
　⑹ 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- -; } //*
　　　　 else x++;
⑻ 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 个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法，并分析算法的时间复杂度。
参考答案:
void max(double[] a) {
double max = a[0];// 初始化最大值为数组中的第一个元素
int index = 0; //
for (int i = 0; i < a.length; i++) {
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)。
参考答案:
0 double getPolynomialResult(double[] a, double x) { //a是多项式中系数数组
1 double result = 0;
2 double powX = 1;// 临时变量，用于减少计算x幂的计算次数
3 for (int i = 0; i < a.length; i++) {
4 result += a[i] * powX;
5 powX *= x;
6 }
7 return result;
8 }

语句1~7的执行次数分别是:1、1、a.length+1、a.length、a.length、1、1
此算法的时间复杂度为O(a.length)，其中a.length也是多项式中的项数。

三、上机实践题
1．编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的Java程序。
参考答案:
package ch01Exercise;
public class Exercise1_3_1 {

public int[] bubbleSort(int[] a) { // a为待排序的整数数组
int n = a.length;
boolean isExchange = true; // 交换标志
for (int i = 0; i < n - 1&&isExchange; i++) { // 最多做n-1趟排序
isExchange = false;
for (int j = 0; j < n - i - 1; j++) {// 对当前无序区进行排序
if (a[j] > a[j + 1]) {// 交换数据元素
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
isExchange = true; // 发生了交换，故将交换标志置为真
}
}
if (!isExchange)
break; // 本趟排序未发生交换，提前终止算法
}
return a;
}

public static void main(String[] args) {
int[] values = { 49, 38, 65, 97, 76, 13, 27, 49 };
System.out.println("排序前数组中数据元素：49 38 65 97 76 13 27 49");
System.out.print("排序后数组中数据元素：");

Exercise1_3_1 e = new Exercise1_3_1();
values = e.bubbleSort(values);
for (int i = 0; i < values.length; i++)
System.out.print(values[i] + " ");
}
}

运行结果:

2．设计一个复数类，要求：
(1) 在复数内部用双精度浮点数定义其实部和虚部。
(2) 实现3个构造函数：第1个构造函数没有参数；第2个构造函数将双精度浮点数赋给复数的实部，虚部为0；第3个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。
(3) 编写获取和修改复数的实部和虚部的成员函数。
(4) 编写实现复数的减法、乘法运算的成员函数。
设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。

参考答案:
package ch01Exercise;
//复数类
class Complex {
private double real;// 实部

private double imag; // 虚部

//无参构造函数
public Complex() {
this(0, 0);
}

//带一个参数的构造函数
public Complex(double real) {
this(real, 0);
}

//带两个参数的构造函数
public Complex(double real, double imag) {
this.real = real;
this.imag = imag;
}

public double getReal() {
return real;
}

public void setReal(double real) {
this.real = real;

}

public double getImag() {
return imag;
}

public void setImag(double imag) {
this.imag = imag;

}

public void add(Complex Z) {
if (Z != null) {
real += Z.getReal();
imag += Z.getImag();
}
}

//计算与另一复数的差,其中Z是减数
public void minus(Complex Z) {
if (Z != null) {
real -= Z.getReal();
imag -= Z.getImag();
}
}

// 计算与另一复数的乘积,其中 Z是乘数
public void multiply(Complex Z) {
if (Z != null) {
double temp = (real * Z.getReal() - imag * Z.getImag());
imag = (real * Z.getImag() + imag * Z.getReal());
real = temp;
}
}
}

// 测试类
public class Exercise1_3_2 {

public static void main(String[] args) {
Complex c1 = new Complex(2, 3);
System.out.println("修改前c1的实部为：" + c1.getReal() + " 虚部为：" +
c1.getImag());

c1.setReal(1);
c1.setImag(2);
System.out.println("修改后c1的实部为：" + c1.getReal() + " 虚部为：" +
c1.getImag());

Complex c2 = new Complex(4, 5);
c1.add(c2);
System.out.println("执行加法运算后c1的实部为：" + c1.getReal() + " 虚部为："
+ c1.getImag());

c1.minus(c2);
System.out.println("执行减法运算后c1的实部为：" + c1.getReal() + " 虚部为："
+ c1.getImag());

c1.multiply(c2);
System.out.println("执行乘法运算后c1的实部为：" + c1.getReal() + " 虚部为："
+ c1.getImag());

}
}
运行结果: