2022年数据结构—广义线性表定义 .pdf

1 第4 章 广义线性表 多维数组和广义表课后习题讲解1. 填空 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。【解答】存取，修改，顺序存储【分析】 数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 二维数组A 中行下标从10 到 20，列下标从 5 到 10 ，按行优先存储，每个元素占4 个存储单元， A105 的存储地址是1000 ，则元素A1510的存储地址是（）。【解答】 1140 【分析】数组 A 中每行共有6 个元素，元素 A1510 的前面共存储了(15-10) 6+5 个元素，每个元素占4 个存储单元，所以，其存储地址是1000+140=1140。 设有一个10 阶的对称矩阵A 采用压缩存储，A00 为第一个元素，其存储地址为d，每个元素占1 个存储单元，则元素A85 的存储地址为（）。【解答】 d+41 【分析】元素A85 的前面共存储了(1+2+8)+5=41个元素。 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。【解答】三元组顺序表，十字链表 广义表 (a), (b),c),(d)的长度是（），深度是（），表头是（），表尾是（）。【解答】 3，4，(a)，(b),c),(d) 已知广义表LS=(a ，(b，c， d) ， e)，用 Head 和 Tail 函数取出LS 中原子 b 的运算是 （ ）。【解答】 Head(Head(Tail(LS) 2. 选择题 二维数组A 的每个元素是由6 个字符组成的串，行下标的范围从08 ，列下标的范围是从 09 ，则存放A 至少需要（）个字节， A 的第 8 列和第 5 行共占（）个字节，若 A 按行优先方式存储，元素A85 的起始地址与当A 按列优先方式存储时的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A85 I A310 J A58 K A49 【解答】 D，E，K 【分析】数组A为 9 行 10 列，共有 90 个元素，所以，存放A 至少需要906=540 个存储单元，第 8 列和第 5 行共有 18 个元素（注意行列有一个交叉元素），所以，共占108 个字节，元素 A85 按行优先存储的起始地址为d+8 10+5=d+85，设元素 Aij 按列优先存储的起始地址与之相同，则d+j 9+i=d+85，解此方程，得i=4 ，j=9 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 2 将数组称为随机存取结构是因为（）A 数组元素是随机的B 对数组任一元素的存取时间是相等的C 随时可以对数组进行访问D 数组的存储结构是不定【解答】 B 下面的说法中，不正确的是（）A 数组是一种线性结构B 数组是一种定长的线性结构C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】 C 【分析】 数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。 对特殊矩阵采用压缩存储的目的主要是为了（）A 表达变得简单B 对矩阵元素的存取变得简单C 去掉矩阵中的多余元素D 减少不必要的存储空间【解答】 D 【分析】 在特殊矩阵中， 有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。 下面（）不属于特殊矩阵。A 对角矩阵B 三角矩阵C 稀疏矩阵D 对称矩阵【解答】 C 若广义表A 满足 Head(A)=Tail(A)，则 A 为（）A ( ) B ( ) C ( ),( ) D( ),( ),( ) 【解答】 B 下面的说法中，不正确的是（）A 广义表是一种多层次的结构B 广义表是一种非线性结构C 广义表是一种共享结构D 广义表是一种递归【解答】 B 【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。 下面的说法中，不正确的是（）A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储【解答】 D 【分析】 稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律， 就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3. 判断题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 3 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。 使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。 稀疏矩阵压缩存储后，必会失去随机存取功能。【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。 若一个广义表的表头为空表，则此广义表亦为空表。【解答】错。如广义表L=( ) ， (a，b) 的表头为空表，但L 不是空表。4一个稀疏矩阵如图4-4 所示，写出对应的三元组顺序表和十字链表存储表示。【解答】对应的三元组顺序表如图4-5 所示，十字链表如图4-6 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 4 5已知 A 为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。【解答】设稀疏矩阵为m 行 n 列，如果采用二维数组存储，其空间复杂度为(mn)；因为要将所有的矩阵元素累加起来，所以， 需要用一个两层的嵌套循环，其时间复杂度亦为(mn)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t 个非零元素，其空间复杂度为 (t) ，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为(t) 。当 t m n 时，采用三元组顺序表存储可获得较好的时、空性能。6设某单位职工工资表ST 由“ 工资 ” 、 “ 扣除 ” 和“ 实发金额 ” 三项组成， 其中工资项包括“ 基本工资 ” 、“ 津贴 ” 和“ 奖金 ” ，扣除项包括 “ 水” 、“ 电 ” 和“ 煤气” 。 请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的“ 奖金 ” 项； 画出该工资表ST 的存储结构。【解答】ST=( 基本工资，津贴，奖金)， (水，电，煤气 )，实发金额 ) Head(Tail(Tail(Head(ST)=奖金 工资表 ST 的头尾表示法如图4-7 所示。7若在矩阵A 中存在一个元素ai,j（0 i n-1，0 j m-1），该元素是第i 行元素中最小值且又是第 j 列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 5 【解答】 在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。具体算法如下：分析算法，外层for 循环共执行n 次，内层第一个for 循环执行m 次，第二个for 循环最坏情况下执行n 次，所以，最坏情况下的时间复杂度为(mn+n2) 。学习自测及答案1二维数组M 中每个元素的长度是3 个字节，行下标从0 到 7，列下标从0 到 9，从首地址 d 开始存储。若按行优先方式存储，元素M75 的起始地址为（），若按列优先方式存储，元素M75 的起始地址为（）。【解答】 d+22 ，d+141 2一个 n n 的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（）。【解答】 n(n+1)/2 3 设 n 行 n 列的下三角矩阵A （行列下标均从1 开始）已压缩到一维数组S1Sn(n+1)/2中，若按行优先存储，则Aij 在数组 S 中的存储位置是（）。【解答】 i (i-1)/2+j 4已知广义表LS=(a, (b, c), (d, e, a)，运用 Head 函数和 Tail 函数取出LS 中原子 d 的运算是（）。【解答】 Head(Head(Tail(Tail(LS) 5广义表 (a, b, (c, (d)的表尾是（）。A (d) B (c,(d) C b,(c,(d) D (b,(c,(d) 【解答】 D 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 6 6设有三对角矩阵Ann（行、列下标均从0 开始），将其三条对角线上的元素逐行存于数组 B3n-2 中，使得Bk=aij求： 用 i, j 表示 k 的下标变换公式； 用 k 表示 i, j 的下标变换公式。【解答】要求 i, j 表示 k 的下标变换公式，就是要求在k 之前已经存储了多少个非零元素，这些非零元素的个数就是k 的值。元素aij 求所在的行为i，列为 j，则在其前面的非零元素的个数是；k=2 + 3(i1)+( j i + 1)= 2i+ j。 因为 k 和 i, j 之间是一一对应的关系，k+1 是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即：7已知两个n n 的对称矩阵按压缩存储方法存储在已维数组A 和 B 中，编写算法计算对称矩阵的乘积。【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -