数据结构（本）辣程帕导与练习一第1章 第1章堵论 一、数无结构的凝念和相关术语 本章介铅数据结构的基本概念和相关术语，简单介馆算法、算法的特征及算法时间复杂 度和空间复桑度的概念： ·数据 数据（购）是描述和量化客观事物和信息等的符号，在计算机领域是指所有能输入计 算机并能被计算机系统和程序识别、存储、如工和处理的符号的总称。包括数字、字符、图 像和声音等。 ·数据元素(dat由element) 数据元素是数据的基本单位，在计算机程序中通常把数据元素作为一个整体米存储和处 理。数据元素可由一个或若干个数据项组成，数据项是数据的不可分刺的最小单位。 ·数据项 数据项是数据不可分刺的，具有独立含义的最小数据单位。 数据元素可以具是单个的数据项，例如学生的年静就是一个数据元素。数据元素也可以 由多个数据项复合组成，例如根据需要可以把学生的相关信息如学号、姓名、年龄、性别、 电话号码等多个数据项组成一个数据元素统一处理。数据元素在许多应用中又被称为记录。 ·数据对象 数据对象是数据的一个子集，是性质相同的数据的集合。 。数据结构 数据站构是相互之间存在的一种成多种特定关系的数据元素的集合，数据元素间的关系 称为结构。 数据结构一般包括以下三方面内容： (1)数据元素之间的逐辑关系，也称数据的逐辑结构(L0 gical Structure》·数据的逻 辑结构是从逻辑关系上描述数据，与数据的存销无关，是鞋立于计算机的，数据的逻铜结构 可以看作是从具体月题拍象出来的数学模型。 (2)数据元素及其关系在计算机存储署内的表示，称为数据的存储结构(Ss Structure)。数据的存储结构是逐辑结构用计算机语言的实现（亦称为骏象），它依赖于计
数据结构（本）课程辅导与练习－第 1 章 第 1 章 绪论 一、数据结构的概念和相关术语 本章介绍数据结构的基本概念和相关术语，简单介绍算法、算法的特征及算法时间复杂 度和空间复杂度的概念。 ● 数据 数据（data）是描述和量化客观事物和信息等的符号，在计算机领域是指所有能输入计 算机并能被计算机系统和程序识别、存储、加工和处理的符号的总称。包括数字、字符、图 像和声音等。 ● 数据元素（data element） 数据元素是数据的基本单位，在计算机程序中通常把数据元素作为一个整体来存储和处 理。数据元素可由一个或若干个数据项组成，数据项是数据的不可分割的最小单位。 ● 数据项 数据项是数据不可分割的，具有独立含义的最小数据单位。 数据元素可以只是单个的数据项，例如学生的年龄就是一个数据元素。数据元素也可以 由多个数据项复合组成，例如根据需要可以把学生的相关信息如学号、姓名、年龄、性别、 电话号码等多个数据项组成一个数据元素统一处理。数据元素在许多应用中又被称为记录。 ● 数据对象 数据对象是数据的一个子集，是性质相同的数据的集合。 ● 数据结构 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据元素间的关系 称为结构。 数据结构一般包括以下三方面内容： （1）数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）。数据的逻 辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构 可以看作是从具体问题抽象出来的数学模型。 （2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计
算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存他结 构。 (3》数据的运算。即对要据能加的慢作。数据的运算定义在数据的亚辑结构上，每种 逻细结构都有一个运算的集合。最常用的检常、插入、刷除、更新、排序等运算实际上具是 在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我门只知道这线操作是做什么”，而无须考感如何敏？。只有确 定了存储结构之后，才考虑如何具体实现这些运算。 ·数据结构研究的内容 数据结构研究的内容是： (1)研究数据元素之间因有的客观联系《逻辑结构) (2)研究数据在计算机内部的存储方法（存储结构） (3)研究如何在数据的各种结构（逻辑和物理）上实连有效的操作《算法】 ·数据的逻辑结构 数架的逻辑结构是指数据元素之间的逻辑关系，是用户根据使用需要建立起来的数据组 织形式，是鞋立于计算机的. 根据数据元素之间的不同关系，有以下四种基本正辑结构。 (1)集合：结构中的数据除了“同属于一个集合“的关系外，不存在其它关系。 (2)线性结构：结构中的数据元素的位置之间存在一对一的关系。 (3)树形结构：结构中的元素之间存在一对多的关系。 (4)图状结构：结构中的数据元素存在多对多的关系。图状结构又称网状结构。 如图教材11所示。 数据的速辑结构可概括为两大类：线性结构和非线性结构。 ·数据的存销结构 数据的存储结构又称物理结构，是数据的逐辑结构在计算机存储墨中的存储形式（或称 陕象)。对机器语言来说，这种存储形式是具体的，高领语言可以借尉它的数据类型采描述 存储形式的具体细节。依据数据元素在计算机中的表示，主要有以下四种不月的存储结构
算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结 构。 （3） 数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种 逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是 在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确 定了存储结构之后，才考虑如何具体实现这些运算。 ● 数据结构研究的内容 数据结构研究的内容是： （1）研究数据元素之间固有的客观联系（逻辑结构） （2）研究数据在计算机内部的存储方法（存储结构） （3）研究如何在数据的各种结构（逻辑和物理）上实施有效的操作（算法） ● 数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系，是用户根据使用需要建立起来的数据组 织形式，是独立于计算机的。 根据数据元素之间的不同关系，有以下四种基本逻辑结构。 （1）集合：结构中的数据除了“同属于一个集合”的关系外，不存在其它关系。 （2）线性结构：结构中的数据元素的位置之间存在一对一的关系。 （3）树形结构：结构中的元素之间存在一对多的关系。 （4）图状结构：结构中的数据元素存在多对多的关系。图状结构又称网状结构。 如图教材 1-1 所示。 数据的逻辑结构可概括为两大类：线性结构和非线性结构。 ● 数据的存储结构 数据的存储结构又称物理结构，是数据的逻辑结构在计算机存储器中的存储形式（或称 映象）。对机器语言来说，这种存储形式是具体的，高级语言可以借助它的数据类型来描述 存储形式的具体细节。依据数据元素在计算机中的表示，主要有以下四种不同的存储结构
(1)顺序存储结构：是件助元素在存储器中的相对位置来表示数据元素之间的逻辑关 系，可用一推数组描述， (2)链式存他结构：是础助指示元素存储陆址的指针来表示数据元素之间的逻辑关系， 可用指针类型来精述 (3)素到存储结构：是在原有存销数据结构的基健上，附加建立一个素引表，素引表 中的每一项都由关键字和地址组成。采取素引存储结构的主要作用是提高数据的检素速度。 (4)酸列存销结构：是通过构迹散列函数来确定数暴存储地址或查找地址。 ·算法的假念 算法(g0hm)简言之就是解决特定月题的方法，是对特定月题求解步骤的一种描述。 或者说算法是为了解决列愿面规定的一个有限长的操作序列，是对解思过程的准确且完整的 描述。 ·算法的特任 算法具有五个基本特征： ①有穷性：算法的执行必類在有限步内结束。 ②确定性：算法的每一个步叠必须是确定的无二义性的。 ③输入：算法可以有0个咸多个输入： ①输出：算法一定有输出结果 ⑤可行性，算法中的运算都必须是可以实现的。 ·算法与程序的区别 主要表现在以下几个方面 (1)算法代表了对问题的求解过程，而程序则是算法在计算机上的实现，算法川特定 的程序设计语言来摇述，就成了程序。 《2)程序中的指◆必筑是机器可执行的，而算法中的指令则无此限制， (3)一个算法经须在有穷步之后结桌。一个程序不一定满足有穷性。 ·算法的描述 算法可以用流程图、白然语言、计算机程序设计语言（如C语言成类C语言）来描述， 但描述必须精确地说明过程
（1）顺序存储结构：是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关 系，可用一维数组描述。 （2）链式存储结构：是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系， 可用指针类型来描述。 （3）索引存储结构：是在原有存储数据结构的基础上，附加建立一个索引表，索引表 中的每一项都由关键字和地址组成。采取索引存储结构的主要作用是提高数据的检索速度。 （4）散列存储结构：是通过构造散列函数来确定数据存储地址或查找地址。 ● 算法的概念 算法（algorithm）简言之就是解决特定问题的方法，是对特定问题求解步骤的一种描述。 或者说算法是为了解决问题而规定的一个有限长的操作序列，是对解题过程的准确且完整的 描述。 ● 算法的特征 算法具有五个基本特征： ①有穷性：算法的执行必须在有限步内结束。 ②确定性：算法的每一个步骤必须是确定的无二义性的。 ③输入： 算法可以有 0 个或多个输入。 ④输出： 算法一定有输出结果 ⑤可行性：算法中的运算都必须是可以实现的。 ● 算法与程序的区别 主要表现在以下几个方面 （1）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特定 的程序设计语言来描述，就成了程序。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 （3）一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。 ● 算法的描述 算法可以用流程图、自然语言、计算机程序设计语言（如 C 语言或类 C 语言）来描述， 但描述必须精确地说明过程
·时间复杂度 算法的时间复杂度是评估算法的重要标准之一，它能较好地体现算法本身的时间效率， 面与具体实现算法的计算机软件、硬件无关。一个算法的执行时间等于其所有语句执行时间 的总和，而任一语句的执行封间为该语句执行次数与执行该语句一次所需时间的乘机。当算 法转换程序之后，每条语句的执行时间取决于机器的硬件速度、指令类型及编译的代码质量， 而这些是很难确定的。因此，将算法中重复执行的次数作为其执行时间的量度。 一般情况下，算法基本操作重复执行的次数是问题规校的某个函数。而算法的时 间复条度简单说来是指算法中某种基本操作执行次数的数量级。通常用TO)表示， 其中0表示育n)的数量级. ·空间复杂皮 一个程序的空间复杂度是指程序运行从开始到结束所需的存储空间，包括算法木身所占 用的存储空间。类似于算法的时间复杂度，算法所需存储空间的量度记作： S(n=O(fn)) 其中n为何恶的规模，算法所需存储空间是同恶规横n的函数直)： 二、练习题 《一》单项选释圈 1组成数据的基本单位是()， A。数据项 B.数据类型 C,数据元素D.数据变量 2.研究数据结构就是研究(》。 A。数据的边钳结构 B.数据的存销结构 C.数据的逻辑结构和存储结构 D。数据的逻辑结构和存储结构以及其数据在运算上的实现 3.在数据结构中，从逻辑上呵以把数据结构分成()。 A。动态结构和静老结构B。紧凑结构和非紧凑结构 C,线性结构和幸线性结构D,内翘结构和外部结构
● 时间复杂度 算法的时间复杂度是评估算法的重要标准之一，它能较好地体现算法本身的时间效率， 而与具体实现算法的计算机软件、硬件无关。一个算法的执行时间等于其所有语句执行时间 的总和，而任一语句的执行时间为该语句执行次数与执行该语句一次所需时间的乘机。当算 法转换程序之后，每条语句的执行时间取决于机器的硬件速度、指令类型及编译的代码质量， 而这些是很难确定的。因此，将算法中重复执行的次数作为其执行时间的量度。 一般情况下，算法基本操作重复执行的次数是问题规模 n 的某个函数 f(n)。而算法的时 间复杂度简单说来是指算法中某种基本操作执行次数的数量级。通常用 T(n)=O(f(n))表示， 其中 O 表示 f(n)的数量级。 ● 空间复杂度 一个程序的空间复杂度是指程序运行从开始到结束所需的存储空间。包括算法本身所占 用的存储空间。类似于算法的时间复杂度，算法所需存储空间的量度记作： S(n)=O(f(n)) 其中 n 为问题的规模，算法所需存储空间是问题规模 n 的函数 f(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下列关于算法的说法，正确的是()， A。算法最终必须由计算机程序实观 B,算法的可行性是指指令不從有二义性 C。为解决某问题的算法为与该问题编写的程序含义是相同的 D.。程序一定是算法 7.下列不是算法的基本特征的是()。 A,可行性 B,确定性 C,在规定的时问内完成 D.长度有限 8,一个算法型该是《)。 A。程序 B,风题求解步骤的描述 C,为要满足五个基本特征 D.A和C (二)填空思 1。数据的逻辑结构包括 和 四种类裂。 2.算法的5个特性是一一一 和
4．数据结构是一门研究计算机中（ ）对象及其关系的科学。 A．数值运算 B．非数值运算 C．集合 D．非集合 5．设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲 的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（ ）结构。 A．树形 B．图形 C．线性 D．集合 6．下列关于算法的说法，正确的是（ ）。 A．算法最终必须由计算机程序实现 B．算法的可行性是指指令不能有二义性 C．为解决某问题的算法为与该问题编写的程序含义是相同的 D．程序一定是算法 7．下列不是算法的基本特征的是（ ）。 A．可行性 B．确定性 C．在规定的时间内完成 D．长度有限 8．一个算法应该是（ ）。 A．程序 B．问题求解步骤的描述 C．为要满足五个基本特征 D．A 和 C （二）填空题 1．数据的逻辑结构包括 、 、 和 四种类型。 2．算法的 5 个特性是 、 、 、 和
3,线性结构中元素之问存在关系，树形结构中元素之间存在一关系，图形 结构中元素之间存在一· 4,存储结构主要有 四种。 然习题答案 (一)单项选释盟 1.C2.D3.C4.B5.B6.B7.D8.B (二) 1。集合结构线性结构树形结构图形结构《或网状结构) 2。有穷性、确定性、可行性、零个成多个输入，一个成多个输入 3。一对一一对多多对多 4。顺序存销结构链式存锦结构素引存储结构散列存储结构
3．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系， 图形 结构中元素之间存在 。 4．存储结构主要有 、 、 、 四种。 练习题答案 （一）单项选择题 1．C 2．D 3．C 4．B 5．B 6．B 7．D 8．B （二） 1．集合结构 线性结构 树形结构 图形结构（或网状结构） 2．有穷性、确定性、可行性、零个或多个输入、一个或多个输入 3．一对一 一对多 多对多 4．顺序存储结构 链式存储结构 索引存储结构 散列存储结构