- 搜標題
- 搜題干
- 搜選項
問答題
【簡答題】試證明：若借助棧由輸入序列12…n得到的輸出序列為p1p2…pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i＜j＜k使pj＜pk＜pi。
答案：
因為輸入序列是從小到大排列的，所以若pj＜pk＜pi，...
你可能感興趣的試題
問答題
【簡答題】假設以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準則，并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列。
答案：
任何前n個序列中S的個數(shù)一定大于X的個數(shù)。
設兩個合法序列為：
T.1=S…&hell...
設兩個合法序列為：
T.1=S…&hell...
