数据结构第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 ）两大类。【武汉交通科技大学1996】
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
二、填空题
1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。
2①数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。
三、判断题
（F）1①数据元素是数据的最小单位。
（T ）2①记录是数据处理的最小单位。
（ F ）3①数据的逻辑结构是指数据的各数据项之间的逻辑关系。
（T ）4①数据的物理结构是指数据在计算机内的实际存储形式。
四、简答题
1①简述什么是数据结构?
2②数据结构与数据类型有什么区别? 【哈尔滨工业大学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++）
x++;
时间复杂度为（ C ）。
A ．O （1）
B ．O （n ）
C ．O （2n ）
D ．O （3n ）
4② 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000】
A ．效率
B ．复杂性
C ．现实性
D ．难度
5② 算法的时间复杂度取决于（ C ）【中科院计算所 1998】
A ．问题的规模
B ．待处理数据的初态
C ．A 和B
6② 下面关于算法说法错误的是（ A ）【南京理工大学 2000】
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 （ A[j]>A[j+1]）
A[j]与A[j+1]对换；
其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）【南京理工大学1998】
A ．O （n ）
B ．O （2log n n ）
C ． O （3n ）
D ． O （2n ）
二、填空题
1① 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。 2① 一个算法的效率可分为___时间______效率和__空间_______效率．
3②有一个程序片断如下：
for（i=0;i x=x+1; 则其时间复杂度为：_O（n）________ 4②有一个程序片断如下： for（i=0;i for（j=i;j for（k=j;k m=1; 则其时间复杂度为：O（n3） 5②有一个程序片断如下： for（i=0;i j=i; while（j>=2） j=j/2; } log n） 则其时间复杂度为：O（n 2 三、判断题 （T ）1①算法的优劣与算法描述语言无关，但与所用计算机有关。 （T ）2①健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （ F ）3①程序一定是算法。 四、简答题 1①如何判断一个算法的好坏? 2③调用下列C 函数f（n）回答下列问题： （1）试指出f（n）值的大小，并写出f（n）值的推导过程； （2）假定n= 5，试指出f（5）值的大小和执行f（5）时的输出结果。 C 函数： int f（int n） { int i,j，k,sum= 0; for（i=l; i { for（j=n;j>i-1; j--） for（k=1;k sum++; printf（"sum=%d\n",sum）; } return （sum）; } 【华中理工大学2000】