数据结构与算法第三版第章参考答案精品

【关键字】方法、空间、问题、系统、执行、建立、特点、位置、关键、需要、方式、结构、关系、分析、满足、解决、实现

习题参考答案

一．选择题

1.从逻辑上可以把数据结构分为（C)两大类。

A.动态结构、静态结构

B.顺序结构、链式结构

C.线性结构、非线性结构

D.初等结构、构造型结构

2.在下面的程序段中，对x的斌值语句的频度为（C)。

for( t＝1；k＜＝n;k＋＋）

for（j=1;j＜＝n; j＋＋）

x=x十1；

A. O(2n)

B. O (n)

C. O (n2)．

D. O（1og2n)

3.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（A)。

A.一定连续B．一定不连续

C.不一定连续

D.部分连续，部分不连续

4.下面关于算法说法正确的是（D）。

A.算法的时间复杂度一般与算法的空间复杂度成正比

B.解决某问题的算法可能有多种，但肯定采用相同的数据结构

C.算法的可行性是指算法的指令不能有二义性

D.同一个算法，实现语言的级别越高，执行效率就越低

5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。

A.正确性

B.健壮性

C.可读性

D.可移植性

二、判断题

1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√）

2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×）

3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×）

4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×）

5.算法必须有输出，但可以没有输人。（√）

三、筒答题

1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？

【答】常见的四种逻辑结构：

①集合结构：数据元素之间是“属于同一个集合”

②线性结构：数据元素之间存在着一对一的关系

③树结构：数据元素之间存在着一对多的关系

④结构：数据元素之间存在着多对多的关系。

常见的四种存储结构有：

①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。

②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。

③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。

④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。

2．简述算法和程序的区别。

【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。

3.试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这3方面的内容。

【解答】略。

4.运算是数据结构的一个重要方面。试举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，使得两个结构具有显著不同的特性。

【解答】比如顺序栈和循环队列，二者的逻辑结构都是线性结构，都采用顺序存储方式存储，但它们的运算不同，栈限定元素的插入和删除在栈顶进行，队列限定元素在队尾插入、在队首删除，因此它们是截然不同的数据结构。

5．分析下列程序段中带标号“＃’’语句的执行频度(n为正整数）。

（1) j＝1；k=0;

while（j<=n-1）

{j＋＋；

k＋=j; ／*＃*／

【解答】n-1

（2）i=0；s=0；n=100；

do {i++；

s＋＝10*i；／*＃*／

}while!(i

【解答】1

（3）k＝0；

for(i＝0；i＜n；i＋＋）

for(j＝i;j＜n;j＋＋）

k＋＋；／＊＃＊／

【解答】n(n＋1)/2

(4) a=1；b =0;

while（a＋b＜＝n）

{if( a＜b）a++；／＊＃＊／

else b++；

}

［解答］n

（5）x＝91；y＝100；

while（y>0)

{if (x>100) {x-=10; y--;} ／＊＃＊／

else x＋＋;

}

［解答] 1000

6.写出下列各程序段关于n的时间复杂度。

（1）a＝1；m＝1；

while（a＜n）

{m＋= a;

a*＝3；

}

[解答］O(n)

（2）设n是偶数。

for（i=1，s＝0；i＜＝n；i＋＋）

for（j=2*i；j＜＝n；j＋＋）

s＋＋；

［解答］O（n2）

（3）for（i=1；i＜=n-1；i＋＋）

{k＝i；

for(j=i＋1；j＜=n;j＋＋）

if(R[j]＞R[j＋1]）k＝j；

t＝R［k］；R［k］=R［i］；R［i］=t；

}

［解答］O（n2）

7.计算一元n次多项式P( x，n）=a0＋a l x＋a2x2＋．．＋a n x n“的值，输人x,n，a0，a l，…，

a n，输出多项式P(x，n)的值。设计算法求解，请选择合适的输人、输出格式，要求算法具有较好的时间性能。

【解答】

①将一元n次多项式做如下改写：

P( x，n）=a0＋a l x＋a2x2＋．．＋a n x n

=a0＋x(a l＋a2x＋．．＋a n x n-1)

=……

=a0＋x(a l＋x(a2＋x(a3+．．x(a n-1＋xa n)…))))

②按指数递减次序输人各系数，即输人次序为an，an-1，…，a2，a0

③算法如下：

main( )

{s＝0;

scanf(”%f" ,&x);

for(k=n; k>=1；k--）

{scanf ("% f”,&a）；

s=s*x+a；

}

printf（”P（x,n）=%f”，s）；

}

④分析：该算法仅使用了n次乘法和n次加法，来完成一元n次多项式的求值问题，具有较好的时间和空间性能。