第3课 栈队列和数组100927重点讲义资料.docx
《第3课 栈队列和数组100927重点讲义资料.docx》由会员分享，可在线阅读，更多相关《第3课 栈队列和数组100927重点讲义资料.docx（23页珍藏版）》请在冰点文库上搜索。
第3课栈队列和数组100927重点讲义资料
第三课栈、队列和数组
一选择题
1．对于栈操作数据的原则是（B）。
A．先进先出B．后进先出C．后进后出D．不分顺序
2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。
A．不确定B．n-i+1C．iD．n-i
3．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D）。
A．i-j-1B．i-jC．j-i+1D．不确定的
4．设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的出栈序列为（D）。
A．fedcbaB．bcafedC．dcefbaD．cabdef
5．输入序列为ABC，可以变为CBA时，经过的栈操作为（B）
A．push,pop,push,pop,push,popB．push,push,push,pop,pop,pop
C．push,push,pop,pop,push,popD．push,pop,push,push,pop,pop
6．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（C）。
A．top=top+1;V[top]=xB．V[top]=x;top=top+1
C．top=top-1;V[top]=xD．V[top]=x;top=top-1
7．若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）。
A．|top[2]-top[1]|==0B．top[1]+1==top[2]C．top[1]+top[2]==mD．top[1]==top[2]
8．执行完下列语句段后，i值为：
（B）。
intf（intx）
{return（（x>0）?
x*f（x-1）:
2）;}
inti;
i=f（f
（1））;
A．2B．4C．8D．无限递归
9．表达式a*（b+c）-d的后缀表达式是（B）。
A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd
10．表达式3*2^（4+2*2-6*3）-5求值过程中当扫描到6时，对象栈和算符栈为（D），其中^为乘幂。
A．3,2,4,1,1；（*^（+*-B．3,2,8；（*^-C．3,2,4,2,2；（*^（-D．3,2,8；（*^（-
11．用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D）。
A．仅修改队头指针B．仅修改队尾指针
C．队头、队尾指针都要修改D．队头、队尾指针都可能要修改
12．递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。
A．队列B．多维数组C．栈D．线性表
13．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（B）。
A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front
14．循环队列存储在数组A[0..m]中，则入队时的操作为（D）。
A．rear=rear+1B．rear=（rear+1）mod（m-1）
C．rear=（rear+1）modmD．rear=（rear+1）mod（m+1）
15．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（B）
A．1和5B．2和4C．4和2D．5和1
16．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（B）。
A．（rear+1）MODn==frontB．rear==front
C．rear+1==frontD．（rear-l）MODn==front
17．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（C）。
A．6B．4C．3D．2
18．数组A[0..4,-1..-3,5..7]中含有元素的个数（B）。
A．55B．45C．36D．16
19．设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（A）。
A．（i-1）*n+jB．（i-1）*n+j-1C．i*（j-1）D．j*m+i-1
20．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。
A．13B．33C．18D．40
21．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（B）。
A．BA+141B．BA+180C．BA+222D．BA+225
22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（A）。
A．1175B．1180C．1205D．1210
23．将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（B）。
A．198B．195C．197D．196
24．对稀疏矩阵进行压缩存储目的是（C）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
25．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B）。
A．60B．66C．18000D．33
26．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）。
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++
二、应用题
1．有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
答：
三个：
CDEBA，CDBEA，CDBAE
2．如果输入序列为123456，试问能否通过栈结构得到以下两个序列:
435612和135426，请说明为什么不能或如何才能得到。
答：
不能得出435612，理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
能得到135426：
1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：
13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
3．试证明：
若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：
存在着i答：
假设存在i4．用栈实现将中缀表达式8-（3+5）*（5-6/2）转换成后缀表达式，画出栈的变化过程图。
答:
835+562/-*-
5．设输入元素为1、2、3、P和A，输入次序为123PA。
元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。
答：
P,A,PA,AP1,PA1,AP21,PA21,PA321,PA32
6．简述如下算法功能。
Statusex1（StackS,inte）{
InitStack（T）;
while（!
StackEmpty（S））{
Pop（S,d）;
if（d!
=e）Push（T,d）;
}
while（!
StackEmpty（T））{
Pop（T,d）;
Push（S,d）;
}
}//ex1
7．写出如下程序段输出结果。
voidex3（）{
charx='e',y='c';
InitQueue（Q）;
EnQueue（Q,'h'）;
EnQueue（Q,'r'）;
EnQueue（Q,y）;
DeQueue（Q,x）;
EnQueue（Q,x）;
DeQueue（Q,x）;
EnQueue（Q,'a'）;
while（!
QueueEmpty（Q））{
DeQueue（Q,y）;
printf（y）;
}//while
printf（x）;
}//ex3
8．将如下递归过程改写为非递归过程。
⑴
voidtest（int&sum）{
intx;
scanf（x）;
if（x==0）sum=0;
else{
test（sum）;
sum+=x;
}
printf（sum）;
}
⑵
intack（intm,intn）{
if（!
m）returnn+1;
elseif（!
n）returnack（m-1,1）;
elsereturnack（m-1,ack（m,n-1））;
}//ack
9．三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？
如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7]的存贮首地址。
10．若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n（n+1）/2]中，那么，⑴A中任一个下三角元素aij（i≥j）,在数组B中的下标位置k是什么？
⑵A中任一个下三角元素aij（i≤j）,在数组B中的下标位置k是什么？
11．设有三对角矩阵（ai,j）m╳n,将其三条对角线上的元素逐行的存于数组B（1:
3n-2）中，使得B[k]=ai,j，求：
⑴用i,j表示k的下标变换公式；⑵若n=103，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。
12．设有矩阵ａ且
a=
，执行下列语句后，矩阵ｃ和ａ的结果分别是什么？
⑴for（i=1;i<=3;i++）
for（j=1;j<=3;j++）c[i][j]=a[a[i][j],a[j][i]];
⑵for（i=1;i<=3;i++）
for（j=1;j<=3;j++）a[i][j]=a[a[i][j],a[j][i]];
三、算法设计题
1．设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[0..maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。
试设计S1,S2有关入栈和出栈的操作算法。
参考答案：
两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。
两栈顶指针相邻时为栈满。
两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#definemaxsize两栈共享顺序存储空间所能达到的最多元素数
#defineElemtypeint//假设元素类型为整型
typedefstruct
{
Elemtypestack[maxsize];//栈空间
inttop[2];//top为两个栈顶指针
}stk;
stks;//s是如上定义的结构类型变量，为全局变量
⑴入栈操作
intpush（inti,intx）
//入栈操作。
i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。
入栈成功返回1，否则返回0。
{
if（i<0||i>1）{printf（“栈号输入不对”）;exit（0）;}
if（s.top[1]-s.top[0]==1）{printf（“栈已满\n”）;return（0）;}
switch（i）
{
case0:
s.stack[++s.top[0]]=x;return
（1）;break;
case1:
s.stack[--s.top[1]]=x;return
（1）;
}
}//push
⑵出栈操作
Elemtypepop（inti）
//退栈算法。
i代表栈号，i=0时为s1栈，i=1时为s2栈。
退栈成功返回退栈元素，否则返回-1。
{
if（i<0||i>1）{printf（“栈号输入错误\n”）;exit（0）;}
switch（i）
{
case0:
if（s.top[0]==-1）{printf（“栈空\n”）;return-1;}
elsereturn（s.stack[s.top[0]--]）;
case1:
if（s.top[1]==maxsize）{printf（“栈空\n”）;return-1;}
elsereturn（s.stack[s.top[1]++]）;
}
}//算法结束
2．设从键盘输入一列整数：
a1,a2,a3，…，an，试编写算法实现：
用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
参考答案：
#definemaxsize栈空间容量
voidInOutS（ints[maxsize]）
//s是元素为整数的栈，本算法进行入栈和出栈操作。
{
inttop=0;//top为栈顶指针，定义top=0时为栈空。
for（i=1;i<=n;i++）//n个整数序列作处理
{
scanf（“%d”,&x）;//从键盘读入整数序列
if（x!
=-1）//读入的整数不等于-1时入栈
if（top==maxsize-1）{printf（“栈满\n”）;exit（0）;}
elses[++top]=x;//x入栈
else//读入的整数等于-1时退栈
{
if（top==0）{printf（“栈空\n”）;exit（0）;}
elseprintf（“出栈元素是%d\n”,s[top--]）;
}
}
}
3．假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
⑴下面所示的序列中哪些是合法的？
A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIOO。
⑵通过对⑴的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
参考答案：
⑴A和D是合法序列，B和C是非法序列。
⑵设被判定的操作序列已存入一维数组A中。
intJudge（charA[]）
//判断字符数组A中的输入输出序列是否是合法序列。
如是，返回true，否则返回false。
{
i=0;//i为下标。
j=k=0;//j和k分别为I和字母O的的个数。
while（A[i]!
=’\0’）//当未到字符数组尾就作
{
switch（A[i]）
{
case’I’:
j++;break;//入栈次数增1
case’O’:
k++;if（k>j）{printf（“序列非法\n”）;exit（0）;}
}
i++;//不论A[i]是‘I’或‘O’，指针i均后移
}
if（j!
=k）{printf（“序列非法\n”）;return（false）;}
else{printf（“序列合法\n”）；return（true）;}
}//
在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。
整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
4．设计一个算法，判断一个算术表达式中的括号是否配对。
算术表达式保存在带头结点的单循环链表中，每个结点有两个域：
ch和link，其中ch域为字符类型。
参考答案：
表达式中的括号有以下三对：
‘（’、‘）’、‘[’、‘]’、‘{’、‘}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。
当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。
intMatch（LinkedListla）
//算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对
{
chars[];//s为字符栈，容量足够大
p=la->next;//p为工作指针，指向待处理结点
StackInit（s）;//初始化栈s
while（p!
=la）//循环到头结点为止
{
switch（p->ch）
{
case‘（‘:
push（s,p->ch）;break;
case‘）’:
if（StackEmpty（s）||StackGetTop（s）!
=’（’）{printf（“括号不配对\n”）;return（0）;}
elsepop（s）;
break;
case‘[‘:
push（s,p->ch）;break;
case‘]’:
if（StackEmpty（s）||StackGetTop（s）!
=’[’）{printf（“括号不配对\n”）;return（0）;}
elsepop（s）;
break;
case‘{‘:
push（s,p->ch）;break;
case‘}’:
if（StackEmpty（s）||StackGetTop（s）!
=’{’）{printf（“括号不配对\n”）;return（0）;}
elsepop（s）;
break;
}
p=p->next;//后移指针
}//while
if（StackEmpty（s））{printf（“括号配对\n”）;return
（1）;}
else{printf（“括号不配对\n”）;return（0）;}
}
算法中对非括号的字符未加讨论。
遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。
最后，若栈不空，仍结论括号不配对。
5．如果允许在循环队列的两端都可以进行插入和删除操作。
要求：
⑴写出循环队列的类型定义；⑵写出“从队尾删除”和“从队头插入”的算法。
用一维数组v[0..M-1]实现循环队列，其中M是队列长度。
设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。
定义front=rear时为队空，（rear+1）%m=front为队满。
约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。
⑴
#defineM队列可能达到的最大长度
typedefstruct
{
Elemtypedata[M];
intfront,rear;
}cycqueue;
⑵
Elemtypedelqueue（cycqueueQ）
//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。
{
if（Q.front==Q.rear）{printf（“队列空”）;exit（0）;}
Q.rear=（Q.rear-1+M）%M;//修改队尾指针
return（Q.data[（Q.rear+1+M）%M]）;//返回出队元素。
}//从队尾删除算法结束
voidenqueue（cycqueueQ,Elemtypex）
//Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。
{if（Q.rear==（Q.front-1+M）%M）{printf（“队满”;exit（0）;）
Q.data[Q.front]=x;//x入队列
Q.front=（Q.front-1+M）%M;//修改队头指针。
}//结束从队头插入算法
6．已知Ackermann函数定义如下，⑴写出Ack（2,1）的计算过程；⑵写出计算Ack（m,n）的非递归算法。
参考答案：
intAck（intm,n）
{if（m==0）return（n+1）;
elseif（m!
=0&&n==0）return（Ack（m-1,1））;
elsereturn（Ack（m-1,Ack（m,m-1））;
}
⑴Ack（2,1）的计算过程
Ack（2,1）=Ack（1,Ack（2,0））//因m<>0,n<>0而得
=Ack（1,Ack（1,1））//因m<>0,n=0而得
=Ack（1,Ack（0,Ack（1,0）））//因m<>0,n<>0而得
=Ack（1,Ack（0,Ack（0,1）））//因m<>0,n=0而得
=Ack（1,Ack（0,2））//因m=0而得
=Ack（1,3）//因m=0而得
=Ack（0,Ack（1,2））//因m<>0,n<>0而得
=Ack（0,Ack（0,Ack（1,1）））//因m<>0,n<>0而得
=Ack（0,Ack（0,Ack（0,Ack（1,0））））//因m<>0,n<>0而得
=Ack（0,Ack（0,Ack（0,Ack（0,1））））//因m<>0,n=0而得
=Ack（0,Ack（0,Ack（0,2）））//因m=0而得
=Ack（0,Ack（0,3））//因m=0而得
=Ack（0,4）//因n=0而得
=5//因n=0而得
⑵
intAckerman（intm,intn）
{intakm[M][N];inti,j;
for（j=0;jfor（i=1;i{akm[i][0]=akm[i-1][1];
for（j=1;jakm[i][j]=akm[i-1][akm[i][j-1]];
}
return（akm[m][n]）;
}//
7．利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。
参考答案：
Statusenqueue（Stack&S1,Stack&S2,ElemTypex）{
while（!
StackEmpty（S2））{
P
升级会员 