一、基本题
1．填空：线性表、栈和队列都是_____结构，可以在线性表的_____位置插入和删除元素，对于栈只能在_______位置插入和删除元素，对于队只能在______位置插入和______位置删除元素。
2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？
3．设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。
4．试证明：若借助栈由输入序列1，2，… ，n得到输出序列为p1p2…pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 二、设计算法题 1． 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是 回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。 2． 设以数组se[m]存放循环队列的元素，同时设变量rear 和front分别作为队头队尾指针， 且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。 3． 假设以数组se[m]存放循环队列的元素，同时设变量rear 和num分别作为队尾指针和队 中元素个数记录，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法。 4． 假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点（注 意不设头指针），试写出相应的置空队、入队、出队的算法。 5． 设计一个算法判别一个算术表达式的圆括号是否正确配对。 6． 写一个算法，借助于栈将一个单链表置逆。 7．两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示栈号。 3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ (2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。 解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 3.2 简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。 3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() { Stack S; char x,y; InitStack(S); 1 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);} 解：stack 3.4 简述以下算法的功能（栈的元素类型SElemType为int）。 (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);}} 解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e，将其从栈中清除 3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。 解：任何前n个序列中S的个数一定大于X的个数。 设两个合法序列为： T1=S??X??S?? T2=S??X??X?? 假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。 第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为??ba??，而T2的输出顺序为??ab??，说明两个不同的合法栈操作序列的输出元素的序列一定不同。 3.6 试证明：若借助栈由输入序列12…n得到的输出序列为p1p2?pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若pj 2 则可以理解为通过输入序列pjpkpi可以得到输出序列pipjpk，显然通过序列123是无法得到312的，参见3.1题。所以不可能存在着i 3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A-B×C/D+E↑F 解：BC=G G/D=H A-H=I E^F=J I+J=K 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # A-B*C/D+E^F# PUSH(OPND,A) 2 # A -B*C/D+E^F# PUSH(OPTR,-) 3 #- A B*C/D+E^F# PUSH(OPND,B) 4 #- A B *C/D+E^F# PUSH(OPTR,*) 5 #-* A B C/D+E^F# PUSH(OPND,C) 6 #-* A B C /D+E^F# Operate(B,*,C) 7 #- A G /D+E^F# PUSH(OPTR,/) 8 #-/ A G D+E^F# PUSH(OPND,D) 9 #-/ A G D +E^F# Operate(G,/,D) 10 #- A H +E^F# Operate(A,-,H) 11 # I +E^F# PUSH(OPTR,+) 12 #+ I E^F# PUSH(OPND,E) 13 #+ I E ^F# PUSH(OPTR,^) 14 #+^ I E F# PUSH(OPND,F) 15 #+^ I E F # Operate(E,^,F) 16 #+ I J # Operate(I,+,J) 17 # K # RETURN 3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。 解：2n?1 3.9 试将下列递推过程改写为递归过程。 void ditui(int n) { int i; i = n; while(i>1) cout< 解： void ditui(int j) { if(j>1){ cout< 3.10 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x; 3 cin>>x; if(x==0) sum=0; else { test(sum); sum+=x;} cout< void test(int &sum) { Stack s; InitStack(s); int x; do{ cin>>x; Push(s,x); }while(x>0); while(!StackEmpty(s)){ Pop(s,x); sum+=x; cout< 3.11 简述队列和堆栈这两种数据类型的相同点和差异处。 解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。 队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。 （2） 取顺序栈的栈顶元素 Status GetTop ( SqStack S, SElemType &e ) { // 如果栈 S 空，返回 ERROR；如果栈 S 不空，用 e 返回栈 S 的栈顶元素，并返回 OK 。 if ( S.top = = S.base ) return ERROR; // 如果栈 S 为空，则返回 ERROR e = *( S.top - 1); // 将栈顶指针减 1 后所指向的单元内的值赋给 e return OK; } // GetTop （3）将元素压入顺序栈算法（进栈） Status Push ( SqStack &S, SElemType e ) { // 将元素 e 插入到栈 S 中，成为新的栈顶元素 if ( S.top - S.base > S.stacksize ) { // 如果栈满，则追加存储空间 S.base = ( SElemType * ) realloc ( S.base, ( S.stacksixe + STACKINCREMENT* sizeof ( SElemType ) ); if ( ! S.base ) exit ( OVERFLOW ); // 追加存储空间失败 S.top = S.base + S.stacksize; // 修改栈顶指针 S.stacksize += STACKINCREMENT; // 修改当前栈的存储空间 } // if 结束 *S.top ++= e; // 先将 e 送入栈顶，然后将栈顶指针加 1 return OK; 4 } // Push （4）将元素弹出顺序栈算法（退栈） Status Pop ( SqStack &S, SElemType &e ) { // 如果栈 S 空，返回 ERROR ；如果栈 S 不空，删除 S 栈顶元素，用 e 返回其值，并返回 OK 。 if ( S.top = = S.base ) return ERROR; // 如果栈 S 为空，则返回 ERROR e = *--S.top; // 先令 top 减 1，再将 top 所指单元值赋给 e return OK; } // Pop （5） 判栈空否 Int Empty ( SqStack S) { // 如果栈 S 空，返回 1 ；如果栈 S 不空，返回 0 。 if ( S.top = = S.base ) return 1; // 如果栈 S 为空，则返回 1 else return 0; // 如果栈 S 为空，则返回 0 } // Empty end 4.链栈 （1）链栈结构及数据类型 栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图3-4。 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; while (栈不空) {若当前位置可通， 则{ 将当前位置插入栈顶； // 纳入路径 若该位置是出口位置，则算法结束； // 此时栈中存放的是一条从入口位置到出口位置的路径 否则切换当前位置的北邻方块为新的当前位置； } 否则 5