第三章栈和队列

第三章栈和队列

一．选择题

1．栈与一般线性表的区别在于____________。

A．数据元素的类型不同B．运算是否受限制

C．数据元素的个数不同D．逻辑数据不同

分析：该题目主要考查栈的定义。栈属于特殊的线性表，特殊性在于其删

除和插入操作只能够在栈顶进行，是一种运算受到限制的线性表。答案为Ｂ。

2．一个顺序栈—旦被声明，其占用空间的大小____________。

A．已固定B．可以改变C．不能固定D．动态变化

分析：该题目主要考查顺序栈存储结构的特点。顺序栈用数组实现，因此

一旦顺序栈被声明，则其空间大小固定。答案应选择A。

3．设有—顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6 个元素出

栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是____________。

A．3 B．4 C．5 D．

6

分析：该题目主要考查顺序栈的存储空间定义。当s2 出栈时，则栈的容量为2(s1,s2 在栈中)；当s4 出栈时，则栈的容量为3(s1,s3,s4 在栈中)；

当s6 出栈时，则栈的容量为3(s1,s5,s6 在栈中)；因此栈的最小容量应为3。答案应选择A。

4．从一个栈顶指针为top 的链栈中删除一个结点时，用x 保存被删除的

结点，执行________。

A．x=top->data；top=top->next；B．top=top->next；x=top；

C．x=top->data；D．x=top；top=top->next；

分析：该题目主要考查链栈的具体操作。首先将指针变量x 保存被删除结点，然后调整栈顶指针(top=top->next)。选项 A 中，x=top->data 操作目

的是将栈顶结点的元素值赋给x，故无法满足题目要求。选项B 中，首先进行栈顶指针top 调整，则x 保存的不是当前删除的结点，而是栈调整后的

栈顶元素。因此答案应选择D。

5．在—个栈顶指针为top 的链栈中，将一个s 指针所指的结点入栈，执行____________。

A．top->next＝s：B ．s->next=top->next;

top->next=s;

C．s->next=top; top＝s；D．s->next=top; top=top-

>next;

分析：该题目主要考查链栈的具体操作。根据链栈入栈操作定义，即可得

到答案。答案为C。从选择题4、5 可以看出，链栈的入栈和出栈操作实质上是对没有头结点的单链表进行插入与删除操作。

6．链栈和顺序栈相比，有一个比较明显的优点，即____________。

A．插入操作更加方便B．通常不会出现栈满的情况

C．不会出现栈空的情况D．删除操作更加方便

分析：该题目主要考查链栈和顺序栈的特点。栈的两种存储方式各有特点，即顺序栈所需存储空间较少，但栈的大小受数组的限制；链栈由于每个结

点都包含数据域和指针域，则所需空间相对较大，但栈的大小不受限制(受内存容量的限制)。所以答案为B。对顺序栈而言，其插入操作(入栈)不需要大量地移动元素，故插入操作(入栈)则不是链栈的优点，因此A 选项说法有问题。

7．用单链表表示的链式队列的队头在链表的____________位置。

A．链头B．链尾C．链中D．任意位置

分析：该题目主要考查链式队列的存储结构，如图3.2 所示。队列的队头是对队列元素进行删除的一端，链队列的队头在链表的链头位置。(不考虑不包含数据元素的头结点)，答案为A。

图3.2 链式队列

8．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个____________结构。

A．堆栈B．队列C．数组D．线性表

分析：该题目主要考查队列的性质和应用。缓冲区中的数据应该是先到达的先打印，所以使用具有FIFO 性质的队列来实现。答案为B。

9．做入栈运算时，应先判断栈是否为(1)

，做出栈运算时，应先判

断栈是否为(2)

。当顺序栈中元素为n 个，做入栈运算时发生上溢，

则说明该栈的最大容量为(3)

。为了增加内存空间的利用率和减少发

生上溢的可能性，由两个顺序栈共享一片连续的内存空间时，应将两栈的(4)

分别设在这片内存空间的两端，这样，只有当(5)

时，才产生上

溢。

(1)、(2)A．空B．满C．上溢D．下溢

(3) A．n-l B．n C．n＋1 D．n／2

(4) A．长度B．深度C．栈顶D．栈底

(5) A．两个栈的栈顶同时到达栈空间的中心点

