第一章绪论练习题一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的______以及它们之间的______和运算等的学科。

2.数据结构被形式地定义为（D,R），其中D是______的有限集合，R是D上的______有限集合。

3.数据结构包括数据的______、数据的______和数据的______这三个方面的内容。

4.数据结构按逻辑结构可分为两大类，它们分别是______和______。

5.线性结构中元素之间存在______关系，树形结构中元素之间存在______关系，图形结构中元素之间存在______关系。

6．在线性结构中，第一个结点______前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点______后继结点，其余每个结点有且只有1个后继结点。

7.在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点；叶子结点没有______结点，其余每个结点的后继结点数可以______。

8.在图形结构中，每个结点的前驱结点数和后继结点数可以______。

9．数据的存储结构可用四种基本的存储方法表示，它们分别是______。

10.数据的运算最常用的有5种，它们分别是______。

11.一个算法的效率可分为______效率和______效率。

12.计算机专业人员必须完成的两项基本任务是：______和______。

13.数据在计算机存储器中的存在形式称为______。

14.概括地说，数据结构课程的主要内容包括:数据的______、定义在______、数据的______的实现。

此外，该课程还要考虑各种结构和实现方法的______。

15.由一种______结构和一组______构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

16.存储结构是逻辑结构的______实现。

17.数据表示任务是逐步完成的，即数据表示形式的变化过程是______->______->______。

18.数据处理任务也是逐步完成的，即转化过程是______->______->______。

19.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即______、______和______。

20.根据需要，数据元素又被称为______、______、______或______。

21.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标识单位。

22.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个__________构成，数据元素可由若干个__________构成。

23.根据数据元素之间关系的不同特性，通常有__________、_________、__________、__________四类基本逻辑结构，它们反映了四类基本的数据组织形式。

24.根据操作的效果，可将运算分成以下两种基本类型：A）__________型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；B）__________型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。

25.将以某种逻辑结构S为操作对象的运算称为“__________”，简称“__________”。

26.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。

在这种情况下，称A可以“__________”为B。

27.存储实现的基本目标是建立数据的__________。

28.一般地，一个存储结构包括__________、__________、__________三个主要部分。

29.通常，存储结点之间可以有__________、__________、__________、_________四种关联方式，称为四种基本存储方式。

30.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑结构S中数据元素之间的逻辑关系。

由此得到的存储结构，称为____________________或__________。

31.一个运算的实现是指一个完成该运算功能的__________。

运算实现的核心是处理步骤的规定，即___________。

32.任何算法都必须用某种语言加以描述。

根据描述算法的语言的不同，可将算法分为：___________、___________、___________三类。

33.数据结构课程着重评论算法的___________，又称为“___________”。

34.通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。

35.一个算法的时空性能是指该算法的___________和______________________，前者是算法包含的___________，后者是算法需要的___________。

36.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：①根据该类问题的特点合理地选择一种或几种操作作为“___________”；②确定每个算法在给定输入下共执行了多少次___________，并将此次数规定为该算法在给定输入下的___________。

37.通常，一个算法在不同输入下的计算量是不同的。

则可用以下两种方式来确定一个算法的计算量：①以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的________或___________。

②以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的___________或___________。

38.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。

39.在一般情况下，一个算法的时间复杂性是___________的函数。

40.一个算法的输入规模或问题的规模是指___________。

41.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O(___________)、平方阶O(___________)、和指数阶O(___________)。

通常认为，具有指数阶量级的算法是___________，而量级低于平方阶的算法是___________的。

42.数据结构的基本任务是数据结构的___________和___________。

43.数据结构的课程的主要内容可以概括为：___________、___________、___________和___________。

44.___________与数据元素本身的内容和形式无关。

45.从逻辑关系上讲，数据结构主要分为两大类，它们是___________和___________。

46.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)=___。

47.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)=_____。

二、单项选择题（）1.非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（）2.数据结构中，与所使用的计算机无关的是数据的结构；A)存储B)物理C)逻辑D)物理和存储（）3.算法分析的目的是：A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性（）4.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（）5.计算机算法指的是：A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法（）6.计算机算法必须具备输入、输出和等5个特性。

A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性（）7.以下说法错误的是A）用数字式计算机解决问题的实质是对数据的加工处理B）程序设计的实质是数据处理C）数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式D）运算实现是完成运算功能的算法，或这些算法的设计E）数据处理方式总是与数据某种相应的表示形式相联系，反之亦然（）8.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。

以下解释错误的是A）集合中任何两个结点之间都有逻辑关系但组织形式松散B）线性结构中结点按逻辑关系依次排列形成一条"锁链"C）树形结构具有分支、层次特性，其形态有点像自然界中的树D）图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接（）9.关于逻辑结构，以下说法错误的是A）逻辑结构与数据元素本身的形成、内容无关B）逻辑结构与数据元素的相对位置有关C）逻辑结构与所含结点个数无关D）一些表面上很不相同的数据可以有相同的逻辑结构E）逻辑结构是数据组织的某种"本质性"的东西（）10.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。

对于表格处理中的五种功能以下解释错误的是A）查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置B）读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容C）插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点D）删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点E）更新加工型运算，功能是修改s(线形结构)中某指定结点的内容（）11.一般地，一个存储结构包括以下三个主要部分。

以下说法错误的是A）存储结点每个存储结点可以存放一个或一个以上的数据元素B）数据元素之间关联方式的表示也就是逻辑结构的机内表示C）附加设施，如为便于运算实现而设置的“哑结点”等等（）12.一般地，一个存储结构包括以下三个主要部分。

以下说法错误的是A）每个存储结点只能存放一个数据元素B）数据元素之间的关联方式可由存储结点之间的关联方式直接表达C）一种存储结构可以在两个级别上讨论。

其一是机器级，其二是语言级D）语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示（）13.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。

以下解释错误的是A）正确性算法应能正确地实现预定的功能(即处理要求)B）易读性算法应易于阅读和理解以便于调试修改和扩充C）健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D）高效性即达到所需要的时间性能（）14.对于数据结构课程的主要内容，以下解释正确的是A）数据结构的定义，包括逻辑结构、存储结构和基本运算集B）数据结构的实现，包括存储实现、运算实现和基本运算集C）数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择（）15.与数据元素本身的形式、内容、相对位置、个数无关的是数据的A）存储结构B）存储实现C）逻辑结构D）运算实现（）16.顺序存储结构A）仅适合于静态查找表的存储B）仅适合于动态查找表的存储C）既适合静态又适合动态查找表的存储D）既不适合静态又不适合动态查找表的存储（）17.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点A）正确B）错误（）18.以下说法正确的是A）所谓数据的逻辑结构指的是数据元素之间的逻辑关系。