①、資料結構
輸入序列ABCABC經過棧操作變成ABCCBA，下面哪些是可能的棧操作()
A： push pop push pop push pop pushpush push pop pop pop
B： push push push push push push poppop pop pop pop pop
C： push push push pop pop pop pushpush pop pop push pop
D： push push push push pop pushpop push pop pop pop pop
答案：AD
解析：棧(Stack)是一個基礎的資料結構，它的特點是先進後出，或者是後進先出(Last in first out, LIFO)，可以用於逆序輸出。裝子彈的梭子和疊在一起的盤子等都是棧結構在實際中的應用。對棧中資料的操作是在棧頂進行的，進棧push操作和出棧pop操作是兩個基本的操作。A選項中第一組pushpop操作push A pop A 輸出 A，第二組pushpop操作push B pop B 輸出 B，第三組pushpop操作push C pop C 輸出 C，接著三個push操作，依次把ABC壓棧，三個pop操作反向輸出為CBA，滿足題目要求。類似的可以求出，選項B的結果為CBACBA，選項C的結果為CBABAC，選項D的結果為ABCCBA。
②、資料結構
下列關鍵碼序列哪些是一個堆( )
A：90 31 53 23 16 48
B：90 48 31 53 16 23
C：16 53 23 90 3148
D：1631 23 90 53 48
答案:AD
解析:與棧一樣，堆也是一個基礎的資料結構，分為最大堆和最小堆兩類。最大堆中根節點的值是整個堆中最大的，該屬性對於堆的`分支也是成立的。最小堆中根節點的值是整個堆中最小的，該屬性對於堆的分支也是成立的。需要注意的是：堆首先是一個完全二元樹，是二元樹的推廣。堆的建立複雜度是O(n)，插入和刪除都可以在O(logn)時間內完成。堆可以用於構造優先佇列，在作業系統中有著重要應用。依據堆是一個完全二元樹的性質，選項A可以構成成一個最大堆，31和53分別是根節點90的左右孩子，23和16分別是節點31的左右孩子，48是節點53的左孩子。依次類推，選項D是一個最小堆，選項B和選項C不滿足堆的假設條件。
③、演算法
二元樹的後序排列DBEFCA，中序排列DBAECF，那麼對其做先序線索化二元樹，節點E的線索化指向節點()
A：BC
B：AC
C：DF
D：CF
答案:D
解析: 先序 (根-左子樹-右子樹)、中序 (左子樹-根-右子樹)和後序 (左子樹-右子樹-根)遍歷是遍歷二元樹的三種基本方式。先序遍歷的第一個值就是根節點，後序遍歷的最後一個節點就是根節點。由先序和中序遍歷可以唯一確定一個二元樹，同樣的，由後序和中序遍歷也可以唯一確定一個二元樹。需要注意的是：由先序和後序遍歷不能唯一確定一個二元樹。由題目給定的後序和中序遍歷結果，可以確定二元樹的根為 A，A的左孩子為B，A的右孩子為C。B的左孩子為D。C的左孩子為E，C的右孩子為F。因此，該樹先序遍歷的結果為ABDCEF。線索化指的是在遍歷的過程中，使用線索來代替空指標(比如葉子節點的左右孩子都是空指標)。線索二元樹可以用於更快的線性遍歷二元樹。線索化時，E的前驅是C，後繼是F，因此，選項D正確。