数据结构练习题第三章栈队列和数组习题及答案doc.docx
《数据结构练习题第三章栈队列和数组习题及答案doc.docx》由会员分享，可在线阅读，更多相关《数据结构练习题第三章栈队列和数组习题及答案doc.docx（32页珍藏版）》请在冰点文库上搜索。
数据结构练习题第三章栈队列和数组习题及答案doc
第三章栈、队列和数组
一、名词解释：
1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵
二、填空题：
1.栈修改的原则是或称,因此，栈又称为线性表。
在栈顶
进行插入运算，被称为——或,在栈顶进行删除运算，被称为
或=
2.栈的基本运算至少应包括—、、、—、一—五
种。
3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“”。
4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“
5.一般地，栈和线性表类似有两种实现方法，即——实现和——实现。
6.top=0表示，此时作退栈运算，则产生""；top=sqstack_maxsizeT表示,此时作进栈运算，则产生"”。
7.以下运算实现在顺序栈上的初始化，请在处用适当的句子予以填充。
intInitStack（SqStackTp*sq）
return
（1）;}
8.以下运算实现在顺序栈上的进栈，请在——处用适当的语句予以填充。
IntPush（SqStackTp*sq,DataTypex）
{if（sp->top==sqstac‘k_maxsizeT}{error（''栈满”）:
return（0）;}else{:
=x;
return
（1）;}
}
9.以下运算实现在顺序栈上的退栈，请在用适当句了予以填充。
IntPop（SqStackTp*sq,DataType*x）
（if（sp->top==0）（error（''T溢"）:
return（0）;}
else（*x=;
return
（1）;}
}
10.以下运算实现在顺序栈上判栈空，请在处用适当句子予以填充。
IntEmptyStack（SqStackTp*sq）
（if（）return
（1）;
elsereturn（0）;
}
11.以下运算实现在顺序栈上取栈顶元素，请在处用适当句子予以填
充。
IntGetTop（SqStackTp*sq,DataType*x）（if（）return（0）;
else{*x=;
return
（1）;}
}
12.以下运算实现在链栈上的初始化，请在处用请适当句了予以填充。
VoidInitStacl（LstackTp*ls）{;}
13.'以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。
VoidPush（LStackTp*ls,DataTypex）
（LstackTp*p;p=malloc（sizeof（LstackTp））;
p->next=ls;
14.以下运算实现在链栈上的退栈，请在处用请适当句了予以填充。
IntPop（LstackTp*ls,DataType*x）
{LstackTp*p:
if（ls!
=NULL）
{P=ls;
*x=;
ls=ls—〉next;
return
（1）；
}elsereturn（0）;
}
15.以下运算实现在链栈上读栈顶元素，请在处用请适当句了予以填
充。
IntGetTop（LstackTp*ls,DataType*x）
（if（Is!
=NULL）{:
return
（1）:
}
elsereturn（0）;
}
16.必须注意，递归定义不能是“循环定义”。
为此要求任何递归定义必须同时满足如下条件：
%1被定义项在定义中的应用（即作为定义项的出现）具有—
%1被定义项在最小“尺度”上的定义不是的。
17.队列简称。
在队列中，新插入的结点只能添加到,
被删除的只能是排在的结点。
18.队列以线性表为逻辑结构，至少包括、、
、、五种基本运算。
19.顺序队的出、入队操作会产生"
20.以下运算实现在循环队上的初始化，请在处用适当句子予以填充。
VoidInitCycQueue（CycqueueTp*sq）
（;sq-〉rear=0;}
21.以下运算实现在循环队上的入队列，请在处用请适当句子予以填
充。
IntEnCycQueue（CycquereTp*sq,DataTypex）
（if（（sq->rear+l）%maxsize==）{error（“队满"）;return（0）;
else{;
return
（1）;
}
22.以下运算实现在循环队上的出队列，请在处用适当句子予以填充。
IntOutCycQueue（CycquereTp*sq,DataType*x）
（if（sq->front==）{error（"队空”）;return（0）；}else{;
return
（1）;
}
}
23.以下运算实现在循环队上判队空，请在处用适当句子予以填充。
IntEmptyCycQueue（CycqueueTpsq）
（if（）return
（1）;
elsereturn（0）;
}
24.以下运算实现在循环队上取队头，请在处用适当句子予以填充。
IntGetHead（CycqueueTpsq,DataType*x）
（if（sq.rear==return（0）;
else（*x=sq.data[];
return
（1）;
}
25.链队在一定范围内不会出现的情况。
当lq.front=lq.rear试，队
中无元素，此时o
26.以下运算实现在链队上的初始化，请在处用适当句子予以填充。
voidInitQueue（QueptrTp*lp）
（LqueueTp*p;
p=（LqueueTp*）malloc（sizeof（LqueueTp））；
lq->rear=p;
（lq->front）->next=;
}
27.以下运算实现在链队上的入队列，请在处用适当句子予以填充。
VoidEnQueue（QueptrTp*lq,DataTypex）
（LqueueTp*p;
p=（LqueueTp*）malloc（sizeof（LqueueTp））;
=x;
p->next=NULL;
（lq->rear）-〉next=;
28.以下运算实现在链队上的出队列，请在处用适当句了予以填充。
intOutQueue（QuetrTp*lq,DataType*x）
{LqueueTp*s;
if（lq->front==lq->rear）{erroe（"队空”）；return（0）:
}
else（s=（lq-〉front）->next;
=s->data;
（lq->front）->next=；
if（s-〉next==NULL）lq->rear=lq->front;
free（s）;
return
（1）;
}
}
29.以下运算实现在链队上判队空，请在处用适当句了予以填充
intEmptyQueue（QueptrTp*lq）
{if（）return
（1）；
elsereturn（0）:
}
30.以下运算实现在链队上读队头元素，请在处用适当句了予以填充。
IntGetHead（QueptrTplq,DataType*x）
{LqueueTp*p;
if（lq.rear==lq.front）return（0）;
else{;
=p_〉data;
return
（1）;
}
}
31.一般地，一个n维数组可视为其数据元素为——维数组的线性表。
数组通常只有
和两种基本运算。
32.通常采用——存储结构来存放数组。
对二维数组可有两种存储方法：
一种是以
为主序的存储方式，另一种是以为主序的存储方式。
C语言数组用
的是以序为主序的存储方法；FORTRAN语言用的是以序为主序的存
储方法
33.需要压缩存储的矩阵可分为矩阵和矩阵两种。
34.对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元
素压缩存储到个元素的存储空间中。
35.假设以一维数组M（1：
n（n+l）/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为-
36.上三角矩阵中，主对角线上的第t行（l〈=t〈=n）有个元素，按行优先顺序存
放上三角矩阵中的元素膈时，a“之前的前iT行共有个元素，在第i行上，ai：
是该行的第个兀素，M［k］和的对应关系是。
当i〉j时，aij=c,c存放在］中。
37.下三角矩阵的存储和对称矩阵类似。
M［K］和喝的对应关系是o
38.基于二元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置,
请在处用适当的句了用以填充。
Trans_Sparmat（SpMatrixTpa,SpMatrixTp*b）
（（*b）.mu=a.nu;（*b）.nu=a.mu;（*b）.tu=a.tu;
if（a.tu）
{q=l；
for（col=l;;co1++）for（p=l;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;
}
}
39.基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组a.data的次序进行转置，请在处用适当的句子用以填充。
Fast_Trans_Sparmat（SpMatrixTpa,SpMatrixTp*b）
（（*b）.mu=a.nu;（*b）.nu=a.mu;（*b）.tu=a.tu=a.tu;
if（a.tu）
（for（col=l;;col++）num[col]=0;
for（t=l;t<=a,tu;t++）num[a.data[t].j]++;
cpot[1]=1;
for（col=2;col<=a.nu;col++）cpot[col]=;
for（p=l;p<=a.tu;p++）
{col=a.data[p].j;
q=cpot[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;
}
}
40.栈称为线性表。
；
41.队称为线性表。
42设一个链栈的栈顶指针为Is,栈中结点的格式为infonext,栈空的条件是
;如果栈不为空，则退栈操作为p=ls;;ls=ls->next;free（p）o
43.设有二为数组intM[10][20]（注：
m为0...10,n为0...20）,每个元素（整数）
栈两个存储单元，数组的起始地址为2000,元素M[5][10]的存储位置为,M[8][19]的存储值为o
44.在具有n个单元的循环队列中，队满时共有个元素。
45.可以作为实现递归函数调用的一种数据结构。
46.数组M中每个元素的长度是3个字节，行下标i从1到8,列下标j从1到0,从首的址EA开始连续存放在存储其中。
若按行方式存放，元素M[8][5]的起始地址为
;若按列优先方式存放，元素M[8][5]的地址为。
47.对带有头结点的列队列lq,判定队列中只有一个数据元素的条件是o
48.二维数组M的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i
的范围从0到8,列下标j的范围从1到10,则存放M至少需要个字节；M的第
8列和第5行共占个字节；若M按行方式存储，元素M[8][5]的起始地址与当M
按列优先方式存储时的元素的起始地址一致。
1.在以下栈的基本运算中，不是加工型运算的是（）
%1InitStack（S）②Push（S,X）③Pop（S）④empty（S）
2.以下说法正确的是（）
%1因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
%1因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
%1对于链栈而言,在栈满状态下，如果此时再作进栈运算，则会发生“上溢”
%1对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
3.在以下队列的基本运算中，不是加工型运算的是（）
%1
③OutQueu（Q,X）④GetHead（Q,x）
sq.data[sq.rear]二x
sq.rear=sq.rear+1
sq.data[sq.rear]=x
sq.rear=（sq.rear+1）%maxsize
sq.data[sq.rear]二x
sq.rear二sq.rear+1
sq.data[sq.rear]二x
sq.rear=（sq.rear+1）%maxsize
InitQueue（Q）②EnQueue（Q,X）
4.顺序队列的人队操作应为（）
%1sq.rear二sq.rear+1
%1sq.data[sq.rear]=x
%1sq.rear=（sq.rear+1）%maxsize;
%1sq.data[sqrear]=x
5.循环队列的人队操作应为（）
%1sq.rear二sq.rear+1
%1sq.data[sq.rear]=x
%1sq.rear=（sq.rear+1）%maxsize
%1sq.data[sq.rear]=x
6.顺序队列的出队操作为（）
%1sq.front、（sq.front+1）%maxsize
%1sq.front二sq.front+1
%1sq.rear=（sq.rear+1）%maxsize
%1sq.rear二sq.rear+1
7.循环队列的出队操作为（）
%1sq.front=（sq.ftont+1）%maxsize
%1sq.front二sq.front+1
%1sq.rear=（sq.rear+）%maxsize
%1sq.rear=sq.rear+1
8.循环队列的队满条件为（）
%maxsize;
%maxsize
®（sq.rear+1）%mazsize==（sq.front+1）
%1（sq.rear+1%maxsize==sq.front+1
%1sq.（rear+1）%maxsize==sq.front
%1sq.rear二二sq.front
9.循环队列的队空条件为（）
®（sq.rear+1）%maxsize==（sq.front+1）
%1（sq.rear+）%maxsize==sq.front+1
%1（sp.rear+1）%maxsize==sq.front
%1sq.rear==sq.front
10.数组的数据元素类型DataType可根据实际需要而定义。
以下说法完全正确的是（）
%1数组的读运算可以读取一个数据元素整体，写运算只能修改一个数据元素的一部分
%1数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
%1数组的读、写运算只能读取或修改一个数据元素的一部分
%1数组的读、写运算只能读取或修改一个数据元素整体
11.对于以行序为主序的存储结构来说，在数组山，C2•••d打中，cl和dl分别为数组A的第一个下标的上、下界，5“由分别为第二各下标的上、下界，每个数据元素占K个存储单元，二维数组中任一元素a[i,j]的存储位置可由（）式确定.
%1Loc[i,j]=[（d2-c2+l）（i-ci）+（j-C2）]*k
%1Loc[i,j]=loc[ci,c2]+[（d2-c2+l）（i~ci）+（j-c2）]*k
%1Loc{i,j}=A[ci,c2]+[（d2-c2+l）（i-Ci）+（j-c2）]*k
%1Loc[i,j]=loc[0,0]+[（d2-c2+l）（i~Ci）=（j-c2）]*k
12对于C语言的二维数组DataTypeA[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j]的存储位置可由（）式确定.
©Loc[i,j]=A[m,n]+[（n+l）*i+j]*k
%1Loc[i,j]=loc[0,0]+[（m+n）*i+j]*k
%1Loc[i,j]=loc[0,0]+[（n+l）*i+j]*k
%1Loc[i,j]=[（n+l）*i+j]*k
13.线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一种（）的存
储结构。
%1随机存取②顺序存储
14.如果以链表作为栈的存储结构，则退栈操作是（）
%1必须判别栈是否满②必须判别栈是否空
%1判别栈元素的类型④对栈不做任何操作
15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是（）
%1按照矩阵A的列序来进行转置，算法的时间复杂度为0（nu+tu）
%1按照A的二元组a.data的次序进行转置，算法的时间复杂度为0（nu*tu）
%1按照矩阵A的列序来进行转置的方法称快速转置
%1按照矩阵A的列序进行转置，对于tu«muxnu才有意义。
16.稀疏矩阵的压缩存储方法是只存储（）
①非零元素②三元祖（i,j,a“）③au④i,j
17.基于三元组的稀疏矩阵，对每个非零元素是,可以用一个（）唯一确定。
①非零元素②三元组（i,j,aij）③au④i,j
18如果以链表作为栈的存储结构,则退栈操作时（）
①必须判别栈是否满②判别栈元素的类型
③必须判别栈是否空④队栈不做任何判别
19.设C语言数组Datahn+1]作为循环队列SQ的存储空间，front为队头指针，rear为队
为指针，则执行出队操作的语句为（）
①front=front+l②front=（front+1）%m
③rear=（rear+1）④front=（front+1）%（m+1）
20.二角矩阵可压缩存储到数组（）中。
①M[l:
n（n+l）/2+l]②M[1:
n（n+1）/2]
®M[n（n+l）/2+l]@M[n（n+l）/2]
21.设有一顺序栈S,元素Sl,S2,S3,Sl,S5,S6依次进栈，如果6个元素出线的顺序是S2,S3,S.l,S6,
S5,S“则栈的容量至少应该是（）
①2②3③5④6
22.设有一顺序栈已含3个元素，如下图所不，元素a4正等待进栈。
那么下列4个序列
中不可能出现的出栈序列是（）
sq
al
a2
a3
0123
maxsize-1
ttop
①a3,al,a4,a2②a3,a2,a4,al③a3,a4,a2,al④a4,a3,a2,al
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
③x=Top;Top=Top->next
25.在一个链队中，若f,r分别为队首、
①f-〉next=c;f=s
③s-〉next=r;r=s
26常对数组进行的两种基本操作是
①建立与删除②索引与修改
②Top=Top-〉next;x=Top-〉data
④x=Top->data
队尾指针，则插入s所指结点的操作为（
②r-〉next=s;r=s
④s-〉next=f;f=s
③查找与修改
④查找与索引
（
27.链栈与顺序栈相比，有一个比较明显的优点即
①插入操作更方便②通常不会出现栈满的情况
③不会出现栈空的情况④删除操作更方便
28.若采用二元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，
了对该矩阵的转置运算，这种观点（
①正确②错误
29o二为数组的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从。
到4,列下标j的范围从。
到5。
M按行存储时元素M[3,5]的起始地址与M按列存储时元素（）的起始地址相同。
©M[2,4]②4]®M[3,5]@M[4,4]
30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是
①edcba②decba3dceab
31.一个队列的人列序是1,2,3,4,则队列的输出系列是
①4,3,2,1②1,2,3,4,③1,4,3,2
32.设计一个判别表达式中左、右括号是否配对出线的算法，采用（
①线性标的顺序存储结构②栈
③队列④线性表的链式存储结构
33.若已知一个栈的输入序列为1,2,3,其输出序列为P】、R、...P%若p】=n,则Pi为
就完成
）
（）
④abcde
（）
④3,2,4,1
）数据结构最佳。
②n=i③n-i+1
④不确定
34.以下说法正确的是
%1顺序队和循环队的队满和队空判断条件是一样的
%1栈可以作为实现过程调用的一种数据结构
%1插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用
%1在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear
35,以下说法正确的是
%1数组是同类型值的集合
%1数组是一组相继的内存单元
%1数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的
%1使用三元组表表不稀疏矩阵的元素，有时并不能节省存储空间四、简答及应用
1.简述顺序栈的类型定义。
2.简述链栈的类型定义。
3.简述顺序队列、循环队列的类型定义。
4.简述链队的类型定义。
5.写出基于三元组的稀疏矩阵的类型说明。
6.对于循环队列，试写出求队列长度的算法。
7.设有编号为t,2,3,4的四辆列车。
顺序进入一个占世界共的展台，试写出这四两列车开出车站的所有可能的顺序。
8设有上二角矩阵（aQn*n,将其上二角元素逐行存于数组B（l:
m）中（m充分大），使得B[k]=an,且k=f1（i）+f2（j）+Co是推导出函数fbf2和常数C（要求fl和f2中不含常数项）o
9
升级会员 