数据结构c++版课后习题解析

第 1 章绪论 (1)

1.1 本章导学 (1)

1.2 习题解析 (2)

第 2 章线性表 (8)

2.1 本章导学 (8)

2.2 习题解析 (9)

第 3 章栈和队列 (17)

3.1 本章导学 (17)

3.2 习题解析 (18)

第 4 章字符串和多维数组 (24)

4.1 本章导学 (24)

4.2 习题解析 (25)

第 5 章树和二叉树 (30)

5.1 本章导学 (30)

5.2 习题解析 (31)

第 6 章图 (40)

6.1 本章导学 (40)

6.2 习题解析 (41)

第7 章查找技术 (53)

7.1 本章导学 (53)

7.2 习题解析 (54)

第8 章排序技术 (63)

8.1 本章导学 (63)

8.2 习题解析 (64)

第9 章索引技术 (74)

9.1 本章导学 (74)

9.2 习题解析 (74)

第 1 章绪论

1.1 本章导学

1. 知识结构图

本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。

图1-1 知识结构图

2. 学习要点

对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。

在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法

1.2 习题解析

1. 填空

（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素

（2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

（3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构、图结构

（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系

（5）算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

（6）算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

（7）在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模

（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为2n*log25n + 8n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)

【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题

（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构

B 非线性结构

C 存储位置

D 指针

【解答】C，D

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（）。

A 树

B 图

C 线性表

D 集合

【解答】B

所示。

（3）计算机所处理的数据一般具有某种内在联系，这是指（ ）。

A 数据和数据之间存在某种关系

B 元素和元素之间存在某种关系

C 元素内部具有某种结构

D 数据项和数据项之间存在某种关系

【解答】B

【分析】数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据

结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。

（4）对于数据结构的描述，下列说法中不正确的是（ ）。

A 相同的逻辑结构对应的存储结构也必相同

B 数据结构由逻辑结构、存储结构和基本操作三方面组成

C 对数据结构基本操作的实现与存储结构有关

D 数据的存储结构是数据的逻辑结构的机内实现

【解答】A

【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，在不同的存储结构下

基本操作的实现是不同的，例如线性表可以顺序存储也可以链接存储，在顺序存储和链

接存储结构下插入操作的实现截然不同。

（5）可以用（ ）定义一个完整的数据结构。

A 数据元素

B 数据对象

C 数据关系

D 抽象数据类

型

【解答】D

【分析】抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。

（6）算法指的是（ ）。

A 对特定问题求解步骤的一种描述，是指令的有限序列。

B 计算机程序

C 解决问题的计算方法

D 数据处理

【解答】A

【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处

理是通过算法完成的。所以，只有A 是算法的准确定义。

（7）下面（ ）不是算法所必须具备的特性。

A 有穷性

B 确切性

C 高效性

D 可行性

【解答】C

【分析】高效性是好算法应具备的特性。

（8）算法分析的目的是（ ），算法分析的两个主要方面是（ ）。

A 找出数据结构的合理性

B 研究算法中输入和输出的关系

C 分析算法的效率以求改进

D 分析算法的易读性和文档性

图1-2 遗产继承逻辑结构图

E 空间性能和时间性能

F 正确性和简明性

G 可读性和文档性 H 数据复杂性和程序复杂性

【解答】C ，E

3. 判断题

⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。

【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。

⑵ 每种数据结构都具备三个基本操作：插入、删除和查找。

【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。

⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。

【解答】错。是数据之间的逻辑关系的整体。

⑷ 逻辑结构与数据元素本身的内容和形式无关。

【解答】对。因此逻辑结构是数据组织的主要方面。

⑸ 基于某种逻辑结构之上的基本操作，其实现是唯一的。

【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。

4. 分析以下各程序段，并用大O 记号表示其执行时间。

【解答】⑴ 基本语句是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)2≤n ，所以T (n )=O (n 1/2)。

⑸ x++是基本语句，所以 ∑∑∑=====n i i j j

k n O n T 1113)(1)(

5．解答下列问题

（1）设有数据结构（D ，R ），其中D = {1, 2, 3, 4, 5, 6}，R = {(1, 2),(2, 3),(2, 4),(3, 4),(3,

⑴ 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 <= n)

if (i > j) j++;

else i++; ⑸ for (i = 1; i <= n; i++)

for (j = 1; j <= i; j++)

for (k = 1; k <= j; k++) x++;

5),(3, 6),(4, 5),(4, 6)}。试画出其逻辑结构图并指出属于何种结构。

