熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第三章 答案[5]

2013-11-15 15:00:56  來源: 數據結構 

  輸入序列為不能得出其理由是輸出序列最後兩元素是前面個元素()得到後棧中元素剩在棧頂不可能棧底元素在棧頂元素之前出棧

  得到的過程如下入棧並出棧得到部分輸出序列然後入棧出棧部分輸出序列變為接著入棧依次出棧部分輸出序列變為最後入棧並退棧得最終結果

  能得到出棧序列BCAED不能得到出棧序列DBACE其理由為若出棧序列以D開頭說明在D之前的入棧元素是AB和C三個元素中C是棧頂元素B和A不可能早於C出棧故不可能得到DBACE出棧序列

  借助棧結構n個入棧元素可得到/(n+)((n)!/(n!*n!))種出棧序列本題個元素可有種出棧序列abcd和dcba就是其中兩種但dabc和adbc是不可能得到的兩種

  不能得到序列棧可以用單鏈表實現這就是鏈棧由於棧只在棧頂操作所以鏈棧通常不設頭結點

  如果i<j則對於pi<pj情況說明pi在pj入棧前先出棧而對於pi>pj的情況則說明要將pj壓到pi之上也就是在pj出棧之後pi才能出棧這就說明對於i<j<k不可能出現pj<pk<pi的輸出序列換句話說對於輸入序列不可能出現的輸出序列

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22718.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.