第5章 数组和广义表

第5章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120

G. 156 H. 234 I. 276 J. 282 K. 283 L. 288

⑤： A．行与列的上界相同 B. 行与列的下界相同

C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141 B. BA+180 C. BA+222 D. BA+225

4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。

A. 808 B. 818 C. 1010 D. 1020

5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188

7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。供选择的答案： A. 198 B. 195 C. 197

8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。 （1）存放A至少需要（ ）个字节；

（2）A的第8列和第5行共占（ ）个字节；

（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（ ）的起始地址一致。

供选择的答案：

（1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150

（3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

9. 二维数组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] 10. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

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-1 12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 13. 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1

14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。 A. 60 B. 66 C. 18000 D. 33 15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A. 55 B. 45 C. 36 D. 16

16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 17. 对稀疏矩阵进行压缩存储目的是（ ）。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度

18. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。

A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 19. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。

Head(Tail(Head(Tail(Tail(A)))))

A. (g) B. (d) C. c D. d 21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

tail(head(tail(C))) =( )。

A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。

A. (c,d) B. c,d C. ((c,d)) D. d 23. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。

A. c B. b，c C.（b，c） D.（（b，c）） 24. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 25. 广义表（a,(b,c),d,e）的表头为（ ）。

A. a B. a,(b,c) C. (a,(b,c)) D. (a) 26. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3 27. 下面说法不正确的是( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

二、判断题

1. 数组不适合作为任何二叉树的存储结构。（ ）

2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ） 3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ ） 4. 数组是同类型值的集合。（ ）

5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）

6. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ）

7. 二维以上的数组其实是一种特殊的广义表。（ ）

8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ） 9. 若一个广义表的表头为空表，则此广义表亦为空表。（ ）

10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ） 11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（ ）12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（ ）

13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ） 14. 一个广义表可以为其它广义表所共享。（ ）

三、 填空题

1. 数组的存储结构采用_______存储方式。

2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）_。

3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。

5. 二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)

6. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，

若按列优先顺序存储，则元素A[6,6]存储地址为_______。

7. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。

8. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。

9. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_（1）_行，第_（2）_列的元素。

10. 设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_______;

（2） 存放数组的第8列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素A[5,8]的起始地址是_______。

11．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。

12. n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为__(1)______，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[(3)],i

14. 设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。

15. 所谓稀疏矩阵指的是_______。

16. 对矩阵压缩是为了_______。

17. 上三角矩阵压缩的下标对应关系为：_______。

18. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_______。（注：矩阵元素下标从1开始）

?a11??a21a22????a31a32a33???..........???an1an2....ann?? 19．设下三角矩阵A=?如果按行序为主序将下三角元素Ai j (i,j)存储在一个一维数组B[ 1..n(n+1)/2]中，对任一个三角矩阵元素Aij ,它在数组B中的下标为_______。

20. 当广义表中的每个元素都是原子时，广义表便成了_______。

21. 广义表的表尾是指除第一个元素之外，_______。

22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__

23. 广义表的_______ 定义为广义表中括弧的重数。

24．设广义表L=((),()), 则head(L)是(1)___；tail(L)是(2)____；L的长度是(3)___；深度是 (4)__。

25. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。 26. 广义表的深度是_______。

27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。

28. 已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_______。

29. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: _______。 30. 设某广义表H=（A，（a,b,c）） ，运用head函数和tail函数求出广义表H中某元素b的运算式_______。

31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 。 32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。

34. 利用广义表的GetHead和GetTail操作，从广义表L=（（apple，pear）（banana，，orange））中分离出原子banana的函数表达式是_______。

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: ARRAY[1..m] OF integer; BEGIN

FOR i:=1 TO m DO d[i]:=(1) ; i:=1; j:=1; k:=1;

WHILE (i<=l) AND (j<=m) DO

BEGIN

IF a[i]>d[j] THEN BEGIN(2) ; (3) _END

ELSE BEGIN (4)__; (5) __END; c[k]:=x; (6) END;

WHILE(7) _DO

BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END; WHILE(8) _DO

BEGIN c[k]:=d[j]; 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 100

int a[MAXN],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=a[low]; do{while (i

本文来源：https://www.bwwdw.com/article/fsvt.html