内容发布更新时间 : 2024/5/20 7:52:41星期一 下面是文章的全部内容请认真阅读。

第五章 数组与广义表作业（50分）

一、选择题（每题 2 分，共 20 分）。

1．两个串相等必有（ A ，D（或写D也可以得全分））。 A．串长度相等 B．串长度任意

C．串中各位置字符任意

D．串中各位置字符均对应相等

2．对称矩阵的压缩存储：以行序为主序存储下三角中的元素，包括对角线上的元素。二维下标为( i, j ),存储空间的一维下标为k，给出k与 i, j (i

3．二维数组A[7][8]以列序为主序的存储，计算数组元素A[5][3] 的一维存储空间下标 k=（ C ）。

A．38 B．43 C．26 D．29

4．已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ D ）。

A．108 B.180 C.176 D.112 5. 下面（ C ）不属于特殊矩阵。

A．对角矩阵 B. 三角矩阵

C. 稀疏矩阵 D. 对称矩阵

6. 假设二维数组M[1..3, 1..3]无论采用行优先还是列优先存储，其基地址相同，那么在两种存储方式下有相同地址的元素有（ A ）个。

A. 3 B. 2 C. 1 D. 0

7. 若Tail(L)非空，Tail(Tail(L))为空，则非空广义表L的长度是（ B ）。(其中Tail表示取非空广义表的表尾)

A. 3 B. 2 C. 1 D. 0 8．串的长度是（ D ）。

A．串中不同字母的个数 B．串中不同字符的个数

C．串中所含字符的个数，且大于0 D．串中所含字符的个数

9．已知广义表(( ),(a), (b, c, (d), ((d, f))))，则以下说法正确的是（ A ）。 A．表长为3，表头为空表，表尾为((a), (b, c, (d), ((d, f)))) B．表长为3，表头为空表，表尾为(b, c, (d), ((d, f))) C．表长为4，表头为空表，表尾为((d, f))

D．表长为3，表头为(())，表尾为((a), (b, c, (d), ((d, f))))

10．广义表A=(a,b,c,(d,(e,f)))，则Head(Tail(Tail(Tail(A))))的值为（ A ）。(Head与Tail分别是取表头和表尾的函数)

A．(d,(e,f)) B．d C．f D．(e,f)

二、填空题（每空 2 分，共 8 分）。

1．一个广义表为 F = (a, (a, b), d, e, (i, j), k)，则该广义表的长度为_________6___________。GetHead(GetTail(F))= ______（a,b）__________。

2．一个n*n的对称矩阵，如果以行或列为主序压缩存放入内存，则需要 n(n+1)/2 个存储单元。

3．有稀疏矩阵如下： 0 0 5 7 0 0 -3 0 0 0 4 0 0 2 0

它的三元组存储形式为: （1,3,5）（2,1,7）(3,1,-3) (4,2,4) (5,2,2) 。

三、综合题（共 22 分）。

1．稀疏矩阵如下图所示，描述其三元组的存储表示，以及转置后的三元组表示（8分）。

0 -3 0 0 0 4 0 6 0 0 0 0 0 0 7 0 15 0 8 0 转置前：

（1,2，-3）（2，1,4）（2,3,6）（3,5,7）（4,2,15），（4,4,8） 转置后：

（1,2,4）（2,1，-3）（2,4,15），（3,2,6）（4,4,8）（5,3,7） 2. 稀疏矩阵M的三元组表如下，请填写M的转置矩阵T的三元组表，并按要求完成算法。

（1）写出M矩阵转置后的三元组存储（6分）：

M的三元组表： T的三元组表： i j e i j e

1 2 3 2 1 3

1 5 6 3 2 4

2 3 4 4 2 5

4 3 5 2 4 5

5 1 6 3 4 5 5 3 6 3 5 6

2）如下提供了矩阵采用三元组存储时查找指定行号（m）和列号（n）元素值的算法框架，将代码补充完整（8分）。 typedefstruct{ inti,j;

ElemType e;

}Triple;

typedefstruct{

Triple data[MAXSIZE+1]; //data[0]未用

intmu,nu,tu; //矩阵的行数，列数和非零元的个数 }TSMatrix；

voidFind_TSMatrix(TSMatrix M, int m, int n, ElemType&e)

//M为要查找的稀疏矩阵三元组存储，m为要查找的元素的行号，n为列号，e为查找后得到的值。 {

for ( i=1 ; i<=M.tu ;i++)

if( M.data[i].i==m&&M.data[i].j==n ) { e=M.data[i].e; break ; }

if( i>M.tu) e=0; }