数据机构第四章——java语言描述第4章串与数组习题参考答案.pdf

数据机构第四章——java语言描述第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.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进

行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，

则a85的地址为（B）。

A.13B.33C.18D.40

7.有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节

存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个

字节。

A.48B.96C.252D.288

8.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存

首地址BA开始以列序为主序顺序存放，则数组元素A[5，8]的存储首地

址为(B)。

A.BA+141B.BA+180C.BA+222D.BA+225

9.稀疏矩阵的三元组存储表示方法(B)

A.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即

可

B.矩阵的非零元素个数和位置在操作过程中变化不大时较有效

C.是一种链式存储方法

D.比十字链表更高效

10.用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有(A)

域的结点表示。

A.5B.4C.3D.2

二、填空题

1.

2．串长度为0

3.

4.

5.模式串模式串的ne某t[]

ne某tval[]数组值为。

6.设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，

若以行序为主序顺序

存储，则元素

A[5,5]

7．在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组

表以外，还需要表示矩

阵的行数、列数和

8．一个n某n

的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则

其元素压

9

10.

三、算法设计题

1．编写基于SeqString类的成员函数count(),统计当前字符串中的

单词个数。

参考答案:

publicintcount(){

intwordcount=0;//单词个数

charcurrChar,preChar;

for(inti=1;ithi.length();i++){

currChar=thi.charAt(i);//当前字符

preChar=thi.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(i