【解答】其逻辑结构图如图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 相减

输出：相减的结果

后置条件：整数a 的值发生改变

Multi

前置条件：存在一个整数a

输入：一个整数b

功能：将整数a 与输入的整数b 相乘

输出：相乘的结果

后置条件：整数a 的值发生改变

图1-3 逻辑结构图

前置条件：存在一个整数a

输入：一个整数b

功能：将整数a与输入的整数b相除

输出：若整数b为零，则抛出除零异常，否则输出相除的结果

后置条件：整数a的值发生改变

Mod

前置条件：存在一个整数a

输入：一个整数b

功能：求当前整数与输入整数的模，即正的余数

输出：若整数b为零，则抛出除零异常，否则输出取模的结果

后置条件：整数a的值发生改变

Equal

前置条件：存在一个整数a

输入：一个整数b

功能：判断整数a与输入的整数b是否相等

输出：若相等返回1，否则返回0

后置条件：整数a的值不发生改变

endADT

（3）求多项式A(x)的算法可根据下列两个公式之一来设计：

①A(x)=a n x n+a n-1x n-1+…+a1x+a0

②A(x)=(…(a n x+a n-1)x+…+a1)x)+a0

根据算法的时间复杂度分析比较这两种算法的优劣。

【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。

（4）选择和评价数据结构的标准与方法是什么？

【解答】首先，对给定的实际问题可以建立不同的数据结构；其次，对于给定的数据结构，可以选择不同的存储实现，即采用不同的存储结构；再次，在给定数据结构和存储结构的条件下，对同一基本操作可以设计出不同算法。因此，数据的逻辑结构、存储结构和操作（特别是基本操作）的实现这三者是密切相关的。一般地，在建立数据结构时应该考虑以下三个方面：

①确定表示问题所需的数据及其特性；

②确定必须支持的基本操作，并度量每种操作所受的时、空资源限制，某些重要的操作，例如查找、插入和删除的资源限制通常决定了数据结构的选择；

③选择（或设计）最接近这些开销的数据结构。

6. 算法设计（要求：用伪代码和C++描述两种方法描述算法，并分析时间复杂度）

⑴对一个整型数组A[n]设计一个排序算法。

【解答】下面是简单选择排序算法的伪代码描述。

下面是简单选择排序算法的C++描述。

分析算法，有两层嵌套的for 循环，所以，∑=∑=

