第5章 数组和广义表.doc

第五章习题参考答案一、简答题1【参考答案】 ：数组是一组具有相同数据类型的数据集合。数据元素按次序存储于一段地址连续的内存空间中。可以通过下标找到存放该元素的存储地址，访问该数据元素的值。数组中的每一个元素和下标惟一对应。访问数组中任意指定的数据元素形式是，数组名下标。举例略。2【参考答案】 ：数组是一组具有相同数据类型的数据集合。数据元素按次序存储于一段地址连续的内存空间中。即数组是数据元素的线性组合，类似于顺序存储结构的线性表。3【参考答案】 ：在n阶方阵A中，若元素满足下述性质：aij=aji （0i，jn-1）则称A为n阶对称矩阵。三角矩阵是指n阶矩阵中上三角（不包括对角线）或下三角（不包括对角线）中的元素均为常数c或为0的n阶方阵。以主对角线划分，三角矩阵有上三角和下三角两种。在n阶矩阵A中，所有的非零元素都集中在以对角线为中心的带状区域中，则称A为n阶对角矩阵。实质上，除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素均为零或为常数c。稀疏矩阵压缩存储方法有两类：顺序存储结构和链式存储结构。共同点：为了节省存储单元，可只存储非零元素，压缩零元素的存储空间；非零元素的分布一般是没有规律的；在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能惟一确定非零元素是矩阵中的哪一个元素。稀疏矩阵中的所有非零元素构成了三元组线性表。4【参考答案】 ：一个阶数较大的mn矩阵中，设有s个非零元素，如果smn时，则称该矩阵为稀疏矩阵。准确的讲，在矩阵A中，有s个非零元素。令e=s/(mn),称e为矩阵的稀疏因子。通常认为e0.05时，称矩阵A为稀疏矩阵。特点：非零元素分布没有规律，而且很少，远小于矩阵中的元素总个数。采用压缩存储，节省存储空间，只存储非零元素，并且每个非零元素都需要一个三元组（i,j,aij）惟一表示。5【参考答案】 ：广义表是n（n0）个元素构成的一个序列，则广义表的一般表示与线性表相同：LS=(a1,a2,a3,ai,an)其中，LS为广义表(a1,a2,a3,ai,an)的名称，n表示广义表的长度，即广义表的包含元素的个数；当n=0时，则称为空表。广义表的特性：（1）广义表是一种线性结构。广义表的数据元素之间有着固定的相对次序，如同线性表。（2）广义表也是一种多层次的结构。当广义表的数据元素中包含子表时，该广义表就是一种多层次的结构。（3）广义表可为其他广义表共享。（4）广义表可以是一个递归表。（5）任何一个非空广义表LS均可分解为表头head(LS)=a1和表尾tail(LS)=(a2,a3,an)两部分。6【参考答案】 ：对于三对角矩阵可按行为主序的方式，只将矩阵A中的非零元素压缩存储到一维数组SA中。矩阵A中第0行和第n-1行都只有2个非零元素，其余各行有3个非零元素。对于不在第0行的非零元素aij来说，它前面有i行元素，共2+3(i-1)个元素；第j列前有j-(i-1)个数据元素。所以，用i和j表示k的下标变换公式为：k=2i+j+1.7【参考答案】 ：（1）三元组表示为： (1,3,8),(2,4,9),(4,1,3),(4,5,15)（2）稀疏矩阵三元组的顺序存储结构数组的下标i（行下标）j（列下标）value01381249241334515（3）十字链表表示：13824945155413二、选择题【1】B 【2】C 【3】A 三、实验题1【参考答案】 ：class MultiMatrix public static void main(String args) int a= 9, 2, 5, 9, 2, 0, 3, 7, 15, 4, 5, 6, 8, 3, 12, 5 ; MultiMatrix mm=new MultiMatrix(); mm.mMatrix(a); public void mMatrix(int a) /求主对角线元素之和 int sum = 0; int i; for(i = 0; i 4; i+) sum += aii; System.out.println(矩阵A的主对角线元素之和为：+sum); 2【参考答案】 ：public class MultiMatrix int multiplyMatrix; public static void main(String args) int a= 1, 5, 7, 3, 3, 6, 3, 9, 1, 2, 8, 7, 0, 3, 1, 9, 3, 2, 5, 4 ; int b= 3, 9, 1, 4, 5, 6, 7, 9, 3, 2, 7, 2, 9, 3, 1, 5, 1,8,0,8 ;MultiMatrix mm=new MultiMatrix(); mm.mMatrix(a,b); mm.display(); public void mMatrix(int a,int b) /进行矩阵加法运算 multiplyMatrix=new inta.lengthb0.length; for (int i = 0; ia.length; i+) for (int j = 0; jb0.length; j+) multiplyMatrixij=aij+bij; public void display() /输出数组中的数据元素 for (int i = 0; imultiplyMatrix.length; i+) for (int j = 0; jmultiplyMatrixi.length; j+) System.out.print (multiplyMatrixij+ ); System.out.println (); 四、思考题1【参考提示】：数组是一组具有相同数据类型的数据集合。数据元素按次序存储于一段地址连续的内存空间中。即数组是数据元素的线性组合，类似于顺序存储结构的线性表。2【参考提示】：稀疏矩阵转置最简单的方法是把三元组表中的行与列的内容互换，然后再按照新的的行号对各三元组重新排序，但是其时间复杂度为O(n2),n为稀疏矩阵的阶