3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：
(1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？
(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。
可分为五种情况：
（1）：1、2、3进，再3、2、1出，即321；
（2）：1进，1出；2进，2出；3进、3出，即123；
（3）：1进，2进，2出，1出，3进3出，即213；
（4）：1进，1出，2进，3进，3出，2出，即132
（5）：1进，2进，2出，3进，3出，1出，即231；
也可以反过来思考这个问题：排列组合总共有6种情况，其中只有312不可能，因为3进栈必然有1、2也进栈，只会有321的情况。
3.2❶简述栈和线性表的差别。
3.3❷写出下列程序段的输出结果（栈的元素类型SElemType为char）。
void main()
{
Stack S;
char x, y;
InitStack(S);
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
栈是先进后出。
Push(S,x); Push(S, ‘a’); Push(S,y); 推进去c a k,栈内容c a k
Pop(S,x); Push(S, ‘t’); Push(S,x); 推出k,x=k 栈内容c a;推进t, 站内容c a t; 推入x=k,栈内容 catk
Pop(S,x); Push(S, ‘s’); 推出k, x=k 栈内容cat,推进s,栈内容cats
下面循环打印stac,
最后printf(x)，即打印k
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]);
}
status algo1(Stack s){
//定义函数 algo1, 参数为Stack类型,返回值status类型
int i,n ,A[255]; //定义变量
n=0;
while (!StackEmpty(s)) {
n++;
Pop(S,A[n]);
}
//如果栈不空,栈顶元素出栈,放在A[n]里面,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);
}
void algo2 (Stack S,int e)｛
Stack T, int d;
InitStack(T);
//初始化栈T
while(!StackEmpty(S)){
//循环条件：如果栈S不为空
Pop(S,d);
//S最顶元素出栈
if(d!=e) Push(T,d);
//若d！=e，就将d赋给栈T
}
while(!StackEmpty(T)){
//循环条件：如果栈T不为空
Pop(T,d);
//T最顶元素出栈
Push(S,d);
//将d赋给栈T
}
}
综上所述：该代码的作用是 将栈S中不等于e的元素赋给栈T，然后将栈T中的元素赋给S；所以总功能是清除栈S中等于e的元素 }
3.5❹假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
3.6❹ 试证明：若借助栈由输入序列12…n得到的输出序列为p1p2…pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i
3.7❹按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B×C/D+E↑F
3.8❸试推导求解n阶梵塔问题至少要执行的move操作的次数。
3.9❸试将下列递推过程改写为递归过程。
void ditui(int n)
{
int i;
i = n;
while(i>1)
cout<
}
3.10❸试将下列递归过程改写为非递归过程。
void test(int &sum)
{
int x;
cin>>x;
if(x==0)
sum=0;
else
{
test(sum);
sum+=x;
}
cout<
}
3.11❸简述队列和堆栈这两种数据类型的相同点和差异处。
3.12❸写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{
Queue Q;
InitQueue(Q);
char x= ‘e’, y= ‘c’;
EnQueue(Q, ‘h’);
EnQueue(Q, ‘r’);
EnQueue(Q, y);
DeQueue(Q, x);
EnQueue(Q, x);
DeQueue(Q, x);
EnQueue(Q, ‘a’);
While(!QueueEmpty(Q))
{
DeQueue(Q,y);
cout<
}
cout<
}
首先要明白队列是 先进先出
InQueue(Q,'H');
InQueue(Q,'R');
InQueue(Q,y);
//现在队列内容从前到后依次是HRC
OutQueue(Q,x);InQueue(Q,x);
//，H 出队列，并且把H赋于x，然后x='H' 入队列，现在队列内容从前到后依次是RCH
OutQueue(Q,x);InQueue(Q,'A');
//，R 出队列，并且把H赋于x，注意现在x=‘R’,因为最后输出的x，就是R；然后 'A' 入队列，现在队列内容从前到后依次是CHA
while(!QEmpty(Q))
{OutQueue(Q,y);
printf(y);
}
//这个循环依次输出CHA
printf(x);
//输出R
3.13❷简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3(Queue &Q)
{
Stack S;
int d;
InitStack(S);
while(!QueueEmpty(Q))
{
DeQueue(Q, d);
Push(S, d);
}
while(!StackEmpty(S))
{
Pop(S, d);
EnQueue(Q, d);
}
}
3.14❹若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
(3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
算法设计部分正在研究,希望大家多多指教
题目转载自:迷路的国王 - 博客园,但是他的题目答案实在是简略,我又自己重新写了做了一遍
数据结构非常重要,温故而知新,必有新的收获