=+=021)(1)(i i j n O n T 。

⑵ 找出整型数组A[n]中元素的最大值和次最大值。

【解答】算法的伪代码描述如下：

算法的C++描述如下：

分析算法，只有一层循环，共执行n -

2次，所以，T (n )=O (n )。

第 2 章线性表

2.1 本章导学

1. 知识结构图

本章的知识结构如图2-1所示，其中第二层的椭圆代表本章的学习主线。

图2-1 知识结构图

2. 学习要点

本章虽然讨论的是线性表，但涉及的许多问题都具有一定的普遍性，因此，本章是本课程的重点之一，也是其它后续章节的重要基础。

对于本章的学习要从两条明线、一条暗线出发。两条明线是线性表的逻辑结构和存储结构，一条暗线是算法（即基本操作的实现）。注意线性表的ADT定义、顺序表类定义和单链表类定义三者之间的关系；注意在不同的存储结构下，相同操作的不同实现算法；注意对顺序表和链表从时间性能和空间性能等方面进行综合对比，在实际应用中能为线性

2.2 习题解析

1. 填空

⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置

⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

【解答】108

【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108

⑶设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next

⑷单链表中设置头结点的作用是（）。

【解答】为了运算方便

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。【解答】p->next=head

【分析】如图2-8所示。

图2-8 尾结点p与头指针head的关系示意图

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next; rear->next =s; rear =s;

q=rear->next->next; rear->next->next=q->next; delete q;

【分析】操作示意图如图2-9所示：

图2-9 带尾指针的循环链表中插入和删除操作示意图

⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为

【解答】Ο(1)，Ο(n)

【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。

⑻可由一个尾指针唯一确定的链表有（）、（）、（）。

【解答】循环链表，循环双链表，双链表

2.选择题

⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

A 随机存取

B 顺序存取

C 索引存取

D 散列存取

【解答】A，B

【分析】参见2.2.1。

⑵线性表采用链接存储时，其地址（）。

A 必须是连续的

B 部分地址必须是连续的

C 一定是不连续的

D 连续与否均可以

【解答】D

【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

⑶单循环链表的主要优点是（）。

A 不再需要头指针了

B 从表中任一结点出发都能扫描到整个链表；

C 已知某个结点的位置后，能够容易找到它的直接前趋；

D 在进行插入、删除操作时，能更好地保证链表不断开。

【解答】B

⑷链表不具有的特点是（）。

A 可随机访问任一元素

B 插入、删除不需要移动元素

C 不必事先估计存储空间

D 所需空间与线性表长度成正比

【解答】A

⑸若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。

A 顺序表

B 单链表

C 双链表

D 单循环链表

【解答】A

【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。

A 单链表

B 带头指针的单循环链表

C 双链表

D 带尾指针的单循环链表

【解答】D

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D 。

⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。

A 单链表

B 循环双链表C单循环链表 D 带尾指针的单循环链表

【解答】B

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。

⑻在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

A O(1)

B O(n)

C O(n2)

D O(n log2n)

【解答】B

【分析】首先应顺序查找新结点在单链表中的位置。

⑼对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。

A O(1)

B O(n)

C O(n2)

D O(n log2n)

【解答】C

【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。

⑽使用双链表存储线性表，其优点是可以（）。

A 提高查找速度

B 更方便数据的插入和删除

C 节约存储空间

D 很快回收存储空间

【解答】B

【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。

⑾在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s 所指结点，则执行（）操作。

A s->next=p->next; p->next=s;

B q->next=s; s->next=p;

C p->next=s->next; s->next=p;

D p->next=s; s->next=q;

【解答】B

【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。

⑿在循环双链表的p所指结点后插入s所指结点的操作是（）。

A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;

C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

D s->prior=p; s->next=p->next;p->next->prior=s;p->next=s

【解答】D

辑特征，图2-10给出备选答案C 和D 的图解。

（13）用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中某结点，则

j 后移的操作语句为（ ）。

A j = r[j].next

B j = j + 1

C j = j->next

D j = r[j]-> next

【解答】A

【分析】注意next 是数组下标，因此排除C 和D ，对于备选答案B ，假设工作指针j 指向

某结点p ，则j+1不一定指向结点p 的后继结点。

（14）设线性表有n 个元素，以下操作中，（ ）在顺序表上实现比在链表上实现的

效率更高。

A 输出第i （1≤i ≤n ）个元素值

B 交换第1个和第2个元素的值

C 顺序输出所有n 个元素

D 查找与给定值x 相等的元素在线性表中的序号

【解答】A

【分析】在顺序表上输出第i （1≤i ≤n ）个元素值需要O (1)时间，在链表上输出第i （1≤i

≤n ）个元素值需要O (n )时间；在顺序表上和链表上交换第1个和第2个元素的值都需要

O (1)时间；在顺序表上和链表上顺序输出所有n 个元素都需要O (n )时间；在顺序表上和链

表上查找与给定值x 相等的元素都需要进行顺序查找，需要O (n )时间。

3. 判断题

⑴ 线性表的逻辑顺序和存储顺序总是一致的。

【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。 ⑵ 线性表的顺序存储结构优于链接存储结构。

【解答】错。两种存储结构各有优缺点。

⑶ 设p ，q 是指针，若p=q ，则*p=*q 。

【解答】错。p=q 只能表示p 和q 指向同一起始地址，而所指类型则不一定相同。

⑷ 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。

【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最

后一个元素没有后继。

⑸ 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随

机存取结构。

(a) 备选答案C 操作示意图(第4步指针修改无法进行) (b) 备选答案D 操作示意图 图2-10 双链表插入操作修改指针操作示意图

【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。

⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。

⑵如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。

⑶描述一个城市的设计和规划。

【解答】顺序表的优点：①无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

②可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：①插入和删除操作需移动大量元素；②表的容量难以确定；③造成存储空间的“碎片”。

单链表的优点：①不必事先知道线性表的长度；②插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：①指针的结构性开销；②存取表中任意元素不方便，只能进行顺序存取。

⑴应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。

⑵应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。

⑶应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计

⑴设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环左移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。

⑵已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。

【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：

分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。

⑶试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。

【解答】参见2.2.3。

⑷试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i 个元素与第length-i-1个元素相交换。具体算法如下：

单链表的逆置请参见2.2.4算法2-4和算法2-6。

⑸假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。

【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：

图2-11 删除结点s的前驱结点操作示意图

⑹已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。

【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A 中分别存放字母、数字和其他字符。具体算法如下：

⑺设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：

⑻判断带头结点的双循环链表是否对称。

【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。

第 3 章栈和队列

3.1 本章导学

1. 知识结构图

本章的知识结构如图3-1所示，其中第二层的椭圆表示本章的学习主线。

图3-1 知识结构图

2. 学习要点

对于本章的学习要从两条主线出发，一条主线是栈，另一条主线是队列，要以栈和队列的操作特性为切入点，并注意将栈和队列进行对比。

这部分有较多的经典应用，如汉诺塔问题、迷宫问题、八皇后问题、车厢重排问题、开关盒布线、舞伴问题等等。要有意识地接触这些经典问题，深刻理解栈和队列在程序设计中的重要作用，在实践中培养数据结构应用能力和算法设计能力。

3.2 习题解析

1.填空

⑴设有一个空栈，栈顶指针为1000H，每个元素需要1个单位的存储空间，则执行push、push、pop、push、pop、push、push后，栈顶指针为（）。

【解答】1003H

⑵栈结构通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间

⑶（）可作为实现递归函数调用的一种数据结构。

【解答】栈

【分析】递归函数的调用和返回正好符合后进先出性。

⑷表达式a*(b+c)-d的后缀表达式是（）。

【解答】abc+*d-

【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同

⑹循环队列的引入是为了克服（）。

【解答】假溢出

⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

【解答】（rear-front+n）% n

【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。

【解答】Ｏ(1)，Ｏ(n)

【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

2.选择题

（1）一个栈的入栈序列是1、2、3、4、5，则栈的不可能的输出序列是（）。

A 54321

B 45321

C 43512

D 12345

【解答】C

【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指

《数据结构》课后习题答案

第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构

数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)

