发布时间 : 星期二 文章数据结构与算法第三版第章参考答案更新完毕开始阅读
习题参考答案 一．选择题
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＋alx＋a2x2＋．．＋anxn“的值，输人x,n，a0，al，…，an，输出多项式P(x，n)的值。设计算法求解，请选择合适的输人、输出格式，要求算法具有较好的时间性能。 【解答】 ①将一元n次多项式做如下改写： P( x，n）=a0＋alx＋a2x2＋．．＋anxn =a＋x(a＋ax＋．．＋anxn-1) 0l2 =…… =a0＋x(al＋x(a2＋x(a3+．．x(an-1＋xan)…)))) ②按指数递减次序输人各系数，即输人次序为an，an-1，…，a2，a0 ③ 算法如下： main( ) {s＝0; scanf(”%f\ for(k=n; k>=1；k--） {scanf (\”,&a）； s=s*x+a； } printf（”P（x,n）=%f”，s）； } ④分析：该算法仅使用了n次乘法和n次加法，来完成一元n次多项式的求值问题，具有较好的时间和空间性能。