习题四参考答案
一、选择题
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="ababaab"的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.稀疏矩阵一般采用的压缩存储方法有两种，即三元组和十字链表。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。