【安徽大学-数据结构】第45章习题.docx

习题四1单项选择题
1. 空串与空格串是相同的，这种说法—O正确B.不正确
2. 串是一中特殊的线性表，其特殊性体现在—。
A. 可以顺序存储数据元素是一个字符
B. 可以链接存储数据元素可以是多个字符
3. 设有两个串p和q,求q在P中首次出现的位置的运算称作—oA.连接B.模式匹配
C.求子串D.求串长设串 si二'ABCDEFG' ,s2二'PQRST'，函数con (x, y)返回 x和y 串的连接串,subs(s, i, j)
返回串s的从序号i的字符开始的j个字符组成的子串,len (s)返回串s的长度，则con (subs (si, 2, len (s2)), subs (si, len (s2), 2))的结果串是。
A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF
4.2填空题(将正确的答案填在相应的空中)串的两种最基本的存储方式是—o
1. 两个串相等的充分必要条件是—o空串是—，其长度等于—o
2. 空格串是—，其长度等于—。
3. 设 s='LAM曲^TEACHER'，其长度是。
4.3算法设计题：
1. 编写算法，从串s中删除所有和串t相同的子串。
2. 编写算法，实现串的基本操作Replace (&S, T, V) o习题五 数组
4. 1 单项选择题(其中A[i.. j]表示下标从i到j)常对数组进行的两种基本操作是—o
A.建立与删除B.索引和修改C.查找和修改D.查找与索引
1. 二维数组M的成员是6个字符(每个字符占一个存储单元，即一个字节)组成的串，行
下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要—①—个字节；M 的第8列和第5行共占—②—个字节。
① A. 90B. 180C. 240D. 540A. 108B. 114C. 54D. 60
4. 数组A中，每个元素A的长度为3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是o
A. 80B. 100C. 240D. 270数组A中每个元素A的长度为3个字节，行下标i从1到8,列下标j从1到10,从
首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8] [5]的起始地址为oA. SA+141 B. SA+144 C. SA+222 D. SA+225
5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8,列下标j从1到10,从 首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5] [8]的起始地址为A. SA+141 B. SA+180 C. SA+222 D. SA+225
7若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B (1..(n(n+l))/2)中，则在B中确定aij (i1) /2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是()o
A. i (i-1) /2+jB. j (j-1) /2+iC. i (j-i) /2+1D. j
(i-1) /2+1设二维数组A[l. . m, 1. . n](即川行n列)按行存储在数组B[l. . m*n]中，则二维数 组元素A[i, j]在一维数组B中的下标为()o
A. (i-l)*n+jB. (i-l)*n+jTC. i*(j-l)D.
j*m+iT设每个整型数占2字节，则用三元组表

设每个整型数占2字节，则用三元组表
9. 有一个100*90的稀疏矩阵，非0元素有10个,示该矩阵时所需的字节数是(

示该矩阵时，所需的字节数是(
)o
A. 60
B. 66
C.

10. 数组A[0..4,-l..-3, 5.. 7]中含有元素的个数()oC.

C.
A. 55B. 4536D. 16
13用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿 链移动的操作为()。
A. j=r[j]. nextB.j=j+1C.
j=j->nextD. j=r[j]-> next对稀疏矩阵进行压缩存储目的是()o
A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度
14. 己知广义表L=((x, y, z), a, (u, t, w)),从L表中取出原子项t的运算是()。
A. head (tail (tail (L)))tail (head (head (tail (L))))
B. head (tail (head (tail (L))))head (tail (head (tail (tail (L)))))
15. 己知广义表LS= ((a, b, c), (d, e, f)),运用head和tail函数取出LS中原子e的运算是)o
B.
C.
D.
A. head(tail (LS)) tail(head(LS)) head(tail(head(tai 1 (LS))) head(tai 1(tai 1(head (LS)))))o

)o
16. 广义表A二(a, b, (c, d), (e, (f, g))),则下面式子的值为(Head(Tail(Head(Tai 1(Tai 1(A)))))
B. (d)
D. d
A. (g)C. c
18.已知广义表：A= (a, b), tai 1 (head(tai 1(C)))二( A.
(b)
E.
B=(A,A), C= (a, (b, A), B),求下列运算的结果: )o
B. A
b
F.
C.
(A)
D.
19.
A.
((c, d))
广义表运算式Tail (((a, b), (c, d)))的操作结果是( (c, d)B.
D. d
)o
c, d
C.

(L)操作后的结果为(
)o
C.

20.广义表 L=(a, (b, c)),进行 TailA. cB. b
5.2填空题(将正确的答案填在相应的空中，其中A[i, j]表示下标从i到j)已知二维数组A[m] [n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个 元素的存储地址是LOC(A[O] [0]),则A[i][j]的地址是—o
1. 二维数组A[10] [20]采用列序为主方式存储，每个元素占一个存储单元并且A[0] [0]的存储地址是200,则A[6] [12]的地址是o
2. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且 A[10] [5]的存储地址是1000,则A[18] [9]的地址是 。