数据结构第1章答案(已核)

1、1.6 习题一、名词解释1. 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。结构，就是数据之间的关系，即数据与数据之间的排列方式。2. 数据元素：是有一定意义数据的基本单位，可由若干个数据项组成，在计算机中通常作为整体处理，也可称为结点、记录。如：在人类社会中，一个“人”是一个数据元素，是有一定意义的作为整体处理的基本单位，在社会关系里，一般都是拿某个人说事儿，不会拿某个人的胳膊或 腿儿 说事儿；但在医学结构上，人又由若干部分组成，比如四肢、心、肝、脾、肺、肾等。3. 数据项：是具有独立含义的最小标识单位。如一个“人”有眼睛、耳朵、手等数据项，也可有姓名、年龄、性别等这些数据项。一

2、个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。4. 逻辑结构有时也称数据结构，它是数据元素之间关系的描述，可以看作是从具体问题抽象出来的数学模型，与数据的存储无关，是独立于计算机的。5. 物理结构是数据的逻辑结构在计算机中的表示和实现，也称存储结构。6. 时间复杂度： 当问题规模很大时，程序执行时间随问题规模增长程度的一个度量。7. 空间复杂度：是指程序运行从开始到结束所需的存储量。二、判断题(1)数据元素是最小的项。(X)(2)算法就是程序。(X )(算法是解决问题的有限指令序列，它可以用某个具体的程序来表示，也可以用自然语言、流程图、伪代码表示。即可以用程序来表达算法，但

3、算法不见得就是程序。目前， 用来表达算法用得最多的是伪代码，因为伪代码比具体的程序要求宽松、易理解，同时又比自然语言更容易转换成可实现的程序。)(3)数据结构是数据对象与对象中数据元素之间关系的集合。(V )(4) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。(5)数据的逻辑结构与数据元素本身的内容和形式无关。(，)三、填空题(1)算法的一个特性是 确定性，即针对一组确定的输入，算法应始终得出一组确定的 结果。(2)算法的一个特性是 有穷性，即算法必须执行有限步就结束。(3)数据是信息的载体,它能够被计算机程序识别、存储和加工处理。(4)此题不严谨。数据结构是带结构的数据元素

4、的集合，因此，可以说数据结构由“数据”和“结构”两个元素组成；另外，一般讨论一个具体的 数据结构时，我们会讨论它的一逻辑数据、物理结构和婺 据的运算三个方面。(就像“土豆炒牛肉”由土豆和牛肉两样主菜组成，当我们讨论这个菜品时，会讨论它的色、香、味三个方面。)(5)数据结构的逻辑结构包括线性结构 和 非线性结构 结构两大类。四、简答题1 .数据结构中数据元素之间的逻辑关系可以由四种基本数据关系组成，简述它们的名 称与含义。答:O集合是元素(1)集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”关系极为松散的一种结构。(2)线性结构：该结构的数据元素之间存在着“一对一”的关系。(3)树型

5、结构：该结构的数据元素之间存在着“一对多”的关系。(4)图形结构：该结构的数据元素之间存在着“多对多”的关系。2 .简述算法的特性。答：（ 1）有穷性。一个算法必须在有穷步之后结束，即必须在人类现有的寿命长度下、有现实意义的有限时间内完成。如你编写算法，计算机需要30 年的时间才能结束，算法的意义就不大。（ 2）确定性。算法的每一步必须有确切的定义，无二义性。相同的输入仅有唯一的输出结果。（比如 : 小明对小强说他的爸爸去出差了就是一个歧义句。）（ 3）可行性。算法中的每一步都可实现，即每一步都在当前环境条件下可以通过有限次运算实现。（ 4）输入。一个算法具有零个或多个输入，可以没有输入。（

6、5） 输出。 一个算法具有一个或多个输出，至少有一个输出。（ 没有输出对我们人类就没有反馈, 那么这个算法就没有意义。）（ . 设计一个好的算法通常要考虑哪些要求？要设计一个好的算法通常要考虑以下的要求。（ 1）正确性。算法的执行结果应当满足预先规定的功能和性能要求。“正确性”的含义是所设计的程序没有语法错误，对于刁难性的数据也能够得到满足要求的输出结果。（ 2）可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂。一个好的算法首先应该是便于交流，其次才是机器可执行，可读性好的算法有助于编程人员对算法的理解，而难懂的算法对于隐藏的错误不易调试和修改。（ 3） 健壮性 （鲁棒性）。 当输入

7、不合法数据时，应能作适当处理，不至引起严重后果，陷入死机。（ 4）高效率和低存储量。有效使用存储空间和有较高的时间效率。4. 常用算法大致可以分为几大类？答：常用的算法大致可以被分为蛮力算法、分治算法、减治算法、变治算法以及动态规划算法等几大类。五、观察下列算法回答以下问题。（ 1 ）每一个算法的意图是什么？（ 2）每一个算法的关键步骤是什么？( 3)每一个算法的关键步骤执行了多少步？( 4)算法的时间复杂度是什么？ for(i=0;in;i+)for(j=0;jn;j+)a+;答：算法意图：变量a自增n2次；算法的关键步骤：a+;关键步骤执行次数：n2次；算法的时间复杂度：T(n)=O( n2) for(i=0;in;i+)for(j=i;ji;j+)x+;答：算法意图：什么也不做；算法的关键步骤：x+;关键步骤执行次数：0 次；算法的时间复杂度：T(n)=O( 1)分析：虽然看起来是双层循环, 但 第二次循环for(j=i;ji;j+) 的循环体因为不满足ji 的条件而不执行；所以事实上第一层循环的任何一次执行，都是什么也不做。无论问题规