欢迎来到天天文库
浏览记录
ID:48349583
大小:197.00 KB
页数:8页
时间:2019-11-24
《第1章的绪论习题参考答案.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、习题一参考答案一、概念题1.试述下列各组概念:⑴数据、数据元素、数据项⑵数据结构、数据的逻辑结构、数据的存储结构⑶数据类型、数据操作⑷算法、算法的时间复杂度、算法的空间复杂度参考答案:略2.试述数据结构研究的3个方面的内容。参考答案:数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算(操作)。3.试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案:集合结构:集合中数据元素之间除了“同属于一个集合”的特性外,数据元素之间无其它关系,它们之间的关系是松散性的。线性结构:线性结构中数据元素之间存
2、在“一对一”的关系。即若结构非空,则它有且仅有一个开始结点和终端结点,开始结点没有前趋但有一个后继,终端结点没有后继但有一个前趋,其余结点有且仅有一个前驱和一个后继。树形结构:树形结构中数据元素之间存在“一对多”的关系。即若结构非空,则它有一个称为根的结点,此结点无前驱结点,其余结点有且仅有一个前驱,所有结点都可以有多个后继。图形结构:图形结构中数据元素之间存在“多对多”的关系。即若结构非空,则在这种数据结构中任何结点都可能有多个前驱和后继。4.设有数据的逻辑结构的二元组定义形式为B=(D,R),其中D={a1,a2,…,an}
3、,R={
4、i=1,2,…,n-1},请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案:顺序存储结构示意图如下:链式存储结构示意图如下:5.设一个数据结构的逻辑结构如图1.9所示,请写出它的二元组定义形式。图1.9第5题的逻辑结构图参考答案:它的二元组定义形式为B=(D,R),其中D={k1,k2,k3,k4,k5,k6,k7,k8,k9},R=,,,,,,,,5、9>,}。6.设有函数f(n)=3n2-n+4,请证明f(n)=O(n2)。证明:因为存在c=6,N=1,对所有的n≥N,0≤3n2-n+4≤6×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)(9)n(10)log2n(11)1/log2n(12)log2(log2n)(13)nlog2n(14)nlog2n参考答案:按增长率递增的排6、列顺序是:1/log2n<2100 7、=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(i>j)j++;//* elsei++; } ⑹x=n;y=0;//n是不小于1的常数 while(x>=(y+1)*(y+1)){ y++;//* } ⑺x=91;y=100; while(y>0){ if(8、x>100){x-=10;y--;}//* elsex++;⑻a=1;m=1;while(a1时语句频度为n-1(3)n-1(4)n(n+1)/2(5)n(6)取整(7)1100(8)log3n二、算法设计题1.有一个包括100个数据元素的数组,每个数据元素的值都是实数,试编写一个求最大数据元素的值及其下标的算法,并分析算法的时间复杂度。参考答案:voidmax(double[]a){doublem9、ax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;i
5、9>,}。6.设有函数f(n)=3n2-n+4,请证明f(n)=O(n2)。证明:因为存在c=6,N=1,对所有的n≥N,0≤3n2-n+4≤6×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)(9)n(10)log2n(11)1/log2n(12)log2(log2n)(13)nlog2n(14)nlog2n参考答案:按增长率递增的排
6、列顺序是:1/log2n<2100 7、=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(i>j)j++;//* elsei++; } ⑹x=n;y=0;//n是不小于1的常数 while(x>=(y+1)*(y+1)){ y++;//* } ⑺x=91;y=100; while(y>0){ if(8、x>100){x-=10;y--;}//* elsex++;⑻a=1;m=1;while(a1时语句频度为n-1(3)n-1(4)n(n+1)/2(5)n(6)取整(7)1100(8)log3n二、算法设计题1.有一个包括100个数据元素的数组,每个数据元素的值都是实数,试编写一个求最大数据元素的值及其下标的算法,并分析算法的时间复杂度。参考答案:voidmax(double[]a){doublem9、ax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;i
7、=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(i>j)j++;//* elsei++; } ⑹x=n;y=0;//n是不小于1的常数 while(x>=(y+1)*(y+1)){ y++;//* } ⑺x=91;y=100; while(y>0){ if(
8、x>100){x-=10;y--;}//* elsex++;⑻a=1;m=1;while(a1时语句频度为n-1(3)n-1(4)n(n+1)/2(5)n(6)取整(7)1100(8)log3n二、算法设计题1.有一个包括100个数据元素的数组,每个数据元素的值都是实数,试编写一个求最大数据元素的值及其下标的算法,并分析算法的时间复杂度。参考答案:voidmax(double[]a){doublem
9、ax=a[0];//初始化最大值为数组中的第一个元素intindex=0;//for(inti=0;i
此文档下载收益归作者所有