第5章 数组

第 5 章 数组一、选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。A. 13 B. 33 C. 18 D. 402.有一个二维数组A1:6，0:7每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（L）个字节。假设存储数组元素A1，0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（J）。若按行存储，则A2，4的第一个字节的地址是（C）。若按列存储，则A5，7的第一个字节的地址是（I）。就一般情况而言，当（C）时，按行存储的AI，J地址与按列存储的AJ，I地址相等。供选择的答案：-： A12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ： A行与列的上界相同 B.行与列的下界相同 C.行与列的上、下界都相同 D.行的元素个数与列的元素个数相同 3.设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( B )。A. BA+141 B. BA+180 C. BA+222 D. BA+2254.假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（ B ）。 A. 808 B. 818 C. 1010 D. 10205.数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( A )。 A. 1175 B. 1180 C. 1205 D. 12106.有一个二维数组A0:8,1:5,每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A0,1的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ H ）。若按行存储，则A3,5和 A5,3的第一个字节的地址是（ C ） 和（ E ）。若按列存储，则A7,1和A2,4的第一个字节的地址是（ A ）和（ F ）。-:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.1887.将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ B ）。供选择的答案：A. 198 B. 195 C. 197 8.二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。（1）存放A至少需要 （ E ）个字节；（2）A的第8列和第5行共占（ A ）个字节；（3）若A按行存放，元素A8，5的起始地址与A按列存放时的元素（ B ）的起始地址一致。供选择的答案：（1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A8,5 B. A3,10 C. A5,8 D. A0,9 9.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A3,10 C. A5,8 D. A0,910.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（i<j）的位置k的关系为( B )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i11.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2中，对上述任一元素aij(1i，jn，且ij)在B中的位置为( B )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-112. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ B ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+113.设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai，j在一维数组B中的下标为( A )。A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-114.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ B ）。A. 60 B. 66 C. 18000 D. 33 15.数组A0.4,-1.-3,5.7中含有元素的个数（ B ）。A. 55 B. 45 C. 36 D. 1616.用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为( A )。 A. j=rj.next B. j=j+1 C. j=j->next D. j=rj-> next17.对稀疏矩阵进行压缩存储目的是（ C ）A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度 二、判断题1.数组不适合作为任何二叉树的存储结构。（ F ）2.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ T ）3.稀疏矩阵压缩存储后，必会失去随机存取功能。（ T ）4.数组是同类型值的集合。（F ）5.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ F ） 6.一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ F ） 7.二维以上的数组其实是一种特殊的广义表。（ T ） 三、 填空题1.数组的存储结构采用_顺序存储结构_存储方式。2.设二维数组A-20.30,-30.20,每个元素占有4个存储单元,存储起始地址为200.如按行优先顺序存储,则元素 A25,18的存储地址为_（1）9572_；如按列优先顺序存储,则元素A-18,-25的存储地址为_（2)1228_。 3.设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_（1）9174_;若以列序为主序顺序存储，则元素a45,68的存储地址为_（2）8788_。4.将整型数组A1.8，1.8按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A7，3的地址是：_1100_。6.设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6存储地址为_232_。7.已知数组A0.9,0.9的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A6，8的地址为_1340_。8.已知二维数组A1.10，0.9中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A5，9的地址是：_1196 _。9.用一维数组B与列优先存放带状矩阵A中的非零元素Ai,j (1in,i-2ji+2),B中的第8个元素是A中的第_（1）一_行，第_（2）3_列的元素。10.设数组A0.8,1.10,数组中任一元素Ai,j均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_270_; （2） 存放数组的第8列的所有元素至少需要的单元数是_27_;（3） 数组按列存储时，元素A5,8的起始地址是_2204_。11设n行n列的下三角矩阵A已压缩到一维数组B1.n*（n+1）/2中，若按行为主序存储，则Ai,j对应的B中存储位置为_i(i-1)/2+j (1<=i,j<=n)_。 12. n阶对称矩阵a满足aij=aji,i,j=1.n,，用一维数组t存储时，t的长度为_(1)n(n+1)/2 _，当i=j，aij=t(2)i(i+1)/2,i>j,aij=t(3)i(i-1)/2+j,i<j,aij=t(4)j(j-1)/2+i。13己知三对角矩阵A【1.9,1.9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A7,8的地址为_k=2(i-1)+j (1<=i,j<=n)_。15.所谓稀疏矩阵指的是_非零元很少(t<<m*n)且分布没有规律 _。16.对矩阵压缩是为了_节省存储空间_17.上三角矩阵压缩的下标对应关系为：_k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (i£j)_。18.假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_ 93_。（注：矩阵元素下标从1开始）19设下三角矩阵A=如果按行序为主序将下三角元素Ai j(i,j)存储在一个一维数组B 1.n(n+1)/2中，对任一个三角矩阵元素Aij ,它在数组B中的下标为_i(i-1)/2+j_。35.已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。 PROCEDURE sort; VAR i, j, k, x: integer; d: ARRAY1.m OF integer; BEGIN FOR i:=1 TO m DO di:=(1)bm-i+1 ; i:=1; j:=1; k:=1; WHILE (i<=l) AND (j<=m) DO BEGINIF ai>dj THEN BEGIN(2)x:=ai ; (3)i:=i+1 _END ELSE BEGIN (4)x:=dj_; (5)j:=j+1_END; ck:=x; (6)k:=k+1 END;WHILE(7)i<=l _DOBEGIN ck:=ai; k:=k+1; i:=i+1；END;WHILE(8) j<=m _DOBEGIN ck:=dj; k:=k+1; j:=j+1；END;END. sort 36.下列程序段search(a,n,k)在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。#define MAXN 100int aMAXN,n,k;int search_c(int a, int n, int k)int low, high, i, j, m, t; k-,;low=0 ;high=n-1; do i=low; j=high ; t=alow; dowhile (i<j && t<aj) j-; if (i<j) ai+=aj; while (i<j && t>=ai) i+ if (i<j) aj-=ai; while (i<j);ai=t;if (1)(i=k) return ; if (i<k) low= (2)i+1 ; else high= (3)i-1 ;while(4)i!=k _;return(ak); 38.完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,n*n,依次按蛇型方式存放在二维数组A1.n,1.n中。即 (示意圖编者略)。（a）算法的PASCAL语言程序描述（编者略）：（b）算法的C语言程序描述：#define NMAX 10#include“stdio.h”main() int i,j,n,k,p,q,m; int a NMAXNMAX; scanf(“%d”,&n); m=1; for(k=1；(1)k<=2*n-1 ；k+)if（k<n） q=k； else(2)q=2*n-k _; for(p=1;p<=q;p+) if(3) k%2！=0 i=q-p+1；j=p； elsei=p；j=q-p+1； if(4)k>=n i=i+n-q；j=j+n-q； aij=m；(5)m+ _; for（i=1；i<=n;i+） for（j=1；j<=n；j+） printf（“%4d”,aij）;printf(“n”);