第三章栈和队列：习题
习
题
一、选择题
1．栈和队列都是( )。
A.顺序存储的线性结构 B.限制存取点的线性结构 C．链接存储的线性结构 D.限制存取点的非线性结构
2．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。 A. edcba B. decba C. dceab D. abcde
3．若已知一个栈的入栈序列是l，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p
1=n，则Pi为 ( )。
A.i B. n-i C. n-i+l D.不确定
4．循环队列SQ采用数组空间SQ.data[0，n-l]存放其元素值，已知其头尾指标分别是front
和rear，则当前队列中的元素个数是( )。 A. (rear-front+n)%n B. rear-front+l C. rear-front-l D. rear-front
5．中缀表达式A-(B+C/D)*E的后缀形式是( )。 A. AB-C+D／E* B. ABC+D／E* C. ABCD／E*+- D. ABCD／+E*-
6．一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。 A.4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1
7．若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从
队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。 A.1和5 B.2和4 C.4和2 D.5和l
8．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，
则在进行出队运算时( )。
A.仅修改队头指针 B.仅修改队尾指针
C.对头、队尾指针都要修改 D.对头、对尾指针都可能要修改
9．若进栈序列为a，b，c，则通过入出栈运算可能得到的a，b，c的不同排列个数为( )。 A.4 B.5 C.6 D.7
10.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针， 则执行出队运算后其头指针front值为( )。 A. front=front+l B. front=(front+l) %(m-l) C.front=(front-1)%m D. front=(front+l)%m
11.在一个链队中，假定front和rear分别为队首指标和队尾指标，则删除一个结点的运 算应执行( )。
A. front front->next； B.rear=rear->next; C.rear=front->next; D. front=rear->next;
12.向一个栈顶指标为hs的链栈中插入结点*s时，应执行( )。 A.hs->next=s； B. s->next=hs; hs=s;
C.s->next=hs->next; hs->next=s; D. s->next=hs; hs=hs->next:
13.在具有n个单元的顺序循环队列中，假定front和rear分别为队首指针和队尾指针， 顺序表的下标下界从0开始，则判断队满的条件是( )。 A.(l+rear)% n=front B.(l+rear)% (n-l)=front C.l+rear%n=front D.(l+front)%n=rear
14.若已知一个栈的入栈序列是l，2，3，?，30，其输出序列是pl,p2，p3，?，pn，若p
1=30，则pl0为( )。
A. 11 B. 20 C. 30 D. 21 二、填空题
1．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队运算的时间复杂度分别为____和____；若只设尾指针，则入队和出队运算的时间复杂度分别为和 一。 2．基本线性表，栈和队列都是____ 结构。可以在基本线性表的____插入和删除元素；对于栈只能在____ 插入和删除元素；对于队列只能在____插入元素和删除元素。
3．一个栈的输入序列是235614，则栈的输出序列54321是____。（可能或不可能） 4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R表示，出队时，队首指针循环加l可表示F=____。
5．因为顺序栈的空间是有限的。因此，在进行插入运算时，可能会发生____。
6．假设以s和x分别表示进栈和退栈运算，则对输入序列a，b，c，d，e进行一系列栈运算ssxsxssxxx之后，得到的输出序列为____。 7．栈顶的位置是随着____ 运算而变化的。 8．有如下递归函数： int dunno (int m) { int value； if(m==0) value=3;
else value=dunno (m-l) +5; return (value)； }
执行语句printf(”%d\\n'’，dunno(3))；的结果是_________。
9．设a是含有N个分量的整数数组，写出求n个整数之和的递归定义________，写出求n个整数之积的递归定义____。
10.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b，d，c，f, e，a，则栈S的容量至少应该是________。 三、简答题
1．什么是队列的“假溢出”现象？一般有哪几种处理方法？
2．试证明：若借助栈由输入序列1，2，3，?，n，得到输出序列P1，P2，P3，?，Pn（它是输入序列 的一个排列），则输出序列中不可能出现这样的情况：若i 3．顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray[O...n-l]，队列头指针为front，队列尾指针为rear，则listarray[rear]表示下一个可以插入队列的位置。请解释其原因。 4．试推导求解n阶Hanoi塔问题至少需执行的move运算的次数。 四、算法设计题 1．利用两个栈S1和S2模拟一个队列时，要求实现该队列的进队、出队、判队空3种运算。 2．假设如题图3-1所示，火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的运算（入栈或出栈运算）序列，以使所有的软席车厢都被调整到硬席车厢之前。 3．求两个正整数m和n的最大公约数可以用如下gcd (m，n)公式表示： (1)编写一个计算gcd(m，n)的递归过程。 (2)将上述过程转化成非递归过程。 (3)画出计算gcd (20，6)的过程及栈的状态变化，给出计算结果。 4．如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或l来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。 5．用单链表实现队列，如题图3-2所示，并令front reaFNULL表示队列为空，编写实现队列的如下5种运算的函数： SetNull:将队列置成空队列。 GetFirst:返回队列的第一个元素。 EnQueue：把元素插入队列的后端。 DeQueue：删除队列的第一个元素。 Empty：判定队列是否为空。 6．若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入( EnQueue)和删除(DeQueue)算法，并给出p为何值时队列空。 7．编写程序将一个循环队列的内容倒置，该循环队列存储在一个数组A[1...N-1]中，例如，题图3-3 (a)中为倒置前的队列，题图3-3 (b)中为倒置后的队列。 8．已知Ackermann函数的定义如下： 写出计算Ack(m，n)的非递归算法 第三章 栈和队列 第3章栈和队列 一、选择题 1.B 2.C 3.C 4.A 5.D 6.B 7.A 8.D 9.B 10.B 11.A 12.B 13.A 14.D 二、填空题 1．O(n)，O(1)，O(1)，O(n)。 2．线性任何栈顶队尾队首。 3．不可能。 4．F=(1+F)%M。 5．上溢。 6．Bceda。 7．进栈或出栈。 8. 18。 9． 10.3 三、简答题 1．假设顺序队列的头指针为front，尾指针为rear，队列的容量为MaxSize，下标下界为0，则最后一个单元的下标为MaxSize-1。 (1)“假溢出”是指rear=MaxSize-l，而front≠0的现象。 (2)处理“假溢出”的方法通常有下列3种： 1)每当从队首删除一个元素时，将队列中剩余的全部元素均向队首方向移动一个位置。 2)当发生假溢出时，将队列中现有的全部元素均向低下标方向移动一个位置。 3)上述两种方法都要进行大量元素的移动，效率低。最巧妙的方法是采用循环队列方式。循环队列是通过头、尾指针的循环来实现的。入队时，修改尾指针：rear=(l+rear)%MaxSize;出队时，修改队首指针：front=(l+front)%MaxSize。 2．要想得到PkPiPj，则必须先按i，j．k顺序全部进栈以后，再进行出栈操作。显然，第1个出栈的是最后进栈的Pk，而Pk出栈之后，栈顶元素是Pj，因此第2个出栈的应该是Pj。最后出栈的才是Pi，即出栈序列应该为PkPjPi，而不是PkPiPj。 3．-般环状队列头或尾其中之一要进行特殊处理，否则，当队列“空”或“满”时，只凭q.rear= =q.front无法判断。一般的处理方法是将q.rear指向下一个要插入的位置。这样，虽牺牲了一个单元的存储空间，但可以很容易地区分队列“空”或“满”。当q.rear==q.front时，表示队列“满”，当q.rear==(q.front+l)%n时，表示队列“空”。 4．设至少要执行M (n)次move操作，则 求解此方程，得M(n)=2一l。 也可以递推得到，并由“数学归纳法”证明。 四、算法设计题 1．【分析与解答】 用一个栈SI作为输入栈，另一个栈S2作为输出栈。进行入队操作时，总是将数据加入到S1中;进行出队操作时，如果S2不空，则输出S2的元素;如果S2为空，则读取Sl的全部元素加入到S2中，然后由S2输出。当SI和S2均为空时，表示队列为空。假设栈的类型为STACK。 (1)进队。 void EnQueue (STACK *S, ElemType x) { if (SI->top==MaxSize-l) printf(¨overflow”); else Push (Sl，x); //以进栈代替进队 } n