数据结构-王红梅-课后答案

目 录

第 1 章 绪 论 ................................................................................................................................. 2 第 2 章 线性表 ............................................................................................................................... 8 第 3 章 特殊线性表——栈、队列和串 ..................................................................................... 16 第 4 章 广义线性表——多维数组和广义表 ............................................................................. 23 第 5 章 树和二叉树 ..................................................................................................................... 27 第 6 章 图..................................................................................................................................... 37 第 7 章 查找技术 ......................................................................................................................... 45 第 8 章 排序技术 ......................................................................................................................... 53 第 9 章 索引技术 ......................................................................................................................... 61

第 1 章 绪 论

课后习题讲解

1. 填空

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

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

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

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

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

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

⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模

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

为n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题

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

系是由（ ）表示的。

A 线性结构 B 非线性结构 C 存储位置 D 指针

【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数

组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中 的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不

能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合

【解答】B

【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

⑶ 算法指的是（ ）。

A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A

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

的。所以，只有A是算法的准确定义。

⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C

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

⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 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++是基本语句，所以 5．设有数据结构（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,6)}。 试画出其逻辑结构图并指出属于何种结构。

【解答】其逻辑结构图如图1-3所示，它是一种图结构。

6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接

口需定义前置条件、输入、功能、输出和后置条件。 【解答】整数的抽象数据类型定义如下： ADT integer Data

整数a：可以是正整数(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的值发生改变 Div

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

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

输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod

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

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

输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal

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

功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0

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

7. 求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+?+a1x+a0 ⑵ A(x)=(?(anx+an-1)x+?+a1)x)+a0

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

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

减少了不必要的乘法运算。

8. 算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度） ⑴ 对一个整型数组A[n]设计一个排序算法。

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

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

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

⑵ 找出整型数组A[n]中元素的最大值和次最大值。 【解答】算法的伪代码描述如下：

算法的C++描述如下：

分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。

学习自测及答案

1．顺序存储结构的特点是（ ），链接存储结构的特点是（ ）。 【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示

数据元素之间的逻辑关系。

2. 算法在发生非法操作时可以作出处理的特性称为（ ）。 【解答】健壮性

3. 常见的算法时间复杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。

【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)

4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n

【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!

5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及

定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的

总称。抽象数据类型可以看成是对数据类型的一种抽象。

6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。 ⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,,,,}

⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,} ⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}，

R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}

【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构，其逻辑结构图如图1-4(b)所示；

⑶ 属于树结构，其逻辑结构图如图1-4(c)所示；⑷ 属于图结构，其逻辑结构图如图1-4(d)所示。

7. 求下列算法的时间复杂度。 count=0; x=1; while (x { x*=2; count++; }

return count;

【解答】Ｏ(log2n)

第 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所示。

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

【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示：

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

在给定值为

x的结点后插入一个新结点的时间复杂度为（ ）。 【解答】Ο(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(nlog2n)

【解答】B

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

⑼ 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n)

【解答】C

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

⑽ 使用双链表存储线性表，其优点是可以（ ）。 A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间 【解答】B

【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针

⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。

【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：

⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。

【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素

的次数，提高算法的效率。算法如下：

⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。 【解答】参见3.2.5

学习自测及答案

1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指

针，当出栈时，top的变化为（ ）。

A 不变 B top=0; C top=top-1; D top=top+1; 【解答】C

2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C

3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）。 A x=top; top=top->next; B x=top->data;

C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D

4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++

程序设计语言的变量名。

【解答】PA321, P3A21, P32A1, P321A, AP321

5.设S=\，其长度为（ ）。 【解答】15

6．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是 （ ）。

【解答】Ｏ(1)

7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？

答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，

CBDA，CDBA，DCBA

8．简述队列和栈这两种数据结构的相同点和不同点。

【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。

不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进

行插入，在另一端进行删除的线性表，是先进先出的线性表。

9. 利用两个栈S1和S2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。

【解答】利用两个栈S1和S2模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已输入的元

素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S1中元素全部送入到S2中，

再从S2中删除栈顶元素，最后再将S2中元素全部送入到S1中；判断队空的条件是：栈S1和S2同时为 空。

10. 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。

【解答】算法基于原理：N=(N div d)×d + N mod d （div为整除运算，mod为求余运算）。

11．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号“{”和“}”，且

这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。 【解答】假设表达式已存入字符数组A[n]中，具体算法如下：

第 4 章 广义线性表——多维数组和广义表

课后习题讲解

1. 填空

⑴ 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。 【解答】存取，修改，顺序存储

【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了

初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]

的存储地址是1000，则元素A[15][10]的存储地址是（ ）。 【解答】1140

