數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

1、第三章習(xí)題 1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度，回答： 如進(jìn)站的車廂序歹 0 為123,則可能得到的出站車廂序歹 0 是什么？ 如進(jìn)站的車廂序列為123456,能否得到435612和135426的出站序列，并說(shuō)明原因。(即寫出 以“S”表示進(jìn)棧、以“ X”表示出棧的棧操作序列)。 2. 設(shè)隊(duì)列中有A、B、C、E這5個(gè)元素，其中隊(duì)首元素為 A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列 4步 操作： (1) 輸出隊(duì)首元素； (2) 把隊(duì)首元素值插入到隊(duì)尾； (3) 刪除隊(duì)首元素； (4) 再次刪除隊(duì)首元素。 直到隊(duì)列成為空隊(duì)列為止，得到輸出序列： (1) A G E、G C (

2、2) A、C、E (3) A、C、E、C、C、C (4) A、C、E、C 3. 給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？ 4. 按照四則運(yùn)算加、減、乘、除和籍運(yùn)算(f)優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操 作數(shù)棧和運(yùn)算符棧的變化過(guò)程： A B* C/D+ E f F 5. 試寫一個(gè)算法，判斷依次讀入的一個(gè)以遂結(jié)束符的字母序列，是否為形如序列 1 &序列2 模式的字符序歹 0。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序歹 0。例如， a+b&b+a是屆該模式的字符序歹 0,而1 +3 &3 1 則不是。 6.

3、假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式且書寫 正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。 7. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)， 試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。 8. 要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用，設(shè)置一個(gè)標(biāo)志域tag ,以tag為0或1來(lái)區(qū)分 頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。 9. 簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類型均為 int ): (1) void proc_1(Stack S) ( int i, n, A255; n=0; whil

4、e(!EmptyStack(S) (n+; Pop(&S, &An); for(i=1; itop=-1表示?？?。 判斷棧S滿：如果S-top=Stack_Size-1 表示棧滿。 (2)鏈棧(top為棧頂指針，指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn)) 判斷?？眨喝绻鹴op-next=NULL表示?？?。 判斷棧滿：當(dāng)系統(tǒng)沒有可用空間時(shí)，申請(qǐng)不到空間存放要進(jìn)棧的元素，此時(shí)棧滿。 3. 4照四則運(yùn)算加、減、乘、除和籍運(yùn)算的優(yōu)先慣例，畫出對(duì)下列表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧 的變化過(guò)程：A-B*C/D+E f F 【解答】OVS OPTR OVS OPTR OVS OPTR,+ OPTR7,

5、生成 T(1)/D T(2) A OVS CPTR OVS OPTR 右邊界* T(4) front=Q-front & tag=1) /* 隊(duì)滿 */ return(FALSE); if(Q-front=Q-front & tag=0) /*x入隊(duì)前隊(duì)空，x入隊(duì)后重新設(shè)置標(biāo)志*/ tag=1; Q-elememtQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /*設(shè)置隊(duì)尾指針 */ Return(TRUE); 出隊(duì)算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) ( /*刪除隊(duì)頭元素，用x

6、返回其值*/ if(Q-front=Q-rear & tag=0) /* 隊(duì)空 */ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新設(shè)置隊(duì)頭指針 */ if(Q-front=Q-rear) tag=0; /*隊(duì)頭元素出隊(duì)后隊(duì)歹0為空，重新設(shè)置標(biāo)志域 */ Return(TUUE); 編寫求解Hanoi問(wèn)題的算法，并給出三個(gè)盤子搬動(dòng)時(shí)的遞歸調(diào)用過(guò)程。 【解答】算法： void hanoi (int n ,char x, char y, char z) ( /*將塔座X上按直徑由小到大且至上而下編號(hào)

7、為 1到n的n個(gè)圓盤按規(guī)則搬到塔座Z上，Y可用 做輔助塔座*/ if(n = =1) move(x,1,z); else ( Hanoi(n-1,x,z,y); move(x, n, z); Hanoi(n-1, y,x,z); Hanoi(3,A,B,C)的遞歸調(diào)用過(guò)程: Hanoi(2,A,C,B): Hanoi(2,B,A,C) 提示: 習(xí)題 1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度，回答: 如進(jìn)站的車廂序列為 123,則可能得到的出站車廂序列是什么? 如進(jìn)站的車廂序列為 123456，能否得到435612和135426的出站序列，并說(shuō)明原因。(即寫出以“ S

8、”表 示進(jìn)棧、以“ X”表示出棧的棧操作序列)。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6 A、B、C、D、E這5個(gè)元素，其中隊(duì)首元素為 A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列 4步操作: (1) 輸出隊(duì)首兀素； 2) 把隊(duì)首兀素值插入到隊(duì)尾; 3) 刪除隊(duì)首兀素； 4) 再次刪除隊(duì)首兀:素。 Hanoi(1,A,B,C) move(A-C) 1 號(hào)搬到 C Move(A-B) 2號(hào)搬到B Hanoi(1,C,A,B) move(C-B) 1 號(hào)搬到 B Move(A-C) 3號(hào)搬到C Hanoi(1,B,C,A) move(B-A) 1 號(hào)搬到 A Move

9、(B-C) 2號(hào)搬到C Hanoi(1,A,B,C) move(A-C) 1 號(hào)搬到 C 第3章 限定性線性表 棧和隊(duì)列 123、213、132、231、321 (312) 2. 設(shè)隊(duì)列中有 直到隊(duì)列成為空隊(duì)列為止，則是否可能得到輸出序列: 提示： A、B、C、D、E （輸出隊(duì)首元素A） A、 B、C、D、E、A （把隊(duì)首元素 A插入到隊(duì)尾） B、 C、D、E、A （刪除隊(duì)首元素A） C、 D、E、A （再次刪除隊(duì)首元素B） C、D、E、A （輸出隊(duì)首元素C） C、 D、E、A、C （把隊(duì)首元素 C插入到隊(duì)尾） D、 E、A、C （刪除隊(duì)首元素C） E、 A、C （再次刪除隊(duì)首元素D） 3.

10、給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？ 4. 按照四則運(yùn)算加、減、乘、除和藉運(yùn)算（f）優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算 符棧的變化過(guò)程： A B * C/D+ E f F 5. 試寫一個(gè)算法，判斷依次讀入的一個(gè)以 為結(jié)束符的字母序列，是否為形如序列 1 & 序列2模式的字符 序列。其中序列1和序列2中都不含字符&且序列2是序列1的逆序列。例如，a+b&b+a 是屬該模式 的字符序列，而1 + 3 & 3 1則不是。 提示： 邊讀邊入棧，直到& 6. 假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試

11、寫一個(gè)算法，將一個(gè) 通常書寫形式（中綴） 且書寫正確 的表達(dá)式轉(zhuǎn)換為逆波蘭式（后綴）。 提示： 例: 中綴表達(dá)式：a+b 后綴表達(dá)式：ab + 中綴表達(dá)式：a+b xc 后綴表達(dá)式：abc x+ 中綴表達(dá)式：a+bXc-d 后綴表達(dá)式：abc d- (3) A、 A、 C、 E、 C、 C (2) A、 C、 E C、E、 C、C、C (4) A、 C、 E、 C (2) 邊讀邊出棧邊比較，直到, 中綴 表達(dá)式：a+b Xc-d/e 后綴 表達(dá)式：abc x+de/- 中綴表達(dá)式：a+b Xc-d)-e/f 后綴 表達(dá)式：abcd - +ef/- 后綴表達(dá)式的計(jì)算過(guò)程：(簡(jiǎn)便) 順序掃描表達(dá)式

12、， (1) 如果是操作數(shù)，直接入棧； (2) 如果是操作符op,則連續(xù)退棧兩次，得操作數(shù) X, Y ,計(jì)算X op Y ,并將結(jié)果入棧。 * 如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？ 順序掃描中綴表達(dá)式， (1) 如果是操作數(shù)，直接輸出； (2) 如果是操作符op 2,則與棧頂操作符op 1比較： 如果op 2 op 1,則op 2入棧； 如果op 2 = op 1,則脫括號(hào)； 如果op 2 op 1,則輸出op 1 ； 7. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng) 的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。 提示: 參P.56 P.70 先畫圖.

13、 typedef LinkList CLQueue ; int InitQueue( CLQueue * Q) int EnterQueue( CLQueue Q, QueueElementType x) int DeleteQueue( CLQueue Q, QueueElementType *x) 8. 要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用 ，設(shè)置一個(gè)標(biāo)志域tag ,以tag為0或1來(lái)區(qū)分頭尾指針相同 時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。 提示: 初始狀態(tài)： front=0, rear=0, tag=0 隊(duì)空條件： front=rear, tag= 0 隊(duì)滿條件

14、: front=rear, tag= 1 其它狀態(tài)： front !=rear, tag= 0 （或 1、2） 入隊(duì)操作： ,(入隊(duì)) if (front=rear) tag= 1;(或直接 tag= 1) 出隊(duì)操作： ,(出隊(duì)) tag= 0; 問(wèn)題:如何明確區(qū)分 隊(duì)空、隊(duì)滿、非空非滿三種情況？ 9. 簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類型均為 int) (1) void proc_1(Stack S) ( int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i=n; i+) Push(

15、&S, Ai); 將棧S逆序。 ( Stack T; int d; InitStack(&T); while(!EmptyStack(S) ( Pop(&S, &d); if (d!=e) Push( &T, d); while(!EmptyStack(T) ( Pop(&T, &d); Push( &S, d); 刪除棧S中所有等于e的元素。 (3) void proc_3(Queue *Q) ( Stack S; int d; InitStack(&S); while(!EmptyQueue(*Q) ( DeleteQ

16、ueue(Q, &d); Push( &S, d); while(!EmptyStack(S) ( Pop(&S, &d); EnterQueue(Q , d) 將隊(duì)列Q逆序。 實(shí)習(xí)題 1. 回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。 試寫一個(gè)算法，判斷依次讀入的一個(gè)以 為結(jié)束符的字母序列，是否為形如序列 1 &序列2模式的 字符序列。其中序列 1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a 是屬 該模式的字符序列，而1 +3 & 3 1則不是。 2. 停車場(chǎng)管理。 設(shè)停車場(chǎng)是一個(gè)可停放 n輛車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi)，汽車按到達(dá)的 先后次序，由北向南依次排列（假設(shè)大門在最南端）。若車場(chǎng)內(nèi)已停滿 n輛車，則后來(lái)的汽車需在門外的便道 上等候，當(dāng)有車開走時(shí)，便道上的第一輛車即可開入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須 先退出車場(chǎng)為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場(chǎng)。每輛車離開停車場(chǎng)時(shí)，應(yīng)按其停 留時(shí)間的長(zhǎng)短交費(fèi)（在便道上停留的時(shí)間不收費(fèi)）。 試編寫程序，模擬上述管理過(guò)程。要求以順序棧模 擬停車場(chǎng)，以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá) 或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項(xiàng)：是“到達(dá)