数据结构与算法第1章参考答案08.doc

习题参考答案
一．选择题
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.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。
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<n&&s <n)；
【解答】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
=a0＋x(al＋a2x＋．．＋anxn-1)
=……
=a0＋x(al＋x(a2＋x(a3+．．x(an-1＋xan)…))))
②按指数递减次序输人各系数，即输人次序为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次多项式的求值问题，具有较好的时间和空间性能。