【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4

个存储单元，所以，其存储地址是1000+140=1140。

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个

存储单元，则元素A[8][5]的存储地址为（ ）。 【解答】d+41

【分析】元素A[8][5]的前面共存储了(1+2+?+8)+5=41个元素。

⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（ ）和（ ）。 【解答】三元组顺序表，十字链表

⑸ 广义表((a), (((b),c)),(d))的长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。 【解答】3，4，(a)，((((b),c)),(d))

⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。 【解答】Head(Head(Tail(LS)))

2. 选择题

⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存 放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行优先方式存储， 元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54

H A[8][5] I A[3][10] J A[5][8] K A[4][9]

【解答】D，E，K

【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列

和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存

储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，

解此方程，得i=4，j=9。

⑵ 将数组称为随机存取结构是因为（ ）

A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定 【解答】B

⑶ 下面的说法中，不正确的是（ ）

A 数组是一种线性结构 B 数组是一种定长的线性结构

C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操 【解答】C

【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常

没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（ ） A 表达变得简单 B 对矩阵元素的存取变得简单

C 去掉矩阵中的多余元素 D 减少不必要的存储空间 【解答】D

【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。

⑸ 下面（ ）不属于特殊矩阵。

A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵 【解答】C

⑹ 若广义表A满足Head(A)=Tail(A)，则A为（ ） A ( ) B (( )) C (( ),( )) D(( ),( ),( )) 【解答】B

⑺ 下面的说法中，不正确的是（ ）

A 广义表是一种多层次的结构 B 广义表是一种非线性结构 C 广义表是一种共享结构 D 广义表是一种递归 【解答】B

【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。

⑻ 下面的说法中，不正确的是（ ）

A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。 B 对角矩阵只须存放非零元素即可。

C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。

D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 【解答】D

【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，

就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。

3. 判断题

⑴ 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。 【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。

⑵ 使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。

【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。

⑶ 稀疏矩阵压缩存储后，必会失去随机存取功能。

【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。

⑷ 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。 【解答】对。

⑸ 若一个广义表的表头为空表，则此广义表亦为空表。

【解答】错。如广义表L=(( )，(a，b))的表头为空表，但L不是空表。

4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链 表存储表示。

【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。

5．已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成

求 运算的优缺点。

代入上式有：

B=n0+n0-1-1=2(n0-1)

5．证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。 【解答】证明采用归纳法。

设二叉树的前序遍历序列为a1a2a3? an，中序遍历序列为b1b2b3? bn。 当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一

确定该二叉树；

假设当n<=k时，前序遍历序列a1a2a3? ak和中序遍历序列b1b2b3? bk可唯一确定该二叉树，下面证

明当n=k+1时，前序遍历序列a1a2a3? akak+1和中序遍历序列b1b2b3? bk bk+1可唯一确定一棵二叉 树。

在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1

的结点，假设为bi，则a1=bi且b1b2? bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列

a2a3? ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3? ai和中序遍历

序列b1b2? bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2? ak+1和中序遍历序列

bi+1bi+2? bk+1唯一确定了根结点的右子树。

6．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，??，nm个度为m的结点，问

该树中共有多少个叶子结点？

【解答】设该树的总结点数为n，则 n=n0+n1+n2+……+nm 又：

n=分枝数+1=0×n0+1×n1+2×n2+??+m×nm+1 由上述两式可得：

n0= n2+2n3+……+(m-1)nm+1

7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。 【解答】二叉树的构造过程如图5-12 所示。

8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长 度。

【解答】构造的哈夫曼树如图5-13所示。

zzzz

树的带权路径长度为：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120

9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，

对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。

【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度

=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符z

10．算法设计

⑴ 设计算法求二叉树的结点个数。 【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的“访问”操作改为“计 数操作”，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。

具体算法如下：

⑵ 设计算法按前序次序打印二叉树中的叶子结点。

【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不

同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历

算法中的访问操作改为条件打印即可。算法如下：

⑶ 设计算法求二叉树的深度。

【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右

子树深度的求解又可通过递归调用本算法来完成。具体算法如下：

⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。

【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右

子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：

⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：

⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指

向结点x的指针置空。具体算法如下：

⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。 【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下：

① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到 左子树为空。

② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。

具体算法如下：

⑻ 编写算法交换二叉树中所有结点的左右子树。

【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。 具体算法如下：

⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。

【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild

找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的 指针。

树的孩子兄弟表示法中的结点结构定义如下： template struct TNode {

T data;

TNode *firstchild, *rightsib; };

具体算法如下：

学习自测及答案

