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

数据结构复习题广义表一判断题下列各题正确的请在前面的括号内打错误的打维的多维数组可以视为维数组元素组成的线性结构稀疏矩阵中非零元素的个数远小于矩阵元素的总数上三角矩阵主对角线以上不包括主对角线中的元素均为常数数组元素可以由若干个数据项组成数组的三元组表存储是对稀疏矩阵的压缩存储任何矩阵都可以进行压缩存储广义表是线性表的推广所以广义表也是线性表广义表则是其表尾广义表的表头和表尾是相等的一个广义表的表尾总是一个广义表二填空题多维数组的顺序存储方式有按行优先顺序存储和按列优先顺序存储两种在多维数组中数据元素的存放地址可以直接通过地址计算公式算出所以多维数组是一种随机存取结构在维数组中的每一个元素最多可以有个直接前驱输出二维数组中所有元素值的时间复杂度为数组元素的实际地址上元素长度是则稀疏矩阵的三元组有列稀疏矩阵的三元组中第列存储的是数组中非零元素所在的行数阶对称矩阵如果只存储下三角元素只需要个存储单元稀疏矩阵如下图所示其非零元素存于三元组表中三元组按列优先顺序存储在三元组表的第项稀疏矩阵稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种任何一个非空广义表的表尾必定是广义表或子表设广义表则将分离出来的运算是广义表表尾是阶下三角矩阵因为对角线的上方是同一个常数需要个存储单元稀疏矩阵中有个非零元素则三元组有行广义表的长度是广义表的深度是广义表则的深度是广义表的表尾是三选择题在一个维数组中恰好有个直接前驱和个直接界后继开始结点总终端结点边界结点内部结点对下述矩阵进行压缩存储后失去随机存取功能是对称矩阵三角矩阵三对角矩阵稀疏矩阵在按行优先顺序存储的三元组表中下述陈述错误的是同一行的非零元是按列号递增次序存储的同一列的非零元是按行号递增次序存储的三元组表中三元组行号递增的三元组表中三元组列号递增的对稀疏矩阵进行压缩存储是为了降低运算时间节约存储空间便于矩阵运算便于输入和输出若数组按列优先顺序存储则的地址为下列矩阵是一个对称矩阵三角矩阵稀疏矩阵带状矩阵在稀疏矩阵的三元组表示法中每个三元组表示矩阵中非零元素的值矩阵中数据元素的行号和列号矩阵中数据元素的行号列号和值矩阵中非零数据元素的行号列号和值已知二维数组每个数组元素占个存储单元若按行优先顺序存放数组元素的存储地址是则的存储地址是广义表是线性表的推广它们之间的区别在于能否使用子表能否使用原子项是否能为空表的长度下列广义表属于线性表的是广义表的表尾是广义表则运算为的结果是若广义表满足则的形式是空表若则若则数组是一个线性表结构非推广了的加了限制的不加限制的数组共有元素广义表的表头是广义表则表尾为空表以下是稀疏矩阵的压缩存储方法一维数组二维数组三元组表广义表设广义表其深度为四算法阅读题已知是一个下三角矩阵下述算法的功能是什么设存放下三角元素算法功能求矩阵主对角线上元素之和分析注意的变化依次为正好是在中的存储位置在循环中每次增加第行主对角线上的元素其在中的位置为第行主对角线上的元素其在中的位置为得在按行优先顺序存储的三元组表中求某列非零元素之和的算法如下填空以完成算法定义一个足够大的三元组表非零元素的行列值三元组类型定义稀疏矩阵矩阵的行列及非零元素的个数三元组表三元组表的存储类型求第列非零元素之和列错五编程题试编写求一个三元组表的稀疏矩阵对角线元素之和的算法试编写求广义表中原子元素个数的算法解设为原子个数则求广义表中原子元素个数的算法可递归定义如下为空表尾原子元素个数非空且表头为原子元素表头子表原子元素个数表尾原子元素个数非空且表头子表试编写求广义表最大中原子元素个数的算法例在按行存储的三元组表中求某列的非零元素之和的算法如下请填空以完成算法定义一个足够大的三元组表定义三元组三元组非零元素的行列和值定义稀疏矩阵稀疏矩阵行列和非零元素的个数三元组表求第列非零元素之和非零元素的个数是不大于列号不合法分析本算法首先检查非零元素的个数是否大于以及给定的列号是否合法然后依次扫描三元组表将列号等于给定列号的非零元素相加因此有