发布时间 : 星期二 文章广州大学松田学院6数据结构复习题-广义表-参考答案更新完毕开始阅读765dc3bc8ad63186bceb19e8b8f67c1cfbd6ee43
6数据结构复习题(广义表)
一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ )
(√)(1)n维的多维数组可以视为n-1维数组元素组成的线性结构。 (√)(2)稀疏矩阵中非零元素的个数远小于矩阵元素的总数。
(ㄨ)(3)上三角矩阵主对角线以上(不包括主对角线中的元素),均为常数C。 (√)(4)数组元素可以由若干个数据项组成。
(√)(5)数组的三元组表存储是对稀疏矩阵的压缩存储。 (ㄨ)(6)任何矩阵都可以进行压缩存储。
(ㄨ)(7)广义表是线性表的推广,所以广义表也是线性表。 (ㄨ)(8)广义表LS=(a0,a1,……an-1),则an-1是其表尾。 (√)(9)广义表((a,b),a,b)的表头和表尾是相等的。 (√)(10)一个广义表的表尾总是一个广义表。
二.填空题
(1) 多维数组的顺序存储方式有按行优先顺序存储和 按列优先顺序存储
两种。
(2) 在多维数组中,数据元素的存放地址可以直接通过地址计算公式算出,
所以多维数组是一种 随机 存取结构。
(3) 在n维数组中的每一个元素最多可以有 n 个直接前驱。
(4) 输出二维数组A[n][m]中所有元素值的时间复杂度为 O(n*m) 。 (5) 数组元素a[0..2][0..3]的实际地址上2000,元素长度是4,则LOC[1,2]= 2024 。 LOC[1,2]=2000+(1*4+2)*4 (6)稀疏矩阵的三元组有 3 列。
(7)稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。 (8)n阶对称矩阵,如果只存储下三角元素,只需要 n(n-1)/2 个存储单元。 (9)稀疏矩阵A如下图所示,其非零元素存于三元组表中,三元组(4,1,5)按列优先顺序存储在三元组表的第 4 项。
稀疏矩阵A
1
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
(10)稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。 (11)任何一个非空广义表的表尾必定是 广义表(或子表) 。 (12)tail(head((a,b),(c,d))= b 。
(13) 设广义表((a,b,c)),则将c分离出来的运算是 head(tail(tail(head(L)))) 。 (14) 广义表((a,b),c,d),表尾是 (c,d) 。
(15) n阶下三角矩阵,因为对角线的上方是同一个常数,需要 n(n-1)/2+1 个存储单元。
(16)稀疏矩阵中有n个非零元素,则三元组有 n 行。 (17) 广义表LS=(a,(b),((c,(d))))的长度是 3 。 (18) 广义表LS=(a,(b),((c,(d))))的深度是 4 。 (19) 广义表L=((),L),则L的深度是 ∞ 。
(20) 广义表LS=(a,(b),((c,(d))))的表尾是 ((b),((c,(d)))) 。
三.选择题
(1)在一个m维数组中,( D )恰好有m个直接前驱和m个直接界后继。
A.开始结点 B.总终端结点 C.边界结点 D.内部结点
(2)对下述矩阵进行压缩存储后,失去随机存取功能是( D )。 A.对称矩阵 B.三角矩阵 C.三对角矩阵
D.稀疏矩阵
(3)在按行优先顺序存储的三元组表中,下述陈述错误的是( D )。
A. 同一行的非零元,是按列号递增次序存储的 B. 同一列的非零元,是按行号递增次序存储的 C. 三元组表中三元组行号递增的 D. 三元组表中三元组列号递增的 (4)对稀疏矩阵进行压缩存储是为了( B )。 A.降低运算时间 C.便于矩阵运算
B.节约存储空间 D.便于输入和输出
(5)若数组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] (6)下列矩阵是一个( B )
2
A.对称矩阵 B.三角矩阵 C.稀疏矩阵
D.带状矩阵
(7)在稀疏矩阵的三元组表示法中,每个三元组表示( D )。
A. 矩阵中非零元素的值
B. 矩阵中数据元素的行号和列号 C. 矩阵中数据元素的行号、列号和值 D. 矩阵中非零数据元素的行号、列号和值
(8)已知二维数组A[6][10],每个数组元素占4个存储单元,若按行优先顺序存放数组元素a[3][5]的存储地址是1000,则a[0][0]的存储地址是( B )。
A.872
B.860
C.868
D.864
1000=B+(3*10+5)*4 B=1000-(3*10+5)*4=1000-140=860 (9)广义表是线性表的推广,它们之间的区别在于( A )。 A.能否使用子表 B.能否使用原子项 C.是否能为空
D.表的长度
(10)下列广义表属于线性表的是( B )。
A.E=(a,E) B.E=(a,b,c) C.E=(a,(b,c))
A.a
D.E=(a,L);L=()
D.(c,d)
(11)广义表((a,b),c,d)的表尾是( D )。
B.d
C.(a,b)
(12)广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为( A )。
A.x A.b
B.(a,b) C.(x,(a,b)) B.(b)
C.(a,b)
D.A D.(d)
(13)tail(head((a,b),c,(c,d)))的结果是( B )。 (14)若广义表满足head(L)=tail(L),则L的形式是( B )
A.空表
B.若L=(a1,…,an),则a1=(a2,…an)
C.若L=(a1,…,an),则a1=a2=…=an) D.((a1),(a1)) (15)数组是一个( B )线性表结构。 A.非
B.推广了的 D.不加限制的
D.8
C.加了限制的
A.4
(16)数组A[0:1,0:1,0:1]共有( D )元素。
B.5
C.6
(17)广义表((a,b),c,d)的表头是( C )。
3
A.a A.a
B.d C.(a,b)
C.空表
D.(c,d) D.(a)
(18)广义表A=(a),则表尾为( C )。
B.(())
(19)以下( C )是稀疏矩阵的压缩存储方法。 A.一维数组 B.二维数组 C.三元组表
A.2
D.广义表
C.4 D.∞
(20)设广义表D=(a,b,c,D), 其深度为( D )。
B.3
四.算法阅读题
1. 已知A[]是一个下三角矩阵,下述算法的功能是什么?
int f1(int A[],int n)
{ // 设B[0..(n+1)n/2-1]存放下三角元素
int i,k,s=0; k=0; s=A[0];
for (i=0;i 算法功能:求矩阵主对角线上元素之和。 分析:注意k的变化依次为:0,2,5,9,14,正好是aii在A中的存储位置。在循环中k每次增加i+2。 第i行主对角线上的元素aii,其在A中的位置为: i(i+1)/2+i; (1) 第i+1行主对角线上的元素ai+1 i+1,其在A中的位置为: (i+1)(i+2)/2+(i+1), (2) (2)-(1)得i-2。 2. 在按行优先顺序存储的三元组表中,求某列非零元素之和的算法如下,填空以完成算 法。 #define SMAX 100 // 定义一个足够大的三元组表 typedef struct { 4