数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ）

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构

最全数据结构课后习题答案(耿国华版[12bb]

第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i

《数据结构基础教程》习题及解答

《数据结构基础教程》习题解答(新) 第1章习题解答 一、填空 1.数据就是指所有能够输入到计算机中被计算机加工、处理得符号得集合。 2.可以把计算机处理得数据,笼统地分成数值型与非数值型两大类。 3.数据得逻辑结构就就是指数据间得邻接关系。 4.数据就是由一个个数据元素集合而成得。 5.数据项就是数据元素中不可再分割得最小标识单位,通常不具备完整、确定得实际意义,只就是反映数据元素某一方面得属性。 6.数据就是以数据元素为单位存放在内存得,分配给它得内存区域称为存储结点。 7.每个数据元素都具有完整、确定得实际意义,就是数据加工处理得对象。 8.如果两个数据结点之间有着逻辑上得某种关系,那么就称这两个结点就是邻接得。 9.在一个存储结点里,除了要有数据本身得内容外,还要有体现数据间邻接关系得内容。 10.从整体上瞧,数据在存储器内有两种存放得方式:一就是集中存放在一个连续得内存存储区中;一就是利用存储器中得零星区域, 分散地存放在内存得各个地方。 11.在有些书里,数据得“存储结构”也称为数据得“物理结构”。 12.“基本操作”就是指算法中那种所需时间与操作数得具体取值无关得操作。 二、选择 1.在常见得数据处理中, B 就是最基本得处理。 A.删除 B.查找 C.读取 D.插入 2.下面给出得名称中, A 不就是数据元素得同义词。 A.字段 B.结点 C.顶点 D.记录 3. D 就是图状关系得特例。 A.只有线性关系 B.只有树型关系 C.线性关系与树型关系都不 D.线性关系与树型关系都 4.链式存储结构中,每个数据得存储结点里 D指向邻接存储结点得指针,用以反映数据间得逻辑关系。 A.只能有1个 B.只能有2个 C.只能有3个 D.可以有多个 5.本书将采用 C 来描述算法。 A.自然语言 B.流程图(即框图) C.类C语言 D.C语言 6.有下面得算法段: for (i=0; i

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

(完整word版)数据结构课后习题及答案

填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0;

数据结构课后习题答案

数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值

实用数据结构基础(第四版)课后习题知识讲解

一、判断题 （第一章绪论） 1.数据元素是数据的最小单元。 答案：错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确 4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间 答案：正确 （第二章线性表） 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误 9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确 10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误 （第三章栈）

11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误 12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。答案：错误 13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确 14.空栈就是所有元素都为0上的栈。 答案：错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章队列） 16.队列式限制在两端进行操作的线性表。 答案：正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误 18.在循环链列队中无溢出现像。 答案：错误 19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确 20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案：错误 （第五章串） 21.串是n个字母的有限序列。 答案：错误 22.串的堆分配存储是一种动态存储结构。

数据结构课后习题及答案

填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

实用数据结构基础参考答案

单元练习1 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ ) (√)(1)数据的逻辑结构与数据元素本身的内容与形式无关。 (√)(2)一个数据结构就是由一个逻辑结构与这个逻辑结构上的一个基本运算集构成的整体。 (ㄨ)(3)数据元素就是数据的最小单位。 (ㄨ)(4)数据的逻辑结构与数据的存储结构就是相同的。 (ㄨ)(5)程序与算法原则上没有区别,所以在讨论数据结构时可以通用。 (√)(6)从逻辑关系上讲,数据结构主要分为线性结构与非线性结构两类。 (√)(7)数据的存储结构就是数据的逻辑结构的存储映像。 (√)(8)数据的物理结构就是指数据在计算机内实际的存储形式。 (ㄨ)(9)数据的逻辑结构就是依赖于计算机的。 (√)(10)算法就是对解题方法与步骤的描述。 二.填空题 （1）数据有逻辑结构与存储结构两种结构。 （2）数据逻辑结构除了集合以外,还包括:线性结构、树形结构与图形结构。（3）数据结构按逻辑结构可分为两大类,它们就是线性结构与非线性结构。（4）树形结构与图形结构合称为非线性结构。 （5）在树形结构中,除了树根结点以外,其余每个结点只有 1 个前趋结点。 （6）在图形结构中,每个结点的前趋结点数与后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括:顺序存储、链式存储、索引存储与散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系, （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构与算法(或运算) 三个方面的内容。 （13）数据结构被定义为(D,R),其中D就是数据的有限集合,R就是D上的关系的有限集合。 （14）算法就是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法与事后统计法。 （16）一个算法的时间复杂性就是算法输入规模的函数。 （17）算法的空间复杂度就是指该算法所耗费的存储空间 ,它就是该算法求解问题规模n的函数。 （18）若一个算法中的语句频度之与为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n) 。

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