1．前序遍历和中序遍历结果相同的二叉树是（ ）。

A 根结点无左孩子的二叉树

B 根结点无右孩子的二叉树

C 所有结点只有左子树的二叉树

D 所有结点只有右子树的二叉树

【解答】D

2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。 A 24 B 48 C 53 D 72 【解答】C

3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]

若有左子树，

则左子树的根结点是（ ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D

4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（ ）。 A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律 【解答】C

5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ）。 A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D

6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次 为（ ）。

A h B h+1 C h或h+1 D 任意 【解答】C

7．假定一棵度为3的树中结点数为50，则其最小高度应为 。 A 3 B 4 C 5 D 6

【解答】C

8．在线索二叉树中，一个结点是叶子结点的充要条件为（ ）。

A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C

9．对于一棵具有n个结点的树，其所有结点的度之和为（ ）。 【解答】n-1

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（ ）。 【解答】

11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？ 【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

所以生成树中最长路径的终点的度为1。

同理可证起点v1的度不能大于1，只能为1。

7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进

行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

【解答】邻接矩阵表示如下：

深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下：

8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。

【解答】按Prim算法求最小生成树的过程如下：

按Kruskal算法求最小生成树的过程如下：

9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。

源点 终点 最短路径 最短路径长度

v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22

v1 v3 v1 v7 v4 v6 v3 25

10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。

源点 终点 最短路径 最短路径长度

v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45

11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。 【解答】

任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2?vn-1，我们来证明此时的

邻接矩阵A为上三角矩阵。证明采用反证法。

假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从

vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓

扑序列v0v1v2?vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。

12. 算法设计

⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。

【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表

中插入相应的边表结点。

邻接矩阵存储结构定义如下： const int MaxSize=10; template

struct AdjMatrix {

T vertex[MaxSize]; //存放图中顶点的数组

int arc[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum, arcNum; //图的顶点数和边数 };

邻接表存储结构定义如下：

const int MaxSize=10;

struct ArcNode //定义边表结点 {

int adjvex; //邻接点域 ArcNode *next; };

template

struct VertexNode //定义顶点表结点 {

T vertex;

ArcNode *firstedge; };

struct AdjList {

VertexNode adjlist[MaxSize];

int vertexNum, arcNum; //图的顶点数和边数 };

具体算法如下：

⑵ 设计算法，将一个无向图的邻接表转换成邻接矩阵。

【解答】在邻接表上顺序地取每个边表中的结点，将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表

的存储结构定义与上题相同。具体算法如下：

⑶ 设计算法，计算图中出度为零的顶点个数。

【解答】在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，

当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数

是否为零，若是则计数器加1。具体算法如下：

⑷ 以邻接表作存储结构，设计按深度优先遍历图的非递归算法。 【解答】参见6.2.1。

⑸ 已知一个有向图的邻接表，编写算法建立其逆邻接表。

【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算

法思路：首先将逆邻接表的表头结点firstedge域置空，然后逐行将表头结点的邻接点进行转化。

⑹ 分别基于深度优先搜索和广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到

顶点vj的路径（i≠j）。

【解答】⑴ 基于深度优先遍历：

⑵ 基于广度优先遍历：

学习自测及答案

1．某无向图的邻接矩阵A=，可以看出，该图共有（ ）个顶点。 A .3 B. 6 C. 9 D .以上答案均不正确 【解答】A

2．无向图的邻接矩阵是一个（ ），有向图的邻接矩阵是一个（ ） A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D

3．下列命题正确的是（ ）。

A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B

4．十字链表适合存储（ ），邻接多重表适合存储（ ）。 【解答】有向图，无向图

5. 在一个具有n 个顶点的有向完全图中包含有（ ）条边： A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2 【解答】B

6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ ）个非零元素。 【解答】2(n-1)

7．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（ ）个非零矩阵元素。 【解答】1000

8．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1

【解答】C

9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则

输出的顶点序列是（ ）。

A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A

10. 关键路径是AOE网中（ ）。

A 从源点到终点的最长路径 B 从源点到终点的最长路径 C 最长的回路 D 最短的回路 【解答】A

11. 已知无向图G的邻接表如图6-10所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相 应的生成树。

【解答】深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为：

广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为：

12. 已知已个AOV网如图6-11所示，写出所有拓扑序列。

【解答】拓扑序列为：v0 v1 v5 v2 v3 v6 v4、 v0 v1 v5 v2 v6 v3 v4、 v0 v1 v5 v6 v2 v3 v4。

第 7 章 查找技术

课后习题讲解

1. 填空题

本文来源：https://www.bwwdw.com/article/n9ra.html