数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性,而与其在计算机
内部如何表示和实现无关。无论其内部结构如何变化,只要它的数学特性不变就不影响它
的外部使用。抽象数据类型和数据类型实质上是一个概念。此外,抽象数据类型的范围更
广,它已不再局限于机器已定义和实现的数据类型,还包括用户在设计软件系统时自行定
义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分,封装在一
起,对用户透明(提供接口),而不必了解实现细节。抽象数据类型的出现使程序设计不
再是“艺术”,而是向“科学”迈进了一步。
4.(1)数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式
或“邻接关系”),数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及
其关系的表示。数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存
储结构无关,而运算的实现则是依赖于存储结构。
(2)逻辑结构相同但存储不同,可以是不同的数据结构。例如,线性表的逻辑结构属于
线性结构,采用顺序存储结构为顺序表,而采用链式存储结构称为线性链表。
(3)栈和队列的逻辑结构相同,其存储表示也可相同(顺序存储和链式存储),但由于
其运算集合不同而成为不同的数据结构。
(4)数据结构的评价非常复杂,可以考虑两个方面,一是所选数据结构是否准确、完整
的刻划了问题的基本特征;二是是否容易实现(如对数据分解是否恰当;逻辑结构的选择
是否适合于运算的功能,是否有利于运算的实现;基本运算的选择是否恰当。)
5.评价好的算法有四个方面。一是算法的正确性;二是算法的易读性;三是算法的健
壮性;四是算法的时空效率(运行)。
6.(1)见上面题 3 (2)见上面题 4 (3)见上面题 3
(4)算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该
算法输入的数据所含数据元素的数目,或与此数目有关的其它参数。有时考虑算法在最坏
情况下的时间复杂度或平均时间复杂度。
(5)算法是对特定问题求解步骤的描述,是指令的有限序列,其中每一条指令表示一个
或多个操作。算法具有五个重要特性:有穷性、确定性、可行性、输入和输出。
(6)频度。在分析算法时间复杂度时,有时需要估算基本操作的原操作,它是执行次数
最多的一个操作,该操作重复执行的次数称为频度。
7.集合、线性结构、树形结构、图形或网状结构。 8.逻辑结构、存储结构、操作
(运算)。
9.通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面:
程序运行时所需输入的数据总量,对源程序进行编译所需时间,计算机执行每条指令所需
时间和程序中指令重复执行的次数。
10.D 是数据元素的有限集合,S 是 D 上数据元素之间关系的有限集合。
11.“数据结构”这一术语有两种含义,一是作为一门课程的名称;二是作为一个科学
的概念。作为科学概念,目前尚无公认定义,一般认为,讨论数据结构要包括三个方面,
一是数据的逻辑结构,二是数据的存储结构,三是对数据进行的操作(运算)。而数据类
型是值的集合和操作的集合,可以看作是已实现了的数据结构,后者是前者的一种简化情
况。
12.见上面题 2。
13.将学号、姓名、平均成绩看成一个记录(元素,含三个数据项),将 100 个这
样的记录存于数组中。因一般无增删操作,故宜采用顺序存储。
typedef struct
{int num;//学号
评论0
最新资源