数据结构部分习题解答

习题二

2-4、以下声明有什么错误？为什么？

template

bool SeqList::operator==(SeqList &list) //比较两个顺序表对象是否相等 {

return this->count==list.count && this->element==list.element; }

【答】在深拷贝的含义下，两个顺序表相等意味着：两个顺序表长度相同且所有元素值相等。而不是两个顺序表对象的所有成员变量值对应相等。

比较两个顺序表对象是否相等的多种情况如图2.4所示，函数实现见教材第40页。

thisnlengthelement01234?length-156412345list（a）若this和list表示同一个顺序表对象，则this==&list，相等55646412345thislist（b）若顺序表浅拷贝，this.element与list.element指向同一个数组，则this.element==list.element，相等thislist546464112233445

（c）两个顺序表对象，若this.n!=list.n，则不相等thislist5564641122334455（d）两个顺序表对象，若this.n==list.n且所有元素对应相等，则相等图1.1 比较两个顺序表对象是否相等顺序表的深拷贝（顺序表元素是指针或引用类型）

2-5、已知结点类Node有数据域data和指针域next，写出下列数据结构的声明。

table∧?∧（a）∧∧（b）data next?∧table∧?∧data nextdata next?∧ 【答】table可声明为数组或顺序表。

（a）元素为结点指针或单链表对象，声明为以下之一：

Node* table[N]; Node **table; SeqList*> table; SeqList> table;

//一维静态数组，元素为结点指针 //一维动态数组，元素为结点指针 //顺序表，元素为结点指针 //顺序表，元素为单链表对象 //一维静态数组，元素为结点 //一维动态数组，元素为结点 //顺序表，元素为结点

SinglyList *table; //一维动态数组，元素为单链表对象

（b）元素为结点，声明为以下之一：

Node table[N]; Node *table; SeqList> table;

2-10 、oubleNode类能否继承单链表结点类Node？为什么？

【答】不能。因为，如果DoubleNode类声明如下，继承单链表结点类Node。

template

class DoubleNode : public Node

//双链表结点类，继承单链表结点类

