文档介绍：自考数据结构课后****题答案本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系, 难点是算法复杂度的分析方法。需要达到< 识记> 层次的基本概念和术语有: 数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。需要达到< 领会> 层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念, 算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。对于基本概念,仔细看书就能够理解,这里简单提一下: 数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位,有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中, 10 这个数就可称是一个数据元素. 又比如在一个数据库( 关系式数据库)中, 一个记录可称为一个数据元素,而这个元素中的某一字段就是一个数据项。数据结构的定义虽然没有标准, 但是它包括以下三方面内容: 逻辑结构、存储结构、和对数据的操作。这一段比较重要,我用自己的语言来说明一下,大家看看是不是这样。比如一个表( 数据库) ,我们就称它为一个数据结构,它由很多记录( 数据元素) 组成,每个元素又包括很多字段( 数据项) 组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点( 其实也就是元素、记录、顶点, 虽然在各种情况下所用名字不同,但说的是同一个东东) 之间的关系来分析的,对于这个表中的任一个记录( 结点) ,它只有一个直接前趋, 只有一个直接后继( 前趋后继就是前相邻后相邻的意思), 整个表只有一个开始结点和一个终端结点, 那我们知道了这些关系就能明白这个表的逻辑结构了。而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表, 在计算机语言中描述为连续存放在一片内存单元中,还是随机的存放在内存中再用指针把它们链接在一起,这两种表示法就成为两种不同的存储结构。(注意,在本课程里,我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算, 比如一张表格, 我们需要进行查找, 增加, 修改, 删除记录等工作, 而怎么样才能进行这样的操作呢? 这也就是数据的运算, 它不仅仅是加减乘除这些算术运算了, 在数据结构中, 这些运算常常涉及算法问题。弄清了以上三个问题,就可以弄清数据结构这个概念。通常我们就将数据的逻辑结构简称为数据结构, 数据的逻辑结构分两大类: 线性结构和非线性结构( 这两个很容易理解) 数据的存储方法有四种: 顺序存储方法、链接存储方法、索引存储方法和散列存储方法。下一个是难点问题,就是算法的描述和分析,主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度, 一个是渐近时间复杂度。前者是某个算法的时间耗费, 它是该算法所求解问题规模 n 的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。当我们评价一个算法的时间性能时, 主要标准就是算法的渐近时间复杂度, 因此, 在算法分析时, 往往对两者不予区分,经常是将渐近时间复杂度 T(n)=O(f(n) 简称为时间复杂度,其中的 f(n) 一般是算法中频度最大的语句频度。此外, 算法中语句的频度不仅与问题规模有关, 还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度, 按数量级递增排列依次为: 常数阶 O(1) 、对数阶 O(log2n) 、线性阶 O(n) 、线性对数阶 O(nlog2n) 、平方阶 O(n^2) 、立方阶 O(n^3) 、k 次方阶 O(n^k) 、指数阶 O(2^n) 。时间复杂度的分析计算请看书本上的例子,然后我们通过做练****加以领会和巩固。[size=+3] 数据结构****题一 简述下列概念:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。◆数据:指能够被计算机识别、存储和加工处理的信息载体。◆数据元素:就是数据的基本单位,在某些情况下,数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。◆数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。◆数据结构: 指的是数据之间的相互关系, 即数据的组织形式。一般包括三个方面的内容: 数据的逻辑结构、存储结构和数据的运算。◆逻辑结构:指各数据元素之间的逻辑关系。◆存储结构:就是数据的逻辑结构用计算机语言的实现。◆线性结构:数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。◆非