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

第五章数组和广义表：习题

习题

一、选择题

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

12.广义表A=(a，b，(c，d)，(e，(f,g)))，则下面式子的值为( )。

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

A．(g) B．(d)C.c D.d

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

A.a

B.( )

C.(a,b,c,d)

D.(b,c,d)

14．设广义表L=((a，b，c))，则L的长度和深度分别为( )。

A.1和1

B.1和3

C.1和2

D.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；

if (p==NULL) q=NULL;

else

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

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

elsef

____；

if______

{ 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=l;

s->val．ptr.tp=NULL;

s->val.ptr.hp=h;____;

}

else

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

q->val.ptr.tp=NULL;____;

}

}

}

return (q)；

}

三、判断题

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

2.稀疏矩阵压缩存储后，必会失去随机存取功能。( )

3.数组是同类型值的集合。( )

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

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

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

7.若一个广义表的表头为空表，则此广义表亦为空表。( )

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

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]，分别编写相应函数实现如下功能：

(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章数组与广义表

一、选择题

1.B

2.C

3.E, A,B

4.B

5.A

6.C

7.C

8.C

9.B 10.B 11.D 12.D 13.C,B 14.C 15.A

二、填空题

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

3. 1166。

4.n*(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->val.ptr.hp, p->next!=NULL, q=t, reverse(h)。

三、判断题

1．× 2．× 3．√ 4．× 5．× 6．×

7．× 8．× 9．× 10. √ 11. √

四、简答题

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", &n);

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; i

{for(j=O;j

printf ("%4d",a [i][j]);

printf(¨\n");

}

}

4．深度为4广义表的链接存储结构为：

5.((x,(y)),((()),(),(z)))

6．ki由k2, k3, k4构成

k

1 k

2

k

3

k

4

k

5

k

6

长度： 3 2 3 2 2 2

深度： 4 3 1 2 2 l

五、算法设计题

1． (1)

#define M 5

#define N 7

long sum side (int a[M] [N]) //计算四边元素之和，注意不要重复 {

long sum=0;

int i;

for(i=0; i

sum+=a[i][0];

for(i=1; i

sum+=a[O][i];

for (i=1; i

sum+=a[i] [N-1];

for (i=l; i

sum+=a[M-1] [i];

return sum;

}

(2)

long sum tilt (int a[M][N]) //计算两条对角线元素之和

{

long sum=0;

int i，j ;

if (M!=N)

{

printf ("\nM不等于N\n”);

return O;

}

for (i=O; i

sum+=a[i][i];

for (i=M-1; i>=0; i--)

sum+=a[i][M-i-l];

if (M%2!=0)

sum-= a[M/2] [M/2];//M为奇数时中间元素加了两遍

return (sum);

}

2．

#define NMAX 20 //最大N值

int a[NMAX*NMAX]，b[NMAX] [NMAX]，cnt; //定义全局变量利于通信

void MakeLine (int RowStart, int ColStart, int RowEnd)

{ /*功能：用数组A中的元素去填充数组B的一个对角线

参数含义：RowStart-斜线起始行号

ColStart----斜线起始列号

RowEnd---斜线结束行号*/

int i，j，step;

if (RowStart<=RowEnd) //求出数组B的下标i的增量，j的增量与之相反 step=l;

else

step=-l;

for (i=RowStart,j=ColStart; (RowEnd-i) *step>=0 ;i+-.s tep,j -=ste p)

b[i][j]=a[cnt++]; //斜线赋值，cnt用于赋值计数，初值为O

}

void MakeArray (int n) //给数组B的所有斜线赋值，n为数组大小

{

int d：

for (d=O;d<2*n; d++)

if(d

if (d%2==0)

MakeLine(d，O，O);

else

MakeLine(O，d，d);

else //下三角赋值

if ( d%2==0)

Makeline (n-l, d-n+l, d-n+l);

else

MakeLine (d-n+l, n-l, n-l);

}

main()

{

int i,j,n;

printf ("\nPlease input n: ¨);

scanf(¨%d"，&n);

for (i=O ;i

a[i]=i+1;

cnt=0; //赋值计数

MakeArray (n);

for(i=O;i

{

printf(¨＼n”);

for (j=0; j

printf(¨%5d¨,b[i][j]);

}

}

3.

int equal(GListNode *ha, GListNode *hb);

//函数原型：判别由ha和hb指向的广义表元素是否相等相等返回1，否则返回o

void GListInsertTail(GListNode *h, GListNode *s);

//函数原型：将s所指向的广义表元素插入到广义表h的末尾

GListNode* GListMerge (GListNode *ha, GListNode *hb) /*将广义表hb合并至广义表ha中，并充分利用原有空间*/

{

GListNode p,q，r;

if (ha= =NULL) //如果ha为空表，则hb即为合并结果

{

ha=hb;

return ha;

}

else

{

p=hb->val. sublist;

while(p!=NULL) //循环将hb中的各个元素合并至ha中

{

q=ha->val．sublist;

while (q! =NULL)

{

if (equal (p,q)) //相等元素不合并

break;

q=q->link;

}

if (q= =NULL)

{

r=p->link;

GListInsertTail (ha,p); //若ha中无相同元素，则插入到末尾

p=r;

}

else

p=p->link; //请读者在此处添加释放hb结点的代码

}

}

return ha;

}

int equal (GListNode *ha, GlistNode *hb)

{//判别由ha和hb指向的广义表元素是否相等，相等返回l，否则返回0 GListNode *p，*q ;

if (ha= =NULL) //空表情况判断

if (hb= =NULL)

return 1;

else

return O;

if (ha->tag! =hb->tag) //子表元素与单元素必不等

return O;

if (ha->tag= -0) //单元素相等判定

if (ha->val. data= =hb->val. data)

return l;

else

return O;

else //子表相等判定

{

p=ha->val. sublist;

q=hb->val．sublist; //通过循环依次比较两表中的元素是否相等 while(p!-NULL＆＆ql =NULL＆&equal (P,q)) //递归调用

{

p=p->link;

q=q->link;

}

if (p=-NULL＆＆q==NUIL)

return l;

else

return O;

}

}

void GlistInsertTail (GListNode *h, GListNode *s)

{，/将s所指向的广义表元素插入到广义表h的末尾

GListNode p，r;

p=h->val. sublist; r=h; //r指向前驱 while (p!=NULL)

{

r-p;

p=p->link;

}

r->link=s;

s->link=NULL;

}

第五章 数组和广义表

第五章数组和广义表 一．选择题 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)))))

(完整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 中的第_ _行，第_ _列的元素。

第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

数据结构 第4—5章串和数组自测卷答案

第4～5章串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。 答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （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）; 二、单选题（每小题1分，共15分） （ D ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：

第五章 数组和广义表

第5章数组和广义表习题 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。 i×（i-1）/2+j-1~~~~（i>=j） 8×7÷2+5=33因为a11从1开始所以要加1 A. 13 B. 33 C. 18 D. 40 2. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A)。 所求=a+(j*n+j)*l A. 1175 B. 1180 C. 1205 D. 1210 3. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

数据结构 串和数组 练习试题

第4～5章串和数组自测卷姓名班级 一、填空题（每空1分，共20分） 1. 称为空串；称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 4. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。 8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== ; （2）GetHead【GetTail【((a,b),(c,d))】】=== ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ; 二、单选题（每小题1分，共15分） （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （）3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

数据结构课后习题及解

数据结构课后习题及解析第五章

第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];

实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p

数据库系统l试题库及答案 第5章数组和广义表

第5章 数组和广义表 5.1数组 一、填空题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置 （基地址）为1000，则数组A 的体积（存储量）为 ；末尾元素A 57的第一个字节地址为 。 2. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 、 和 。 3. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则 元素a[32,58]的存储地址为 。 4. 设n 行n 列的下三角矩阵A 已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j] 对应的B 中存储位置为 。 5. 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：a 11=1），则a 85 的地址为 。 6. 设下三角矩阵A 如果按行序为主序将下三角元素A i j (i ≤j)存储在一个一维数组B[1..n(n+1)/2]中， 对任一个三角矩阵元素A ij ,它在数组B 中的下标为 。 二、选择题 1. （ ）假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000， 每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。 A ．16902 B ．16904 C ．14454 D ．答案A, B, C 均不对 2. （ ）对特殊矩阵采用压缩存储的目的主要是为了 。 A ．表达变得简单 B ．对矩阵元素的存取变得简单 C ．去掉矩阵中多余元素 D ．减少不必要的存储空间 3. （ ）对于n 阶对称矩阵，如果以行序或列序放入内存中，则需要 个存储单元。 A ．n(n+1)/2 B ．n(n-1)/2 C ． n 2 D ．n 2 /2 4. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时， 所需的字节数是 。 A. 60 B. 66 C. 18000 D. 33 5. 对稀疏矩阵进行压缩存储目的是（ ）。 A ．便于进行矩阵运算 B ．便于输入和输出 C ．节省存储空间 D ．降低运算的时间复杂度 6. （ ）设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一 维数组B[1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是 。 A ．i(i-1)/2+j-1 B ．i(i-1)/2+j C ．i(i+1)/2+j-1 D ．i(i+1)/2+j 三、判断题： 1．（ ）一个稀疏矩阵Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 ?????? ? ???????=n n n n a a a a a a A ,2,1 ,2,21,21,1Λ Λ

(习题)数据结构第五章 数组与广义表

第五章数组与广义表 5.1 假设有二维数组A6×8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，计算： (1)数组A的体积（即存储量）； (2)数组A的最后一个元素a57的第一个字节的地址； (3)按行存储时，元素a14的第一个字节的地址； (4)按列存储时，元素a47的第一个字节的地址。 5.2 若矩阵A m×n中的某个元素a i×j是第I行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵A m×n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。 5.3 现有如下的稀疏矩阵A如图所示，要求画出以下各种表示法。 (1)三元组表示法； (2)伪地址表示法； (3)带行指针向量的单链表示法； (4)十字链表法。 5.4 求下列广义表操作的结果： ⑴GetHead【(p,h,w)】 ⑵GetTAil【(b,k,p,h)】 ⑶GetHead【((a,b),(c,d))】 ⑷GetTail【((a,b),(c,d))】 ⑸GetHead【GetTail【((a,b),(c,d))】】 ⑹GetTail【GetHead【((a,b),(c,d))】】 ⑺GetHead【GetTail【GetHead【((a,b),(c,d))】】】 ⑻GetTail【GetHead 【GetTail 【((a,b),(c,d))】】】 注意：【】是函数的符号。 5.5 利用广义表的GetHead和GetTail操作写出如上题的函数表达式，把原子banana分别从下列广义表中分离出来。 ⑴L1=(apple,pear,banana,orange); ⑵L2=((apple,pear),(banana,orange)); 5.6 下述广义表的长度和深度各是多少？ ⑴L1=((a),((b),c),(((d)))); ⑵L2=(a,(a,b),d,e,((i,j),k));

中南大学数据结构与算法第5章数组和广义表课后作业答案

第5章数组与广义表习题练习答案 5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。 解： 按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002 a0010a0011a0012 a0100a0101a0102 a0110a0111a0112 a0200a0201a0202 a0210a0211a0212 a1000a1001a1002 a1010a1011a1012 a1100a1101a1102 a1110a1111a1112 a1200a1201a1202 a1210a1211a1212 按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)： a0000a1000 a0100a1100 a0200a1200 a0010a1010 a0110a1110 a0210a1210 a0001a1001 a0101a1101

a0201a1201 a0011a1011 a0111a1111 a0211a1211 a0002a1002 a0102a1102 a0202a1202 a0012a1012 a0112a1112 a0212a0212 5.2 给出C语言的三维数组地址计算公式。 解： 因为C语言的数组下标下界是0，所以 Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d 其中Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。 5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求： (1)用i , j 表示k的下标变换公式。 (2)用k 表示i,j 的下标变换公式。 (1) 解： 要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k 的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为： (i*3-1)+j-(i+1) 其中(i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数 化简可得： k=2i+j; // c下标是从0开始的。

数据结构复习题-第5章答案2014-6-16

第5章数组与广义表 一、选择题（每小题1分，共10分） 1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ A ）。 A.110 B.108 C.100 D.120 2.在数组A中，每一个数组元素A[i][j]占用3个存储字节，行下标i从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存 储字节数是（ C ）。 A.80 B.100 C.240 D.270 3.假设有60行70列的二维数组a[1,60, 1,70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ C ）。（无第0行第0列元素） A.16902 B.16904 C.14454 D.答案A, B, C均不对 4.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。 A. 198 B. 195 C. 197 D.196 5.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（ A ）。 A. 1175 B. 1180 C. 1205 D. 1210 6.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]= （ B ）。 A. 808 B. 818 C. 1010 D. 1020 7. 设有数组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 8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A、 13 B、 33 C、 18 D、 40 9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,,,8,列下标 j=1,2,,,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。 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（inext D、 j=r[j]-> next 13. 数组A[0..4,-3..-1,5..7]中含有元素的个数为（ B ）。

第5章 数组和广义表答案

第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得 B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;pdata[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } } } 算法(二) FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) { int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { for(col=1;col<=A.n;col++) position[col]=0; for(t=1;t<=A.len;t++) position[A.data[t].col]++; /*计算每一列的非零元素的个数*/ /*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]中*/ for(col=A.n,t=A.len;col>0;col--) { t=t-position[col]; position[col]=t+1; } for(p=1;p

《数据结构》第五章 数组 习题

《数据结构》第五章 数组 习题 基本概念题： 5-1 分别写出一维数组和二维数组的存储映象公式。 5-2 什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？C 语言采用的是行序优先存储还是列序优先存储？ 5-3 什么叫随机存储结构？为什么说数组是一种随机存储结构？ 5-4 动态数组和静态数组在使用方法上有什么不同？ 5-5 什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？ 5-6 什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？ 5-7 什么叫稀疏矩阵的三元组？什么叫稀疏矩阵的三元组线性表？ 5-8 稀疏矩阵主要有哪些压缩存储结构？ 复杂概念题： 5-9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[n][m]中每个数据元素占k 个存储单元，且第一个数据元素的存储地址是Loc(a[0][0])，求数据元素a[i][j](0≤i≤n -1, 0≤j≤m -1)的存储地址。 5-10 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[10][8]中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a[4][5]的存储地址。 5-11 画出一个3行3列二维动态数组存储结构示意图。 5-12 对于如下所示的稀疏矩阵A （1）写出该稀疏矩阵的三元组线性表； （2）画出稀疏矩阵A 的三元组顺序表结构； （3）画出稀疏矩阵A 的带头结点单链表结构； （4）画出稀疏矩阵A 的行指针数组链表结构； （5）画出稀疏矩阵A 的三元组十字链表结构。 算法设计题： 5-13 为节省内存，n 阶对称矩阵采用压缩存储，要求： （1）编写实现C = A + B 操作的函数。设矩阵A 、矩阵B 和矩阵C 均采用压缩存储方式存储，矩阵元素均为整数类型。 （2）编写一个采用压缩存储的n 阶对称矩阵的输出函数，要求输出显示成矩阵形式，设矩阵元素均为整数类型。 （3）设矩阵A 和矩阵B 为如下所示的矩阵，编写一个用矩阵A 和矩阵B 作为测试例子的测试上述函数的主程序。 ?????????? ????????????=0000000033000220000000000001900000000000090000500000A

《数据结构》习题集：第5章_数组与广义表

第5章数组与广义表 一、选择题 1.在以下讲述中，正确的是（B ）。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出 2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转 置运算，这种观点（A ）。 A、正确 B、错误 3.二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始 连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（B）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225 4.数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续 存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270 5.常对数组进行的两种基本操作是（B ）。 A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5] 在B 数组中的位置K 为（ B ）。 A、19 B、26 C、21 D、15 7.若广义表A 满足Head(A)=Tail(A)，则A 为（B ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8.广义表（（a）,a）的表头是（ C ），表尾是（C ）。 A、a B、b C、(a) D、((a)) 9.广义表（（a,b）,c,d）的表头是（ C ），表尾是（D ）。 A、a B、b C、(a,b) D、(c,d) 10.广义表（（a））的表头是（ B ），表尾是（C ）。 A、a B、(a) C、() D、((a)) 11.广义表（a,b,c,d）的表头是（A ），表尾是（D ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12.广义表（（a,b,c,d））的表头是（C ），表尾是（B ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13.下面结论正确的是（BC ）。 A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表 C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14.广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D ) A、(G) B、(D) C、C D、D

第五章数组和广义表

第五章数组与广义表 一．选择题 1．下面的说法不正确的是____________。 A．数组是一种线性结构B．数组是一种定长的线性表结构 C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和 排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操 作 分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改 错误。答案应选择C。 2．一维数组A 采用顺序存储结构，每个元素占用6 个字节，第6 个元素的起始地址为100，则该数组的首地址是 。 A．64 B．28 C．70 D．90 分析：设数组元素的首地址为x，则存在关系x+5*6=100，因此x 为70，答案应选择C。 3．稀疏矩阵采用压缩存储的目的主要是______________ 。 A．表达变得简单B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 分析：答案应选择D。 4．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B 中确 定aij(i