发布时间 : 星期四 文章数据结构习题及答案——严蔚敏更新完毕开始阅读
6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）
（A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front
7.栈和队列的共同点是（ ）
（A） 都是先进后出 （B）都是先进先出
（C）只允许在端点处插入和删除元素（D）没有共同点 8.表达式a*(b+c)-d的后缀表达式是（ ）。
（A）abcd*+-（B）abc+*d- （C）abc*+d-（D）-+*abcd
9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（ ） (A)a4，a3，a2，a1 (B)a3，a2，a4，a1 (C)a3，a1，a4，a2 (D)a3，a4，a2，a1
10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ） (A)rear－qulen (B)rear－qulen＋m
(C)m－qulen (D)1＋（rear＋m－qulen）% m 二、填空题
1.栈的特点是_______________________,队列的特点是__________________________。
2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素，对于栈只能在________
word文档 可自由复制编辑
插入和删除元素，对于队列只能在_______插入元素和_________删除元素。
3.一个栈的输入序列是12345,则栈有输出序列12345是____________。(正确/错误)
4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_____个元素。 三、算法设计题
1.假设有两个栈s1和s2共享一个数组stack[M],其中一个栈底设在stack[0]处，另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的C函数push（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。
2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。 一个栈s1用于插入元素,另一个栈s2用于删除元素. 参考答案： 一、选择题
1. C 2.A 3. B 4. B 5. B 6.B 7、C 8、C 9、C 10、D 二、填空题
word文档 可自由复制编辑
1、先进先出；先进后出2、线性 ； 任何 ；栈顶；队尾；对头3、正确的 4、3
三、算法设计题 1.
#define M 100 elemtype stack[M]; int top1=0,top2=m-1; int push(elemtype x,int i) {
if(top1-top2==1) return(1); /*else
if(i==1) stack[top1++]=x; if(i==2)stack[top2--]=x; return(0); }
int pop(elemtype *px,int i) { if(i==1)
if(top1==0) return(1); else {
word文档 可自由复制编辑
上溢处理*/
top1--;
*px=stack[top1]; return(0); } else if(i==2)
if(top2==M-1) return(1); else { top2++;
*px=stack[top2]; return(0); } } 2.
elemtype s1[MAXSIZE],s2[MAZSIZE]; int top1,top2;
void enqueue(elemtype x) {
if(top1==MAXSIZE) return(1); else {
push(s1,x);
word文档 可自由复制编辑