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

1、页眉内容1.6习题一、选择题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）两大类。【武汉交通科技大学1996】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D,初等结构、构

2、造型结构二、填空题1数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。_2数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链丸宗豆。三、判断题（F）1数据元素是数据的最小单位。（T）2记录是数据处理的最小单位。（F）3数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）4数据的物理结构是指数据在计算机内的实际存储形式。四、简答题1简述什么是数据结构？2数据结构与数据类型有什么区别？【哈尔滨工业大学2001】、选择题1计算机算法指的是（C）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法2算法分析的目的是（1）C）,算法分析的两个主要方面（2）A）.（1）

3、A.找出数据结构的合理性B.研究算法中的输入与输出的关系C.分析算法的效率以求改进D.分析算法的易查性和文档性（2） A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性3设语句X+的时间是单位时间，则语句：for（i=1;i<=n;i+）x+;时间复杂度为（C）。23AO（1）BO（n）CO（n2）DO（n3）4算法的计算量的大小称为计算的（B）。【北京邮电大学2000】A.效率B.复杂性C.现实性D.难度5算法的时间复杂度取决于（C）【中科院计算所1998】A问题的规模B待处理数据的初态CA和B6下面关于算法说法错误的是（A）【南京理工大学2000

4、】A.算法最终必须由计算机程序实现B为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D以上几个都是错误的7下面说法错误的是（D）【南京理工大学2000】（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（Aj>Aj+1

5、）Aj与Aj+1对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）【南京理工大学1998】32AO（n）BO（nlog2n）CO（n）DO（n）二、填空题1以夹杂自然语言和程序语句的形式来描述解决问题的方法称为伪码。2一个算法的效率可分为一时间效率和空间效率.3有一个程序片断如下：for（i=0;i<n;i+）x=x+1;则其时间复杂度为：_O(n)4有一个程序片断如下：for(i=0;i<n;i+)for(j=i;j<n;j+)for(k=j;k<n;k+)m=1;则其时间复杂度为：O(n3)5有一个程序片断如下：for(i=0;i<n;i+)j=i；while(j>=2)j/2;则其时间复杂度为：O!nlog2nJ三、判断题(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=0;for(i=l;i<n+1;i+)for(j=n;j>