内容发布更新时间 : 2024/11/5 13:04:55星期一 下面是文章的全部内容请认真阅读。
习题四 参考答案
一、选择题
1．下面关于串的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储 2．串的长度是指( A )
A. 串中包含的字符个数 B. 串中包含的不同字符个数 C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ） A．求子串 B．联接 C．模式匹配 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. 13 B. 33 C. 18 D. 40
7. 有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ D ）个字节。 A. 48 B. 96 C. 252 D. 288
8. 设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素 A[5，8]的存储首地址为( B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 9. 稀疏矩阵的三元组存储表示方法( B )
A. 实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可 B. 矩阵的非零元素个数和位置在操作过程中变化不大时较有效 C. 是一种链式存储方法 D. 比十字链表更高效
10. 用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有( A )域的结点表示。
A.5 B.4 C. 3 D. 2 二、填空题
1. 一个串的任意连续字符组成的子序列称为串的 子串 ，该串称为 主串 。 2．串长度为0的串称为 空串 ，只包含空格的串称为 空格串 。 3. 若两个串的长度相等且对应位置上的字符也相等，则称两个串 相等 。 4. 寻找子串在主串中的位置，称为 模式匹配 。其中，子串又称为 模式串 。 5. 模式串t=\的next[]数组值为 -1001231 ，nextval[]数组值为 -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.稀疏矩阵一般采用的压缩存储方法有两种，即 三元组 和 十字链表 。 三、算法设计题
1． 编写基于SeqString类的成员函数count(),统计当前字符串中的单词个数。 参考答案:
public int count() {
int wordcount = 0; //单词个数 char currChar, preChar;
for (int i = 1; i < this.length(); i++) { currChar = this.charAt(i); //当前字符 preChar = this.charAt(i - 1); //前一个字符
if (((int) (currChar) < 65 || (int) (currChar) > 122 //当前字符不是字母
|| ((int) (preChar) > 90 && (int) (preChar) < 97)) && (((int) (preChar) >= 65 && (int) (preChar) <= 90) //当前字符的前一个字符是字母
|| ((int) (preChar) >= 97 && (int) (preChar) <= 122))) { wordcount++; } }
return wordcount; }
2． 编写基于SeqString类的成员函数replace(begin,s1,s2)。要求在当前对象串中，从下
标begin开始，将所有的s1子串替换为s2串。 参考答案:
//begin int 开始位置;s1 String 原始字符串; s2 String 目标字符串; public SeqString replace(int begin, SeqString s1, SeqString s2) { if (s1 == null || s2 == null) { return null; }
SeqString ss = new SeqString(\产生空串 SeqString source = this; int index = -1;
while ((index = source.indexOf(s1, begin)) != -1) { ss.concat(source.substring(0, index)); //串连接 ss.concat(s2);
source = (SeqString) source.substring(index + s1.length());
//取子串
}
ss.concat(source); //串连接 return ss; }
3． 编写基于SeqString类的成员函数reverse()。要求将当前对象中的字符反序存放。
参考答案:
public SeqString reverse() {
for (int i = 0, j = this.length() - 1; i < j; i++, j--) { char temp = this.charAt(i); setCharAt(i, this.charAt(j)); setCharAt(j, temp); }
return this; }
4． 编写基于SeqString类的成员函数deleteallchar(ch)。要求从当前对象串中删除其值
等于ch的所有字符。 参考答案:
public SeqString deleteAllChar(char ch) {
SeqString s1 = new SeqString(String.valueOf(ch)); if (s1 == null) { return null; }
SeqString ss = new SeqString(\产生空串 SeqString source = this; //当前串赋值到sourse int index = -1;
while ((index = source.indexOf(s1, 0)) != -1) {
ss.concat(source.substring(0, index)); //串连接 source = (SeqString) source.substring(index + 1); //取子串 }
ss.concat(source); //串连接 return ss; }
5． 编写基于SeqString类的成员函数stringcount(str)。要求统计子串str在当前对象串
中出现的次数，若不出现则返回0。 参考答案:
public int stringCount(SeqString str) { SeqString source = this.curstr; int count = 0, begin = 0;