B．其中一个栈的栈顶到达栈空间的中心点

C．两个栈的栈顶在栈空间的某一位置相遇

D．两个栈均不为空,且一个栈的栈顶到达另一个栈的栈底

分析：该题目主要考查栈的性质、结构和操作。答案为：(1)B (2)A (3)B

a1

a2

…….

a

n

∧

front

rear

(4) D (5) C

10 ．若已知一个栈的入栈序列是l,2,3, …,30 ，其输出序列是

p1,p2,p3,…,pn，若p1＝30，则p10 为____________。

A．11 B．20 C．30 D．2l

分析：该题目主要考查栈的性质、结构和操作。已知数据的入栈序列是l，2，3，…，30，出栈序列的第1 个元素是30，因此可以确定，所有元素是

按入栈序列顺序全部入栈之后才开始出栈的。也就是说，出栈序列与入栈

序列刚好相反，可求得出栈序列的第10 个元素为21，即D 答案正确。11．循环队列A[m]存放其元素，用front 和rear 分别表示队头及队尾，则

循环队列满的条件是_________。

A．(Q->rear+1)%m==Q->front B．Q->rear==Q->front+1

C．Q->rear+1==Q->front D．Q->rear==Q->front

分析：该题目主要考查循环队列的存储结构以及队满的判断条件。循环队

列的引入是为了解决队列存在的“假溢出”问题，但在循环队列中会出现

队满和队空的判断条件相同而导致无法判断，通常采用少用一个元素空间

的策略来解决该问题(其它策略讲解请参考配套教材)。使队尾指针Q->rear

无法赶上Q->front，即队尾指针加1 就会从后面赶上队头指针，这种情况

下队满的条件是：(Q->rear+1) %m== Q->front。答案是A。

12．设数组data[m]作为循环队列sq 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为_________。

A．front=front+1 B．front=(front+1)%(m-1)

C．front=(front-1)%m D．front=(front+1)%m

分析：该题目主要考查循环队列的存储结构和出队操作。队列的头指针指

向队首元素的实际位置，因此出队操作后，头指针需向上移动一个元素的

位置。根据第11 题的解答可知，循环队列的容量为m，所以头指针front

加1 以后，需对m 取余，使之自动实现循环，即当front 取到最大下标(m-1 处)以后，自动循环回来取0 值。所以答案是D。

13．由两个栈共享一个向量空间的好处是_________ 。

A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢

发生的机率

C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢

发生的机率

分析：该题目主要考查对顺序栈存储结构的理解。两个栈无论是共享向量

空间还是单独分配空间，对它们的操作所需的时间没有影响。两个栈共享

向量空间，主要是为了节省存储空间，降低上溢的发生机率，因为当一个

栈中的元素较少时，另一个栈可用空间可以超过向量空间的一半。答案应

选择B。

14．若用单链表来表示队列，则应该选用___________。

A．带尾指针的非循环链表B．带尾指针的循环链表

C．带头指针的非循环链表D．带头指针的循环链表

分析：本题主要考查读者对循环单链表存储结构和队列定义的理解。设尾

指针rear，则通过rear 可以访问队尾，通过rear->next 可以访问队头，

因此带尾指针的循环链表较适合。答案应选择B。

二．判断题

1．消除递归不一定需要使用栈，此说法是否正确。

分析：该题目主要考查栈在递归中的应用。对于尾递归可以将其转化成递推，不需栈。所以这种说法是正确的。

尾递归是指一个递归函数的递归调用语句是递归函数的最后一句可执行

语句。

例如下面是一个输出数组元素的递归函数。

void RPrintArray(int list[],int n)

{

if(n>=0)

{

printf(“%d”,list*n+);

RPrintArray(list,--n);

}

}

此程序是尾递归程序，消除尾递归很简单，只需首先计算新的n 值，

n=n-1，然后程序转到函数的开始处执行就行了，可以使用while 语句来实现。

相应非递归函数如下：

void PrintArray(int list[],int n)

{

while (n>=0)

{

printf(“%d”,list*n+);

--n;

}

}

2．栈和队列都是限制存取点的线性结构。

正确

分析：该题目主要考查栈和队列的定义。它们都只能在一端或两端存取数据的线性结构。见选择题第 1 题解答。