{

DoubleNode *prev; //指向前驱结点的指针域 };

该类声明没有语法错，但语义不对，因为从基类继承来的next类型为Node*，仍然

指向单链表结点。等价于以下声明，此处需要next指向双链表结点，类型是DoubleNode*。

template

class DoubleNode

//双链表结点类

{

T data; //继承基类的成员变量 Node *next; DoubleNode *prev; };

//继承基类的成员变量，数据类型错误

习题三

3-7、Brute-Force模式匹配算法的主要特点是什么？算法思路是怎样的？给出最好情况和最坏情况及其时间复杂度。

【答】Brute-Force是一种带回溯的模式匹配算法，它将目标串中所有长度为m的子串依次与模式串匹配，如果一次匹配失败，则模式串再与目标串的下一个子串匹配。

Brute-Force算法最好情况下的时间复杂度是O(m)，最坏情况下的时间复杂度是O(m×n)。

3-8、已知target=\、pattern=\，画出采用Brute-Force算法的模式匹配过程，给出比较结果、子串匹配次数和字符比较次数。

【答】比较结果：匹配不成功，匹配子串位置为-1；子串匹配5次，字符比较14次。

t0targetat1at2at3bt4at5at6at7btargett0at1at2at3bt4aat5at6at7btargett0at1at2at3bt4aat5aat6at7b＝＝＝≠＝＝≠＝patternapatternaaaapatternaaa（a）比较4次targetaaabaaaaaabtargetaa（b）比较3次abaaab（c）比较2次≠a

≠＝＝＝apatternapatternaa（d）比较1次（e）比较4次，匹配失败模式串\的Brute-Force算法模式匹配过程

3-9、已知target=\，pattern=\，求模式串改进的next数组，画出KMP算法模式匹配过程，给出比较结果，以及子串匹配次数和字符比较次数。

本题目的：理解改进next数组的next[j]=next[k]。

【答】比较结果：匹配成功，匹配子串位置为10；子串匹配3次，字符比较21次。

≠a

表1-2 模式串\的next数组

j 模式串 \p0p1?pj?1\中最长相同的前后缀子串长度k pk与pj比较 0 a ?1 ?1 1 b 0 ≠ 0 2 a 0 = ?1 3 b 1 = 0 4 c 2 ≠ 2 5 a 0 = ?1 6 b 1 = 0 7 a 2 = ?1 8 b 3 = 0 9 c 4 = 2 next[j] KMP模式匹配算法过程如图3.5所示，算法说明如下。

① 第1次匹配，如图3.5（a）所示，t0?p0，t1?p1，t2?p2；j=2，因p0?p1，k=0，导致t2?p1；因p0?p2，导致t2?p0，下次匹配t3需与p0比较，所以next[2]=next[0]=-1。

j=9，\p0p1?pj?1\② 第2次匹配，如图3.5（b）所示，t3?p0，?，t12?p9；中最长相同的前后缀子串\长度k=4，则下次匹配字符为p4；因p4?p9，导致t12?p4；

再因p0p1?p2p3=\，即\中有更短的相同前后缀子串\，子串长度k=2，如图3.5（c）所示，下次匹配t12需与p2比较，所以next[9]=next[4]=2。

③ 第3次匹配，如图3.5（d）所示，t12?p2，?，t19?p9，匹配成功。

targettargett0t0aat1t1bbt2t2cct3t3aat4t4bbt5t5aat6t6bbt7t7cct8t8aa＝＝＝＝patternababcababcpatternababcababcp0p1p2p3p4p5p6p7p8p9p0p1p2p3p4p5p6p7p8p9a）第1次匹配，t0＝p0，t1＝p1，t2≠p2；因p0≠p1，导致t1≠p0；因p0=p2，导致t2≠p0，所以next[2]=-1（a）第1次匹配，t0＝p0，t1＝p1，t2≠p2；因p0≠p1，导致t1≠p0；因p0=p2，导致t2≠p0，所以next[2]=-1t0t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15t16t17t18t19t0t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15t16t17t18t19targetabcababcabababcababctargetabcababcabababcababc＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ≠≠t9t10t9t10babat11t12t11t12babat13t14t15t13t14t15bcabcat16t17t16t17babat18t19t18t19bcbcpatternababcababcpatternababcababcp0p1p2p3p4p5p6p7p8p9p0p1p2p3p4p5p6p7p8p9（b）第2次匹配，t3＝p0，?，t12≠p9；因t8…t11=p5…p8=p0…p3，k=4，且p4=p9，导致t12≠p4（b）第2次匹配，t3＝p0，?，t12≠p9；因t8…t11=p5…p8=p0…p3，k=4，且p4=p9，导致t12≠p4t0targetat1bt2ct3at4bt5at6bt7c t8at9t10t11t12t13t14t15t16t17t18t19bbaabb ＝＝≠≠ patterna≠（c）t12≠p4，因p0p1=p2p3，k=2，有更短的相同前后缀子串，所以next[9]=next[4]=2t0targetat1bt2ct3at4bt5at6bt7ct8at9t10t11t12t13t14t15t16t17t18t19b ＝＝＝＝＝＝＝patternababcababp0p1p2p3p4p5p6p7p8p9（d）第3次匹配，t12=p2，??，t19=p9，匹配成功图1.2 模式串\的KMP算法模式匹配过程

＝ acbacbaabbacbcp0p1p2p3p4p5p6p7p8p9

ababcababcc习题四

4-4、写出中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K对应的后缀表达式。

【答】ABCDEF+*G/-H+*+IJ+K*-

4-9、什么是队列？有何特点？说明在什么情况下需要使用队列。

【答】队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。队列的特点是“先进先出”。广度优先搜索遍历算法需要使用队列作为辅助结构。

4-10、已知入队序列为{A, B, C, D}，有几种出队序列？

【答】一种{A, B, C, D}。

4-11、什么是队列的假溢出？为什么顺序队列会出现假溢出？怎样解决队列的假溢出问题？

【答】顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。

顺序栈会出现假溢出吗？为什么？ 【答】不会。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。

链式队列会出现假溢出吗？为什么？

【答】不会。因为每次元素入队，都要申请新结点，数据不会溢出。

习题六

6-20、找出分别满足下面条件的所有二叉树，并说明原因。

① 先根次序遍历序列和中根次序遍历序列相同； ② 中根次序遍历序列和后根次序遍历序列相同； ③ 先根次序遍历序列和后根次序遍历序列相同。

【答】① 右单支二叉树（包括空树或仅有一个结点的二叉树）的先根和中根次序相同，如下图所示。因为在中根次序遍历序列中，左子树的遍历是在根结点之前；而在先根次序遍历序列中，左子树的遍历序列是在根结点之后，而且对每个子树都是如此，因此，如果一棵二叉树的先根次序遍历序列和中根次序遍历序列相同，那么该二叉树中任一结点必无左子树。须注意的是，空二叉树满足这种情况。

② 左单支二叉树（包括空树或仅有一个结点的二叉树）的先根和中根次序相同，如图6.1（b）所示。

③ 先根次序遍历序列和后根次序遍历序列相同是，空树或仅有一个结点的二叉树。

ABC（a）右单支二叉树先根：ABC中根：ABC后根：CBAC（b）左单支二叉树BA先根：ABC中根：CBA后根：CBA

单支二叉树

6-22、 已知一棵二叉树的中根和后根遍历序列如下，画出据此构造的二叉树。 中根遍历序列：C D B E G A H F I J K； 后根遍历序列：D C E G B F H K J I A

【答】如图所示。

ABCDEGHFI

JK

6-33、 设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依

次为{23,5,17,4,9,31,29,18}，采用Huffman编码对这段正文进行压缩存储，画出所构造的Huffman树，并写出每个字符的Huffman编码。 【答】Huffman树及Huffman编码如图所示。

1360600G29131F0C1735118H0E90D40181915B0176141123AHuffman编码 A：111 B：11011 C：100 D：11010 E：1100

F：01G：00H：101 Huffman树及Huffman编码

习题七

7-15、 画出以下带权无向图G7的邻接矩阵表示和邻接表表示；再画出删除G7中顶点D后的

邻接矩阵表示和邻接表表示。

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