栈和队列习题
- 格式：doc
- 大小：91.00 KB
- 文档页数：7
栈和队列习题一：举例.例子：对于一个栈，给出输入序列为abc，试写出全部可能的输出序列。
分析：本题有如下几种情况：（1）a进 a出 b进 b出 c进 c出产生输出序列abc(2) a进 a出 b进 c进 c出 b出产生输出序列acb(3) a进 b进 b出 a出 c进 c出产生输出序列bac(4) a进 b进 b出 c进 c出 a出产生输出序列bca(5) a进 b进 c进 c出 b出 a出产生输出序列cba(6) 不可能产生输出序列cab答案：abc、acb、bac、bca、cba.例子：利用顺序栈的基本运算，试设计一个算法，判断一个输入字符串是否具有中心对称（也就是所谓的“回文”，正读和反读均相同的字符序列），例如ababbaba，abccba都是中心对称的字符串。
算法如下：int Symmetry(){SeqStack S;int j,k,i=0;char str[80[;gets(str);while(str[i]!=’\0’) i++; /*求串长度*/for(j=0;j<i/2;j++)push(S,str[j]); /*前一半字符入栈*/if(i%2!=0)k=i+1;elsek=i;for(j=k/2;j<i;j++) /*后一半字符与栈中字符比较*/if(str[j]!=pop(S)return 0;elsecontinue;return 1;}二：单选题1．按字母a,b,c,d,e顺序入栈，则出栈的输出序列不可能的是（）。
A. decba B、 dceab C. abcde D.edcba2.判断一个顺序栈st(最多元素为StackSize)为栈满的条件是（）。
A. st.top!= StackSizeB. st.top!=0C. st.top!= -1 D、st.top== StackSize-13.栈又称为（）的线性表。
A. 顺序进出B.后进后出C、后进先出 D. 先进先出4.一个队列的入队顺序是1，3，5，7，9，则出队的输出序列只能是（）。
A.9，7，5，3，1 B、 1，3，5，7，9C.1，5，9，3，7D. 9，5，1，7，35. 判断一个顺序队列sq(最多元素为QueueSize)为空队列的条件是（）。
A、 sq.rear=sq.front B. sq.rear=0C. sq.front =QueueSizeD. sq.rear =QueueSize+16. 判断一个循环队列cq(最多元素为QueueSize)为满队列的条件是（）。
A. cq.rear=cq.frontB.cq.rear= QueueSizeC、(cq.rear+1)% QueueSize=cq.frontD.cq.rear% QueueSize+1=cq.front三：问答题简述下面所给算法的功能是什么？（假设栈元素为整数类型）（1） void ex31(SeqStack *S){int A[80],i,n;n=0;while(!empty(S)){ A[n]=pop[S];n++;}for(i=0;i<n;i++)push(S,A[i]);}答案：此算法功能是通过一个数组将一个栈中的所有元素逆置存放。
例如原来栈S中存放5个元素abcde，经过算法执行后，变为edcba。
(2) void ex32(SeqStack *s,int c){SeqStack T;int d;while(!StackEmpty(S)){ d=pop(S);if(d!=c) push(T,d);}while(!StackEmpty(T)){ d=pop(T);if(d!=c) push(S,d);}}答案：通过一个中间栈T，达到删除栈S中所有与变量c相同的元素。
四：算法设计题试利用循环队列（长度为k）存储,编写求斐波那契的前n（n>k）项(f0,f1,f2,…)的算法，其函数定义如下：0 n=01 n=1f(n)=f(n-2)+f(n-1) n>=2算法如下：因为循环队列长度为K，所以在执行算法结束时，留在队列中的元素应是所求序列中的最后k项。
由于只有k个元素空间，则在计算fi时，队列总是处在头尾相接的状态，因此只须一个指针rear 指向当前的队尾。
每次求得一个fi之后即送入(rear% k)的位置上，冲掉原来对头元素。
#define m maxlentypedef struct{int rear;int data[m];}CirQueue;int Fibonacci(int i) //求序列的前n项算法{ if(i == 0)return 0;else if(i= = 1)return 1;else return (Fibonacci(i-2) +Fibonacci(i-1));}void Fibonacci( CirQueue * Q, int k){int i, n;Q->rear = 0;scanf(“%d” ,&n);for(i =0; i<n ; i++){ Q->rear =i;if ( i> =k) Q->rear = Q->rear% k;Q->data [Q->rear] = Fibonacci(i);}}2．算法阅读假设两个队列共享一个循环向量空间（参见右下图），其类型Queue2定义如下：typedef struct{DateType data[MaxSize]；int front[2],rear[2]；}Queue2；对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。
请对以下算法填空，实现第i个队列的入队操作。
int EnQueue (Queue2 *Q,int i,DateType x){//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；if(Q－>rear[i]==Q－>front[ ① ]return 0； Q－>data[ ② ]=x；Q－>rear[i]=[ ③ ];return1；}①②③①(i＋1)%2(或1－i)②Q－>rear[i]③(Q－>rear[i]＋1)%Maxsize3、假定在一个链队列中只设置队列为指针，不设置对首指针，并且让队尾节点的指针域指向队首节点（称此微循环队列），试分别写出在循环链队上进行插入和删除操作的算法。
插入算法：void QInsert（LNode * &Rear , const Elemtype & item）{LNode * newptr = new LNode ;if(newptr = = NULL){printf(“wrong”);exit(1);}newptr ->data =item;if(Rear = = NULL)Rear = newptr ->next = newptr;else {newptr->next =Rear ->next;Rear ->next = newptr;Rear = newptr;}}删除算法：ElemType QDelte(LNode * & Rear){if(Rear = =NULL){printf(“Linked queue is empty ！”)；exit(1);}LNode * p = Rear ->next;if( p = = Rear)Rear =NULL;elseRear ->next = p->next;ElemType temp = p->data;free(p);return temp;}编写一个递归算法，输出自然数1…n这n个元素的全排列。
对n元素的全排列是一种递归算法，描述如下：void permute(int a[],int s,int n)//对a[s]…a[n-1]中的n-s个元素进行全排列，s的初值为0 {int i,temp;if(s==n-1){ //当递归排序到最后一个元素时结束递归//输出a中保存的一种排列for(i=0;i<n;i++)count<<a[i]<<””;count<<””;}else //继续递归排列for(i=s;i<n;i++){ //每循环一次使a[s]取一个新值，并对其后的//所有元素进行递归排序temp=a[s];a[s]=a[i];a[i]=temp;//交换a[s]与a[i]的元素值。
permute(a,s+1,n);//对a[s+1]...a[n-1]中的元素进行递归排序。
temp=a[s];a[s]=a[i];a[i]=temp;//恢复a[s]与a[i]的原有值}}调用此算法的完整程序如下：#include <iostream.h>const int UpperLimit=6;void permute(int a[],int s,int n)//对a[s]….a[n-1]中的n-s个元素进行全排列，s的初值为0 {} //函数提省略。
void main(void){int a[UpperLimit]; //定义存储n个整型元素的数组。
int n;count<<”Enter a number ‘n’ between 1 and”<< UpperLimit<<”:”;cin>>n; //输入待全排列的元素个数。
for(int i=0;i<n;i++)a[i]=i+1; //给数组a赋初值count<<end1;Permute(a,0,n);Count<<end1;}。
