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

习 题

一、选择题

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. 降低运算的时间复杂度 1

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))))) 12.广义表A=(a，b，(c，d)，(e，(f,g)))，则下面式子的值为( )。 Head(TaiI(Head(TaiI(Tail(A))))) A．(g) B．(d)

13．广义表((a，b，c，d))的表头是( )，表尾是( )。

B.( ) C.(a,b,c,d) D.(b,c,d) 14．设广义表L=((a，b，c))，则L的长度和深度分别为( )。 和1 和3 和2 和3 15.下面说法不正确的是( )。

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

二、填空题

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

2.二维数组A[10][20]每个元素占一个存储单元，并且A[0][O]的存储地址是200，若采用行序为主方式存储，则A[6][12]的地址是____ ，若采用列序为主方式存储，则A[6][12]的地址是____。

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

4. n阶对称矩阵a满足a[i][j]=a[j][i]，i,j=1．．n，，用一维数组t存储时，t的

长度为____， glist p； { glist q，h，t，s；

2

if (p==NULL) q=NULL; else

{ if____{q= (glist)malloc( sizeof (gnode));q->tag=0; q->=p->; } elsef ____； if______

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

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

s->val .ptr. tp=( glist) malloc( sizeof (gnode)); s=s->val .; s->tag=l; s->val．=NULL; s-> } else

{ q=( glist) malloc( sizeof( gnode));q->tag=l; q-> } } }

return (q)； } 三、判断题

1.数组不适合作为任何二叉树的存储结构。( ) 2.稀疏矩阵压缩存储后，必会失去随机存取功能。( ) 3.数组是同类型值的集合。( )

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

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

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

8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )

3

v1.0 可编辑可修改 9.所谓取广义表的表尾就是返回广义表中最后一个元素。( )

10.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。( ) 11. 一个广义表可以为其他广义表所共享。( ) 四、简答题

1.在以行序为主序的存储结构中，给出三维数组A2*3*4的地址计算公式（下标从0开始计数）。

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

求：

(1)存放该数组所需多少单元

(2)存放数组第4列所有元素至少需多少单元 (3)数组按行存放时，元素A[7，4]的起始地址是多少 (4)数组按列存放时，元素A[4，7]的起始地址是多少

3．将数列1，2，3，…，n*n，依次按下列方式存放在二维数组A[1．．n，1一n]

中。例如：n=5时，二维数组为

4．画出下列广义表的链接存储结构，并求其深度。 ((((),a,((b,c),(),d),(((e))))

5．已知题图5-1为广义表的链接存储结构，写出该图表示的广义表。

题图5-1

6．设有广义表K1(K2(K5(a，K3(c，d，e))，K6(b，k))，K3，K4(K3，f))，要求： (1)指出K1的各个元素及元素的构成。

(2)计算表K1，K2，K3，K4，Ks，K6的长度和深度。 (3)画出K1的链表存储结构。 五、算法设计题

1．对于二维整型数组A[m,n]，分别编写相应函数实现如下功能： 4

v1.0 可编辑可修改 (1)求数组A4边元素之和。

(2)当m=n时分别求两条对角线上的元素之和，否则显示m≠n的信息。 2．编写子程序，将一维数组A[n*n](n<=10)中的元素按蛇形方阵存放在二维数组B[n][n]中，即：B[0][0]=A[0]；

B[0][1]=A[1];B[1][0]= A[2]；

B[2][0]=A[3];B[1][1]=A[4];B[0][3]=A[6]； 依此类推，如图题5-2所示：

3．编写一个函数将两个广义表合并成一个广义表。合并是指元素的合并，如两个广义表((a，b)，(c))与(a，(e，f))合并后的结果是((a，b)，(c)，a，(e，f

第五章 数组与广义表

第5章数组与广义表

一、选择题

, A,B ,B 二、填空题

1．顺序存储方式。 2. 313, 327。

3. 1166。 *(n+1)/2,i*(i+l)/2。 5．线性表。 6．由其余元素构成的子表。 7．深度。 8．()，(())，2，2。

9. head (head (tail(L))). 10. (i= =k) break, i+l, i-l, i!=k。

11. p->tag==0, h=p-> p->next!=NULL, q=t, reverse(h)。 三、判断题

1．× 2．× 3．√ 4．× 5．× 6．× 7．× 8．× 9．× 10. √ 11. √ 四、简答题 5

v1.0 可编辑可修改 1. LOC(A[i][j][k]=LOC(A[0][0][0]+i*12+j*4+k. 2．

(1) 12l*32/16=242。 (2) 11*32/16=22

(3) LOC(A[0][0])+(8*11+3)*32/16=LOC(A[0][0])+182. (4) LOC(A[0][0])+182。 3．程序如下所示： #define NMAX 10 #include main() {

int i,j，n，k，m; int a [NMAX] [NMAX]; scanf( \"%d\ m=l;

for (i=O; i{ for (j=i*n,k=O; j<(i+1)*n; j++,k++) a[i][k]=m++; }

for(i=O; i4．深度为4广义表的链接存储结构为：

5.((x,(y)),((()),(),(z))) 6．ki由k2, k3, k4构成

k1 k2 k3 k4 k5 k6 长度： 3 2 3 2 2 2 6

深度： 4 3 1 2 2 l 五、算法设计题 1． (1) #define M 5 #define N 7

long sum side (int a[M] [N]) int equal(GListNode *ha, GListNode *hb); sublist;

while(p!=NULL) data= return l; else

return O; else sublist;

q=hb->val．sublist; r=h; //r指向前驱 while (p!=NULL) { r-p; p=p->link; }

r->link=s; s->link=NULL; }

7

=hb->val. data) sublist;