第五章数组和广义表习题_数据结构范文

习题五数组和广义表

一、单项选择题

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

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

4. 所谓稀疏矩阵指的是_ 。

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

6．设广义表L=((),()), 则head(L)是；tail(L)是；L的长度是；深度是 __。

7．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)

{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;

if(a.tu)

{ q=1;

for(col=1; ___________;col++)

for(p=1;p<=a.tu;p++)

if(___________==col)

{(*b).data[q].i=a.data[p].j;

(*b).data[q].j=a.data[p].i;

(*b).data[q].v=a.data[p].v;

___________;

}

}

8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。

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

}

三、应用题

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

2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。

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

3. 数组，广义表与线性表之间有什么样的关系？

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

B[k]=a ij，求：

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

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

5．画出下面广义表的两种存储结构图示：

((((a), b)), ((( ), d), (e, f)))

6．求下列广义表运算的结果：

（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))]]];

7. 利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e)）。

四、算法设计题

1. 给定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)。

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

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

(2) 试分析算法的时间复杂度。

3. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。

4．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

5. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,a n） n>=0，其中a i或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。

第5章数组和广义表

一、单项选择题

1． C

2． C

3． A

4． A

5． B

6． A

7． C

8． C

9． C

10． C

11． A

二、填空题

1．顺序、列序、行序

2. 第1行第3列

3．i(i-1)/2+j (1<=i,j<=n)

4. 非零元很少(t<

5．（1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。

（2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号的层数6．（1）（）（2）（（））（3）2 （4）2

7． col<=a.nu, a.data[p].j, q++

8. （1）(p->tag==0) //处理原子

（2）h=reverse(p->val.ptr.hp) //处理表头

（3）(p->val.ptr.tp) //产生表尾的逆置广义表

（4）s->val.ptr.tp=t; //连接

（5）q->val.ptr.hp=h //头结点指向广义表

三、应用题

1. 958 三维数组以行为主序存储，其元素地址公式为：

LOC(A ijk)=LOC(A c1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1

其中c i,d i是各维的下界和上界，V i=d i-c i+1是各维元素个数，L是一个元素所占的存储单元数。

2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t<

3. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组

是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

4. 三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。

（1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系i=j，k与i和j的关系为k=3(i-1)+1; 主对角线右上那条对角线上元素下标间有关系i=j-1，k与i和j的关系为k=3(i-1)+2。综合以上三等式，有k=2(i-1)+j (1<=i,j<=n, |i-j|<=1)

（2）i=k/3+1；（1≤k≤3n-2） // k/3取小于k/3的最大整数。下同

j=k-2(i-1)=k-2(k/3)=k%3+k/3

5．

第一种存储结构

第二种存储结构

6．

（1）HEAD[((a,b),(c,d))]; (a,b)

（2）TAIL[((a,b),(c,d))]; ((c,d))

（3）TAIL[HEAD[((a,b),(c,d))]]; (b)

（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b

（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)

7. Head（Tail（Head（Head（L1））））

Head（Head（Head（Tail（Head（Tail（L2））））））

四、算法设计题

1. ．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j]

void search(datatype A[ ][ ], int a,b,c,d, datatype x)

//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.

{i=a; j=d; flag=0; //flag是成功查到x的标志

while(i<=b && j>=c)

if(A[i][j]==x) {flag=1;break;}

else if (A[i][j]>x) j--; else i++;

if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.

else printf(“矩阵A中无%d 元素”，x)；

}算法search结束。