3．入栈操作、出栈操作算法的时间复杂性均为O(n)。

错误

分析：该题目主要考查栈的操作算法。入栈与出栈操作都在确定的栈顶位置进行，算法的时间复杂性均为O(1)。所以这种说法是错误的。

4．队列逻辑上是一个下端和上端既能增加又能减少的线性表。

错误

分析：该题目主要考查队列的逻辑结构和操作。队列是上端只能进行入队操作(即增加操作)，下端只能进行出队操作(即减少操作)。

5．用I 代表入栈操作，O 代表出栈操作，栈的初始状态和栈的最终状态都为空，则使用栈的入栈和出栈可能出现的操纵序列为IOIOIOOI。

错误

分析：该题目主要考查栈的操作和“溢出”问题。在栈的操作中，保证出栈前提是栈中有元素，否则会造成栈的下溢，IOIOIOOI 会出现下溢。6．任何一个递归过程都可以转换为非递归过程。

分析：该题目主要考查栈在递归过程非递归化中的应用。任何一个递归过

程都可以按照一定的步骤机械地转换为非递归过程。由于栈的后进先出特

性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。递归

过程转换为非递归过程的实质就是将递归中隐含的栈机制转化为由用户直

接控制的栈，利用堆栈保存参数。

三．填空题

1．已知一个栈ｓ的输入序列为abcd，判断下面两个序列能否通过栈的

Push_Stack 和Pop_Stack 操作输出：

(1)dbca (1)

(2)cbda (2)

答案：(1)不能(2)能

分析：该题目主要考查栈的操作。(1)不能，因为弹出 d 时，abc 均已依次

压入栈，下一个弹出的元素只能是 c 而不是b。(2)能，Push_Stack (s,a)，Push_Stack (s,b)，Push_Stack (s,c)，Pop_Stack (s)，Pop_Stack (s)，

Push_Stack (s,d), Pop_Stack (s), Pop_Stack (s)。

2．对循环队列Q(设循环队列空间大小为MAXSIZE)，如何修改队头指针? (1)

；

如何修改队尾指针? (2)

答案：(1)front=(front+1)% MAXSIZE (2)rear=(rear+1)% MAXSIZE

分析：该题目主要考查循环队列的操作。具体解答请参见选择题第11 和12 题。

3．设长度为n 的链队列用单循环链表表示，若只设头指针，则入队列出队

列操作的时间分别为(1)

和(2)

；若只设尾指针，则入队列出队列

操作的时间分别为(3)

和(4)

。

答案：(1)O(n) (2)O(n) (3)O(1) (4)O(1)

分析：该题目主要考查链队列和单循环链表的综合知识。当只设头指针时(如图3.3(a)所示)，入队相当于在an 结点之后执行结点插入操作，根据链

