3.1?若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道）凰锡，則請回答：
(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?寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）体捏。
void main()
{
Stack S;
char x, y;
InitStack(S);
x = ’c’; y = ’k’;
Push(S, x); Push(S, ‘a(chǎn)’); 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);
}
結(jié)果輸出:stack
棧是先進后出。
Push(S,x); Push(S, ‘a(chǎn)’); Push(S,y); 推進去c a k,棧內(nèi)容c a k
Pop(S,x); Push(S, ‘t’); Push(S,x); 推出k,x=k 棧內(nèi)容c a;推進t, 站內(nèi)容c a t; 推入x=k,棧內(nèi)容 catk
Pop(S,x); Push(S, ‘s’); 推出k, x=k 棧內(nèi)容cat,推進s,棧內(nèi)容cats
下面循環(huán)打印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){
//定義函數(shù) algo1, 參數(shù)為Stack類型,返回值status類型
int i,n ,A[255]; //定義變量
n=0;
while (!StackEmpty(s)) {
n++;
Pop(S,A[n]);
}
//如果棧不空,棧頂元素出棧,放在A[n]里面,n++,指向數(shù)組下一個位置,同時記錄了個數(shù)
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)){
//循環(huán)條件：如果棧S不為空
Pop(S,d);
//S最頂元素出棧
if(d!=e) Push(T,d);
//若d！=e拇颅，就將d賦給棧T
}
while(!StackEmpty(T)){
//循環(huán)條件：如果棧T不為空
Pop(T,d);
//T最頂元素出棧
Push(S,d);
//將d賦給棧T
}
}
綜上所述：該代碼的作用是 將棧S中不等于e的元素賦給棧T奏司，然后將棧T中的元素賦給S；所以總功能是清除棧S中等于e的元素 }
3.5?假設以S和X分別表示入棧和出棧的操作樟插，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列韵洋。稱可以操作的序列為合法序列（例如竿刁，SXSX為合法序列，SXXS為非法序列）搪缨。試給出區(qū)分給定序列為合法序列或非法序列的一般準則食拜，并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列副编。
3.6? 試證明：若借助棧由輸入序列12…n得到的輸出序列為p1p2…pn(它是輸入序列的一個排列)负甸，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i
3.7?按照四則運算加、減痹届、乘呻待、除和冪運算(↑)優(yōu)先關系的慣例，并仿照教科書3.2節(jié)例3-2的格式队腐，畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程：
A-B×C/D+E↑F
3.8?試推導求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)蚕捉。
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?簡述隊列和堆棧這兩種數(shù)據(jù)類型的相同點和差異處迫淹。
3.12?寫出以下程序段的輸出結(jié)果（隊列中的元素類型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(chǎn)’);
While(!QueueEmpty(Q))
{
DeQueue(Q,y);
cout<
}
cout<
}
首先要明白隊列是 先進先出
InQueue(Q,'H');
InQueue(Q,'R');
InQueue(Q,y);
//現(xiàn)在隊列內(nèi)容從前到后依次是HRC
OutQueue(Q,x);InQueue(Q,x);
//为严，H 出隊列敛熬，并且把H賦于x，然后x='H' 入隊列第股，現(xiàn)在隊列內(nèi)容從前到后依次是RCH
OutQueue(Q,x);InQueue(Q,'A');
//应民，R 出隊列，并且把H賦于x夕吻，注意現(xiàn)在x=‘R’,因為最后輸出的x瑞妇，就是R；然后 'A' 入隊列梭冠，現(xiàn)在隊列內(nèi)容從前到后依次是CHA
while(!QEmpty(Q))
{OutQueue(Q,y);
printf(y);
}
//這個循環(huán)依次輸出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) 既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列默勾。
算法設計部分正在研究,希望大家多多指教
題目轉(zhuǎn)載自:迷路的國王 - 博客園,但是他的題目答案實在是簡略,我又自己重新寫了做了一遍
數(shù)據(jù)結(jié)構非常重要,溫故而知新,必有新的收獲
