第1章绪论习题参考答案

《第1章绪论习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题一参考答案一、概念题1.试述下列各组概念：（1）数据、数据元素、数据项（2）数据结构、数据的逻辑结构、数据的存储结构（3）数据类型、数据操作（4）算法、算法的吋间复杂度、算法的空间复杂度参考答案：略2.试述数据结构研究的3个方面的内容。参考答案：数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3.试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案：集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线性结构中数据元素

2、之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4.设有数据的逻辑结构的二元组定义形式为B=（D,R）,其中D={a„a2,-,an},R=

3、{

4、i=l,2/-,n-1},请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案：顺序存储结构示意图如下：0I2链式存储结构示意图如下:5.设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。图1・9第5题的逻辑结构图参考答案：它的二元组定义形式为B=(D,R),其中D={kbk2,k3,k4,k5,k6,k7,k8,k9},R=,

5、,k8>,,,,,,,,

6、k7>}。1.设有函数f(n)=3n2-n+4,请证明f(n)=0(n2)o证明：因为存在c=6,N=l,对所有的,0W3i?・n+4W6Xn2都是恒成立的，所以由书P16的定义可得f(n)=O(n2)«2.请比较下列函数的增长率，并按增长率递增的顺序排列下列函数：(1)2100(2)(3/2)n(3)(4/3)n⑷廿(5)n2/3(6)n3/2(7)n!(8)V«(9)n(10)log2n(11)l/log2n(12)log2(log2n)(13)nlog2n(14)n,og2n参考答案：按增长率递增的排列顺序是：l/log2n<210

7、0

8、)i=l；j=O;while(i+j<=n){if(i>j)j++；〃*elsei++；)(6)x=n;y=0;//n是不小于1的常数while(x>=(y+l)*(y+l)){y++;//*)⑺x=91;y=100;while(y>0){if(x>100){x-=10;y--;}//*elsex++；(8)a=l;m=l;while(al时语句频度为n-1(3)n-l(4)n(n+l)/2(5)n(6)徧取整(7

9、)1100(8)log3n二、算法设计题1.有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法，并分析算法的时间复杂度。参考答案：voidmax(double[]a){doublemax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;i

10、法的时间复杂度为0(n),其中n为数组的长度。1.试编写一个求一元多项式匕(X)=》q•十的值Pn(Xo)的算法，并确定算法中每一条语句的执行次数和整个算/=0法的时间复杂度。输入是ai(i=