26．队列中的元素个数是( B )。 A．不变的
B．可变的
C．任意的
D．0
27．设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ A ）操作。 A．s->next=top->next；top->next=s C．s->next=top；top=top->next
B．top->next=s D．s->next=top；top=s
28．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B )。 A．5和1 B．4和2 C．2和4 D．1和5 29．以下属于队列的操作有( D )。 A．在队首插入元素 C．按元素的大小排序 LQ->front
H A B C D LQ->rear A．LQ->front== LQ->rear B．LQ->rear==NULL C．LQ->front!= LQ->rear
D．LQ->front==null
Λ
B．删除值最小的元素 D．判断是否还有元素
30.带头结点的链队列LQ示意图如下，LQ为空时（ A ）
第五章
一．判断题
（×）（1）串的长度是指串中不同字符的个数。 （×）（2）串是n个字母的有限序列。 （√）（3）空串不等于空格串。
（×）（4）如果两个串含有相同的字符，则说明它们相等。
（×）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （√）（6）串的堆分配存储是一种动态存储结构。 （×）（7）“DT”是“DATA”的子串。 （×）（8）空串与空格串是相同的。
（×）（9）串中任意个字符组成的子序列称为该串的子串。 （√）（10）子串的定位运算称为模式匹配。
（√）（11）n维的多维数组可以视为n-1维数组元素组成的线性结构。 （√）（12）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。
（ㄨ）（13）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
（ㄨ）（14）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列号和值。
（ㄨ）（15）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。 （√）（16）对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。 （ㄨ）（17）任何矩阵都可以进行压缩存储。
（√）（18）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列号和值。
（√）（19）数组元素可以由若干个数据项组成。
（√）(20）稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。
二．填空题
1．长度为零的字符串称为 空串 。
2．在串的运算中，EqualStr(aaa，aabb)的值为 < 0 。 3．串的顺序存储结构简称为 顺序串 。 4．串的链式存储结构简称为 链式串 。
5．求子串函数SubStr(\is 30 July,2005\的结果是： July 。
6．设S=\，则len(s)= _ 20 。
7．由零个或多个字符组成的有限序列称为 字符串 （或串）。 8．字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。 9．设S=“A:/mydocument/text1.doc”，则strlen(S)= 23 。 10．在空串和空格串中，长度不为0的是 空格串 。
11．串顺序存储紧凑格式的优点是： 空间利用率高 ,对串的字符处理效率低。
12．两个串相等是指两个串相长度等，且对应位置的 字符都相同 。 13．串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。 14．模式匹配成功的起始位置称为： 有效位移 。 15．所有模式匹配不成功的起始位置称为： 无效位移 。
16.多维数组的顺序存储方式有行优先顺序存储和 列优先顺序存储 两种。 17.同一数组中各元素的长度 相等 。
18.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种 随机 存取结构。
19. 在n维数组中的每一个元素最多可以有 n 个直接前驱。
20.输出二维数组A[m][n]中所有元素值的时间复杂度为 O(m*n) 。 数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则Loc[1,2]=
2024 。
21.数组的三元组存储是对 稀疏矩阵 的压缩存储 22.稀疏矩阵的三元组有 3 列。
23.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。 24.n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。 25.稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按
行优先顺序存储在三元组表的第 6 项。
稀疏矩阵A
A=
8 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 26.稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。
27． n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n（n-1）/2+1 个存储单元。
28．稀疏矩阵中有n个非零元素，则三元组有 n 行。
29.稀疏矩阵的三元组中第2列存储的是数组中非零元素所在的 列数 。 30.稀疏矩阵的三元组中，第3列存储的是稀疏数组中的 非零元素 。
三．选择题
1．串是一种特殊的线性表，其特殊性体现在（ B ）。 A.可以顺序存储 B．数据元素是一个字符 C.可以链接存储 D．数据元素可以是多个字符
2．设目标串T=\，P=\，则该模式匹配的有效位移为 ( C )。
A．2
B．3 C．4 D. 5
3．设有两个串p和q，求q在p中首次出现的位置的运算称作( B )。 A.连接 B．模式匹配 C.求子串 为( C )。
A．0 B．小于0 5．串的模式匹配是指（ D ）。
A．判断两个串是否相等 B．对两个串比较大小
C．找某字符在主串中第一次出现的位置
D．找某子串在主串中第一次出现的第一个字符位置 6．朴素模式匹配算法在最坏情况下的时间复杂度是( D )。 A．O（m） B．O（n） 7．以下论断正确的是( A )。 A．\是空串，\ \空格串 C．\
B．\是\的子串 D．\
C．0（m+n） D．0（m*n）
C．大于0
D．不确定
D．求串长
4. S1=\，S2=\，执行串比较函数EqualStr(S1,S2) 后的结果
8. S1=\，S2=\，执行串连接函数ConcatStr(S1,S2)后
的结果为( A )。
A．\ B．\
C．\ D．\9．某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A．链式 B．顺序 C．堆结构
D．无法确定
10. S=\，LenStr(S)=( D )。 A．18 B．19 C．20 D．21 11．设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。 A. 串连接 C. 求子串 ( A )。
A．\
B．\
C．\ D．\
13．在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ C ）存储方式比较合适。
A．链式 B．顺序 C．堆结构 D．无法确定 14. 设串S1=\，S2=\则ConcatStr(S1,S2)=( B )。 A．\
B．\
D. \
C．\
B．模式匹配 D．串比较
12. S1=\，S2=\，执行串连接函数ConcatStr(S1,S2)后的结果为
15. 以下论述正确的是（ C ）。 A．空串与空格串是相同的
B．\是\的子串
C．空串是零个字符的串 D. 空串的长度等于1
16. 在一个m维数组中，（ D ）恰好有m个直接前驱和m个直接界后继。
A.开始结点 B．总终端结点 C.边界结点 D．内部结点 17. 多维数组的体积与（ A ）无关。
A．数组的基地址 B．维数 C．各维的上下界
D．结点的大小
18. 对下述矩阵进行压缩存储后，失去随机存取功能是（ D ）。 A．对称矩阵 B．三角矩阵 C．三对角矩阵
D．稀疏矩阵
19. 在按行优先顺序存储的三元组表中，下述陈述错误的是（ D ）。
A． 同一行的非零元，是按列号递增次序存储的 B． 同一列的非零元，是按行号递增次序存储的 C． 三元组表中三元组行号递增的 D． 三元组表中三元组列号递增的 20. 以下（ C ）是稀疏矩阵的压缩存储方法。
A．一维数组 B．二维数组 C．三元组表
D．广义表
B．节约存储空间 D．便于输入和输出
21. 对稀疏矩阵进行压缩存储是为了（ B ）。 A．降低运算时间 C．便于矩阵运算
22. 若数组A[0..m[0..n]按列优先顺序存储，则aij的地址为（ A ）。 A．LOC(a00)+[j*m+i]
B．LOC(a00)+[j*n+i] D．LOC(a00)+[(j-1)*m+i-1]
C．LOC(a00)+[(j-1)*n+i-1] 23. 下列矩阵是一个（ B ）
A．对称矩阵 B．三角矩阵 C．稀疏矩阵
D．带状矩阵
24.在稀疏矩阵的三元组表示法中，每个三元组表示（ D ）。
A． 矩阵中非零元素的值
B． 矩阵中数据元素的行号和列号 C． 矩阵中数据元素的行号、列号和值 D． 矩阵中非零数据元素的行号、列号和值
25. 已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（ B ）。
A．872 A．972
B．860 B．979
C．868 C．980
D．864 D．982
26. 已知二维数组A[8][10]中，a12的地址为1000，则a00的地址为（ C ）。 27. 数组与一般线性表的区别主要在（ C ）。 A．不能进行插入操作 C．逻辑结构方面 A．非
B．不能进行删除操作
D．存储方面
B．推广了的 D．不加限制的
D．8
28. 数组是一个（ B ）线性表结构。 C．加了限制的
A．4 （ D ）。
A．1000
B．1008
C．1010
D．1020
29. 数组A[0:1,0:1,0:1]共有（ D ）元素。
B．5
C．6
30. 二维数组a[4][4]，数组的元素起始地址Loc[0][0]=1000，元素长度为2，则Loc[0][0]为