[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x

2.[题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1

行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。

int JudgEqual(ing a[m][n],int m,n)

//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。

{for(i=0;i

for(j=0;j

{ for(p=j+1;p

if(a[i][j]==a[i][p]) {printf(“no”); return(0); }

//只要有一个相同的，就结论不是互不相同

for(k=i+1;k

for(p=0;p

if(a[i][j]==a[k][p]) {printf(“no”); return(0); }

}// for(j=0;j

printf(yes”); return(1); //元素互不相同

}//算法JudgEqual结束

（2）二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为(m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂度是O(n4)。

3. [题目分析]题目要求按B数组内容调整A数组中记录的次序，可以从i=1开始，检查是否B[i]=i。如是，则A[i]恰为正确位置，不需再调；否则，B[i]=k≠i，则将A[i]和A[k]对调，B[i]和B[k]对调，直到B[i]=i为止。

void CountSort (rectype A[],int B[])

//A是100个记录的数组，B是整型数组，本算法利用数组B对A进行计数排序

{int i,j,n=100;

i=1;

while(i

{if(B[i]!=i) //若B[i]=i则A[i]正好在自己的位置上，则不需要调整

{ j=i;

while (B[j]!=i)

{ k=B[j]; B[j]=B[k]; B[k]=k; // B[j]和B[k]交换

r0=A[j];A[j]=A[k]; A[k]=r0; } //r0是数组A的元素类型,A[j]和A[k]交换

i++;} //完成了一个小循环，第i个已经安排好

}//算法结束

4．解答：本题首先判断三元组A，B表示的矩阵是否行列相同，若相同才能进行矩阵的加法运算。若三元组表示的矩阵能进行相加运算，其思路如下：

若a,b表的指针均没有到表尾，重复下列步骤：

（1）若a表元素的i 域值小于b表元素的i域值，将a表当前元素插入到c表表尾， a 表指针后移。

（2）若a表元素的i 域值大于b表元素的i域值，将b表当前元素插入到c表表尾， b

表指针后移。

（3）若a表元素的i域值等于b表元素的i域值，又分以下几种情况讨论：

①若a表元素的j域值小于b表元素的j域值，将a表当前元素插入到c表表尾，a表指针后移。

②若a表元素的j域值大于b表元素的j域值，将b表当前元素插入到c表表尾，b表指针后移。

③若a表元素的j域值等于b表元素的j域值，若a,b表当前元素的v域值和非零，则在c表表尾播入元素的I\j域值等于a表当前元素的I\j域的值，域v的值等于a,b表的域值的和，将a,b表当前指针后移。

(4) 若a表的指针没到表尾，b表的指针到表尾，将a表剩余元素依次插入到c表表尾，否则，将b表剩余元素依次插入到c表表尾.

SpMaterixTp trsxsum(SpMaterixTp a, SpMaterixTp b , SpMaterixTp c)

{if ( (a .mu=b. mu)&&(a.nu=b.mu)) /*a，b为同行同列矩阵*/

{c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;

if (a.tu&&b.tu) /*a，b为非空矩阵*/

{cola=a.data[I].i; rowa = a.data[I] .j; /*取三元组a的元素的行、列下标*/ colb= b.data[j].i; rowb =b.data[j] .j; /*取三元组b的元素的行、列下标*/ while ((I<=a.tu)&&(j<=b.tu))

switch

{cola

p++; c.data [p] .i=a.data [I] .i;

c.data [p].j= a.data [I].j;

c.data [p] .v= a.data[I].v;

I++; break; /*a元素后移*/

Cola>colb: /*在c中，插入三元组b的元素*/

P++;c.data[p] .i=b.data [j] .i;

c.data [p].j= b.data [j].j;

c.data [p] .v= b.data[j].v;

j++; break; /*b元素后移*/

Cola =colb :

P++; /*三元组 a，b的元素I域相等*/

If (rowa

{c.data[p].j=a.data [I].j;

c.data[p].j=a.data[j].j;

c.data[p].v=a.data[I].v; I++;

}

else if (rowa>rowb) /*在c中插入三元组b的元素*/

{c.data[p].i=b.data[j].i;

c.data[p].j=b.data[j].j;

c.data[p].v= b.data[j].v; j++;

}

else if (a.data[I].v +b.data[j].v)

/*a中的元素和b中的元素I，j的域都相等且v域的和非零*/

{c.data [p].i =a.data[I].i ;/*在c中元素*/

c.data[p].j=a.data[j].j;

c.data[p].v=a.data[I].v+b.data[j].v;

I++; j++;

} else {p--;I++;j++}; /*a中元素和b中元素的I，j域都相等且v

域的和为零*/

break;

} /*swith结束*/

}

if (I<=a.tu) /*b表到表尾，将a表中剩余元素插入到C表中*/

{p++; c.data[p].i =a.data[p].i; c.data[p].j=a.data[p].j;

c.data[p].v=a.data[p].v; I++;

else{ /*a表到表尾，将b表中剩余元素插入到C表中*/

p++; c.data[p].i=b.data[j].i; c.data[p].j=b.data[j].j;

c.data[p].v=b.data[j].v; j++;}

}c.tu=p; /*c表赋非零元素个数*/

}

5. 、[题目分析] 广义表的元素有原子和表。在读入广义表“表达式”时，遇到左括号‘（’就递归的构造子表，否则若是原子，就建立原子结点；若读入逗号‘，’，就递归构造后续子表；若n=0，则构造含空格字符的空表，直到碰到输入结束符号（‘#’）。设广义表的形式定义如下：

typedef struct node

{int tag; //tag=0为原子，tag=1为子表

struc t node *link; //指向后继结点的指针

union {struct node *slink; //指向子表的指针

char data; //原子

}element;

}Glist;

Glist *creat ()

//建立广义表的存储结构

{char ch; Glist *gh;

scanf(“%c”,&ch);

if(ch==’’) gh=null;

else {gh=(Glist*)malloc(sizeof(Glist));

if(ch==‘(’){gh->tag=1; //子表

gh->element.slink=creat(); } //递归构造子表

else {gh->tag=0;gh->element.data=ch;} //原子结点

}

scanf(“%c”,&ch);

if(gh!=null) if(ch==‘,’) gh->link=creat()； //递归构造后续广义表

else gh->link=null;

return(gh);

}

}算法结束

数据结构第五章习题课课案

1、特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非 零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所 在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组 表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下 标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的 起始地址与M按列存储时元素（）的起始地址相同。 A、M[2][4] B、M[3][4] C、M[3][5] D、M[4][4] 为第 3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。 一元素，其存储地址为1，每个元素占一个地址空间，则a 85 A. 13 B. 33 C. 18 D. 40 4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线 （i

第五章 数组和广义表

第五章数组和广义表 一．选择题 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、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D

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

数组与广义表的算法的实验报告

数组与广义表的算法 实验工具：visual C++ 实验容：1、三元组表示稀疏矩阵的转置算法（一般&快速）<1-7页> 2、稀疏矩阵乘法、加法的算法（一般&十字链表）<8-21页> 3、广义表的各种算法<22-28页> 体验：通过利用visual C++实验工具，实现数组与广义表各类算法的过程中，本人对数组与广义表的知识有了更深的了解，而且认识到数组与广义表各类操作可由形式多样的算法结构实现。算法并非统一标准的，同样的结果可有多种算法得出，算法的编写鼓励创造性思维。 1、三元组表示稀疏矩阵的转置算法（一般&快速） 代码： #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 #define MAXSIZE 100 #define MAXRC 100 typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple; typedef struct { Triple data[MAXSIZE+1]; //非零元三元组 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix; CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵M { int i,m,n; ElemType e; int k,j; printf("输入矩阵的行数、列数、非零元的个数："); scanf("%d%d%d",&M.mu,&M.nu,&M.tu); M.data[0].i=0;

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

第五章数组和广义表：习题 习题 一、选择题 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.散列和十字链表

习题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．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个

(完整版)数据结构---C语言描述-(耿国华)-课后习题答案

第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i]last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X;

L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(minknext->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”); return ERROR; } else { p=L; while(p->next-data<=mink)

第 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

数据结构(C语言版)第5章 数组和广义表

第 5 章数组和广义表 一、选择题 为第一元素，其 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。【燕山大学 2001 一、2 存储地址为1，每个元素占一个地址空间，则a 85 （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中元 （即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： 素A 6665 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按列存放时的元素（）的起始地

第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

数据结构课后习题及解

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

第五章习题 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

数组和广义表习题

习题五数组 5.1 单项选择题（其中A[i..j]表示下标从i到j） 1. 常对数组进行的两种基本操作是__C__。 A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M 至少需要__①D__个字节；M 的第8列和第5行共占__②B__个字节。 ①A. 90 B. 180 C. 240 D. 540 ②A. 108 B. 114 C. 54 D. 60 4. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是__C__。 A. 80 B. 100 C.240 D. 270 5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为_C___。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 (7*10+4)*3=222 6. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_B___。 A. SA+141 B. SA+180 C. SA+222 D. SA+225 (7*8+4)*3=180 5.2 填空题（将正确的答案填在相应的空中，其中A[i,j]表示下标从i到j） 1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_ LOC(A[0][0]) +(i*n+j)*k___。 2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是_326___。200+(12*10+6)*1=326 3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是__1000+(8*6+4)*4=1208__。 5.3算法设计题: 1. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 2. 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加

数组广义表答案及二叉树习题及答案

栈、队列、串、数组和广义表习题 一、选择题 1 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 2若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。 A. i B. n-i C. n-i+1 D. 不确定 3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 4 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。 A． 6 B. 4 C. 3 D. 2 5 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ） A．求子串 B．联接 C．匹配 D．求串长 6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 7 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为（ F ）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 二、填空题 1 在作进栈运算时应先判别栈是否_(1)满_;在作退栈运算时应先判别栈是否_(2)空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)n_。 2 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__return(sq.data(sq.front))；sq.front=(sq.front+1)%(M+1)；_____，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；_。 3 串是一种特殊的线性表，其特殊性表现在__(1) 其数据元素都是字符__；串的两种最基本的存储方式是__(2) 顺序存储__、__(3) 和链式存储__；两个串相等的充分必要条件

第五章 数组和广义表

第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

数据结构第五章习题答案

1.二维数组A行下标i的范围从1到12，列下标j的范围从3到10，采用行序为主序存储，每个数据存储元素占用4个存储单元，该数组的首地址（既A[1][3]的地址）为1200，则A[6][5]的地址为（D） A.1400 B.1404 C.1372 D.1368 2.有一个M*N的矩阵A,若采用行序为主序进行顺序存储，每个元素占用8个字节，则A ij (1≤i≤M,1≤i≤N)元素的相对字节地址（相对首元素地址而言）为（B） A.((i-1)*N+j)*8 B.((i-1)*N+j-1)*8 C.(i*N+j-1)*8 D.((i-1)*N+j+1)*8 3.稀疏矩阵一般的压缩存储方法有两种，即（D） A.二维数组和三维数组 B.三元组和散列 C.散列和十字链表 D.三元组和十字链表 4.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点(B) A.正确 B.错误 5.广义表（（a,b）,c,d)的表头是（C），表尾是（D）。 A.a B.b C.(a,b) D.(c,d) 6.一个广义表的表头总是广义表，这个断言是（B） A.正确 B.错误 7.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（326） 8.有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[4][3]的地址是（14） 9.一个广义表为（a,（a,b）,d,e,((i,j),k))，则该广义表的长度为（5），深度为（3） 10.广义表((a),((b),c),(((d))))的表头是（（a）），表尾是（（((b),c),(((d)))）） 11.已知广义表A=（（a,b,c），（d,e,f）），则广义表运算head(tail(tail(A)))=(e) 12.已知广义表GL=（a,(b,c,d),e），运用head和tail函数取出GL中的原子b的运算是（head(head(tail(GL)))） 13.特殊矩阵和压缩矩阵哪一种压缩存储后会失去随机存取的功能？为什么？ 答：稀疏矩阵在进行压缩存储后会失去随机存取的功能，因为非零元素的位置没有办法确定。 14.稀疏矩阵的三元组表存储结构中，记录的域rows,cols,nums和data分别存放什么内容？ 答：矩阵的行数，列数，非零元素个数及飞灵元三元组表。 15.简述广义表和线性表的区别和联系。 答：广义表中存储的是数据元素，该数据元素可能是单个元素，也可能是广义表；而线性表中只能包含数据元素。 16.广义表GL=((),()),求head(GL),tail(GL),GL的长度和深度。 答：head(GL)=(()) tail(GL)=(()) 长度：2 深度：2