表的插入操作特点可知，插入操作前必须知道结点a1 和an 的地址，获取结点an 的地址的时间复杂度为O(n)；出队则相当于删除结点a1 的操作，因此必须获取结点an 的地址，同样其时间复杂度为O(n)。若设置尾指针(如图3.3(b)，入队相当于在结点a1 之前和an 之后执行结点插入操作，通过rear 和rear->next 可以获得结点an 和a1 的地址，则其时间复杂度为O(1)；出队则相当于删除结点a1 的操作，同样其时间复杂度为O(1)。

(a)

(b)

图3.3 单循环链表表示的链队列示意图

4．对于循环向量中的循环队列，写出求队列中元素个数的公式

___________。

答案：(rear-front＋MAXSIZE)% MAXSIZE，其中MAXSIZE 表示队列的存

储空间。

分析：该题目主要考查循环队列的存储结构特点。

5．向顺序栈插入新元素分为三步：第一步，进行(1)

判断，判断条件

是(2)

；第二步是修改(3)

；第三步把新元素赋给(4)

。同样从

顺序堆栈删除元素分为三步；第一步，进行(5)

判断，判断条件是

(6)

；第二步是把(7)

值返回；第三步(8)

。

答案：(1)栈是否满(2)s->top= MAXSIZE -1(3)栈顶指针(top++)(4)栈

顶对应的数组元素(5)栈是否空(6)s—>top=-1(7)栈顶元素(8)修改栈顶指

针(top--)

分析：该题目是考虑栈的运算规则及其入出栈的实现步骤。入栈时一般考虑判断栈满否，条件是是否超出最大空间。如果没有超出应该修改栈顶指针，然后将元素压入堆栈。出栈时，应首先考虑堆栈是否空。如果不空，先保留栈顶元素，然后修改栈顶指针。

6．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈。对于前者，进入栈的元素为表达式中的(1)

，而对于后者，进

入栈的元素为(2)

。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式

a1

a2

…….

a

n

head

a1

a2

…….

a

n

rear

是(3)

。

答案：(1)运算符(2)操作数(3)ab+c/fde/--

分析：该题目主要考查栈的应用。中缀表达式就是将运算符写于参与运算的操作数的中间，操作数依原序排列。后缀表达式就是将运算符列于参与

运算的操作数之后，操作数的排列依原序。因此计算后缀表达式值的过程

为：从左向右扫描后缀表达式，遇到操作数就进栈，遇到运算符就从栈中

弹出两个操作数，执行该运算符所规定的运算，并将所得结果进栈。如此

下去，直到表达式结束。所以对于计算后缀表达式，进栈的元素为操作数。

7．假设以S 和X 分别表示入栈和出栈操作，则对输入序列a，b，e，d，e

进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为_______。

答案：bceda

分析：该题目主要考查入栈和出栈操作。入栈和出栈操作只能在栈顶位置

进行。根据操作序列，首先a，b 进栈，然后 b 出栈；接着c 进栈、c 出栈；

d、e 相继进栈，栈顶元素为e，最后

e、d、a 相继出栈。这样，得到出栈

序列为bceda。

四．应用题

1．将整数1、2、3、4 依次入栈或出栈，请回答下述问题：

(1)当入、出栈次序为Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，

2)、Push_Stack(S，x3)、Pop_Stack(S)、Push_Stack(S，4)、Pop_Stack(S)，

出栈的数字序列为何？

(2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。

(3)设有n 个数据元素的序列顺序进栈，试给出可能输出序列的个数和不可

能输出序列的个数。当n=4(1、2、3、4)有24 种排列，哪些序列是可以通

过相应的入出栈操作得到的。

分析与解答：该题目主要考查栈的性质、结构和操作。

(1) 出栈序列为l、3、4。

(2) 序列1、4、2、3 不可能得到。因为4 和2 之间隔了3，当4 出栈

后，栈顶元素是3，而2 在3 的下面。序列1、4、3、2 可以得到：Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，3)、Push_Stack(S，

4)、Pop_Stack(S)、Pop_Stack(S)、Pop_Stack(S)。

(3) 设有n 个数据元素的序列(假设这个序列为1，2，3，4，5……n)

顺序进栈，那么输出序列个数f(n)可以递推求出：为讨论方便, 设n=0,

f(0)=1，当，

n=1：显然f(1)=1

n=2：容易得知f(2)=2

n=3：1 最后出栈的序列有f(2)种，2 最后出栈的序列有f(1)* f(1)种，

3 最后出栈的序列有f(2)种，所以f(3)=2* f(2)+f(1)*f(1)=5

n=4：1 最后出栈的序列有f(3)种，2 最后出栈的序列有f(1)* f(2)

种，3 最后出栈的序列有f(2)*f(1)种，4 最后出栈的序列有f(3)种，所以

f(4)=

2*f(3)+ f(1)* f(2)+ f(2)* f(1)=14

可以看出i(i=1,2,3,……n)最后出栈的序列有f(i-1)*f(n-i)

所以f(n)=f(0)*f(n-1)+ f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+……+

f(n-1)*f(0)，用数学方法可得到

f(n)=

! n 2n ! n ! 2n

1 n 1 C 1 n 1 C 2n

n n

对有n 个数据元素的序列，全部可能的排列个数为：Pn=n!

所以，不可能输出序列的个数为：Pn-Cn。

因此4 个元素的出栈序列数为：

14

!

4

!

4

8

1

4

1 C 4 ！

这14 种出栈序列如下：

1234 1243 1324 1342 1432

2134 2143 2314 2341 2431

3214 3241 3421 4321

2 n n! ! 2n

1 n 1 C

2．试说明下述运算的结果

(1) Pop_Stack(Push_Stack(S，A))；

(2) Push_Stack(S，Pop_Stack(S))；

