数据结构练习题第三章栈、队列和数组习题及答案

请在___________处用适当的句子用以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=;(*b).nu=;(*b).tu=; if

{ q=1;

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

if(___________==col) {(*b).data[q].i=[p].j; (*b).data[q].j=[p].i; (*b).data[q].v=[p].v; ___________; } } 39．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组的

次序进行转置，请在___________处用适当的句子用以填充。

Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=;(*b).nu=;(*b).tu==; if

{for(col=1;___________;col++) num[col]=0; for(t=1;t<=a,tu;t++) num[[t].j]++; cpot[1]=1;

for(col=2;col<=;col++) cpot[col]=___________; for(p=1;p<=;p++) { col=[p].j; q=cpot[col];

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

__________________________; } } }

40．栈称为___________线性表。 ; 41．队称为___________线性表。

42设一个链栈的栈顶指针为ls，栈中结点的格式为 info next,栈空的条件是___________；如果栈不为空，则退栈操作为p=ls; ___________;ls=ls->next;free(p)。

43．设有二为数组int M[10][20](注：m为0...10,n为0...20),每个元素（整数）栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为___________，M[8][19]的存储值为___________。

44．在具有n个单元的循环队列中，队满时共有___________个元素。 45．___________可以作为实现递归函数调用的一种数据结构。

46．数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到0，从首的址EA开始连续存放在存储其中。若按行方式存放，元素M[8][5]的起始地址为

5

___________；若按列优先方式存放，元素M[8][5]的地址为___________。

47．对带有头结点的列队列lq,判定队列中只有一个数据元素的条件是___________。 48．二维数组M的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要___________个字节；M的第8列和第5行共占___________个字节；若M按行方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的___________元素的起始地址一致。

三、单项选择题

1．在以下栈的基本运算中，不是加工型运算的是 （ ）

①lnitStack(S) ②Push(S,X) ③Pop(S) ④empty(S) 2.以下说法正确的是 ( )

①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 3．在以下队列的基本运算中，不是加工型运算的是 （ ）

①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x) 4.顺序队列的人队操作应为 ( )

①=+1 []=x ②[]=x =+1 ③=+1)% maxsize; []=x

④[sqrear]=x =+1)% maxsize 5.循环队列的人队操作应为 ( )

①=+1 []=x ②[]=x =+1 ③=+1)% maxsize []=x

④[]=x =+1)% maxsize 6. 顺序队列的出队操作为 ( )

①=+1)% maxsize ②=+1

③=+1)% maxsize ④=+1

7. 循环队列的出队操作为 ( )

①=+1)% maxsize ②=+1

③=+)% maxsize ④=+1

8.循环队列的队满条件为 ( )

①+1) % mazsize ==+1) % maxsize; ②+1 % maxsize ==+1

③sq.(rear+1) % maxsize == ④ ==

9.循环队列的队空条件为 ( )

①+1) % maxsize ==+1) % maxsize

6

②+) % maxsize ==+1 ③+1) % maxsize == ④ ==

10.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是 ( ) ①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 ②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为 数组A的第一个下标的上、下界，c2…d2分别为第二各下标的上、下界，每个数据元素占K 个存储单元，二维数组中任一元素a[i,j]的存储位置可由( )式确定. ①Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k

②Loc[i,j]=loc[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ③Loc{i,j}=A[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ④Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k

12对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. ①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k ②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k ③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k ④Loc[i,j]=[(n+1)*i+j]*k

13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的存储结构。

① 随机存取 ② 顺序存储

14．如果以链表作为栈的存储结构，则退栈操作是 ( ) ①必须判别栈是否满 ②必须判别栈是否空 ③判别栈元素的类型 ④对栈不做任何操作

15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( ) ①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu) ②按照A的三元组的次序进行转置，算法的时间复杂度为O(nu*tu) ③按照矩阵A的列序来进行转置的方法称快速转置

④按照矩阵A的列序进行转置,对于tu<

16．稀疏矩阵的压缩存储方法是只存储 ( ) ①非零元素 ② 三元祖（i,j, aij） ③ aij ④ i,j 17．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。 ①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j

18如果以链表作为栈的存储结构,则退栈操作时 ( ) ①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④ 队栈不做任何判别

19．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为 （ ） ①front=front+1 ② front=（front+1）%m ③rear=(rear+1)%m ④ front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组（ ）中。

7

①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2] ③M[n(n+1)/2+1] ④M[n(n+1)/2] 21.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ ）

①2 ② 3 ③ 5 ④6

22．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列 中不可能出现的出栈序列是 （ ） 0 1 2 3 maxsize-1 sq a1 a2 a3 ↑top

①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1 23.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ） ①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next 24.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（ ）

①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data ③x=Top;Top=Top->next ④ x=Top->data

25.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ ） ①f->next=c;f=s ②r->next=s;r=s ③s->next=r;r=s ④ s->next=f;f=s

26常对数组进行的两种基本操作是 （ ） ①建立与删除 ② 索引与修改 ③ 查找与修改 ④ 查找与索引

27．链栈与顺序栈相比，有一个比较明显的优点即 （ ） ①插入操作更方便 ② 通常不会出现栈满的情况 ③不会出现栈空的情况 ④ 删除操作更方便

28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 （ ） ①正确 ②错误

29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素( )的起始地址相同。

①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4]

30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ） ① e d c b a ②d e c b a ③d c e a b ④a b c d e

31.一个队列的人列序是1，2，3，4，则队列的输出系列是 （ ） ① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，1

32．设计一个判别表达式中左、右括号是否配对出线的算法，采用（ ）数据结构最佳。 ①线性标的顺序存储结构 ②栈

③ 队列 ④ 线性表的链式存储结构

33．若已知一个栈的输入序列为1，2，3，...,n,其输出序列为P1、P2、...Pn。若p1=n,则P1为

①i ②n=i ③ n-i+1 ④ 不确定

8