当前位置：文档库 › 目前最完整的数据结构1800题包括完整答案第五章数组和广义表

目前最完整的数据结构1800题包括完整答案第五章数组和广义表

第 5 章数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其

存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】

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]地址相等。供选择的

答案：【上海海运学院 1998 二、2 （5分）】

①-④： 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

【南京理工大学 1997 一、8 （2分）】

4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存

储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】

A. 808

B. 818

C. 1010

D. 1020

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

的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.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]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】

①-⑤: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 【北京邮电大学 1998 二、5 （2分）】

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]

【山东工业大学 2000 三、1 （4分）】【山东大学 1998 三、1 (4分)】

9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。【西安电子科技大学 1998 一、2 （2分）】

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中确定a ij（i

A. i*(i-1)/2+j

B. j*(j-1)/2+i

C. i*(i+1)/2+j

D. j*(j+1)/2+i

【北京航空航天大学 2000 一、2 （2分）】

11. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素a ij(1≤i，j≤n，且i≤j)在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-1

【南京理工大学 1999 一、9（2分）】

12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。【青岛大学 2002 二、6 （2分）】

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中的下标为( )。【南京理工大学 1998 一、2 （2分）】

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字节，则用三元组表示该矩阵时，所需的字节数是（）。【南京理工大学 1999 二、8 （2分）】

A. 60

B. 66

C. 18000

D. 33

15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（）。【中山大学 1998 二、5（2分）】

A. 55

B. 45

C. 36

D. 16

16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。【南京理工大学 2001 一、16（1.5分）】

A. j=r[j].next

B. j=j+1

C. j=j->next

D. j=r[j]-> next

17. 对稀疏矩阵进行压缩存储目的是（）。【北京工商大学 2001 一、1 (3分)】

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）））)）

【北京邮电大学 1998 二、4（2分）】

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))))

【西安电子科技大学 2001应用一、3（2分）】

20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。【北京邮电大学1999一、2（2分）】

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))) =( )。【长沙铁道学院 1998 三、4 (2分)】

A.（a）

B. A

C. a

D. (b)

E. b

F. (A)

22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。【西安电子科技大学1998

一、4（2分）】

A. (c,d)

B. c,d

C. ((c,d))

D. d

23. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。【中山大学 1999 一、10】

A. c

B. b，c

C.（b，c）

D.（（b，c））

24. 广义表（（a,b,c,d））的表头是（），表尾是（）。【青岛大学 2002 二、7 （2分）】

A. a

B.（）

C.（a,b,c,d）

D.（b,c,d）

25. 广义表（a,(b,c),d,e）的表头为（）。【中山大学 1998 二、6（2分）】

A. a

B. a,(b,c)

C. (a,(b,c))

D. (a)

26. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。【武汉大学 2000 二、9】

A. 1和1

B. 1和3

C. 1和2

D. 2和3

27. 下面说法不正确的是( )。【南京理工大学 2001 一、3 （1.5分）】

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

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

C. 广义表难以用顺序存储结构

D. 广义表可以是一个多层次的结构

二、判断题

1. 数组不适合作为任何二叉树的存储结构。（）【南京航空航天大学 1995 五、2 （1分）】

2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（）

【东南大学 2001 一、2 （1分）】【中山大学 1994 一、2 （2分）】

3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（）【中科院软件所 1997 一、1 （1分）】

4. 数组是同类型值的集合。（）【上海海运学院 1996 一、3（1分）1999 一、4（1分）】

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

【上海交通大学 1998 一、5】

6. 一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了A m*n的转置运算。（）【西安交通大学 1996 二、8 (3分)】

7. 二维以上的数组其实是一种特殊的广义表。（）【北京邮电大学 2002 一、5 （1分）】

8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）

【南京航空航天大学 1996 六、2 （1分）】

9. 若一个广义表的表头为空表，则此广义表亦为空表。（）

【中科院软件所 1997 一、8（1分）】【长沙铁道学院 1998 一、8 (1分)】

10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）

【合肥工业大学 2000 二、3 （1分）】

11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（）【合肥工业大学 2001 二、3 （1分）】

12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（）

【华南理工大学 2002 一、9（1分）】

13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）

【华南理工大学 2002 一、10（1分）】

14. 一个广义表可以为其它广义表所共享。（）【山东大学 2001 一、2（1分）】

三、填空题

1. 数组的存储结构采用_______存储方式。【中山大学 1998 一、6（1分）】

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

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

【华中理工大学 2000 一、5（2分）】

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。【合肥工业大学 1999 三、4（2分）】

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

6. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。【北京工商大学 2001 二、5 （4分）】

7. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。【合肥工业大学 2001 三、4（2分）】

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

9. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_（1）_行，第_（2）_列的元素。【北京邮电大学 2001 二、3（4分）】

10. 设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

