第1章绪论习题参考答案

习题一参考答案

一、概念题

1.试述下列各组概念：

⑴ 数据、数据元素、数据项

⑵ 数据结构、数据的逻辑结构、数据的存储结构

⑶数据类型、数据操作

⑷ 算法、算法的时间复杂度、算法的空间复杂度

参考答案：略

2?试述数据结构研究的3个方面的内容。

参考答案：

数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算(操作)。

3.试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案：

集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。

线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。

树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。

图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

4?设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a i,a2,, ,a n}, R={<a i ,a i+i>| i=1,2,, , n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。

参考答案：

顺序存储结构示意图如下：

Oi-1 a n

a1 a2 a3

5

0 1 2 , n-2 n-1

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

ai A

&试确定下列程序段中有标记符号“ ⑴ i=1; k=0;

while ( i<=n-1) {

k += 10 * 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;

//*”的语句行的语句频度(其中 n 为正整数)。

K 7

图1.9第5题的逻辑结构图

参考答案：

它的二元组定义形式为 B= (D , R ),其中 D={k i ,k 2,k 3,k 4,k 5,k 6,k 7,k 8,k 9}, R=<k i ,k 3>,<k i ,k 8>,<k 2,k 3><k 2,k 4>,<k 2,k 5>,<k 3,k 9>,<k 4,k 6>,<k 4,k 7>,<k 5,k 6>,<k 8,k 9>,<k 9,k 7> }。

2 2

6.设有函数 f (n)=3n -n+4,请证明 f (n)=0(n )。

证明：因为存在c=6, N=1，对所有的n 》N , 0 w 3n 2-n+4 < 6 x n 2都是恒成立的，所以由 书P16的定

义可得f (n)=O(n 2)。

7.请比较下列函数的增长率，并按增长率递增的顺序排列下列函数:

按增长率递增的排列顺序是

K 4 K

5 (1) 2100 ⑵(3/2)n (3) (4/3)n ⑷ n n 2/3 ⑸n 3/2

⑹ n (7) n! (8) 一 n

(9) n (10) log 2 n (11) 1/log 2n 参考答案：

(12)log 2(log 2 n) (13 )n log 2n (14) n log2n

100

1/log2 * 2 <log 2(log 2n)<log 2n<n 1/2 2/3 3/2 log2n n

<n <n <nlog 2n <n <n <(4/3)

< (3/2) n < n! < n K 8

}

⑷ 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 W 1时语句频yac为1，当n>1时语句频度为n-1

(3)n-1

(4)n(n+1)/2

(5)n

(6)i n取整

(7)1100

(8)log3 n

、算法设计题

1?有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写据

个求最大数元素的值及其下标的算法，并分析算法的时间复杂度。

参考答案：

void max(double[] a) {

double max = a[0];〃初始化最大值为数组中的第一个元素

int in dex = 0; //

for (i nt i = 0; i < a.len gth; i++) {

if (max < a[i]) {

max = a[i]; in dex = i;

}

}

System.out.println(”最大的实数为：” + max + "\n其在数组中的下标为：” +

index);

}

此算法的时间复杂度为0(n)，其中n为数组的长度。

n

2?试编写一个求一元多项式P n(x) - 7 a i x i的值P n(x o)的算法，并确定算法中每一条语句

i =0

的执行次数和整个算法的时间复杂度。输入是a(i=0,1,2, , ,n-1)和x0,输出为P n(x0)。参考答案：

0 double getPoly no mialResult(double[] a, double x) { //a 是多项式中系数数组

1double result = 0;

2double powX = 1;//临时变量，用于减少计算x幕的计算次数

3for (int i = 0; i < a.length; i++) {

4result += a[i] * powX;

5powX *= x;

6}

7return result;

8}

语句1~7 的执行次数分别是：1、1、a.length+1、a.length、a.length、1、1

此算法的时间复杂度为O(a.length)，其中a.length也是多项式中的项数。

三、上机实践题

1 ?编写一个实现将整型数组中的数据元素按值递增的顺序进行排序的Java程序。

参考答案：

package chO1Exercise;

public class Exercise1_3_1 {

public int[] bubbleSort(int[] a) { // a 为待排序的整数数组

int n = a.len gth;

boolean isExchange = true; // 交换标志

for (int i = 0; i < n - 1&&isExchange; i++) { // 最多做n-1 趟排序isExcha nge = 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; II发生了交换，故将交换标志置为真} }

if (!isExcha nge)

break; II本趟排序未发生交换，提前终止算法

}

return a;

}

public static void main(String[] args) {

in t[] 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 .len gth; i++)

System.out.pri nt(values[i] + "");

}

}

运行结果：

2 ?设计一个复数类，要求：

(1)在复数内部用双精度浮点数定义其实部和虚部。

(2)实现3个构 …… 此处隐藏：1990字，全部文档内容请下载后查看。喜欢就下载吧 ……