数据结构第1章习题参考答案.docx

《数据结构第1章习题参考答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.6习题1.6.1知识点：数据结构的定义一、选择题1①数据结构通常是研究数据的（A）及它们之间的相互联系。A．存储和逻辑结构B．存储结构C．顺序结构D．链式存储结构2①数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构3①线性结构是数据元素之间存在一种（D）。A．一对多关系B.多对多关系C多对一关系D一对一关系4①计算机内部数据处理的基本单位是（B）。A.数据B．数据元素C.数据项D．数据库5②从逻辑上可以把数据结构分为（C）两大类。

2、【武汉交通科技大学1996】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构二、填空题1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。2①数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。三、判断题（F）1①数据元素是数据的最小单位。（T）2①记录是数据处理的最小单位。（F）3①数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）4①数据的物理结构是指数据在计算机内的实际存储形式。四、简答题1①简述什么是数据结构?2②数据结构与

3、数据类型有什么区别?【哈尔滨工业大学2001】1.6.2知识点：算法的概念一、选择题1①计算机算法指的是（C）A．计算方法B．排序方法C．解决问题的有限运算序列D．调度方法2①算法分析的目的是（（1）C），算法分析的两个主要方面（（2）A）．（1）A．找出数据结构的合理性B．研究算法中的输入与输出的关系C．分析算法的效率以求改进D．分析算法的易查性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3②设语句X++的时间是单位时间，则语句：for（i=1;i<=n;i

4、++）x++;时间复杂度为（C）。A．O（1）B．O（n）C．O（）D．O（）4②算法的计算量的大小称为计算的（B）。【北京邮电大学2000】A．效率B．复杂性C．现实性D．难度5②算法的时间复杂度取决于（C）【中科院计算所1998】A．问题的规模B．待处理数据的初态C．A和B6②下面关于算法说法错误的是（A）【南京理工大学2000】A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的7②下面说法错误的是（D）【南京理工大学2

5、000】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．（1）B．（1）,（2）C．（1）,（4）D．（3）8②程序段for（i=n-1;i>=1;i++）for（j=1;j<=i;j++）if（A[j]>A[j+1]）A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）【南京理工大学

6、1998】A．O（n）B．O（）C．O（）D．O（）二、填空题1①以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。2①一个算法的效率可分为___时间______效率和__空间_______效率．3②有一个程序片断如下：for（i=0;i

7、for（i=0;i=2）j=j/2;}则其时间复杂度为：O（n）三、判断题（T）1①算法的优劣与算法描述语言无关，但与所用计算机有关。（T）2①健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（F）3①程序一定是算法。四、简答题1①如何判断一个算法的好坏?2③调用下列C函数f（n）回答下列问题：（1）试指出f（n）值的大小，并写出f（n）值的推导过程；（2）假定n=5，试指出f（5）值的大小和执行f（5）时的输出结果。C函数：intf（intn）{inti,j，k,sum=

8、0;for（i=l;ii-1;j--）for（k=1;k