(3) Push_Stack(S，Pop_Stack(Push_Stack(S，B)))

分析与解答：该题目主要考查栈的操作。

(1) 首先要实现运算Push_Stack(S，A)，其结果是将元素A 压入栈S

中。若栈S 满，则出现上溢现象的处理；否则把元素 A 压入栈顶，且元素个数加1。然后作Pop_Stack(S)运算，将栈顶元素弹出，且元素个数减1。

(2) 首先作Pop_Stack(S)运算。若栈A 为空，则作下溢处理；否则弹

出栈顶元素。然后再进行压入运算，将刚才弹出的元素压入栈S 中。(3) 这种复合运算复杂一些，在(1)、(2)的基础上可知，这种运算的

结果使栈S 增加了一个栈顶元素B。

3．何谓队列的上溢现象，一般有几种解决方法，试简述之。

分析与解答：该题目主要考查队列的存储结构。

在队列的顺序存储结构中，设队列指针为front，队尾指针为rear，

队列的容量(即存储的空间大小)为MAXSIZE。当有元素要加入队列(即入队) 时，若rear==MAXSIZE-1，则队列已满，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却

不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以

用循环队列解决。

一般地，要解决队列的上溢现象可有以下几种方法：

(1) 可建立一个足够大的存储空间以避免溢出，但这样做往往会造

成空间使用率低，浪费存储空间，一般不采用这种方法。

(2) 采用移动元素的方法，每当有一个新元素入队，就将队列中已

有的元素向对头移动一个位置，假定空余空间足够。每当删去一个队头元素，则可依次移动队列中的元素总是使front 指针指向队列中的第一个位置。

(3) 采用循环队列方式。将队头、队尾看作是一个首尾相接的循环

队列，利用一维数组顺序存储并用取模运算实现。

4．设栈S={1,2,3,4,5,6,7},其中7 为栈顶元素。请写出调用algo(&S)后

栈S 的状态。

void algo(PseqStack S)

{ int x;

PseqQueue Q；PseqStack T；

Q=Init_SeqQueue( )；T=Init_SeqStack( )；

while(!Empty_SeqStack(S))

{ Pop_ SeqStack(S,&x);

if (x/2!=0) Push_SeqStack(T，x)；

else En_SeqQueue(Q，x)；

}

while(!Empty_SeqQueue(Q))

{ Out_ SeqQueue(Q,&x);

Push_SeqStack(S，x)；

}

while(!Empty_SeqStack(T))

{ Pop_ SeqStack(T,&x);

Push_SeqStack(S，x)；

}

}

分析与解答：本函数的功能是将顺序栈S 中递增有序的整数中的所有偶数调整到所有奇数之前，并且要求偶数按递减序排列，奇数按递增序排列。算法首先设置并初始化中间栈T 和中间队列Q，然后将S 栈中的整数出栈，若整数为奇数，入栈T,若为偶数，入队列Q。这样S=Φ,T={7,5,3,1},

其中1 为栈顶元素,Q={6,4,2},其中6 为队头元素。然后，将Q 中整数出队列并入栈S, 这样S={6,4,2},其中2 为栈顶元素,再将T 中元素出栈，并入栈S, 这样S={6,4,2,1,3,5,7},其中7 为栈顶元素。

最后S 栈的状态如图3.4 所示。

1 2 3 4 5 6 7 8 9

10

6 4 2 1 3 5 7

图3.4 调用algo(&S)后栈S 的状态

5．假设两个队列共享一个循环向量空间(如图3.5 所示)，其类型Queue2 定义如下：

…

…

front[1]

rear[1]

rear[0]

front[0]

top

typedef struct{

DateType data[MAXSIZE];

int front[2],rear[2];

} Queue2;

图3.5 双循环队列示意图

对于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[ (1)

]) return 0;

Q->data[ (2)

]=x;

Q->rear[i]=( (3)

);

return 1;

}

分析与解答：入队操作需先判队满。队列是否满，要看一个队列的队尾元

素位置与另一个队列的队首元素位置之间是否还有空间。我们规定，队首

指针总是指向队首元素的实际位置，队尾指针总是指向队尾元素的后一个

位置。

因此，0 号队列队满的判断条件是rear[0]==front[1]。同样，1 号队列

队满的判断条件是rear[1]==front[0]。

