数据结构名词解释
忽悠网-农业经济学
2023年2月15日发(作者：我的语文老师作文500字)1.6习题
一、名词解释
1.数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
结构，就是数据之间的关系，即数据与数据之间的排列方式。
2.数据元素：是有一定意义数据的基本单位，可由若干个数据项组成，在计算机中通
常作为整体处理，也可称为结点、记录。
如：在人类社会中，一个“人”是一个数据元素，是有一定意义的作为整体处理的基本
单位，在社会关系里，一般都是拿某个人说事儿，不会拿某个人的胳膊或腿儿说事儿；
但在医学结构上，人又由若干部分组成，比如四肢、心、肝、脾、肺、肾等。
3.数据项：是具有独立含义的最小标识单位。如一个“人”有眼睛、耳朵、手等数据
项，也可有姓名、年龄、性别等这些数据项。一个记录可称为一个数据元素，而这个元素中
的某一字段就是一个数据项。
4.逻辑结构有时也称数据结构，它是数据元素之间关系的描述，可以看作是从具体问
题抽象出来的数学模型，与数据的存储无关，是独立于计算机的。
5.物理结构是数据的逻辑结构在计算机中的表示和实现，也称存储结构。
6.时间复杂度：当问题规模很大时，程序执行时间随问题规模增长程度的一个度量。
7.空间复杂度：是指程序运行从开始到结束所需的存储量。
二、判断题
（1）数据元素是最小的项。（×）
（2）算法就是程序。（×）
（算法是解决问题的有限指令序列，它可以用某个具体的程序来表示，也可以用自然语
言、流程图、伪代码表示。
即可以用程序来表达算法，但算法不见得就是程序。
目前，用来表达算法用得最多的是伪代码，因为伪代码比具体的程序要求宽松、易理解，
同时又比自然语言更容易转换成可实现的程序。）
（3）数据结构是数据对象与对象中数据元素之间关系的集合。（√）
(4)从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。(√)
(5)数据的逻辑结构与数据元素本身的内容和形式无关。(√)
三、填空题
（1）算法的一个特性是确定性，即针对一组确定的输入，算法应始终得出一组确定的
结果。
（2）算法的一个特性是有穷性，即算法必须执行有限步就结束。
（3）数据是_信息的载体，它能够被计算机程序识别、存储和加工处理。
（4）此题不严谨。
数据结构是带结构的数据元素的集合，因此，可以说数据结构由“数据”和“结构”
两个元素组成；
另外，一般讨论一个具体的数据结构时,我们会讨论它的_逻辑数据、物理结构和数
据的运算三个方面。
(就像“土豆炒牛肉”由土豆和牛肉两样主菜组成，当我们讨论这个菜品时,会讨论它的
色、香、味三个方面。)
（5）数据结构的逻辑结构包括线性结构和非线性结构结构两大类。
四、简答题
1.数据结构中数据元素之间的逻辑关系可以由四种基本数据关系组成，简述它们的名
称与含义。
答：
（1）集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素
关系极为松散的一种结构。
（2）线性结构：该结构的数据元素之间存在着“一对一”的关系。
（3）树型结构：该结构的数据元素之间存在着“一对多”的关系。
（4）图形结构：该结构的数据元素之间存在着“多对多”的关系。
2.简述算法的特性。
答：
（1）有穷性。一个算法必须在有穷步之后结束，即必须在人类现有的寿命长度下、有
现实意义的有限时间内完成。如你编写算法，计算机需要30年的时间才能结束，算法的意
义就不大。
（2）确定性。算法的每一步必须有确切的定义，无二义性。相同的输入仅有唯一的输
出结果。(比如:"小明对小强说他的爸爸去出差了"就是一个歧义句。)
（3）可行性。算法中的每一步都可实现，即每一步都在当前环境条件下可以通过有限
次运算实现。
（4）输入。一个算法具有零个或多个输入，可以没有输入。
（5）输出。一个算法具有一个或多个输出，至少有一个输出。(没有输出对我们人类就
没有反馈,那么这个算法就没有意义。)
3.设计一个好的算法通常要考虑哪些要求？
要设计一个好的算法通常要考虑以下的要求。
（1）正确性。算法的执行结果应当满足预先规定的功能和性能要求。
“正确性”的含义是所设计的程序没有语法错误，对于刁难性的数据也能够得到满足要
求的输出结果。
（2）可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂。
一个好的算法首先应该是便于交流，其次才是机器可执行，可读性好的算法有助于编程
人员对算法的理解，而难懂的算法对于隐藏的错误不易调试和修改。
（3）健壮性（鲁棒性）。当输入不合法数据时，应能作适当处理，不至引起严重后果，
陷入死机。
（4）高效率和低存储量。有效使用存储空间和有较高的时间效率。
4.常用算法大致可以分为几大类？
答：常用的算法大致可以被分为蛮力算法、分治算法、减治算法、变治算法以及动态规
划算法等几大类。
五、观察下列算法回答以下问题。
（1）每一个算法的意图是什么？
（2）每一个算法的关键步骤是什么？
（3）每一个算法的关键步骤执行了多少步？
（4）算法的时间复杂度是什么？
①for(i=0;i for(j=0;j a++; 答： 算法意图：变量a自增n2次； 算法的关键步骤：a++; 关键步骤执行次数：n2次； 算法的时间复杂度：T(n)=O（n2） ②for(i=0;i for(j=i;j x++; 答： 算法意图：什么也不做； 算法的关键步骤：x++; 关键步骤执行次数：0次； 算法的时间复杂度：T(n)=O（1） 分析： 虽然看起来是双层循环,但第二次循环for(j=i;j 条件而不执行；所以事实上第一层循环的任何一次执行，都是什么也不做。 无论问题规模n为多少，关键步骤“x++;”的执行次数都为0次。常量阶的时间复杂度 记为T(n)=O（1）。 ③i=1; 答： 算法意图：将i的值赋值为1； 算法的关键步骤：i=1; 关键步骤执行次数：1次； 算法的时间复杂度：T(n)=O（1）