騰訊2016年校招筆試題

　　①、數據結構

　　輸入序列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

　　解析:與棧一樣，堆也是一個基礎的數據結構，分為最大堆和最小堆兩類。最大堆中根節(jié)點的值是整個堆中最大的，該屬性對于堆的分支也是成立的。最小堆中根節(jié)點的值是整個堆中最小的，該屬性對于堆的分支也是成立的。需要注意的是：堆首先是一個完全二叉樹，是二叉樹的推廣。堆的建立復雜度是O(n)，插入和刪除都可以在O(logn)時間內完成。堆可以用于構造優(yōu)先隊列，在操作系統(tǒng)中有著重要應用。依據堆是一個完全二叉樹的性質，選項A可以構成成一個最大堆，31和53分別是根節(jié)點90的左右孩子，23和16分別是節(jié)點31的左右孩子，48是節(jié)點53的左孩子。依次類推，選項D是一個最小堆，選項B和選項C不滿足堆的假設條件。

　�、�、算法

　　二叉樹的后序排列DBEFCA，中序排列DBAECF，那么對其做先序線索化二叉樹，節(jié)點E的線索化指向節(jié)點()

　　A：BC

　　B：AC

　　C：DF

　　D：CF

　　答案:D

　　解析: 先序 (根-左子樹-右子樹)、中序 (左子樹-根-右子樹)和后序 (左子樹-右子樹-根)遍歷是遍歷二叉樹的三種基本方式。先序遍歷的第一個值就是根節(jié)點，后序遍歷的最后一個節(jié)點就是根節(jié)點。由先序和中序遍歷可以唯一確定一個二叉樹，同樣的，由后序和中序遍歷也可以唯一確定一個二叉樹。需要注意的是：由先序和后序遍歷不能唯一確定一個二叉樹。由題目給定的后序和中序遍歷結果，可以確定二叉樹的根為 A，A的左孩子為B，A的右孩子為C。B的左孩子為D。C的左孩子為E，C的右孩子為F。因此，該樹先序遍歷的結果為ABDCEF。線索化指的是在遍歷的過程中，使用線索來代替空指針(比如葉子節(jié)點的左右孩子都是空指針)。線索二叉樹可以用于更快的線性遍歷二叉樹。線索化時，E的前驅是C，后繼是F，因此，選項D正確。

【騰訊校招筆試題】相關文章：

騰訊校招面試常見問題11-29

騰訊2014校招非業(yè)務類筆試分享11-21

銀行校招筆試題目11-21

搜狗2015校招筆試題11-22

騰訊筆試題 試題分享02-24

阿里巴巴校招筆試題，試題分享02-25

海康威視校招筆試題11-28

阿里巴巴校招筆試題11-29

阿里巴巴校招筆試題目11-29

浙商銀行2014校招筆試題11-21