- 相關(guān)推薦
騰訊2015校招筆試題
�、�、數據結構
輸入序列ABCABC經(jīng)過(guò)棧操作變成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)是一個(gè)基礎的數據結構，它的特點(diǎn)是先進(jìn)后出，或者是后進(jìn)先出(Last in first out, LIFO)，可以用于逆序輸出。裝子彈的梭子和疊在一起的盤(pán)子等都是棧結構在實(shí)際中的應用。對棧中數據的操作是在棧頂進(jìn)行的，進(jìn)棧push操作和出棧pop操作是兩個(gè)基本的操作。A選項中第一組pushpop操作push A pop A 輸出 A，第二組pushpop操作push B pop B 輸出 B，第三組pushpop操作push C pop C 輸出 C，接著(zhù)三個(gè)push操作，依次把ABC壓棧，三個(gè)pop操作反向輸出為CBA，滿(mǎn)足題目要求。類(lèi)似的可以求出，選項B的結果為CBACBA，選項C的結果為CBABAC，選項D的結果為ABCCBA。
�、�、數據結構
下列關(guān)鍵碼序列哪些是一個(gè)堆( )
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
解析:與棧一樣，堆也是一個(gè)基礎的數據結構，分為最大堆和最小堆兩類(lèi)。最大堆中根節點(diǎn)的值是整個(gè)堆中最大的，該屬性對于堆的分支也是成立的。最小堆中根節點(diǎn)的值是整個(gè)堆中最小的，該屬性對于堆的分支也是成立的。需要注意的是：堆首先是一個(gè)完全二叉樹(shù)，是二叉樹(shù)的推廣。堆的建立復雜度是O(n)，插入和刪除都可以在O(logn)時(shí)間內完成。堆可以用于構造優(yōu)先隊列，在操作系統中有著(zhù)重要應用。依據堆是一個(gè)完全二叉樹(shù)的性質(zhì)，選項A可以構成成一個(gè)最大堆，31和53分別是根節點(diǎn)90的左右孩子，23和16分別是節點(diǎn)31的左右孩子，48是節點(diǎn)53的左孩子。依次類(lèi)推，選項D是一個(gè)最小堆，選項B和選項C不滿(mǎn)足堆的假設條件。
�、�、算法
二叉樹(shù)的后序排列DBEFCA，中序排列DBAECF，那么對其做先序線(xiàn)索化二叉樹(shù)，節點(diǎn)E的線(xiàn)索化指向節點(diǎn)()
A：BC
B：AC
C：DF
D：CF
答案:D
解析: 先序 (根-左子樹(shù)-右子樹(shù))、中序 (左子樹(shù)-根-右子樹(shù))和后序 (左子樹(shù)-右子樹(shù)-根)遍歷是遍歷二叉樹(shù)的三種基本方式。先序遍歷的第一個(gè)值就是根節點(diǎn)，后序遍歷的最后一個(gè)節點(diǎn)就是根節點(diǎn)。由先序和中序遍歷可以唯一確定一個(gè)二叉樹(shù)，同樣的，由后序和中序遍歷也可以唯一確定一個(gè)二叉樹(shù)。需要注意的是：由先序和后序遍歷不能唯一確定一個(gè)二叉樹(shù)。由題目給定的后序和中序遍歷結果，可以確定二叉樹(shù)的根為 A，A的左孩子為B，A的右孩子為C。B的左孩子為D。C的左孩子為E，C的右孩子為F。因此，該樹(shù)先序遍歷的結果為ABDCEF。線(xiàn)索化指的是在遍歷的過(guò)程中，使用線(xiàn)索來(lái)代替空指針(比如葉子節點(diǎn)的左右孩子都是空指針)。線(xiàn)索二叉樹(shù)可以用于更快的線(xiàn)性遍歷二叉樹(shù)。線(xiàn)索化時(shí)，E的前驅是C，后繼是F，因此，選項D正確。
【騰訊校招筆試題】相關(guān)文章：
騰訊2014校招非業(yè)務(wù)類(lèi)筆試分享11-21
銀行校招筆試題目11-21
搜狗2015校招筆試題11-22
騰訊筆試題 試題分享02-24
阿里巴巴校招筆試題，試題分享02-25
�？低曅Ｕ泄P試題11-28
阿里巴巴校招筆試題11-29
阿里巴巴校招筆試題目11-29
浙商銀行2014校招筆試題11-21