（l）存放该数组至少需要的单元数是_______;

（2）存放数组的第8列的所有元素至少需要的单元数是_______;

（3）数组按列存储时，元素A[5,8]的起始地址是_______。【中国矿业大学 2000 一、4（4分）】

11．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存

储，则A[i,j]对应的B中存储位置为_______。【武汉大学 2000 一、1】

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

13．己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为______。【合肥工业大学 2000 三、4（2分）】

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

【西安电子科技大学 1999软件一、3 （2分）】

15. 所谓稀疏矩阵指的是_______。【厦门大学 2001 一、2 （14%/5分）】

16. 对矩阵压缩是为了_______。【北京理工大学 2000 二、3（2分）】

17. 上三角矩阵压缩的下标对应关系为：_______。【福州大学 1998 二、6 (2分)】【南京大学 1999】

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

19．设下三角矩阵A=

ann

如果按行序为主序将下三角元素A i j (i,j)存储在一个一维数组B[ 1..n(n+1)/2]中，对任一个三角矩阵元素A ij ,它在数组B中的下标为_______。【北方交通大学 2001 二、3】20. 当广义表中的每个元素都是原子时，广义表便成了_______。【长沙铁道学院 1998 二、8 (2分)】

21. 广义表的表尾是指除第一个元素之外，_______。【中山大学 1998 一、7 （1分）】

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

23. 广义表的_______ 定义为广义表中括弧的重数。【重庆大学 2000 一、5】

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

【中科院计算所 1998 一、2（4分）】【中国科技大学 1998 一、2（4分）】

25. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。【西安交通大学 1996 四、5 (5分)】

26. 广义表的深度是_______。【北京轻工业学院 2000 一、1（2分）】

27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。【山东大学 2001 三、9 (2分)】

【西安电子科技大学 2001软件一、5 （2分）】【哈尔滨工业大学 2001 一、2 （2分）】

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

_______。

【燕山大学 2001 二、2 （3分）】

29. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: _______。

【合肥工业大学 1999 三、5（2分）】

30. 设某广义表H=（A，（a,b,c）），运用head函数和tail函数求出广义表H中某元素b 的运算式_______。

【北京科技大学 1997 一、5】

31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于。

【合肥工业大学 2000 三、5（2分）】

32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。

【西安电子科技大学 1999软件一、9（2分）】

33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。

【合肥工业大学 2001 三、5 （2分）】

（banana，orange））34. 利用广义表的GetHead和GetTail操作，从广义表L=（（apple，pear），

中分离出原子banana的函数表达式是_______。【山东大学 2001 三、6 (2分)】

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} 【上海交通大学 1998 七 (12分)】

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

