数据结构部分习题解答

习题二2-4、以下声明有什么错误？为什么？templateclassTboolSeqListT::operator==(SeqListT&list)//比较两个顺序表对象是否相等{returnthis-count==list.count&&this-element==list.element;}【答】在深拷贝的含义下，两个顺序表相等意味着：两个顺序表长度相同且所有元素值相等。而不是两个顺序表对象的所有成员变量值对应相等。比较两个顺序表对象是否相等的多种情况如图2.4所示，函数实现见教材第40页。（b）若顺序表浅拷贝，this.element与list.element指向同一个数组，则this.element==list.element，相等12345this645list645（a）若this和list表示同一个顺序表对象，则this==&list，相等12345this01…234element64lengthlength-15nlist（c）两个顺序表对象，若this.n!=list.n，则不相等12345this645list6441234（d）两个顺序表对象，若this.n==list.n且所有元素对应相等，则相等12345this645list64512345图1.1比较两个顺序表对象是否相等顺序表的深拷贝（顺序表元素是指针或引用类型）2-5、已知结点类NodeT有数据域data和指针域next，写出下列数据结构的声明。（a）（b）∧table∧datanext∧…∧…∧table∧datanext∧…∧…datanext【答】table可声明为数组或顺序表。（a）元素为结点指针或单链表对象，声明为以下之一：NodeT*table[N];//一维静态数组，元素为结点指针NodeT**table;//一维动态数组，元素为结点指针SinglyListT*table;//一维动态数组，元素为单链表对象SeqListNodeT*table;//顺序表，元素为结点指针SeqListSinglyListTtable;//顺序表，元素为单链表对象（b）元素为结点，声明为以下之一：NodeTtable[N];//一维静态数组，元素为结点NodeT*table;//一维动态数组，元素为结点SeqListNodeTtable;//顺序表，元素为结点2-10、oubleNode类能否继承单链表结点类Node？为什么？【答】不能。因为，如果DoubleNode类声明如下，继承单链表结点类Node。templateclassTclassDoubleNode:publicNodeT//双链表结点类，继承单链表结点类{DoubleNodeT*prev;//指向前驱结点的指针域};该类声明没有语法错，但语义不对，因为从基类继承来的next类型为NodeT*，仍然指向单链表结点。等价于以下声明，此处需要next指向双链表结点，类型是DoubleNodeT*。templateclassTclassDoubleNode//双链表结点类{Tdata;//继承基类的成员变量NodeT*next;//继承基类的成员变量，数据类型错误DoubleNodeT*prev;};习题三3-7、Brute-Force模式匹配算法的主要特点是什么？算法思路是怎样的？给出最好情况和最坏情况及其时间复杂度。【答】Brute-Force是一种带回溯的模式匹配算法，它将目标串中所有长度为m的子串依次与模式串匹配，如果一次匹配失败，则模式串再与目标串的下一个子串匹配。Brute-Force算法最好情况下的时间复杂度是O(m)，最坏情况下的时间复杂度是O(m×n)。3-8、已知target=aaabaaab、pattern=aaaa，画出采用Brute-Force算法的模式匹配过程，给出比较结果、子串匹配次数和字符比较次数。【答】比较结果：匹配不成功，匹配子串位置为-1；子串匹配5次，字符比较14次。≠（a）比较4次aabaatargetaaapatternat0t1t2t3t4t5＝＝＝＝＝aabt6t7＝≠（b）比较3次aabaatargetaaapatternat0t1t2t3t4t5＝＝aabt6t7≠（c）比较2次aabaatargetaaapatternat0t1t2t3t4t5＝aabt6t7≠（d）比较1次aabaatargetaaapatternaaab≠（e）比较4次，匹配失败aabaatargetaaapatternaaab模式串aaaa的Brute-Force算法模式匹配过程3-9、已知target=abcababcabababcababc，pattern=ababcababc，求模式串改进的next数组，画出KMP算法模式匹配过程，给出比较结果，以及子串匹配次数和字符比较次数。本题目的：理解改进next数组的next[j]=next[k]。【答】比较结果：匹配成功，匹配子串位置为10；子串匹配3次，字符比较21次。表1-2模式串ababcababc的next数组j0123456789模式串ababcababc110jppp中最长相同的前后缀子串长度k1001201234kp与jp比较≠==≠=====next[j]1010210102KMP模式匹配算法过程如图3.5所示，算法说明如下。①第1次匹配，如图3.5（a）所示，00pt，11pt，22pt；j=2，因10pp，k=0，导致12pt；因20pp，导致02pt，下次匹配3t需与0p比较，所以next[2]=next[0]=-1。②第2次匹配，如图3.5（b）所示，03pt，…，912pt；j=9，110jppp=ababcabab中最长相同的前后缀子串abab长度k=4，则下次匹配字符为4p；因94pp，导致412pt；再因3210pppp=ab，即ababcabab中有更短的相同前后缀子串ab，子串长度k=2，如图3.5（c）所示，下次匹配12t需与2p比较，所以next[9]=next[4]=2。③第3次匹配，如图3.5（d）所示，212pt，…，919pt，匹配成功。（a）第1次匹配，t0＝p0，t1＝p1，t2≠p2；因p0≠p1，导致t1≠p0；因p0=p2，导致t2≠p0，所以next[2]=-1p1p0p2≠ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7＝＝at8bt9p4cp5ababcp6p7p8p9at10bt11at12bt13ct14at15bt16at17bt18ct19（b）第2次匹配，t3＝p0，…，t12≠p9；因t8…t11=p5…p8=p0…p3，k=4，且p4=p9，导致t12≠p4p1p0p2≠ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7＝＝＝at8bt9p4cp5a＝＝babcp6p7p8p9at10bt11at12＝＝＝＝bt13ct14at15bt16at17bt18ct19（a）第1次匹配，t0＝p0，t1＝p1，t2≠p2；因p0≠p1，导致t1≠p0；因p0=p2，导致t2≠p0，所以next[2]=-1p1p0p2≠ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7＝＝at8bt9p4cp5a（c）t12≠p4，因p0p1=p2p3，k=2，有更短的相同前后缀子串，所以next[9]=next[4]=2babcp6p7p8p9（b）第2次匹配，t3＝p0，…，t12≠p9；因t8…t11=p5…p8=p0…p3，k=4，且p4=p9，导致t12≠p4p1p0p2≠ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7＝＝＝at8bt9p4cp5a＝＝babcp6p7p8p9at10bt11at12＝＝＝＝p1p0p2≠ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7at8bt9p4cp5ababcp6p7p8p9at10bt11at12（d）第3次匹配，t12=p2，……，t19=p9，匹配成功p1p0p2ababcbtargetabapatternat0t1t2t3t4t5t6p3bct7at8bt9p4cp5ababcp6p7p8p9at10bt11at12bt13ct14at15bt16at17bt18ct19＝＝＝＝＝＝＝＝bt13ct14at15bt16at17bt18ct19bt13ct14at15bt16at17bt18ct19at10bt11at12bt13ct14at15bt16at17bt18ct19图1.2模式串ababcababc的KMP算法模式匹配过程习题四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）所示。③先根次序遍历序列和后根次序遍历序列相同是，空树或仅有一个结点的二叉树。ABCCAB（a）右单支二叉树（b）左单支二叉树先根：ABC中根：CBA后根：CBA先根：ABC中根：ABC后根：CBA单支二叉树6-22、已知一棵二叉树的中根和后根遍历序列如下，画出据此构造的二叉树。中根遍历序列：CDBEGAHFIJK；后根遍历序列：DCEGBFHKJIA【答】如图所示。ABIHFECGDJK6-33、设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18}，采用Huffman编码对这段正文进行压缩存储，画出所构造的Huffman树，并写出每个字符的Huffman编码。【答】Huffman树及Huffman编码如图所示。Huffman编码A：111B：11011C：100D：11010E：1100F：01G：00H：10129311718GC1010601035411823HAF1010769945EDB10