《数据结构c++版课后习题解析.doc》由会员分享，可在线阅读，更多相关《数据结构c++版课后习题解析.doc（80页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 绪 论11.1 本章导学11.2 习题解析2第 2 章 线性表92.1 本章导学92.2 习题解析10第 3 章 栈和队列193.1 本章导学193.2 习题解析20第 4 章 字符串和多维数组264.1 本章导学264.2 习题解析27第 5 章 树和二叉树325.1 本章导学325.2 习题解析33第 6 章 图436.1 本章导学436.2 习题解析44第 7 章 查找技术567.1 本章导学567.2 习题解析57第 8 章 排序技术678.1 本章导学678.2 习题解析68第 9 章 索引技术789.1 本章导学789.2 习题解析78第 1 章 绪 论1.1 本章导学
2、1. 知识结构图 本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。数据数据元素数据结构抽象数据类型逻辑结构数据结构的分类存储结构常用存储方法算法算法特性评价算法描述算法问题规模基本语句时间复杂度大O记号图1-1 知识结构图绪 论数据结构算 法基本概念逻辑结构存储结构基本概念算法分析关 系2. 学习要点对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以
3、后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法的效率。1.2 习题解析1. 填空（1）（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素（2）（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。（3）从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。【解答】集合，线性结构，树结构、图结构（4）数据的存储结构主要有（ ）和（ ）两种
4、基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系（5）算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码（7）在一般情况下，一个算法的时间复杂度是（ ）的函数。【解答】问题规模（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为2n*log25n
5、+ 8n，则表示成数量级的形式为（ ）。【解答】(1)，(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2. 选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；
6、子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（ ）。A 树 B 图 C 线性表 D 集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据继承关系画出逻辑结构图如图1-2丈夫妻子子女n子女1图1-2 遗产继承逻辑结构图所示。（3）计算机所处理的数据一般具有某种内在联系，这是指（ ）。A 数据和数据之间存在某种关系 B 元素和元素之间存在某种关系C 元素内部具有某种结构 D 数据项和数据项之间存在某种关系【解答】B【分析】数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般
7、不予考虑。（4）对于数据结构的描述，下列说法中不正确的是（ ）。A 相同的逻辑结构对应的存储结构也必相同B 数据结构由逻辑结构、存储结构和基本操作三方面组成C 对数据结构基本操作的实现与存储结构有关D 数据的存储结构是数据的逻辑结构的机内实现【解答】A【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺序存储也可以链接存储，在顺序存储和链接存储结构下插入操作的实现截然不同。（5）可以用（ ）定义一个完整的数据结构。A 数据元素 B 数据对象 C 数据关系 D 抽象数据类型【解答】D【分析】抽象数据类型是一个数据结构以及定义在该结构
8、上的一组操作的总称。（6）算法指的是（ ）。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（7）下面（ ）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法应具备的特性。（8）算法分析的目的是（ ），算法分析的两个主要方面是（ ）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系C 分析算法的效率以求改进 D 分析算法的易读性和文档性E 空间
9、性能和时间性能 F 正确性和简明性G 可读性和文档性 H 数据复杂性和程序复杂性【解答】C，E3. 判断题 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。 每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。 逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。 基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答】错。基本操作的实现是
10、基于某种存储结构设计的，因而不是唯一的。4. 分析以下各程序段，并用大O记号表示其执行时间。 i = 1; k = 0; while (i = n) k = k + 10 * i;i+; i = 1; k = 0; do k = k + 10 * i;i+; while (i = n); y = 0; while (y + 1) *(y + 1) = n) y = y + 1; i = 1; j = 0;while (i + j j) j+; else i+; for (i = 1; i = n; i+) for (j = 1; j = i; j+) for (k = 1; k = j; k+
11、) x+;【解答】 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2n，所以T(n)=O(n1/2)。 x+是基本语句，所以 5解答下列问题（1）设有数据结构（D，R），其中D = 1, 2, 3, 4, 5, 6，R = (1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5),(4,
12、6)。试画出其逻辑结构图并指出属于何种结构。142563图1-3 逻辑结构图【解答】其逻辑结构图如图1-3所示，它是一种图结构。（2）为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下： ADT integer Data 整数：可以是正整数(1, 2, 3, )、负整数(-1, -2, -3, )和零 Operation Constructor 前置条件：整数a不存在 输入：一个整数b 功能：构造一个与输入值相同的整数 输出：无 后置条件：整数a具有输入的值 Set 前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同 输出：无 后置条件：整数a的值发生改变 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生改变 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果
