1、數據結構應用題答案數據結構應用題答案第2章線性表線性表1.設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。答：答：操作序列如下：qrlink=prlinkprlink=qqrlinkllink=qqllink=p注意答案不唯一第3章棧和隊列棧和隊列1.設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的車站，具體寫

2、出這四輛列車開出車站的所有可能的順序。答：答：共計14種，分別是：1234，1243，1324，1342，1432，2134，2143，2341，2314，2431，3214，3241，3421，43212.如果輸入序列為1，2，3，4，5，6，試問能否通過棧結構得到以下兩個序列：4，3，5，6，1，2和1，3，5，4，2，6；請說明為什么不能或如何才能得到。答：答：（1）不能得到4，3，5，6，1，2；因為1，2，3，4入棧后；4，3

3、出棧；得到序列4，3；棧中還有1，2；5入棧后即出棧，得到序列4，3，5；6入棧后即出棧，得到序列4，3，5，6；此時，棧中還有1，2；必須2先出棧，然后1再出棧，1不可能在2之前出棧。故而得不到該序列。（2）能得到輸出順序為1，3，5，4，2，6的序列。得到的操作如下：1入棧后即出棧，得到序列1；2，3入棧后3即出棧，得到序列1，3；4，5入棧后，5出棧，4出棧，得到序列1，3，5，4；2出棧，得到序列1，3，5，4，2；6入棧后即出

4、棧，得到序列1，3，5，4，2，6。3.假設正讀和反讀都相同的字符序列為“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’則不是回文。假設一字符序列已存入計算機，請用堆棧判斷其是否為回文，簡述算法。答：方法一：答：方法一：使用數據結構:循環(huán)隊列和順序棧。算法思路為：1.將字符串按照用戶輸入的順序分別入棧和隊列2.分別從隊列和棧中取出首個字符3.比較取出的字符，若相等，繼續(xù)分別從隊列和棧中取首個字符；否則

5、跳出循環(huán)，并設置標志flag=04.若隊列和棧中的字符都取完，則結束，設置標志flag=15.flag=1表示字符從前往后和從后往前的序列完全匹配，該字符串屬于回文6.flag=0表示字符從前往后和從后往前的序列不完全匹配，該字符串不屬于回文方法二：方法二：使用棧。將字符串的前一半入棧，再依次出棧，與后一半進行比較，若有不等則不是回文；若依次相等，則是回文。注意：注意：本題要求簡答算法思路，并不要求寫出具體算法。4.試寫出循環(huán)隊列判空和

6、判滿的條件（隊列最大容量為M）。答：答：假設循環(huán)隊列最大存儲容量為M判空：Q.front==Q.rear（1）判滿：（Q.rear1）%M==Q.front（2）評分標準：評分標準：給出（1）和（2）式分別得3分，其他酌情扣分。5.假設Q[0..10]是一個循環(huán)隊列，初始狀態(tài)為front=rear=0，畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。debgh入隊；de出隊；ijklm入隊；nop入

7、隊答：（圖自己根據解答畫出）答：（圖自己根據解答畫出）debgh入隊；狀態(tài)1：front=0，rear=5；答：答：S1和S2共享內存中一片連續(xù)空間（地址1到m），可以將S1和S2的棧底設在兩端，兩棧頂向共享空間的中心延伸，僅當兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當一個棧頂指針為0，另一個棧頂指針m1時為兩棧均空。12.設一數列的輸入順序為123456，若采用堆棧結構，并以A和D分別表示入棧和出棧操作，試問通

8、過入出棧操作的合法序列。（1）能否得到輸出順序為325641的序列。（2）能否得到輸出順序為154623的序列。答：答：（1）能得到325641。在123依次進棧后，3和2出棧，得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？?。得輸出序列325641。其操作序列為AAADDAADADDD。（2）不能得到輸出順序為154623的序列。部分合法操作序列為ADAAAAD

9、DAD，得到部分輸出序列1546后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列154623。13.設輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？為什么？?？梢杂脝捂湵韺崿F嗎？答：答：不能得到序列2，5，3，4，6；其理由是，輸出序列第三四位兩元素是3，4，前面2個元素（2，5）得到后，棧中元素剩3，4，且4在棧頂，棧底元素3不可能在棧頂元素4之前出棧。棧可以用單鏈表實現，這就是鏈棧。由于棧只在

10、棧頂操作，所以鏈棧通常不設頭結點。14.有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？用S表示入棧，X表示出棧，寫出可能得到次序的操作序列。答：答：三個：CDEBA，CDBEA，CDBAECDEBA操作序列：SSSXSXSXXX；CDBEA操作序列：SSSXSXXSXX；CDBAE操作序列：SSSXSXXXSX；15.若以1、2、3、4作為雙端隊列的

11、輸入序列，試分別求出以下條件的輸出序列：（1）能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；（2）能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；（3）既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。答：答：（1）4132（2）4213（3）423116.設一個雙端隊列，元素進入該隊列的次序為a，b，c，d。求既不能由輸入受限的雙端隊列得到又不能由輸出受限的雙端隊列

12、得到的輸出序列。答：答：既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是dbca。第6章樹和二叉樹樹和二叉樹1.（8分）已知一棵樹的邊的集合表示為：(LN)(GK)(GL)(GM)(BE)(BF)(DG)(DH)(DI)(DJ)(AB)(AC)(AD))畫出這棵樹，并回答下列問題：(1)樹根是哪個結點？哪些是葉子結點？哪些是非終端結點？(2)樹的度是多少？各個結點的度是多少？(3)樹的深度是多少？各個結點的層數