最全数据结构课后习题答案耿国华版

绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i

C++与数据结构基础简明教程课后习题答案

C++与数据结构基础简明教程课后习题答案 1-7-1 //输出一个数的10倍 #include using namespace std; int main() { cout<<"Please input an interger:\n"; int a; cin>>a; cout<<"result="< using namespace std; int main() { double x,y,min; cout<<"please input two numbers"<>x>>y; min=(x>y?y:x); cout<<"the smaller is"<<' '<

//输入半径计算周长和面积 #include using namespace std; int main() { cout<<"请输入半径\n"; double rad; cin>>rad; double c,s; c=2*3.14*rad; s=3.14*rad*rad; cout<<"周长是"< using namespace std; int main() { int hour,min,second; hour=10000/3600; min=(10000%3600)/60; second=10000-hour*3600-60*min; cout<

严蔚敏 数据结构课后习题及答案解析

第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。

数据结构课程课后习题答案

《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。

答：①数据元素 ②关系 （4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。 答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。 答：①前驱 ②1 ③后继 ④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答：①顺序 ②链式 ③索引 ④哈希 （8）一个算法的效率可分为 ① 效率和 ② 效率。 答：①时间 ②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a ,b ,…,i }，R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )}，问相对于关系R ，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a 结点没有前驱结点，称为根结点，b 、e 、g 、i 结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度： T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2-1000log 2n T 4(n )=2n log 2n -1000log 2n 答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2)，T 4(n )=O(n log 2n )。 （5）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do { j=j+1; s=s+10*j; } while (j