问南广播电视大季现教中心 第五章数组和广义表课后习题答案 1、判定题 (1)√ (2)× 说明：三元组表表示的矩阵转置基本思想是：对A中的每一列c0l(0≤col≤a)一1)，通过 从头至尾扫描三元组表一>dt,找出所有列号等于c0l的幕些三元组，将它们的行号和列 号互换后依次放人一>ata中，即可得到B的按行优先的压邹存贮表示。 (3)× 说明：原子个数应政为元素个数才对 2、单项选择题 (1)C (2)C (3)A 说明：广义表的长度是广义表中所含元素的个数。广义表的深度是带表展开后所含括号的层 数。 (4)D 说明：根据MIO川51先求L0CO,0)地址： 10C(10,5)"L0C(0,0)+(10*10+5)幸4-1000 L0C(00)=680 再求A18 10C(18,9)=580+(18*10+9）◆-1336 (5)B 说明：4为一个5行6列的数组 按行优先，C(3,5=0C(00)+(1知+J)*d =L0C(0,0)+(3*6+5)4 =L0C0,0)+2 按列优先：0C(i,=10C0,0)+(jn+i)d A2][: 10C(24)=0C(0.0)+(4*5+2)来4=10C0,0)+88 A[3[4]: 10C(3,40=0C(0.0)+(45+3）◆4-10C(0,0)+92 A[3][5]: 10C(35)=0C(0.0)+(55+3）◆410C0,0)+112 A[4][4]: L0C(4,4)=0C(0.0)+《4*5+4）幸4年L0C0,0)+96 (6)B 说明：广义表是nm≥0)个元素al,a2,·1,,即的有限序列。若广文表1s事空（加 ≥1)，则a!是1S的表头，其余元素组成的表(a2.3,,a)称为1s的表尾。 3、月答题 第1顶共3项 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第五章 数组和广义表 课后习题答案 1、 判定题 （1） √ （2） × 说明：三元组表表示的矩阵转置基本思想是：对 A 中的每一列 col(0≤col≤a->n-1)，通过 从头至尾扫描三元组表 a->data，找出所有列号等于 col 的那些三元组，将它们的行号和列 号互换后依次放人 b->data 中，即可得到 B 的按行优先的压缩存贮表示。 （3） × 说明：原子个数应改为元素个数才对 2、 单项选择题 （1） C （2） C （3） A 说明：广义表的长度是广义表中所含元素的个数。广义表的深度是指表展开后所含括号的层 数。 （4） D 说明：根据 A[10][5]先求 LOC(0, 0)地址： LOC( 10, 5 ) = LOC(0, 0) + ( 10*10 + 5 ) * 4=1000 LOC(0, 0)=580 再求 A[18][9]： LOC( 18, 9 ) = 580 + ( 18*10 + 9 ) * 4=1336 （5） B 说明：A 为一个 5 行 6 列的数组 按行优先：LOC(3, 5)= LOC(0, 0) + ( i*n + j ) * d = LOC(0, 0) +（3*6+5）*4 = LOC(0, 0) + 92 按列优先：LOC(i, j)= LOC(0, 0)+ ( j*m + i ) * d A[2][4]： LOC(2, 4)= LOC(0, 0)+ ( 4*5 + 2 ) * 4= LOC(0, 0) + 88 A[3][4]： LOC(3, 4)= LOC(0, 0)+ ( 4*5 + 3 ) * 4= LOC(0, 0) + 92 A[3][5]： LOC(3, 5)= LOC(0, 0)+ ( 5*5 + 3 ) * 4= LOC(0, 0) + 112 A[4][4]： LOC(4, 4)= LOC(0, 0)+ ( 4*5 + 4 ) * 4= LOC(0, 0) + 96 （6） B 说明：广义表是 n(n≥0)个元素 a1，a2，…，ai，…，an 的有限序列。若广义表 Ls 非空(n ≥1)，则 a1 是 LS 的表头，其余元素组成的表(a2，a3，…，an)称为 Ls 的表尾。 3、 问答题
河南厂播电现大学现数中心 (1)参考答案1 稀疏矩阵进行压缩存储通常有两类方法：顺序存储和威式存储。 解硫矩阵的顺序结构有三元组。三元组顺序表又称有序的双下标法，对矩阵中的每个非 零元素用三个城分别表示其所在的行号，列号和元素值。它的特点是，丰零元在表中按行序 有序存储，因此便于进行依行顺序处理的矩阵运算。 稀疏矩阵的威式结构有十字链表等方法，适用于非零元变化大的场合，比较复杂。十字 蓝表是既带行指针又带列指针的链接存储方式，每个三元组结点处于所在行单链表与列单链 表的交点处，当矩阵的非零元个数和位置在操作过程中变化较大时，用这种存储结构更为恰 当。 (2)参考答案： 广义表是线性表的的推广，它也是n(n0)个元素al,2..ai-an的有限序列，其中 ā或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而战性表没有这种 特性，线性表可以看成广义表的特殊情况，当都是原子时，广文表退化成线性表。 (3)参考答案： 0 6 12 12 20 3 15 (4)参考答案1 稀琉距阵A采用二隆数组存储时，需要n帕个存储单元，完成课Eaik0≤i≤一1)时， 由于a[][]随机存取，建度快。但采用三元组表时，若非零元素个数为t,需3(t*1)个存 储单元（第一个分量中存稀流矩阵A的行数，列数和半零元素个数，以后：个分量存各非零 元素的行值、列值、元素值)，比二维数组节省存储单元：但在求aik(0≤i≤一I》时，要 扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性旋比采用二推数组时差， 4、算法设计题 第2风共3项 版权所有河南电大现教中心范制，邮箱5@m加m
河南广播电视大学现教中心 第2页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （1） 参考答案： 稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 稀疏矩阵的顺序结构有三元组。三元组顺序表又称有序的双下标法，对矩阵中的每个非 零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序 有序存储，因此便于进行依行顺序处理的矩阵运算。 稀疏矩阵的链式结构有十字链表等方法，适用于非零元变化大的场合，比较复杂。十字 链表是既带行指针又带列指针的链接存储方式，每个三元组结点处于所在行单链表与列单链 表的交点处，当矩阵的非零元个数和位置在操作过程中变化较大时，用这种存储结构更为恰 当。 （2） 参考答案： 广义表是线性表的的推广，它也是 n(n>0)个元素 a1 ,a2…ai… an 的有限序列，其中 ai 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种 特性，线性表可以看成广义表的特殊情况，当 ai 都是原子时，广义表退化成线性表。 （3） 参考答案： i j v [0] 0 0 10 [1] 0 1 5 [2] 0 2 3 [3] 0 3 17 [4] 1 0 5 [5] 1 1 7 [6] 1 2 12 [7] 1 -3 4 [8] 2 0 3 [9] 2 1 12 [10] 2 2 20 [11] 2 3 23 [12] 3 0 17 [13] 3 2 4 [14] 3 3 23 [15] 3 4 14 （4） 参考答案： 稀疏矩阵 A 采用二维数组存储时，需要 n*n 个存储单元，完成求 Σaik(0≤i≤n-1)时， 由于 a[i][k]随机存取，速度快。但采用三元组表时，若非零元素个数为 t，需 3(t+1)个存 储单元（第一个分量中存稀疏矩阵 A 的行数，列数和非零元素个数，以后 t 个分量存各非零 元素的行值、列值、元素值），比二维数组节省存储单元；但在求 Σaik(0≤i≤n-1)时，要 扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。 4、 算法设计题
河南广播电视大学现黄中心 参考答案：设计将数组A[]的元需值中所有奇数移到所有钙数前的算法，要求不增加存储 空间，且时问复杂度为0(n), void nove (a.n) int a[]: int n: intl0s,high,t6即： low-0:high-n-1:terp-a[high]: while(lowChigh) ifa[1ow]/2=-00 a[high]=a[lov]: high-; a[low]-a[high]: else low++: a[high]-teap: 第3项共3页 版权所有河南电大规教中心范隔，配箱5@p恤团
河南广播电视大学现教中心 第3页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 参考答案：设计将数组 A[n]的元素值中所有奇数移到所有偶数前的算法，要求不增加存储 空间，且时间复杂度为 O（n）。 void move(a,n) { int a[]; int n; int low,high,temp; low=0;high=n-1;temp=a[high]; while(low<high) if(a[low]/2==0) { a[high]=a[low]; high--; a[low]=a[high]; } else low++; a[high]=temp; }