if (i

while (i=a[i]) i++

if (i

} while (i

a[i]=t;

if (1) ;

if (i

}while(4) _;

return(a[k]);

} 【上海大学 1999 一、1（8分）】

37. 完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。（a）算法的PASCAL语言过程描述（编者略）：（b）算法的C语言过程描述：typedef struct glistnode

{int tag;

struct glistnode *next;

union{char data;

struct{struct glistnode *hp,*tp;}ptr;

}val;

}*glist,gnode;

glist reverse(p)

glist p;

{glist q,h,t,s;

if(p==NULL) q=NULL;

else

{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;

q->val.data=p->val.data; }

else {(2)

if (3)

{t=reverse(p->val.ptr.tp); s=t;

while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp;

s->val.ptr.tp=(glist)malloc(sizeof(gnode));

s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL;

s->val.ptr.hp=h; (4) __ }

else {q=(glist)malloc(sizeof(gnode));q->tag=1;

q->val.ptr.tp=NULL; (5) ; }

}

return(q);

}

【上海大学 2002 六、3 （10分）】

38. 完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即 (示意圖编者略)。（a）算法的PASCAL 语言程序描述（编者略）：（b）算法的C语言程序描述：

#define NMAX 10

#include “stdio.h”

main()

{ int i,j,n,k,p,q,m;

int a [NMAX][NMAX];

scanf(“%d”,&n);

m=1;

for(k=1；(1) ；k++)

{if（k

for(p=1;p<=q;p++)

{if(3) {i=q-p+1；j=p；}

else{i=p；j=q-p+1；}

if(4) {i=i+n-q；j=j+n-q；}

a[i][j]=m；(5) _;

}

for（i=1；i<=n;i++）

{ for（j=1；j<=n；j++）

printf（“%4d”,a[i][j]）;printf(“\n”);

}

} 【上海大学 2002 六、1 （10分）】

39. 约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去，直到所有的人都出圈为止。

PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer);

BEGIN

FOR i:= 1 TO n DO A[i]:=i;

sl:=s;

FOR i:=n DOWNTO 2 DO

BEGIN sl:= (1) __；//计算出圈人s1

IF sl=0 THEN (2) _；

w:=A[sl]; //A[s1]出圈

FOR j:= (3) __ DO A[j]:=A[j+1];

A[i]:=w;

END;

write('出圈序列为：’)；//输出出圈序列

FOR i :=n DOWNTO 1 DO write(A[i]); writeln ；

END; 【华南师范大学 2000 五、2 (9分)】

40. 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，W i(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。

Knap(S，n)

若S=0

则Knap←true

否则若（S<0）或(S>0且n<1)

则Knap←false

否则若Knap(1) , _=true

则print(W[n])；Knap ←true

否则 Knap←Knap(2) _ , _

【山东工业大学1996 五（10分）1998 二、1 （4分）】

四应用题

1. 数组A[1..8，-

2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。【厦门大学 1998 五、1 （5分）】

2. 已知b对角矩阵（a ij）n*n，以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用i，j 表示出 a ij的存储位置。【北方交通大学 1996 三（10分）】

3. 数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：

（1）存放该数组所需多少单元？

（2）存放数组第4列所有元素至少需多少单元？

（3）数组按行存放时，元素A[7,4]的起始地址是多少？

（4）数组按列存放时，元素A[4,7]的起始地址是多少？【大连海事大学 1996 四、1 (6分)】

4．假设按低下标优先存储整型数组A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？【清华大学 1996 三】

5．设有三维数组A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为1210，试求A(1,3,-2）所在的地址。【长沙铁道学院 1997 三、1 (3分)】

6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。

【上海海运学院 1995 三（6分） 1997 三（8分）】

7. 设有五对角矩阵A=(a ij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15,16]的存储位置。【东北大学 1999 一、2（4分）】

8．数组A[0..8, 1..10] 的元素是6 个字符组成的串，则存放A至少需要多少个字节？ A 的第8列和第5行共占多少个字节？若A 按行优先方式存储，元素A[8,5]的起始地址与当A 按列优先方式存储时的哪个元素的起始地址一致？【厦门大学 2000 五、3（14%/3分）】9. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素a ij(i≥j),在数组B中的下标位置k是什么？【北京航空航天大学 1998 一、4（4分）】

10. 设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？【北京航空航天大学 1998

一、5（4分）】

11. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。【西北工业大学

1998三、2(5分)】

12. 对一个有t个非零元素的A mn矩阵, 用B[0..t][1..3]的数组来表示，其中第0行的三

个元素分别为m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？【长沙铁道学院 1998 四、4 (6分)】

13. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A[0,1]的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少?若按列存储,则A[7,1]和A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10分）】14. 设有三对角矩阵(a i,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=a i,j，求：

（1）用i,j表示k的下标变换公式；

（2）若n=103,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。

【西安电子科技大学 1996 二、4 （5分）】

15. 已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和

三元组表）完成求∑

aii

运算的优缺点。【西安电子科技大学 1996 二、6（5分）】

16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？

【北京邮电大学 2001 三、1（5分）】

17. 试叙述一维数组与有序表的异同。【西安电子科技大学 1999计应用一、2（5分）】

18. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？

【西安电子科技大学 1999计应用一、3（5分）】

19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。【南开大学 1998 一(8分)】

20. 已知n阶下三角矩阵A（即当i

【北京航空航天大学 1999二(10分)】【中山大学 1999三 2】

21. 设有三对角矩阵(a ij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使

得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；

（2）用k表示i,j的下标变化公式。

【山东科技大学 2001 一、6 （6分）】【长沙铁道学院 1997 五、1 (10分)】

【东北大学 2002 一 (4分)】【北京工业大学 2000 二、1 (9分)】【南京航空航天大学2000 四】

22. 算法Print及所引用的数组A的值如下，写出调用Print(1)的运行结果（其中n=15）。

PROCEDURE print（i：integer）；

BEGIN

IF（i<=n〉 AND （A[i] <>‘0’） THEN

BEGIN Print（2*i）；write（A[i]）；Print（2*i+1）； END；

END；

【合肥工业大学 1999 四、1（5分）】

23. 设数组A的长度为2N，前N个元素A[1..N]递减有序，后N个元素A[N+1.. 2N]递增有序，且2N是2的整数次幂，即k=log22N为整数。例如A[1..8]=[90,85,50,10,30,65,80,100]满足上述要求，这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序。用此例调用如下的Demo过程，并要求：

（1）给出for循环中每次执行PerfectShuffle（A,N）和CompareExchange（A,N）的结果；（2）解释Demo的功能；（3）给出Demo的时间复杂度。

PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer)

[ i:=1; j:=1;

WHILE i<=N DO

[ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ]

A[1..2N]:=B[1..2N]; //B copy to A

]

PROCEDURE CompareExchange(VAR A:arraytype; N:integer)

[ j:=1;

WHILE j<2N DO

[ IF A[j]>A[j+1] THEN A[j]←→A[j+1]; //交换A[j]和A[j+1]

j:=j+2; ]

]

PROCEDURE Demo (VAR A:arraytype;N:integer)

//A的长度为2N,k=log22N为整数

[ FOR i:=1 TO log22N DO

[ PerfectShuffle(A,N); CompareExchange(A,N); ]

] 【中科院计算所 1998 四（15分）】【中国科技大学 1998 4（15分）】

24. 现有算法及正整数n和数组A如下，求数组C的值。

VAR A,B,C:Array[1..100] of integer;

FUNC AAA(s,t:integer):integer;

IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE

BEGIN

l:=AAA(s,(s+t) DIV 2);

r:=AAA((s+t) DIV 2+1,t);

IF l>0 THEN AAA:=l ELSE AAA:=r;

IF (r>0) AND (A[l]>A[r]) THEN AAA:=r

END

ENDF;

PROC BBB;

FOR i:=1 TO n DO B[i]:=0;

FOR i:=1 TO n DO B[AAA(1,n)]:=i;

FOR i:=1 TO n DO C[B[i]]:=A[i];

ENDP;

初始值：n=10,A={121,22,323,212,636,939,828,424,55,262};

【北京邮电大学 2002 五、1（10分）】

25. 设有矩阵ａ且a=

执行下列语句后，矩阵ｃ和ａ的结果分别是什么？

（1） FOR i:=1 TO 3 DO

FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]] （2） FOR i:=1 TO 3 DO

FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]] 【浙江大学 1997 三 (8分)】

26. 设矩阵A为

（1）执行语句

FOR i:=1 TO 3 DO

FOR j:=1 TO 3 DO ①

C[i,j]:=A[A[i,j],A[j,i]]

结果C矩阵的值是什么？

（2）所选择的下标i,j的次序有关系吗？

（3）在语句①中，用A代替C，A的结果值是什么？

（4）对i,j这对下标取反序，即

（3，3），（3，2），（3，1），……，（1，3），（1，2），（1，1）

重复执行（3）,把所得结果与（3）中所得结果作比较。【吉林大学 1995 二 (15分)】27. 指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。

PROCEDURE delk(A, m , last,i, k) ;

｛从数组A[１https://www.wendangku.net/doc/272803505.html,st]中删除第i个元素起的 k个元素，m为A上限｝

BEGIN

IF(i<1) OR (i>last) OR(k<0) OR(last>m)

THEN write ('error')

ELSE FOR count: = 1 TO k TO

[FOR j:=last DOWNTO i+1 DO

A[j-1]:=A[j];

last:=last-1]

ENDP;{delk} 【北方交通大学 1997 一（10分）】

28. 设输入为整数数组A[1..n]，其中1<=A[i]<=k(1<=i<=n)；输出数组为b[1..n]；c[1..k]是临时工作空间；阅读下述算法后，回答下列问题：

PROC Demo(A,B,k){

(1)FOR i:=1 TO k DO C[i]:=0;

(2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1;

(3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1]

(4)FOR j:=n DOWNTO 1 DO {

(5) B[C[A[j]]]:=A[j];

(6)C[A[j]]:=C[A[j]]-1 } }

(a).当标号（2）行的循环执行完后，C[i](1<=i<=n)的值有何意义？

(b).当标号（3）行的循环执行完后，C[i](1<=i<=n)的值有何意义？

(c).算法执行后，B的内容有何特点？

(d).当k=O(n)时，算法的时间复杂度是多少？【中科院软件所 1997 二、2（9分）】29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用i，j表示的k。

【北京工业大学 2001 二、1 (5分)】

30. 设有上三角矩阵(a ij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]=a ij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。

【中科院自动化所 1999】【山东科技大学 2002 一、5 （6分）】

31．设矩阵A=

(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素a ij (0<=i,j<4)；

(2) 若将A视为稀疏矩阵，画出A的十字链表结构。【北京科技大学 1997 三（10分）】

32. 设对称矩阵A=

（1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S:

下标：1 2 3 4 5 6 7 8 9 10

试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系. （2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】

33. 设对角线矩阵A=

（行列下标i ,j 满足：1≤i,j≤5）

（1

下标：

试求出A中已存储之元素的行列下标（i， j）与S中元素的下标K之间的关系

（2）若将A视为稀疏距阵时，请画出其行逻辑链接顺序表。【北京科技大学2000 三(10分)】

34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。

【山东师范大学 1999 四、1 （5分）】

35．假定有下列n ⅹn 矩阵（n 为奇数）A=???

????????????++-..001.......00...21,21......0..................01,2.........22010.........011ann an n n a n a a n a a

如果用一维数组B 按行主次序存储A 的非零元素，问：

（1）A 中非零元素的行下标与列下标的关系；

（2）给出A 中非零元素a ij 的下标(i,j)与B 中的下标R 的关系;

（3）假定矩阵中每个元素占一个存贮单元且B 的起始地址为A 0，给出利用a ij 的下标(i,j)定位在B 中的位置公式。【上海交通大学 1998 三(12分)】

36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分，并按列存放。例如对于一个n*n 的对称矩阵A (如右图) ，用一个一维数组B 来存放它的上三角部分： B=[A 11，A 12，A 22，A 13，A 23，A 33，A 14，…，A 1n ，A 2n ，…，A nn ] 同时有两个函数：MAX(i,j)和MIN(i,j)，分别计算下标i 和 j 中的大者与小者。试利用它们给出求任意一个Aij 在B 中存放位置的公式。（若式中没有MAX(I,j)和MIN （i ，j ）则不给分）【清华大学 1997 五 (10分)】

37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。【山东工业大学 1995 五（10分）】

38. 简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3分)】

39. 数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4分)】

40. 什么是广义表？请简述广义表和线性表的主要区别。【北京大学 1997 二、2 （5分）】

41. 求下列广义表的运算结果。【南京航空航天大学 1998 三（10分）】

（1）CAR(CDR(((a,b),(c,d),(e,f))))

（2）CDR(CAR(((a,b),(c,d),(e,f))))

（3）CAR(CDR(CAR(((a,b),(e,f)))))

（4）CDR(CAR(CDR(((a,b),(e,f)))))

（5）CDR(CDR(CAR(((a,b),(e,f)))))

注：CAR 运算相当于有些教材中的Head 运算，CDR 运算相当于Tail 运算。

42. 利用广义表的Head 和Ｔail 运算，把原子d 分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e ））。【北方交通大学 1996 一、2（5分）】类似本题的另外叙述有：

(1) 已知广义表L=((((a))),((b)),(c),d)，试利用head 和tail 运算把原子项c 从L 中分离出来。

【北京邮电大学 1992 三、2（25/4分）】【青岛海洋大学 1999 一、6 （5分）】

(2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e 。

（ a,（（）,ｂ）,（（（ｅ））））。

???????????????

????

???

?nn n n n A A A A A A

A A A A .....................

333223

221131211

【清华大学 1995 二（10分）】

(3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。

【西安电子科技大学 1996 二、3 （5分）】

(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。

L=(apple,(orange,(strawberry,(banana)),peach),pear)

【北京邮电大学 2000 三、2 （5分）】

(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算，将原子d从下列表中分解出来，请写出每一步的运算结果。

L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三（10分）】

(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。【北京工业大学 2001

二、2 (5分)】

43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。【南京航空航天大学 1999 三（10分）】

44. 假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。

( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) ) 【北方交通大学 1998 一（13分）】

45．知广义表A=（（（a）），（b），c，（a），（（（d，e））））

（1）画出其一种存贮结构图；

（2）写出表的长度与深度；

（3）用求头部，尾部的方式求出e。【东北大学 1997 一、2 (5分)】

46．画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。

【北京工业大学 1996 一、3 (6分)】

47. 广义表的结点结构如下:(TAG,DATA,LINK)。其中LINK为指向表中下一元素的指针;TAG 为标志域；DATA为数据域，具体含义如下: TAG=0表示该结点为原子结点，DATA为其数据；TAG=1表示该结点为一个子表，DATA为指向该子表的指针。

（1）说明下列算法A的功能(注:算法中p,t,m,n,r,q为指针;算法中的NIL对应图中的^) PROCEDURE A(p,t)

BEGIN

q:=NIL;

WHILE p<>NIL DO

BEGIN

IF p^.TAG<>0 THEN

BEGIN

m:=p^.DATA;

A(m,n);

p^.DATA:=n;

END;

r:=p^.LINK;

p^.LINK:=q;

q:=p;

p:=r

END;

t:=q;

END.

（2）对于 p 所指的广义表,画出执行算法A 后的表结构以及p ，t 的值:

【北方交通大学 1993 六（20分）】类似本题的另外叙述有：

题目基本相同，差别仅在于子表(b,c)与原子d 的前后顺序颠倒。【浙江大学 1994 六 (7分)】

48. 写出对广义表A=(x,((a,b),c,d))作运算head(head(tail(A)))后的结果。

【西安电子科技大学 2000计应用一、5（5分）】

49．写出广义表的运算结果: TAIL[HEAD[TAIL[((a,b),(c,d))]]]=?

【武汉交通科技大学 1996 二、7 (3分)】

50. 广义表中原子个数是否即为广义表的长度？【西安电子科技大学 2000计应用一、9（5分）】

51. 给出下列所示的3元多项式的广义表表示（分别以X 1，X 2，X 3第一到第三层变元）

P （X 1X 2X 3）=X 15X 23X 3+2X 15X 22X 34+5X 15X 23X 33+3X 1X 24X 32+X 2X 3+6

【华南理工大学 2001 一、2（4分）】

52. 设某表H 如下：

其中A,B,C 为子表名，a1,a2,b1,c1,c2,x 为其元素。

（1

）试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H 中取出单元素a2的

运算；

（2）画出表H 的链式存储结构；【北京科技大学 1998 三（10分）】

五算法设计题

1. 设有大小不等的n 个数据组（n 个数据组中数据的总数为m ），顺序存放在空间区D 内,每个数据占一个存储单元，数据组的首地址由数组S 给出，（如下图所示），试编写将新数据x 插入到第i 个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D 和数组S 的相互关系仍保持正确。

【东北大学 2000 六 (15分)】

2. 以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。

【北京工业大学 1997 三 (10分)】

3. 设整数x1,x2,…,x N已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。【山东大学 1992 五(13分)】

类似本题的另外叙述有：

（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三（10分）】4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

【中科院软件所 1996 】

5. 设原来将N个自然数1,2,…,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。

FOR I:=N DOWNTO 1 DO

BEGIN

C：=0；

FOR J：=1 TO I-1 DO

IF A[J]

A[I]：=C

END；

编程将经过上述处理后的A还原成原来的A。【上海大学 1996 二（16分）】

6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i 行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。【上海大学 2000 三（20分）】【中科院自动化所 1997】7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所 1999 五、2 （20分）】

8. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。【东南大学2001六(13分)】

类似本题的另外叙述有：

（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。

【清华大学 1998 六（10分）】

(2) 给定n×m矩阵A[a..b,c..d]，并设A[i,j]<=A[i,j+1]（a<=i<=b,c<=j<=d-1）知A[i,j]<=A[i+1,j],(a<=i<=b-1, c<=j<=d)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。【东南大学1994三(17分)】

9. 编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用

【南京航空航天大学 1997 八（12分）】【中科院计算所 1996】

10. 设二维数组a[1..m, 1..n] 含有m*n 个整数。

(1) 写出算法(pascal 过程或c 函数)：判断a 中所有元素是否互不相同?输出相关信息(yes/no)；

(2) 试分析算法的时间复杂度。【华中理工大学 1999 五（10分）】

11. 二项式(a+b)n 展开式的系数为

C （n ，0）=1，C （n ，n ）=1，对于n>=0

C （n ，k ）=C （n-1，k ）+C （n-1，k-1），对于0

(1)试写一个递归算法，根据以上公式生成C （n,k ）。（6分）

(2)试画出计算C （6，4）的递归树。（4分）

(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n 计算C(n,k)（6分）

【清华大学 1999 五（16分）】

12．设任意n 个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。【山东大学 1993 三 (12分)】. 类似本题的另外叙述有：

（1）已知数组A[1..n]的元素类型为整型，设计算法调整A ，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n ））

【北京理工大学 2000 四、1 （4分）】

（2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。

【华南师范大学 1999 六、1 (10分)】

（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。【南开大学 2000 三、2】

（4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。【合肥工业大学 2001 五、3 （8分）】

13.若S 是n 个元素的集合，则S 的幂集P(S)定义为S 所有子集的集合。例如， S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S ，写一递归算法求11111331146411510105116152015611721353521711828567056288121n=0n=1n=2n=3n=4n=5n=6n=7n=8

P(S)。

【东南大学 1993 五（15分）】【东南大学 1997 五（15分）】

14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：

它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right （down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【上海大学 1998 五（16分）】

15. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,a n） n>=0，其中a i或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写) 【北京工业大学 1998 十(15分)】

16. 广义表是n(n>=0)个数据元素a1,a2,a3,…,a n的有限序列。其中a i (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和子表元素结点，为了将两者统一，用了一个标志tag，当其为0时表示是原子结点，其data 域存储结点值，link域指向下一个结点，当其tag为1时表示是子表结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储：

TYPE glist=^gnode;

gnode=RECORD

link:glist;

CASE tag:0..1 OF

0:(data:char);

1:(sublist:glist)

END;

（1）画出广义表((a,b),c)的存储结构；

（2）写出计算一个广义表的原子结点个数的递归算法表示式；

（3）编写实现上述算法的过程或函数程序。【厦门大学 2002 三（12分）】

17. 广义表GL=(a1,a2 ,…,a n),其中 a k(k=1,2,...,n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义：

TYPE tagtype=0..1;

glist=^gnode;

gnode=RECORD

link:glist; {link 域指向下一个结点}

CASE tag:tagtype OF ｛tag=0 表示原子结点｝

0: (data :integer);

1:(sublist: glist)

END;

编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表

(3,(2,4,5),(6,3）) 数据域之和为23。【厦门大学 2000 四、2 （9分）】

18. 数组 H[ 1：1000] 中存放着1000个大小不同的正整数;

（1）选择一分类算法使能最快地得到其中10个最大的数，简要说明理由；

（2）编写一程序seek() ，执行该程序时，在命令行中提供二个参数；

seek a n 表示需打印H[ ]中n个最大数。

seek I n 表示需打印H[ ]中n个最小数。【浙江大学 1994 八 (18分)】

19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，

第一个数组为：4,12,28

第二个数组为：1,7,9,29,45

输出结果为：1,4,7--------------第一个数组

9,12,28,29,45---------第二个数组【上海大学 1998 四（20分）】

20. 设数组A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。【福州大学1998 四、3 (10分)】

21. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。【中科院计算所 2000 七（15分）】22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为O(m+n)) 【华中理工大学 2000 八、1（10分）】

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。【南京理工大学 1998 七、2 （7分）】

数据结构作业电子版

1数据结构课程研究的主要内容包括（）（）（） 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析（1）数据（2）数据元素（3）数据类型（4）数据结构（5）逻辑结构（6）存储结构（7）线性结构（8）非线性结构第二章作业一、判断题(在你认为正确的题后的括号中打√，否则打X)。 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。二、单项选择题。 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。

数组和广义表习题

一、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。 3．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。 4. 所谓稀疏矩阵指的是_ 。 5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____ 。为了区分原子和表，一般用 ____表示表，用 _____表示原子。一个表的长度是指 __，而表的深度是指__ __ 6、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若一行序为主序顺序存储，则元素a[45，68]的存储地址为；若以列序为主序存储，则元素a[45，68]的存储地址为。 7、有一个8ⅹ8的下三角矩阵A，若采用行序为主序顺序存储于一维数组a[1..n]，则n的值为。 8、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。 9、已知广义表A=（（（a））），则A的表头为：，A的表尾为：。 10、求下列广义表操作的结果：（1）Head ((a,b),(c,d)) == ; //头元素不必加括号（2）Head（Tail((a,b),(c,d))）== ; （3）Head（Tail（Head((a,b),(c,d))））== ; （4）Tail(Head(Tail((a,b),(c,d))))== ; 11、设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 12、广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 13、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 14、广义表的深度是__表展开后所含括号的层数 ____ 二、选择题 1、一个nⅹn的对称矩阵，如果以行或列为主序放入内存，则其容量为( )。 A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2 2、对数组经常进行的两种基本操作是( ) 。

目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)

第3章栈和队列一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是

数据结构严蔚敏清华大学出版社习题及答案

第1章绪论 (3) 1、填空题 (3) 2、应用题 (3) 第2章线性表 (4) 1、填空题 (4) 2、选择题 (5) 3、判断题 (5) 4、程序设计题 (5) 第3章栈和队列 (8) 1、填空题 (8) 2、选择题 (8) 3、判断题 (9) 第4章串 (9) 1、选择题 (9) 2、判断题 (9) 第5章数组和广义表 (9) 1、填空题 (9) 2、选择题 (9) 3、判断题 (10) 第6章树和二叉树 (10) 1、填空题 (10) 2、选择题 (11)

4、应用题 (11) 5、读程序写结果 (18) 第7章图 (19) 1、填空题 (19) 2、选择题 (19) 3、判断题 (20) 4、应用题 (20) 5、程序设计题 (25) 第8章动态存储管理 (25) 1、填空题 (25) 2、选择题 (25) 3、判断题 (25) 4、应用题 (25) 5、程序设计题 (25) 第9章查找 (26) 1、选择题 (26) 2、判断题 (27) 3、应用题 (27) 4、程序设计题 (28) 第10章内部排序 (29) 1、填空题 (29)

3、判断题 (30) 4、应用题 (30) 第11章外部排序 (31) 第12章文件 (31) 第1章绪论1、填空题 1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。 2、应用题 1、给出以下算法的时间复杂度. void fun(int n) { int i=1,k=100; while(i

目前最完整的数据结构1800题包括完整答案树和二叉树答案

第6章树和二叉树部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。三.填空题

1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x，则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item

(完整word版)数据结构第五章数组和广义表习题及答案

习题五数组和广义表一、单项选择题 1．常对数组进行的两种基本操作是（） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. 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 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 8. 已知广义表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)))) 9. 广义表（（a,b,c,d））的表头是（），表尾是（）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构二、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。

目前最完整的数据结构1800题包括完整答案第五章数组和广义表

第 5 章数组和广义表一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 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]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】 ①-④： 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 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.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]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤: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 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节；（2）A的第8列和第5行共占（）个字节；（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地

第五章数组和广义表

第五章数组和广义表一．选择题 1．在二维数组A 中引用A[i,j]的时间_________。 A．与i、j的大小有关 B．与i、j的大小无关 C．与i的大小有关，与j的大小无关 D．与i的大小无关，与j的大小有关 2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。 A．行号 B．列号 C．元素值 D.地址 3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。A．470 B．471 C．472 D. 473 4．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。A．行号 B．列号 C．元素值 D.地址 5．下面的说法中，不正确的是________。 A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可 C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销 7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。 A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1) 8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。 A. 行号 B.列号 C.元素值 D.元素总数 9．稀疏矩阵一般的压缩存储方法有两种，即________。 A．二维数组和三维数组 B．三元组和散列 C. 三元组和十字链表 D．散列和十字链表 10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。 A．52 B．48 C．54 D．53 11.数组通常具有的两种基本操作是________。 A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引12．二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 8，列下标j 的范围从1到10，则存放M 至少需要________个字节。 A．90 B．180 C．240 D．540 13．二维数组M 的元素是4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 4 ，列下标j 的范围从0 到 5,M 按行存储时元素M[3 Ⅱ5]的起始地址与M 按列存储时元素________的起始地址相同。

数据结构第五章数组和广义表

第五章数组和广义表：习题习题一、选择题 1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。 A. 长度可以不同B．不限C．类型相同 D. 长度不限 3．二维数组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 (2) A. 108 B. 114 C. 54 D. 60 (3)[8][5] B. A[3][10] [5][8] [O][9] 4.数组与一般线性表的区别主要是( )。 A.存储方面 B.元素类型方面 C.逻辑结构方面 D.不能进行插入和删除运算 5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。 A. (i-l)×n+j B. (i-l)×n+j-l C．i×(j-l) D. j×m+i-l 6．所谓稀疏矩阵指的是( )。 A.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7．对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8．稀疏矩阵一般的压缩存储方法有两种，即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。 A. 60 B. 66 C．18000 D．33 10. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L)))))