这样一来，就要判断传递进来的i 是0 还是1。但程序中没有提供判断i

的语句。因此可以将上述队满的判断条件统一成下列关系式：

rear[i]==front[(i+1)%2]。在上式中，当i=0 时，(i+1)%2 为1，当i=1

时，(i+1)%2 为0。

上述程序，第1 个空是判队列i 是否满；第2 个空是将x 插入到队列i

的当前队尾，即在rear[i]的位置上插入；第3 个空是修改队列i 的尾指针，因为是循环队列，所以要对向量的容量MAXSIZE 取模。

本题答案是：(1) (i+1)%2 (或1-i)

(2) Q->rear[i]

(3) (Q->rear[i]+1)% MAXSIZE

五．算法设计题

1．已知Q 是一个非空队列，S 是一个空栈。仅用队列和栈的基本操作和少

量工作变量，编写一个算法，将队列Q 中的所有元素逆置。

分析：该题目主要考查队列和栈的应用。将队列逆置的步骤为：

(1)顺序取出队列中的元素，将其入栈；

(2)所有元素入栈后，再从栈中逐个取出，入队列。

算法描述如下：

Reverse_queue(PseqQueue q)

{ DataType x ;

PSeqStack S ;

S=Init_SeqStack( );

while(! Empty_SeqQueue(q)) /*若队列非空，则将队列中的元素入

栈*/

{ Out_SeqQueue(q,&x);

Push_SeqStack(S, x);

}

while(!Empty_SeqStack(S)) /*若栈非空，则将栈中元素入队*/

{ Pop_SeqStack(S,&x);

In_SeqQueue(q，x);

}

}

2．试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形

如“序列1&序列2”模式的字符序列。其中序列1 和序列2 中都不含字符

‘&’，且序列 2 是序列1 的逆序列。例如，“a+b&b+a”是属该模式的字符序列，而“1+3&3-1”则不是。

分析：本题主要利用栈的工作原理，对于给定的字符串在读到字符‘&’前

入栈，在逐个读‘&’之后的字符并和栈顶字符比较，若相等，则出栈，否

则序列2 不是序列 1 的逆序列。

算法描述如下：

int IsReverse( ) /*判断输入的字符串中'&'前和'&'后部分是否为逆串,

是则返回1,否则返回0*/

{ PSeqStack S;

char e,ch;

S=Init_SeqStack( );

while ((e =getchar())!='&') /*将输入的字符串中‘&’的前半部分

入栈*/

Push_SeqStack (S,e)；;

while ((e=getchar())!='@') /*遇到字符’@’循环结束，否则进行比

较*/

{

if (Empty_SeqStack(S)) return 0;

Pop_ SeqStack(S, &ch);

if (e!=ch) return 0;

}

if (!Empty_SeqStack(S)) return 0;

return 1;

}

3．请利用两个栈s1 和s2 来模拟一个队列。用栈的运算来实现该队列的三

个运算：inqueue，插入一个元素入队列；outqueue，删除一个元素出队列；queue_empty，判断队列为空。

分析：由于队列是先进先出，而栈是后进先出；所以只有经过两栈，即在

第一个栈里先进后出，再经过第二个栈后进先出来实现队列的先进先出。

因此，用两个栈模拟一个队列运算就是用一个栈作为输入(输入栈)，而另

一个栈作为输出(输出栈)。当入队列时，总是将数据进入到输入栈中。在

输出时，如果输出栈已空，则将输入栈的所有数据压入输出栈中，然后由

输出栈输出数据；如果输出栈不空，就从输出栈输出数据。显然，只有在

输入、输出栈均空时队列才为空。

一个栈s1 作为输入栈，用来插入数据，另一个栈s2 作为输出栈，用来

删除数据，删除数据时应将前一栈s1 中的所有数据读出，然后进入到第二个栈s2 中。s1 和s2 大小相同。

算法描述如下：

void inqueue(SeqStack s1,int x) /*插入一个数据入队列*/

{

if(s1->top==n) /*输入栈s1 已满*/

if(Empty_SeqStack(s2)) /*若输出栈s2 为空，则将s1 中的所有

数据退栈后压入s2*/

while(!Empty_SeqStack(s2))

{

Pop_SeqStack(s1, &x) ;

Push_SeqStack(s2, x);

}

else /*若输出栈s2 不为空，不能利用这里面的空间

存储数据，队列满*/

printf(“队列满”);

else /*输入栈s1 不满，直接入栈*/

Push_SeqStack(s1,x);

}

