绪论习题参考答案

第1章 绪论习题参考答案(共4

页)

-本页仅作为预览文档封面，使用时请删除本页-

习题一参考答案

一、概念题

1. 试述下列各组概念：

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

⑵ 数据结构、数据的逻辑结构、数据的存储结构 ⑶ 数据类型、数据操作

⑷ 算法、算法的时间复杂度、算法的空间复杂度 参考答案: 略

2．试述数据结构研究的3个方面的内容。 参考答案:

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

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

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

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

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

4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,…,an}，

R={| i=1,2,…，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。 参考答案:

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

a1a2a3…an-1an0 1 2 … n-2 n-1

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

a1a2a3…an^

5．设一个数据结构的逻辑结构如图所示，请写出它的二元组定义形式。

2

K2 K4 K6 K5 K3 K1 K8 K9 K7

图 第5题的逻辑结构图

参考答案:

它的二元组定义形式为B=（D，R），其中D={k1,k2,k3,k4,k5,k6,k7,k8,k9}，

R=,,,,,,,,, }。

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)n (9) n (10) log2n (11) 1/log2n (12)log2(log2n) (13)nlog2n (14) nlog2n 参考答案:

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

1/log2n< 2100 8．试确定下列程序段中有标记符号“*”的语句行的语句频度（其中n为正整数)。 ⑴ 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; //* } ⑷ k=0;

3

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(am+=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) n取整 (7) 1100 (8) log3n

二、算法设计题

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

素的值及其下标的算法，并分析算法的时间复杂度。 参考答案:

void max(double[] a) {

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

for (int i = 0; i < ; i++) { if (max < a[i]) { max = a[i]; index = i;

4

}

}

\"最大的实数为：\" + max + \"\\n其在数组中的下标为：\" + index); }

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

2．试编写一个求一元多项式Pn(x)aixi的值Pn(x0)的算法，并确定算法中每一条语句的执行

i0n次数和整个算法的时间复杂度。输入是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 < ; i++) { 4 result += a[i] * powX; 5 powX *= x; 6 }

7 return result; 8 }

语句1~7的执行次数分别是:1、1、+1、、、1、1

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

5