信息技术2015数据结构重修辅导资料

《信息技术2015数据结构重修辅导资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息技术2014数据结构重修辅导资料第一章绪论第一题：选择题1、求解下面程序段的时间复杂度。for(i=0;i

2、，语句执行了一次，共n次，总的算来语句a[i][j]=i*j;总共被执行了m×n次，我们要选择语句执行频度最大值。【答案】答案为C。2、计算下列程序段的时间复杂度函数。intx,y;x=n;//n>1y=0;while(x>=(y+1)﹡(y+1))y++;【分析】这里y++;是循环体，被反复执行，只要计算出它的执行频度即可。【答案】3、一个算法所需时间由下述归方程表示，试求出该算法的时间复杂性的级别（或阶）以大“O”表示。其中：n是问题的规模，为简单起见，设n是2的整数幂。【分析】设n=2k，即

3、k=log2n则有：所以有T(n)=n(log2n+1)，该算法的时间复杂度为O(nlog2n)。【答案】O(nlog2n)4、下述函数中渐进时间复杂度最小的是：【分析】A和D比较，用D项减去A项得到nlog2n-2000log2n，显然D的值大于A的B和C比较，n2显然要小于nlog2n值，故B的值大于C的值。那么B和D这两个值中哪个更大呢？当n趋近于很大值时log2n值要远大于n2，所以这道题最小的是A，最大的是B。【答案】A5、计算下列程序中x=x+1的语句频度for(i=1;i<=n;i+

4、+)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【分析】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/66、算法分析的目的是：A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易读性和文档性【分析】《数据结构》研究的主要内容之一就是算法分析。为什么要分析算法呢，同一个问题可能会有多种方法来求解，但是不同的策略、存储结构都会对算法的运行时间及存储空间

5、有不同的影响，为了更有效率的解决问题，我们当然要对算法的优劣进行分析，以求得更有更优化的求解。【答案】C6．以下说法中正确的是（D）。A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构7．数据结构在计算机内存中的表示是指（A）。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系二、填空题1、线性结构中元素之间存在______关系，树型结构中元素之间存在______关系，图型结构中元素之间存在

6、______关系。2、数据结构是研究数据的______和______以及它们之间的相互关系，并对这种结构定义相应的操作，设计出相应的______，而确保经过这些运算后所得到的新结构是原来的结构类型。3、一个算法的时间复杂度是该算法包含的______的多少，它是一个算法运行时间的______，一个算法的空间复杂度是指该算法在运行过程中临时占用的______的大小。4、一个算法的时间复杂度通常用问题规模的______形式表示，当一个算法的时间复杂度与问题的n大小无关时，则表示为______；成正比时，

7、表示为______，成平方时，则表示为______。5、数据结构、数据元素和数据项在计算机中的映射（或表示）分别称为存储结构、结点和数据域。这句话是______。（填写正确或错误）6、常见的数据结构有______结构，_______结构，_______结构等三种。参考答案：1、一对一一对多多对多2、逻辑结构存储结构算法3、简单操作次数相对量度存储空间4、最高数量级O（1）O（n）O（n2）5、正确6、线性树形图形三、判断题三、判断题1、程序是用计算机语言表述的算法。（）2、算法一定要有输入和输出。

8、（）3、算法分析的目的旨在分析算法的效率以求改进算法。（）4、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（）5、程序就是算法，但算法不一定是程序。（）6、程序越短，程序运行的时间就越少。（）7、数据元素是数据的最小单位。()8、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。()9、算法和程序原则上没有区别，在讨论数据结构时二者是通用的。()10、数据的逻辑结构与数据元素本身的内容和形式无关。()参考答案：1、∨2、Χ3、∨4、Χ