数据结构部分习题解答.doc

《数据结构部分习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题二2-4、以下声明有什么错误？为什么？templateboolSeqList::operator==(SeqList&list)//比较两个顺序表对象是否相等{returnthis->count==list.count&&this->element==list.element;}【答】在深拷贝的含义下，两个顺序表相等意味着：两个顺序表长度相同且所有元素值相等。而不是两个顺序表对象的所有成员变量值对应相等。比较两个顺序表对象是否相等的多种情况如图2.4所示，函数实现见教材第40页。图1.1比较两个顺序表对象是否相等顺序表的

2、深拷贝（顺序表元素是指针或引用类型）2-5、已知结点类Node有数据域data和指针域next，写出下列数据结构的声明。【答】table可声明为数组或顺序表。（a）元素为结点指针或单链表对象，声明为以下之一：Node*table[N];//一维静态数组，元素为结点指针Node**table;//一维动态数组，元素为结点指针SinglyList*table;//一维动态数组，元素为单链表对象SeqList*>table;//顺序表，元素为结点指针SeqList>table;//顺序表，元

3、素为单链表对象（b）元素为结点，声明为以下之一：Nodetable[N];//一维静态数组，元素为结点Node*table;//一维动态数组，元素为结点SeqList>table;//顺序表，元素为结点2-10、oubleNode类能否继承单链表结点类Node？为什么？【答】不能。因为，如果DoubleNode类声明如下，继承单链表结点类Node。templateclassDoubleNode:publicNode//双链表结点类，继承单链表结点类{DoubleNode*prev;//指向前驱结点

4、的指针域};该类声明没有语法错，但语义不对，因为从基类继承来的next类型为Node*，仍然指向单链表结点。等价于以下声明，此处需要next指向双链表结点，类型是DoubleNode*。templateclassDoubleNode//双链表结点类{Tdata;//继承基类的成员变量Node*next;//继承基类的成员变量，数据类型错误DoubleNode*prev;};习题三3-7、Brute-Force模式匹配算法的主要特点是什么？算法思路是怎样的？给出最好情况和最坏情况及其时间复杂度。【答】Brute-F

5、orce是一种带回溯的模式匹配算法，它将目标串中所有长度为m的子串依次与模式串匹配，如果一次匹配失败，则模式串再与目标串的下一个子串匹配。Brute-Force算法最好情况下的时间复杂度是O(m)，最坏情况下的时间复杂度是O(m×n)。3-8、已知target="aaabaaab"、pattern="aaaa"，画出采用Brute-Force算法的模式匹配过程，给出比较结果、子串匹配次数和字符比较次数。【答】比较结果：匹配不成功，匹配子串位置为-1；子串匹配5次，字符比较14次。模式串"aaaa"的Brute-Force算法模式匹配过程3-9、已知ta

6、rget="abcababcabababcababc"，pattern="ababcababc"，求模式串改进的next数组，画出KMP算法模式匹配过程，给出比较结果，以及子串匹配次数和字符比较次数。本题目的：理解改进next数组的next[j]=next[k]。【答】比较结果：匹配成功，匹配子串位置为10；子串匹配3次，字符比较21次。表1-1模式串"ababcababc"的next数组j0123456789模式串ababcababc""中最长相同的前后缀子串长度k-1001201234与比较≠==≠=====next[j]-10-102-10-10

7、2KMP模式匹配算法过程如图3.5所示，算法说明如下。①第1次匹配，如图3.5（a）所示，，，；j=2，因，k=0，导致；因，导致，下次匹配需与比较，所以next[2]=next[0]=-1。②第2次匹配，如图3.5（b）所示，，…，；j=9，""="ababcabab"中最长相同的前后缀子串"abab"长度k=4，则下次匹配字符为；因，导致；再因="ab"，即"ababcabab"中有更短的相同前后缀子串"ab"，子串长度k=2，如图3.5（c）所示，下次匹配需与比较，所以next[9]=next[4]=2。③第3次匹配，如图3.5（d）所示，，…，

8、，匹配成功。图1.1模式串"ababcababc"的KMP算法模式匹配过程习题四4-4、写出中