数据结构 java 语言描述课后答案
【篇一：数据机构第一章  —— java 语言描述 第 1 章 绪论习题参考答案】
概念题
1.试述下列各组概念：
⑴数据、数据元素、数据项
⑵ 数据结构、数据的逻辑结构、数据的存储结构
⑶ 数据类型、数据操作
⑷ 算法、算法的时间复杂度、算法的空间复杂度参考答案 : 略
2 ．试述数据结构研究的    3 个方面的内容。    参考答案 :
数据结构研究的 3 个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。
3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。 参考答案 :
集合结构：集合中数据元素之间除了    “同属于一个集合  ”的特性外，
数据元素之间无其它关系，它们之间的关系是松散性的。
线性结构：线性结构中数据元素之间存在    “一对一 ”的关系。即若结
构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前
趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且
仅有一个前驱和一个后继。
树形结构：树形结构中数据元素之间存在    “一对多 ”的关系。即若结
构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点
有且仅有一个前驱，所有结点都可以有多个后继。
图形结构：图形结构中数据元素之间存在    “多对多 ”的关系。即若结
构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。
4 ．设有数据的逻辑结构的二元组定义形式为    b=(d,r) ，其中
d={a1,a2,?,an}    ， r={ai,ai+1| i=1,2,?    ，n-1} ，请画出此逻辑结构对
应的顺序存储结构和链式存储结构的示意图。
参考答案 :
顺序存储结构示意图如下：
0 1 2 ?n-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,k3k2,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)  。
书 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 log2(log2n)log2nn1/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=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 (ij ) j++ ; //* else i++ ;
}
⑹ x=n; y=0; // n 是不小于 1 的常数 while (x=(y+1)*(y+1)) {
y++; //*
}
⑺ x=91; y=100; while (y0 ) {index复数
if (x100 ) { x -= 10; y- -; } //* else x++;
⑻ a=1; m=1; while(an)
{
m+=a;a*=3;//*
}
参考答案 :
(6)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(x)??axi
i?0ni  的值 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;//    临时变量，用于减少计算
3 for (int i = 0; i a.length; i++) {
4result += a[i] * powx;
5powx *= x;

x 幂的计算次数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。