3 栈和队列答案

本文格式为Word版，下载可任意编辑——3栈和队列答案第3章栈和队列

一、基础知识题

3.1设将整数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种排列中，哪些序列是可以通过相应的入出栈操作得到的。

3.2链栈中为何不设置头结点?

3.3循环队列的优点是什么?如何判别它的空和满?3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?

3.5指出下述程序段的功能是什么?

(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,iF)/*注：按C++的优先级*/(6)!(A&&!((BD)))||(C

(5)AB//假定栈元素的数据类型为字符typedefstruct{

DataTypedata[StackSize];inttop;}SeqStack;

intIsHuiwen(char*t)

{//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;

InitStack(

len=strlen(t);//求向量长度

for(i=0;iTop=-1;//其实只是将栈置空}

由于要置空的是栈S，假使不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开拓另外的单元来对形参进行函数操作。结果等于什么也没

有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。

3.11利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?解：

算法如下：

intStackSize(SeqStackS){//计算栈中结点个数intn=0;

if(!EmptyStack(n++;}

returnn;}

上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最终返回元素个数。

3.12设计算法判断一个算术表达式的圆括号是否正确配对。(提醒：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。解：

根据提醒，可以设计算法如下：intPairBracket(char*SR)

{//检查表达式ST中括号是否配对inti;

SeqStackS;//定义一个栈InitStack(

for(i=0;iquelen==QueueSize

知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：(1)判断队满

intFullQueue(CirQueue*Q)

{//判队满,队中元素个数等于空间大小returnQ->quelen==QueueSize;}(2)入队

voidEnQueue(CirQueue*Q,Datatypex){//入队

if(FullQueue(Q))

Error(\队已满，无法入队\Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1Q->quelen++;}(3)出队

DatatypeDeQueue(CirQueue*Q){//出队

if(Q->quelen==0)

Error(\队已空，无元素可出队\inttmpfront;//设一个临时队头指针

tmpfront=(QueueSize+Q->