2025年广州大学松田学院6数据结构复习题-广义表-参考答案 .pdfVIP

博观而约取，厚积而薄发。——苏轼

6数据结构复习题（广义表）

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）

（√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。

（√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。

（ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。

（√）（4）数组元素可以由若干个数据项组成。

（√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。

（ㄨ）（6）任何矩阵都可以进行压缩存储。

（ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。

（ㄨ）（8）广义表LS=（a,a,……a），则a是其表尾。

01n-1n-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项。

800000

0110000

000600

A=

030070

050000

000090

稀疏矩阵A

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

（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）稀