习题2参考答案及数组广义表习题

习题2参考答案一、单项选择题 1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A 二、填空题 1．线性 2．n-i+1 3．相邻 4．前移，前，后 5．物理存储位置，链域的指针值 6．前趋，后继 7．顺序，链接 8．一定，不一定 9．线性，任何，栈顶，队尾，队头 10．单链表，双链表，非循环链表，循环链表 11．使空表和非空表统一；算法处理一致 12．O(1)，O(n) 13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14．2、3 15．O(1) 三、简答题 1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个

第 5 章数组和广义表答案

第 5 章数组和广义表一、选择 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则 a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到 8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 3. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。 A. 808 B. 818 C. 1010 D. 1020 4. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0 到8，列下标j的范围从0到9。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（ E ）个字节；（2）A的第8列和第5行共占（ A ）个字节；（3）若A按行存放，元素A[8，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. A[8,5] B. A[4,9] C. A[5,8] D. A[0,9] 5. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

目前最完整的数据结构1800题包括完整答案第十章排序

第10章排序一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

第5章数组和广义表自测题含答案

第5章数组和广义表自测题含答案一、单选题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 ；若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。 2. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1， c 2)+[(j-c 2)*( d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。 4. 求下列广义表操作的结果：（1） GetHead 【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号（2） GetHead 【GetTail 【((a,b),(c,d))】】=== (c,d) ; （3） GetHead 【GetTail 【GetHead 【((a,b),(c,d))】】】=== b ; （4） GetTail 【GetHead 【GetTail 【((a,b),(c,d))】】】=== （d ） ; 二、单选题（ A ）1. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。（无第0行第0列元素）Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C 均不对答：此题与填空题第8小题相似。（57列×60行＋31行）×2字节＋10000=16902 ( B )2. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j ??????????????=n n n n a a a a a a A ,2 ,1,2 ,21,21 ,1

考研“数据结构”复习书传说中的1800题

第1章绪论一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和 C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO

目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表

最新版数据结构1800题含完整答案详解

数据结构作业电子版

数组和广义表习题

目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)

数据结构 严蔚敏 清华大学出版社 习题及答案

目前最完整的数据结构1800题包括完整答案树和二叉树答案

(完整word版)数据结构第五章数组和广义表习题及答案

目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表

第五章 数组和广义表

数据结构 第五章数组和广义表

习题2参考答案及数组广义表习题

第 5 章 数组和广义表答案

目前最完整的数据结构1800题包括完整答案 第十章 排序

第5章 数组和广义表 自测题含答案

考研“数据结构”复习书传说中的1800题

目前最完整的数据结构1800题包括完整答案第五章数组和广义表

数据结构严蔚敏清华大学出版社习题及答案

目前最完整的数据结构1800题包括完整答案第五章数组和广义表

第五章数组和广义表

数据结构第五章数组和广义表

第 5 章数组和广义表答案

目前最完整的数据结构1800题包括完整答案第十章排序

第5章数组和广义表自测题含答案