void outqueue(SeqStack s1,SeqStack s2,int x) /*删除一个数据

出队列*/

{ if (Empty_SeqStack(s1) && Empty_SeqStack(s2)) /*队列

空*/

printf(“队列空”);

else

{

if (Empty_SeqStack(s2)) /*s2 空*/

while(!Empty_SeqStack(s1)) /*将s1 的所有元素退栈

后压入s2*/

{

Pop_SeqStack(s1, &x) ;

Push_SeqStack(s2,x);

}

Pop_SeqStack(s2,&x); /*弹出栈s2 的栈顶元素(队首元

素)并赋给x*/

}

}

int queue_empty(SeqStack s1, SeqStack s2) /*判断队列为空*/

{

if (Empty_SeqStack(s1) && Empty_SeqStack(s2))

return 1; /*队列为空*/

else

return 0; /*队列不为空*/

}

4. 用递归方法编程求n 个元素的集合的幂集。n 为整数，集合包含的元素为不大于n 的正整数。

分析：考查集合Sx(x=0，…，n-1，n)，和其幂集P(Sx)，可以分析出它们

之间的关系如下。

S0=Φ，P(S0)={Φ}；

S1={1}，P(S1)={Φ,{1}}；

S2={1，2}，P(S2)={Φ,{1},{2},{1,2}}；

S3={1，2，3}，

P(S3)=,Φ,,1-,,2-,,3-,,1,2-,,2,3-,,1,3-,,1,2,3--=,Φ,,1-,,2-,,1,2

},{3},{1,3},{2,3},{1,2,3}}= P(S2)∪{x|x={3}∪y,y∈P(S2)}；

……

Sn={1，2，3，…，n-1，n}，

P(Sn)=P(Sn-1)∪{x|x={n}∪y,y∈P(Sn-1)}

用n 代表Sn，可以得到递归关系式。

P(0)=,Φ-

P(n)=P(n-1)∪{x|x={n}∪y,y∈P(n-1)}

可以用链表存储幂集，由于幂集的每个元素也是一个集合，所以幂集的

元素也用链表存储，例如P(3)可表示为如图3.6 所示的链表P。该链表有8 个结点，保存幂集的8 个元素，每个结点有两个指针域，SLink 和next，

其中SLink 指向“元素值”, SLink 为空指针时表示元素为空集Φ。由于幂

集的元素也是一个集合，也用链表表示，这个链表称为元素链表，该链表

每个结点有两个域，data 和next。

P

∧

∧

1

∧

2

∧

3

∧

2 3 3 3

图3.6

元素链表的结点定义：

typedef struct node{

int data;

struct node *next;

}Snode;

幂集链表的结点定义：

typedef struct Pnode{

Snode *SLink; /*指向元素链表*/

struct Pnode *Link; 1

∧

2

∧

1

∧

2 1

∧

}PNode;

算法如下：

PNode *Create_P(int n)

{

PNode *T,*P,*Pre,*Thead；

Snode *S；

if(n==0)

{ /*此时幂集只有一个元素,即空集Φ*/

T=(PNode *)malloc(sizeof (PNode));

T->SLink=NULL;

T->Link=NULL;

return T;

}

else

{

T=Create_P(n-1); /* 生成P(n-1)幂集链表*/

P=Copy(T); /* 该函数作用为复制T,得到T 的副本P*/ Thead=T;

while(T) /*扫描P(n-1)幂集链表T,在每个元素中加

入n */

{

Shead=T->SLink; /*得到元素链表头部地址*/

/*生成新元素n,并插入在元素链表的头部*/

S =(Snode *)malloc(sizeof(Snode));

S->data=n;

S->next= Shead;

T->SLink=S;

Pre=T; /*Pre 为T 的前驱*/

T=T->Link; /*扫描到幂集的下一元素*/

}

Pre->Link=P; /*将P(n-1)幂集链表P和增加n元素的链表T,链接, 获得P(n)幂集链表*/

return(Thead);

}

}

