第3章棧和隊(duì)列 作業(yè)(參考答案)

1、第三章棧和隊(duì)列作業(yè)1、若按教材P44頁圖3.1（b）所示鐵道進(jìn)行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請回答：（1）如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？（2）如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到？（寫出進(jìn)棧和出棧的棧操作序列）。123、132、213、231、321輸入序列為123456，不能得出435612，其理由是，輸出序列

2、最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。2、試證明：若借助棧由輸入序列1、2……n得到的輸出序列為p1、p2……pn(它是輸入序列的一個排列)，則在

3、輸出序列中不可能出現(xiàn)這樣的情形：存在著，i〈j〈k使pjpj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于ijk，不可能出現(xiàn)pjpkpi的輸出序列。換whilewhile(c!=Push(sc)c=get()c=get()c=get()c=get()whilewhile(c!=@Pop(sx)ifif(c==x)(c==x)c=get()c=get()elseelsereturnreturnFALS

4、EFALSEifif(c==@(c==@TRUEelseelsereturnreturnFALSEFALSE5、假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。試寫一個算法判別讀入的一個以‘＠’為結(jié)束符的字符序列是否是回文。StatusStatusReturnText()ReturnText()判斷讀入的一個以判斷讀入的一個以‘@’‘@’為結(jié)束符的字符序列

5、是否為回文為結(jié)束符的字符序列是否為回文InitStack(s)InitStack(s)InitQueue(q)InitQueue(q)c=get()c=get()whilewhile(c!=@)(c!=@)Push(sc)Push(sc)EnQueue(qc)EnQueue(qc)c=get()c=get()whilewhile(!EmptyStack(s))(!EmptyStack(s))Pop(sx)Pop(sx)DeQueue(q