当前位置：文档之家 › C语言栈和队列课后题

C语言栈和队列课后题

  • 格式：ppt
  • 大小：158.52 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

栈和队列习题答案

栈和队列习题答案

第三章栈和队列习题答案一、基础知识题设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)(2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。

(3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

答：(1)出栈序列为：1324(2)不能得到1423序列。

因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。

这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。

能得到1432的出栈序列。

具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,4312链栈中为何不设置头结点答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

循环队列的优点是什么如何判别它的空和满答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。

栈和队列参考答案

栈和队列参考答案

int Check( ) { SqStack S; char ch1, ch2; InitStack(&S); ch1=getchar(); while(ch1!=‘&’ && ch1!=’@’) { Push(&S, ch1); ch1=getchar(); } while(ch1!=‘@’) { ch1=getchar(); Pop(&S, &ch2); if(ch1!=ch2) break; } if(ch1==‘@’ && StackEmpty(&S)) return 1; else return 0; }
参考答案： 参考答案：
#define MAXSIZE 6 #define OK 1 #define ERROR 0 typedef int elemType; typedef struct { elemType a[MAXSIZE]; int rear,length; }cycleque;
void InitQueue(cycleque *p) { p->rear=p->length=0; } int EnQueue(cycleque *p, elemType e) { if(p->length==MAXSIZE) //队列满 队列满 return ERROR; p->rear=(p->rear+1)%MAXSIZE; p->a[p->rear]=e; p->length++; return OK; }
int InitQueue(LinkQueue *Q) { Q->rear= (LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(!Q->rear) return ERROR; Q->rear->next= Q->rear; return TRUE; }

第三章栈和队列课后习题及作业

第三章栈和队列课后习题及作业

第三章栈和队列课后习题及作业
第三章栈和队列
1 试证明：若借助栈由输入序列12……n得到的输出序列为p1p2……p n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈j 〈k使p i
例，并仿照教科书
2节3--2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B*C/D+E ↑F
3试将下列递归过程改写为非递归过程。

Void test(int ＆sum){
Int x;
Scanf(x);
If(x==0)sum=0;
Else{test(sum
Printf(sum); }
4假设以顺序存储结构实现一个双向栈，既在一维数组的存储空间存在着两个栈，它们的栈底分别设在数组的两个端点。

试编写实现这个双向栈的三个操作：初始化inistack(tws)、入栈push(tws,i,x)、和出栈pop(tws,i)的算法，其中i 为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优
缺点。

5假设称正读和反读都相同的字符序列为“回文”，例如，…abba?和…abcba?是回文，…abcde?和…ababab?则不是回文。

试写一个算法判别读入的一个以…＠?为结束符的字符序列是否是回文。

第三、四章栈和队列、串答案[1]

第三、四章栈和队列、串答案[1]

第三、四章栈和队列、串答案[1]第三章栈和队列答案一、基础知识题1、单选题（1）栈的插入和删除操作在 A 进行。

A．栈顶B．栈底C．任意位置D．指定位置（2）当利用大小为n的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时首先应执行B 语句修改top指针。

A．top++ B．top-- C．top=0 D．top（3）若让元素1，2，3依次进栈，则出栈次序不可能出现C 种情况。

A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2（4）在一个顺序存储的循环队列中，队头指针指向队头元素的A 位置。

A．前一个B．后一个C．当前D．后面（5）当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为 B 。

A．n-2 B．n-1 C．n D．n+1（6）假定一个不带表头结点链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为 D 。

A．front = = rear B．front ! = NULLC．rear! = NULL D．front = = NULL2、填空题（1）队列的插入操作在队尾进行，删除操作在队头进行。

（2）栈又称为后进先出的表，队列又称为先进后出的表。

（3）向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置，然后把待插入元素写入到这个位置上。

（4）从一个栈删除一个元素时，需要前移一位栈顶指针。

（5）在一个循环队列Q中，判断队空的条件为Q.front = =Q. rear ，判断队满的条件为Q. rear+1）% MaxSize+1= =Q. front 。

（6）在一个顺序栈中，若栈顶指针等于-1 ，则为空栈；若栈顶指针等于MaxSize-1 ，则为满栈。

（7）向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。

（8）向一个循环队列中插入一个元素时，需要首先移动队尾指针，然后再向所指位置写入新插入的元素。

数据结构栈和队列习题及答案

数据结构栈和队列习题及答案

习题三栈和队列一单项选择题1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/22．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2B 一定是2C 可能是1D 一定是13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 64.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（）A.2B. 3C. 5D.65. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。

A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD. top[1]=top[2]6. 执行完下列语句段后，i值为：（）int f(int x){ return ((x>0) ? x* f(x-1):2);}int i ;i =f(f(1));A．2 B. 4 C. 8 D. 无限递归7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。

A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-8. 用链接方式存储的队列，在进行删除运算时（）。

C语言栈和队列课后题

C语言栈和队列课后题

• Status DeCyQueue(CyQueue &Q,int &x)// 带tag域的循环队列出队算法 { if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; x=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=0; //队列空 return OK; }//DeCyQueue
datatype top (twostack *s,int i)
/* 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作 */
{ datatype x; if (s->top[0]==-1 && s->top[1]==m) return(0);/* 栈空 */ else {switch (i) {case 0: x=s->v[s->top[0]];break; case 1: x=s->v[s->top[1]];break; default: printf(“栈编号输入错误”);return(0); } return(x); /* 取栈顶元素成功 */ } } /* 算法结束 */
• Status EnCyQueue(CyQueue &Q,int x)//带 tag域的循环队列入队算法 { if(Q.front==Q.rear&&Q.tag==1) //tag域的值 为0表示"空",1表示"满" return OVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue

第3章++栈和队列+课后习题答案

第3章栈和队列习题1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（）。

A． n+1 B． n-1 C．n D．n+2 （6）栈在（）中有所应用。

A．递归调用B．函数调用C．表达式求值D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A．队列 B．栈C．线性表D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

栈和队列_习题

第三章栈和队列一、单项选择题1．当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈入栈时，首先应执行( )语句修改top指针。

A. top++B. top--C. top=0D. top=N-12.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top= -1表示栈空，并已知栈未满，当元素X入栈时执行的操作为( )。

A. a[--top]=XB. a[top--]=XC. a[++top]=XD. a[top++]=X3.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未空，当退栈并返回栈顶元素执行的操作为( )。

A. return a[--top]B. return a[top--]C. return a[++top]D. return a[top++]4.假定一个链栈的栈顶指针用top表示，每个节点的结构为data域和next指针域，当p所指向的结点进栈时，执行的操作为（）A. p->next=top;top=top->nextB. top=p;p->next=topC. p->next=top->nextD. p->next=top;top=p5．假定一个链栈的栈顶指针用top表示，每个节点的结构为data域和next指针域，当执行退栈时，执行的操作为（）A. top->next=topB. top=top->dataC. top=top->nextD. top->next=top->next->next6．若让元素1，2，3，4依次进栈，则出栈次序不可能出现( )种情况。

A.3,2,1,4B.2,1,4,3C.4,3,2,1D.1,4,2,37. 在一个循环队列中，队首指针指向队首元素的( )位置。

A. 前一个B. 后一个C. 当前D. 最后7. 在一个链队中，假设f与r分别为队首和队尾指针，则插入s所指结点的运算时( )A.f->next=s;f=sB.r->next=s;r=sC.s->next=r;r=sD.s->next=f;f=s8. 假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元素X入队时执行的操作为( )。

第三章栈和队列习题答案

if(tws.top[i]==tws.base[i])
return OVERFLOW; if(i==0) x=*--tws.top[0]; else if(i==1) x=*++tws.top[1];}
else return ERROR;
return OK;
} //pop
5
2、试写一个算法，识别依次读入的一个以 @为结束符的字符序列是否为形如： 序列1&序列2 模式的字符序列。其中序列1和序列2都不含 字符&，且序列2是序列1的逆序列。
9
typedef char ElemType;
Status AllBrackets_Test(Sqlist L){
//判别表达式中三种括号是否匹配
ElemType *p; InitStack(s);
for(p=L.elem; p<p+L.length; p++)
if(*p==‘(’||*p==‘[’||*p==‘{’) push(s,*p); else if(*p==‘)’||*p==‘]’||*p==‘}’){
Push(S,c);EnQueue(Q,c); }
//同时使用栈和队列两种结构
while(!StackEmpty(S)) { Pop(S,a); DeQueue(Q,b)); if(a!=b) return FALSE; }
return TRUE; } //Palindrome_Test
20
Status Palindrome_Test( ){
return OK; }
13
Status DeCiQueue(CiLQueue &Q, int &x){ //出队：从循环链表表示的队列Q头部删除元素x

第二单元(栈和队列)(答案)

{
if(s->top<MAXSIZE)
{s->d[s->top]=x;
s->top++;
}
}
int pop(Seqstack *s)/*出栈操作*/
第二单元 课后练习题
知识点范围：第3章 栈和队列
一、选择题（每小题1分，共28分）
1．栈的特点是B，简称C的线性表；队列的特点是A，简称D的线性表。
A．先进先出B．后进先出
C．LIFOD．FIFO
2．栈和队列的共同点是C。
A．都是先进后出B．都是先进先出
C．只允许在端点处插入和删除元素D．没有共同点
10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。(×)
11.若以链表作为栈的存储结构，则进栈需要判断栈是否满。(×)
12.循环队列中元素个数为rear-front。(×)
四、计算题(第1小题4分，第2小题3分，第3小题4分，共11分)
铁道进行车厢调度，如下图2.2所示a,b二条铁道均为单向行驶，设有1~6编号的6节车厢，若进站的车厢序列为123456，则求解如下问题。
(1)能否得到435612和135426的出站序列？
(2)写出三种不可能的出站序列。
(3)写出2种可能的出站序列及用S表示进栈、X表示出栈的栈操作序列。
图2.2
答：
(1)可以得到135426出站序列，栈操作序列如下：
入栈车厢号：123 45 6
栈操作：SXSSXSSXXXSX
出栈车厢号：1 3 5 4 2 6
20．若一个循环队列，其最多元素个数为MAXSIZE，front为头指针，rear为尾指针，则判定满队列的条件是A。
A．(rear+1)%MAXSIZE==frontB．rear+1==front
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 输出结果为：入队操作，结果为：crh，左边为 对尾，右边是队首， 一次出队一次入队后 变为：hcr， 再一次出队一次入队后变为： ahc ，此时x中存的是r， 语句 while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };执行后结果为：cha； Printf(x);执行后为：r 故结果为：char。。
• 3.4 题答案是： • (1) 程序段的功能是将一栈中的元素按反序 重新排列，也就是原来在栈顶的元素放到 栈底，栈底的元素放到栈顶。此栈中元素 个数限制在255个以内。 • (2)程序段的功能是利用栈T，将一个非空 栈S中值等于e变量的元素全部删去。
3.12写出下列程序段的输出结果（队列中的元素类型
QElemType为char
）
• Void main() { • Queue Q; InitQueue(Q); • Char x=’e’, y=’c’; • 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); • } • Printf(x); • }
• typedef struct /* 两栈共享一向量空间 */ • { datatype v[m]; /* 栈可用空间0—m-1 */ • int top[2] • }twostack;
•
0 栈1底 栈1 顶 栈2顶
M-1
栈2底
• (1)int push(twostack *s,int i, datatype x) • /* 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，*/
3.13、简述以下算法的功能（栈和队列的元 素均为int)
• • • • • • • • • • Void algo3(Queue &Q) { Stack S; int d; InitStack(S); while( !QueueEmpty(Q)) { DeQueue(Q,d); Push(S,d); } While(!StackEmpty(S)) { Pop(S,d); EnQueue(Q,d); } }
• 输出结果是：stack
3.3解答
• 先解释一下你的一个误区： Pop()函数是出栈并 且将出栈的元素存放在第二个行参里，所以在这 里x的值不再是c了，而是出栈的元素。。 过程： 首先是三个压栈操作，之后栈里的元素为：cak， 左边的为栈底，右边是栈顶。 然后一个出栈，此 时栈里的元素为：ca，x中存的是k； 之后两次压 栈，此时栈里的元素为：catk； 之后一个出栈， 此时栈里的元素为：cat，x中存的是k； 最后一次 压栈，此时栈里的元素为：cats，x中存的是k； 之后while(!StackEmpty(S)){ Pop(S,y);printf(y); }; 结果是stac， Printf(x); 结果是k， • 所以最终的结果为stack •
• 程序段的功能是将一个循环队列Q经过S栈的处理， 反向排列，原来的队头变成队尾，原来的队尾变 成队头。
1.假设以顺序存储结构实现一个双向栈，即在一维数组的
存储空间中存在两个栈，它们的栈底分别设在数组的两 个端点。试编写实现这个双向栈tws的三个操作：初始化 initstack(tws),入栈push(tws,i,x) 和出栈pop(tws,i),其 中i 为0或1，用以分别指示设在数组两端的两个栈。
第三章 栈和队列习题课
• 3.3 写出下列程序的输出结果(栈的元素类型SElemType 为char）。
• • • • • • • • • • • Void main() { Stack S; Char x, y; InitStack(S); x=’c’; y=’k’; push(S,x); push(S,’a’); push(S,y); pop(S,x); push(S,’t’);push(S,x); pop(S,x); push(S,’s’); while (!StackEmpty(S)) {pop(S,y); printf(y); } printf(x); }
• /* 本算法是入栈操作 */
• { if (abs(s->top[0] - s->top[1])==1) return(0);/* 栈满 */ • else {switch (i) • {case 0: s->v[++(s->top[0])]=x;break; • case 1: s->v[--(s->top[1])]=x;break; • default: printf(“栈编号输入错误”);return(0); • } • return(1); /* 入栈成功 */ • } • } /* 算法结束 */
2)datatype pop(twostack *s,int i)
/* 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作 */
{ datatype x; if (s->top[0]==-1 && s->top[1]==m) return(0);/* 栈空 */ else {switch (i) {case 0: if (s->top[0]==-1 ) return (0); x=s->v[(s->top[0])--];break; case 1: if(s->top[1]==m) return (0); x=s->v[(s->top[1])++];break; default: printf(“栈编号输入错误”);return(0); } return(x); /* 退栈成功 */ } } /* 算法结束 */
3.4 简述以下算法的功能
• • (1) Status algo1(Stack S) { int i,n,A[255]; n=0; While(!StackEmpty(S)) {n++;Pop(S,A[n]);} For(i=1;i<=n;i++) Push(S,A[i]); } (2) Status algo2(Stack S,int e) { Stack T;int d; InitStack(T); while(!StackEmpty(S)) { Pop(S,d); if (d!=e) Push(T,d); } while (!StackEmpty(T)) { Pop(T,d); Push(S,d); }