还剩1页未读,继续阅读
文本内容:
习题参考答案一.选择题
1.从逻辑上可以把数据结构分为(C两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构
2.在下面的程序段中,对x的斌值语句的频度为(Cfort=1;k<=n;k++)for(j=1;j<=n;j++)x=x十1;A.O2nB.OnC.On2.D.O(1og2n
3.采用顺序存储结构表示数据时,相邻的数据元素的存储地址(AA.一定连续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为正整数)(1j=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!insn;【解答】1
(3)k=0;fori=0;i<n;i++)forj=i;j<n;j++)k++;/*#*/【解答】nn+1/24a=1;b=0;while(a+b<=n){ifa<b)a++;/*#*/elseb++;}[解答]n
(5)x=91;y=100;while(y0{ifx100{x-=10;y--;}/*#*/elsex++;}[解答]
10006.写出下列各程序段关于n的时间复杂度
(1)a=1;m=1;while(a<n){m+=a;a*=3;}[解答]On
(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;forj=i+1;j<=n;j++)ifR[j]>R[j+1])k=j;t=R[k];R[k]=R[i];R[i]=t;}[解答]O(n2)
7.计算一元n次多项式Px,n)=a0+alx+a2x2+..+anxn“的值,输人xn,a0,al,…,an,输出多项式Px,n的值设计算法求解,请选择合适的输人、输出格式,要求算法具有较好的时间性能【解答】
①将一元n次多项式做如下改写Px,n)=a0+alx+a2x2+..+anxn=a0+xal+a2x+..+anxn-1=……=a0+xal+xa2+xa3+..xan-1+xan…
②按指数递减次序输人各系数,即输人次序为an,an-1,…,a2,a0
③算法如下main{s=0;scanf”%fx;fork=n;k=1;k--){scanf%f”a);s=s*x+a;}printf(”P(xn)=%f”,s);}
④分析该算法仅使用了n次乘法和n次加法,来完成一元n次多项式的求值问题,具有较好的时间和空间性能。