发布时间 : 星期四 文章数据结构典型例题 - 图文更新完毕开始阅读22e8e67b168884868762d6f1
数组
一、单项选择题
[例9-1] 下列操作中，( )是数组的基本运算。 A．插入 B．删除 C．修改 D．排序
解析：数组的基本运算只有两种，一种是给定一组下标，存取相应的元素；另一种是 给定一组下标，修改相应数据元素中某个数据项的值。本题答案为：C。 (例9-2) 一维数组和线性表的区别是( )。
A．前者长度固定，后者长度可变 B．后者长度固定，前者长度可变 C．两者长度均固定 D．两者长度均可变
解析：由数组和线性表的定义可知，数组的长度是固定的，而线性表的长度是可变的。 本题答案是：A。
[例9-3] 二维数组A的每个元素是由6个字符组成的字符串，其行下标i＝0，1，…，8，列下标j＝1，2，…，10。当A按行存储时，元素A[8，5]的起始地址与当A按列存储时的元素( )的起始地址相同(设每个字符占一个字节)。
A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9]
解析：当A按行存储时，元素A[8，5]前共有(8—0)×(10—1+1)+(5—1)＝84个元素。对侯选答案进行类似计算可知，本题答案为：B。
(例9-4) 有一个100×90的稀疏矩阵，有非零元素(整型)10个。设每个整型数占2个字节，则用三元组表表示该矩阵时，所需的字节数为( )。
A．60 B．66 C．18 000 D．33
解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用手存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。本题答案为：B。
[例9-5] 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上的所有元素)依次存放于一维数组B[0..(n(n+1))／2—1)中，则在B中确定ai，j(i A． i(i?1)j(j?1)i(i?1)j(j?1)?j B．?i C．?j D．?i 2222解析：参考9.2.3节有关对称矩阵的内容可知，本题答案为：D。 二、填空题 (例9-6) 三维数组A[c1..d1，c2..d2，c3..d3]共含有 个元素。 解析：第一维大小为d1-cl+1，第二维大小为d2-c2+1，第3维大小为d3-c3+1，共有(dl-c1+1)×(d2-c1+1)×(d3-c3+1)个元素。 本题答案为：(d1-c2+1)×(d2-c1+1) ×(d3-c3+1)。 [例9-7] 设二维数组A[-20..30，-30..19]，每个元素占用4个存储单元，存储起始地址为200。如按行优先顺序存储，则元素A[25][18]的存储地址为 ；如按列优先顺序存储，则元素A[一18][一25]的存储地址为 。 解析：当按行优先顺序存储时，元素A[25][18]的存储地址为： LOC(A[25][18])＝LOC(A[-20][-30])+((25-(-20))×(19-(-30)+1) +(18-(-30)))×4 ＝200+9192＝9392 当按列优先顺序存储时，元素A[-18][-25]的存储地址为： LOC(A[-18][-25])＝LOC(A[-20][-30])+((-25-(-30))×(30-(-20)+1) +(-18-(-20))) × 4 =2004+1028=1228 17 本题答案为：9392；1228。 [例9-8] 将一个10阶对称矩阵A用压缩存储方式(以行为主序存储下三角，且a00＝1)进行存储，设每个元素占一个地址空间，则a85的地址为 。 解析：矩阵下标从0开始，以行为主序存储下三角，a85前有8行，第0行1个元素，第1行2个元素，……，第7行8个元素，共计(1+8)×8／2＝36个元素，第8行中a85前有5个元素。所以，a85前共有36+5＝41个元素，其地址为41+l＝42。本题答案为：42。 [例9-9] 一稀疏矩阵有8个非零元素，矩阵元素为整型。现用三元组表方式对其进行压缩存储，假设整型元素占2个存储单元，则该三元组表至少占 个存储单元。 解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用于存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。表头部分占3×2＝6个存储单元，主表部分占8×3×2＝48 个存储单元，总共占6+48＝54个存储单元。本题答案为：54。 三、应用题 [例9-10] 已知An×n为稀疏矩阵，试从空间和时间的角度比较采用两种不同的存储 结构二维数组和三元组表完成求 n?1i?0?aii运算的优缺点。 解析：由题目可知，所进行的运算是计算主对角线元素之和。对于采用二维数组方法存储的矩阵，需要n2个存储单元，但由于可以进行随机存取，即可以随机地访问主对角线上的元素，因此时间效率比较高。采用三元组表方法存储矩阵时是压缩存储，节省了存储空间，但在算法实现上需要从头到尾扫描整个三元组表，因此时间效率相对低一些。 (例9-11) 设给定n维数组A[c1..d1][c2..d2)…[cn..dn)，如果A[c1][c2]…[cn]的存储地址为a，每个元素占用1个存储单元，求A[i1][i2]…[in]的存储地址。 解析：若整个数组采用按行优先顺序存储，则A[i1][i2]…[in]的存储地址为： LOC(A[i1][i2]…[in])=a+((i1-c1)×(d2-c2+1)×…×(dn-cn+1) +(i2-c2)×(d3-c3+1)×…×(dn-cn+1) +(in-cn))×l 若整个数组采用按列优先顺序存储，则A[i1][i2]…[in]的存储地址为： LOC(A[i1][i2]…[in])=a+((in-cn)×(dn-1-cn-1+1)×…×(d1-c1+1) +(in-1-cn-1)×(dn-2-cn-2+1)×…×(d1-c1+1) +(i1-c1))×l (例 9-12) 设上三角矩阵An×n，将其上三角元素逐行存于数组B[m]中，使得B[k]＝aij，且k=f1（i）+f2（j）+c。试推导出函数f1（i）、f2（j）和常数C。 解析：由前面内容的分析可得k和i、j之间的关系为： ?i(2n?i?1)+j-i 当i≤j时 ??2k?? n(n?1)? 当i>j时，存放常数c ??2 当i≤j时，有 f(1)=?n?1?i?1i2 1???2?2f2(j)=j 18 C=0 当i>j时，有 f1(i)=f2(j)=0 C?n(n?1) 2四、算法设计题 (例9—13) 已知一个n×n矩阵B按行优先顺序存储在一个一维数组A[0..n×n一1) 中，试给出一个算法将原矩阵转置后仍存于数组A中。 解析：矩阵转置是将矩阵中第i行第j列的元素与第j行第i列的元素位置互换。因此， 先确定矩阵与一维数组的映射关系：bi，j在一维数组A中的下标为i×n+j，bi，j在一维数组A中的下标为j×n+i。具体算法如下： void trans ( datatype A[]，int n) { int i，j； datatype temp； for(i=0；i temp=A[i * n+1]； A[i * n+j]=A[j * n+i]； A[j * n+i]=temp； } } (例9-14) 假设稀疏矩阵A采用三元组表表示，试编写一个算法求其转置矩阵B，要求B也用三元组表表示。 解析：三元组表表示要求按行的顺序存放，所有转置过程不能直接将行下标和列下标 转换，还必须使得转置后矩阵按顺序存放。因此，首先在A中找出第一列中的所有元素 (即B中第一行)，并把它们依次存放在转置矩阵B的三元组表中；然后依次找出第二列中的所有元素，把它们依次存放在三元组表B中；最后按此方法逐列进行，直到第n列的操作完成。值得注意的是，除了各元素的行号列号需要互换外，表头部分的行数列数也应该互换。具体算法如下： void transmatrix (smatrix * A，smatrix * B) { int p，k，col； B—>m=A—>n； //B的行数为A的列数 B—>n=A—>m； //B的列数为A的行数 B—>t=A—>t； //转置前后非零元素个数不变 if(B—>t!＝0) //非0矩阵 { k=0； //B表元素计数器，作当前放置元素指针 for(col=0；col 19 B—>data[k]．i=A—>data[p].j； B—>data[k].j=A—>data[p].i B—>data[k].v＝A—>data[p].v； K++ } } } 20