第4章 串与数组 习题参考答案

《第4章 串与数组 习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题四参考答案一、选择题1．下面关于串的叙述中，哪一个是不正确的？（B）　　A．串是字符的有限序列　　B．空串是由空格构成的串　　C．模式匹配是串的一种重要运算　　D．串既可以采用顺序存储，也可以采用链式存储2．串的长度是指(A)A.串中包含的字符个数B.串中包含的不同字符个数C.串中除空格以外的字符个数D.串中包含的不同字母个数3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）　　A．求子串        B．联接           C．模式匹配        

2、  D．求串长4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是(C)。A.O(m)B.O(n)C.O(n+m)D.O(n×m)5.串也是一种线性表，只不过(A)。A.数据元素均为字符B.数据元素是子串C.数据元素数据类型不受限制D.表长受到限制6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。A.13B.33C.18D.407.有一个二维数组A[1..6,0..7]，每个

3、数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个字节。A.48B.96C.252D.2888.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素A[5，8]的存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+2259.稀疏矩阵的三元组存储表示方法(B)A.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可B.矩阵的非零元素个数和位置在操作过程中变化不大时

4、较有效C.是一种链式存储方法D.比十字链表更高效10.用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有(A)域的结点表示。A.5B.4C.3D.2二、填空题1.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。2．串长度为0的串称为空串，只包含空格的串称为空格串。3.若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。4.寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。5.模式串t="ababaab"的next[]数组值为-1001231，nextval[]

5、数组值为-10-10-130。6.设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1140。7．在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和非零元个数。8．一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n+1)/2。9．对矩阵压缩的目的是为了节省存储空间。10.稀疏矩阵一般采用的压缩存储方法有两种，即三元组和十字链

6、表。三、算法设计题1．编写基于SeqString类的成员函数count(),统计当前字符串中的单词个数。参考答案:publicintcount(){intwordcount=0;//单词个数charcurrChar,preChar;for(inti=1;i

7、

8、(int)(currChar)>

9、122//当前字符不是字母

10、

11、((int)(preChar)>90&&(int)(preChar)<97))&&(((int)(preChar)>=65&&(int)(preChar)<=90)//当前字符的前一个字符是字母

12、

13、((int)(preChar)>=97&&(int)(preChar)<=122))){wordcount++;}}returnwordcount;}2．编写基于SeqString类的成员函数replace(begin,s1,s2)。要求在当前对象串中，从下标begin开

14、始，将所有的s1子串替换为s2串。参考答案://beginint开始位置;s1String原始字符串;s2String目标字符串;publicSeqStringreplace(intbegin,SeqStrings1,SeqStrings2){if(s1==null

15、

16、s2==null){returnnull;}SeqStringss=newSeqString("");//产生空串SeqStringsource=this;intindex=-1;while((index=source.index