3.1?若按教科書(shū)3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車(chē)廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請(qǐng)回答：
(1) 如果進(jìn)站的車(chē)廂序列為123，則可能得到的出站車(chē)廂序列是什么？
(2) 如果進(jìn)站的車(chē)廂序列為123456，則能否得到435612和135426的出站序列，并請(qǐng)說(shuō)明為什么不能得到或者如何得到（即寫(xiě)出以‘S’表示進(jìn)棧和以‘X’表示出棧的棧操作序列）。
可分為五種情況：
（1）：1、2、3進(jìn)，再3、2、1出，即321；
（2）：1進(jìn)，1出；2進(jìn)，2出；3進(jìn)、3出，即123；
（3）：1進(jìn)，2進(jìn)，2出，1出，3進(jìn)3出，即213；
（4）：1進(jìn)，1出，2進(jìn)，3進(jìn)，3出，2出，即132
（5）：1進(jìn)，2進(jìn)，2出，3進(jìn)，3出，1出，即231；
也可以反過(guò)來(lái)思考這個(gè)問(wèn)題：排列組合總共有6種情況，其中只有312不可能，因?yàn)?進(jìn)棧必然有1、2也進(jìn)棧，只會(huì)有321的情況。
3.2?簡(jiǎn)述棧和線(xiàn)性表的差別。
3.3?寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類(lèi)型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
棧是先進(jìn)后出。
Push(S,x); Push(S, ‘a(chǎn)’); Push(S,y); 推進(jìn)去c a k,棧內(nèi)容c a k
Pop(S,x); Push(S, ‘t’); Push(S,x); 推出k,x=k 棧內(nèi)容c a;推進(jìn)t, 站內(nèi)容c a t; 推入x=k,棧內(nèi)容 catk
Pop(S,x); Push(S, ‘s’); 推出k, x=k 棧內(nèi)容cat,推進(jìn)s,棧內(nèi)容cats
下面循環(huán)打印stac,
最后printf(x)，即打印k
3.4?簡(jiǎn)述以下算法的功能（棧的元素類(lèi)型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類(lèi)型,返回值status類(lèi)型
int i,n ,A[255]; //定義變量
n=0;
while (!StackEmpty(s)) {
n++;
Pop(S,A[n]);
}
//如果棧不空,棧頂元素出棧,放在A[n]里面,n++,指向數(shù)組下一個(gè)位置,同時(shí)記錄了個(gè)數(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?假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱(chēng)可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。
3.6? 試證明：若借助棧由輸入序列12…n得到的輸出序列為p1p2…pn(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i
3.7?按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例，并仿照教科書(shū)3.2節(jié)例3-2的格式，畫(huà)出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：
A-B×C/D+E↑F
3.8?試推導(dǎo)求解n階梵塔問(wèn)題至少要執(zhí)行的move操作的次數(shù)。
3.9?試將下列遞推過(guò)程改寫(xiě)為遞歸過(guò)程。
void ditui(int n)
{
int i;
i = n;
while(i>1)
cout<
}
3.10?試將下列遞歸過(guò)程改寫(xiě)為非遞歸過(guò)程。
void test(int &sum)
{
int x;
cin>>x;
if(x==0)
sum=0;
else
{
test(sum);
sum+=x;
}
cout<
}
3.11?簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類(lèi)型的相同點(diǎn)和差異處。
3.12?寫(xiě)出以下程序段的輸出結(jié)果（隊(duì)列中的元素類(lèi)型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<
}
首先要明白隊(duì)列是 先進(jìn)先出
InQueue(Q,'H');
InQueue(Q,'R');
InQueue(Q,y);
//現(xiàn)在隊(duì)列內(nèi)容從前到后依次是HRC
OutQueue(Q,x);InQueue(Q,x);
//，H 出隊(duì)列，并且把H賦于x，然后x='H' 入隊(duì)列，現(xiàn)在隊(duì)列內(nèi)容從前到后依次是RCH
OutQueue(Q,x);InQueue(Q,'A');
//，R 出隊(duì)列，并且把H賦于x，注意現(xiàn)在x=‘R’,因?yàn)樽詈筝敵龅膞，就是R；然后 'A' 入隊(duì)列，現(xiàn)在隊(duì)列內(nèi)容從前到后依次是CHA
while(!QEmpty(Q))
{OutQueue(Q,y);
printf(y);
}
//這個(gè)循環(huán)依次輸出CHA
printf(x);
//輸出R
3.13?簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類(lèi)型均為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作為雙端隊(duì)列的輸入序列，試分別求出滿(mǎn)足以下條件的輸出序列：
(1) 能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。
(2) 能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列。
(3) 既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。
算法設(shè)計(jì)部分正在研究,希望大家多多指教
題目轉(zhuǎn)載自:迷路的國(guó)王 - 博客園,但是他的題目答案實(shí)在是簡(jiǎn)略,我又自己重新寫(xiě)了做了一遍
數(shù)據(jù)結(jié)構(gòu)非常重要,溫故而知新,必有新的收獲
