发布时间 : 星期三 文章数据结构练习 - 第三章 - 栈和队列更新完毕开始阅读
2．（ ）在循环顺序队列中插入新元素不需要判断队列是否满了。× 3．( )入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。T 4．（ ）栈是一种先进后出的线性表。 √ 5．（ ）消除递归不一定需要使用栈。√
6．（ ）栈是实现过程和函数等子程序所必需的结构。√ 7．（ ）设栈采用顺序存贮结构。若已有i-1 个元素进栈，则将第i个元素进栈时，进栈算法的时间复杂性为O(i)。× 8．（ ）在链队列中，即使不设置尾指针也能进行入队操作。√ 9．（ ）设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。√
10．（ ）栈和队列都是线性表，只是在插入和删除时受到了一些限制。√ 11．（ ）队列在程序调用时必不可少，因此递归离不开队列。×
12．( ) 栈可以作为实现程序设计语言过程调用时的一种数据结构√。 13．（ ）栈又称后进先出表，队列又称为先进先出表。√ 14．（ ）栈和队列都是限制存取点的线性结构。√ 四、简答题
1．简述栈和队列的共同点和不同点。它们与线性表有什么关系？ 2．在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的办法采用循环队列。
3．简述栈和队列这两种数据结构的相同点和不同点。
栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除在另一端进行。
4．如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 ABC；CBA；ACB
5．如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。
DCFEBA可以：
push(A),push(B),push(C),push(D),pop(D),pop(C),pust(E)., Push(F),pop(F),pop(E),pop(B),pop(A)
EDBFCA：根据入栈顺序B不能在C前面出栈。 6．什么是循环队列？
用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和
9
队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。 7．有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？ 三个：CDEBA，CDBEA，CDBAE
8．简述递归思想。现有两个正整数M和N，如果采用递归方法解决M×N运算，试结合递归思想，说明其终止条件和递归语句是什么？
递归是程序设计中的重要技术。利用递归技术编写的程序结构清晰、易读、且其正确性容易证明。当问题的定义是递归的、数据结构是递归的和问题的解法是递归的时，最好利用递归。求解递归问题时，要先写出问题求解的递归定义。递归定义由基本项和归纳项组成。基本项描述了一个或几个递归过程的终结状态，即不需要继续递归就可直接求解的状态。归纳项描述了从当前状态向终结状态的转换。递归过程的实质是将复杂问题分解成若干子问题，子问题与原问题具有相同特征，但是简单了。子问题解决了，原问题迎刃而解。
本题求解两个整数M和N相乘，可以利用递归技术变为M个N相加。基本项是M=1,归纳项是(M-1)个N相乘。其递归过程如下： long MultiToAdd(int m,int n) ∥用递归算法求m*n {if(m==1) return (n);
else return (MultiToAdd(m-1,n)+n); }
9．设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。
n个元素的排列有n!种，但借助栈结构，n个入栈元素只可得到1/(n+1)((2n)！/（n!*n!）)种出栈序列，这个数小于n!。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种；有10(4!-14=10)种排列得不到，其中，dabc和adbc是不可能得到的两种。 10．队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
循环单链表若只设头指针，则出队操作时间复杂度是O(1)，而入队操作时间复杂度是O(n)；若只设尾指针，则出队和入队操作时间复杂度都是O(1)。 11．试推导出当总盘数为n的Hanoi塔的移动次数。
设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y) 则 Hn =2Hn-1+1
∥先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z =2（2Hn-2+1）+1 =22 Hn-2+2+1
=22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 · ·
10
·
= 2k Hn-k+2k-1 +2k-2 +?+21 +20
=2n-1 H1+2n-2+2n-3+?+21+20
因为H1=1，所以原式Hn=2n-1+2n-2+?+21+20=2n-1 故总盘数为n的Hanoi塔的移动次数是2n-1。
12． 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。 两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。
用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]； int top[2]； }anode； anode ds;
int push(int I,elemtype x)
∥ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。I的值为0或1
∥x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0
{if（ds.top[1]-ds.top[0]==1）{printf（“栈满\\n”）；return（0）；} switch（i）
{case 0：ds.s[++ds.top[i]]=x；break； case 1：ds.s[--ds.top[i]]=x； return（1）；∥入栈成功 } }
13．用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。
中缀表达式8-(3+5)*(5-6/2)的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略，表达式生成过程为：
中缀表达式exp1转为后缀表达式exp2的规则如下：
设操作符栈s，初始化为空栈，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。
11
（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。 （2）w为左括号（’（’），w入栈。
（3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。 （4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。 14．有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）
XSXXXSSSXXSXXSXXSSSS
15．计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。
步骤 栈S1 栈S2 输入的算术表达式（按字符读入） 初始 ? A-B*C/D+E/F? 1 A ? A-B*C/D+E/F? 2 A ?- -B*C/D+E/F? 3 AB ?- B*C/D+E/F? 4 AB ?-* *C/D+E/F? 5 ABC ?-* C/D+E/F? 6 AT1（注：T1=B*C） ?-/ /D+E/F? 7 AT1D ?-/ D+E/F? 8 AT2（注：T2=T1/D） ?- +E/F? T3 （注：T3=A-T2） ?+ 9 T3E ?+ E/F? 10 T3E ?+/ /F? 11 T3EF ?+/ F? 12 T3T4（注：T4=E/F） ?+ ? T5（注：T5= T3+ T4） ?
16．简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front
12