PNode *Copy(PNode *T) /*在内存中复制与T 相同的链表*/ { PNode *P,*Q1,*Q2;

if (T==NULL)

return NULL;

Q1=Copy(T->Link); /*复制T->Link*/

Q2=Copy(T->SLink); /*复制T->SLink */

P=(PNode *)malloc(sizeof(PNode));

P->Link=Q1;

P->Slink=Q2;

return P;

}

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

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) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) { x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); } (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) { i=Pop(&T); Push(S,i);

第三章栈和队列习题_数据结构电子教案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. 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. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数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 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

第三章栈和队列练习题

第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data;

PTA第三章栈与队列练习题

1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组

数据结构练习 第三章 栈和队列

数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。

第3章-栈与队列习题参考答案

习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶

第三章+栈和队列(参考答案)

第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。

PTA第三章栈和队列练习题教学提纲

1-1 通过对堆栈S 操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 (2分) T F 作者: DS 课程组 单位: 浙江大学 1-2 在用数组表示的循环队列中，front 值一定小于等于rear 值。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分) T F 作者: DS 课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. (1分) T F 2-1 设栈S 和队列Q 的初始状态均为空，元素a 、b 、c 、d 、e 、f 、g 依次进入栈S 。若每个元素出栈后立即进入队列Q ，且7个元素出队的顺序是b 、d 、c 、f 、e 、a 、g ，则栈S 的容量至少是： (2分)

栈和队列练习题答案

第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;

第三章栈与队列 练习题

第三章栈与队列练习题 一、选择题 1、栈结构通常采用的两种存储结构是（ A ）。 A、顺序存储结构和链表存储结构 B、散列和索引 C、链表存储结构和数组 D、线性链表和非线性存储 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（B） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（） A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（C） A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、 x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next; 7、一个队列的入列序列是1，2，3，4，则队列的输出序列是（B ）//尾插入元素，头删除元素。 A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（C）//不懂啊！！！ A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 11、用单链表表示的链式队列的队头在链表的（A）位置 A、链头 B、链尾 C、链中 12、判定一个链队列Q（最多元素为n个）为空的条件是（ A） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 14、在一个链队列Q中，删除一个结点需要执行的指令是（C） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、 Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（D） A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是（C） A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（B） A、2 B、 3 C、 5 D、 6 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（A） 0 maxsize-1

数据结构第3章栈与队列习题

第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,p n，若p1=3,则p2的值。 A．一定是2 B．一定是1

C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p n=1,则p i(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base B．S.top!= S.base C．S.top!= S.base+S.stacksize D．S.top= = S.base+S.stacksize 13．判定一个顺序栈S为栈满的条件是。 A．S.top-S.base= =S.stacksize B．S.top= = S.base C．S.top-S.base!=S.stacksize D．S.top!= S.base 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 B．只有表尾指针没有表头指针的循环双链表 C．只有表尾指针没有表头指针的循环单链表 D．只有表头指针没有表尾指针的循环单链表 16．如果以链表作为栈的存储结构，则退链栈操作时。 A．必须判别链栈是否满B．判别链栈元素的类型 C．必须判别链栈是否空D．对链栈不作任何判别

第三章 栈与队列 习题及答案(优选.)

第三章栈与队列习题及答案 一、基础知识题 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的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) { x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }

第3章_栈和队列_习题参考答案

第四第3章栈和队列 一、基础知识题 3.1 有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251，34521 3.2 铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 3.3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 【解答】2和 4 3.4 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？ 【解答】4 3.5 循环队列的优点是什么，如何判断“空”和“满”。 【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满，即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队中元素个数来区分队列的“空”和“满”的。 3.6 设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时间如何？若只设尾指针呢？ 【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。 3.7 指出下面程序段的功能是什么？ (1) void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i

数据结构练习题 第三章 栈、队列和数组 习题及答案备课讲稿

数据结构练习题第三章栈、队列和数组 习题及答案

第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性 表。在栈顶进行插入运算，被称为________或________，在栈顶进行删 除运算，被称为________或________。 2.栈的基本运算至少应包括________、________、________、________、 ________五种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生 “________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生 “________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________ 实现。 6.top=0表示________，此时作退栈运算，则产生“________”； top=sqstack_maxsize-1表示________，此时作进栈运算，则产生 “________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以 填充。

int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填 充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予 以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0); else{*x=________________; return(1);} }