第4章 串与数组 习题参考答案
-
习题四
参考答案
一、选择题
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.
< br>设有一个
10
阶的对称矩阵
A<
/p>
，采用压缩存储方式，
以行序为主进行存储，
a
11
为第一元素，
其存储地址为
1
，每个元素占一个地址空间，则
a<
/p>
85
的地址为（
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
< br>，
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
类的成员函数
c
ount(),
统计当前字符串中的单词个数。
参考答案
:
public int
count() {
int wordcount = 0;
//
单词个数
char currChar, preChar;
for
(int i = 1; i < (); i++) {
currChar = (i); //
当前字符
preChar = (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
类的成员函数
r
eplace(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 =
f(s1, begin)) != -1) {
(ing(0, index)); //
串连接
(s2);
source = (SeqString) ing(index + ());
//
取子串
}
(source);
//
串连接
return ss;
}
3
．
编写基
于
SeqString
类的成员函数
r
everse()
。要求将当前对象中的字符反序存放。
参考答案
:
public
SeqString reverse() {
for (int
i = 0, j = () - 1; i < j; i++, j--) {
char temp = (i);
setCharAt(i, (j));
setCharAt(j, temp);
}
return this;
}
4
．
编写基
于
SeqString
类的成员函数
d
eleteallchar(ch)
。要求从当前对象串中删除其值
等于
ch
的所有字符。
参考答案
:
public
SeqString deleteAllChar(char ch) {
SeqString s1 = new SeqString(f(ch));
if (s1 == null) {
return
null;
}
SeqString ss = new
SeqString(
产生空串
SeqString source = this;
//
当前串赋值到
sourse
int index = -1;
while ((index =
f(s1, 0)) != -1) {
(ing(0,
index)); //
串连接
source = (SeqString)
ing(index + 1); //
取子串
}
(source);
//
串连接
return ss;
}
5
．
编写基
于
SeqString
类的成员函数
s
tringcount(str)
。
要求统计子串
str
在当前对象串
中出现的次数，若不出现则返回
0
。
参考答案
:
public int
stringCount(SeqString str) {
SeqString source =
int count
= 0, begin = 0;
int index;
while ((index = f(str, begin))
!= -1) {
count++;
begin = index + ();
}
return
count;
}
6
．
鞍点是
指矩阵中的元素
a
ij
是第
i
行中值最小的元素，同时又是第
j
列中值最大的元素。
试设计一个算法求矩阵
A
的所有鞍点。
参考答案
:
//
存放矩阵中鞍点的类
class Result {
TripleNode data[];
//
三元组表，存放鞍点的行、列、值
int nums;
//
鞍点个数
public
Result(int maxSize) {
//
构造方法
data
=
new
TripleNode[maxSize]; //
为顺序表
分配
maxSize
个存储单元
for (int i = 0; i < i++) {
data[i] = new TripleNode();
}
nums = 0;
}
}
//
返回矩阵中的所有鞍点
public Result allSaddlePoint(int[][]
ar) {
int i, j, flag, m, n;
Result re = new Result();
for (i = 0; i < i++) {
m = i;
n = 0;
flag = 1;
//
假设当前结点是鞍点
for (j = 0; j < ar[i].length; j++) {
if (ar[i][j] < ar[m][n]) {
n = j;
}
}
for (j = 0; j < j++) {
if (ar[j][n] >
ar[m][n]) {
flag =
0; //
不是鞍点
}
}
if (flag == 1) {
//
是鞍点，将其加入
[] = new TripleNode(m, n, ar[m][n]);
++;
}
}
return re;
}
7
．
设计算
法，求出二维数组
A[n,n]
的两条对角线元素之和
参考答案
:
public static int sumOfDiagonal(int[][]
a) {
int i, n = a[0].length,
sum1 = 0, sum2 = 0, sum;
for (i
= 0; i < i++) {
sum1 +=
a[i][i]; //
主对角线之和
sum2 += a[i][n - i - 1];
//
副对角线之和
}
sum = sum1 + sum2;
if (n % 2 == 1) {
//
若矩阵行数为奇数，则减去两条对角线相交的元素。
sum -= a[n / 2][n / 2];
}
return
sum;
}
四、上机实践题
1.
在顺序串类
SeqString
中增加一个主函数，
测试各成员函数的正确性。
参考答案
:
package
ch04Exercise;
import ing;
public class Exercise4_4_1 extends
SeqString{
public static void
main(String args[]) {
char[]
chararray = {'W', 'o', 'r', 'l', 'd'};
SeqString s1 = new SeqString();
//
构造一个空串
SeqString s2 = new
SeqString(
以字符串常量构造串对象
SeqString s3 = new
SeqString(chararray);
//
以字符数组构造串对象
n(
串
s1=
(0, s2);
n(
串
< br>s1
在第
0
个字符前插入串
s2
后
,s1=
(1, s3);
n(
串
< br>s1
在第
1
个字符前插入串
s3
后
,s1=
(1, 4);
n(
串
s1
删除第
1
到第
3
个字符后
,s1=
n(
串
s1
中从第
2
到第
5
个字符组成的子串是：<
/p>
ing(2, 6));
}
}
运行结果
:
2.
已
知两个稀疏矩阵
A
和
B
，试基于三元组顺序表或十字链表的存储结构，编程实现
A+B
的运算。
参考答案
:
package ch04Exercise;
import
Matrix;
public class Exercise4_4_2 {
public static SparseMatrix
addSMatrix(SparseMatrix a, SparseMatrix b) {
//
计算两个三元组表示的稀疏矩阵之和
if (s() != s() || s() != s()) {
n(
这两个矩阵不能相加
return null;
}
SparseMatrix c = new SparseMatrix(s() + s());
int i = 0, j = 0, k = 0;
int len=0;
while (i < s() && j < s()) {
if (a()[i].getRow() < a()[j].getRow()) { //A
行
行
a()[k].setColumn(a()[i].getColumn());
a()[k].setRow(a()[i].getRow());
a()[k].setValue(a()[i].getValue());
s(++k);
i++;
} else if (a()[i].getRow()
== a()[j].getRow()) { // A
行号
=B
行号
if
(a()[i].getColumn()
==
a()[j].getColumn())
{ //A
列
=B
列
if
(a()[i].getValue()
+
a()[j].getValue()
!=
0)
{
a()[k].setColumn(a()[i].getColumn());
a()[k].setRow(a()[i].getRow()); -