数据结构-C++-王红梅版-课后答案.doc

在数据结构的学习中，我们首先需要了解一些基础概念。数据元素是数据的基本单位，而数据项则是数据的最小单位，讨论数据构造时涉及的最小数据单位。数据构造从逻辑关系上可以分为集合、线性构造、树构造和图构造。在存储构造方面，数据的存储构造主要有顺序存储构造和链接存储构造两种基本方式，这两种方式都需要存储数据元素及其之间的关系。此外，数据的存储构造也关注数据的物理组织形式，比如数组、链表、散列表等。 算法是解决特定问题求解步骤的一种描述，它具有五个特性，分别是：有零个或多种输入、有一种或多种输出、有穷性、确定性和可行性。算法的描述方式有自然语言、程序设计语言、流程图、伪代码等，其中伪代码是算法语言的一种，既具有形式化结构又便于理解和阅读。算法的时间复杂度是问题规模的函数，通常用大O记号表达，它忽略了低次幂和最高次幂系数，只关注最高次幂的增长趋势。时间复杂度是衡量算法执行效率的重要指标。 在数据结构的具体应用中，顺序存储构造中数据元素之间的逻辑关系由存储位置决定，而链接存储构造中数据元素之间的逻辑关系是由指针表达的。针对特定问题，选择合适的数据结构是至关重要的，如遗产继承规则更适合用图来表示，因为其包含了复杂的父子和夫妻之间的继承关系。算法在描述上应当是具有确切性、有穷性和可行性的，而效率性是好算法应具有的特性。 算法分析的目的在于分析算法的效率以便改善，其重要方面包括空间性能和时间性能。数据的逻辑构造是指数据之间逻辑关系的整体，而逻辑构造与数据元素自身的内容和形式无关。数据结构中每种数据构造都有一系列的基本操作，但这些操作的实现并非唯一，因为它们是基于存储构造设计的。 在实际问题解决中，我们常常需要分析程序段的时间复杂度。比如一个循环执行n-2次的基本语句k=k+10*i，其时间复杂度可以用大O记号表示为O(n)。类似地，其他程序段也可以通过分析其循环次数、操作复杂度来计算时间复杂度。 数据结构中还会涉及到一些具体的逻辑构造图示，例如通过数据集合D和关系R构造出的图形，这要求我们能够准确地画出对应的图形，并分析其属于何种构造类型，比如树、图等。通过这些图形，我们能够更直观地理解和分析数据之间的逻辑关系。