騰訊校招筆試題

時(shí)間：2024-07-22 19:23:26 面試筆試我要投稿

相關(guān)推薦

騰訊2016年校招筆試題

　　①、數(shù)據(jù)結(jié)構(gòu)

騰訊2016年校招筆試題

　　輸入序列ABCABC經(jīng)過棧操作變成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è)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是先進(jìn)后出，或者是后進(jìn)先出(Last in first out, LIFO)，可以用于逆序輸出。裝子彈的梭子和疊在一起的盤子等都是棧結(jié)構(gòu)在實(shí)際中的應(yīng)用。對棧中數(shù)據(jù)的操作是在棧頂進(jìn)行的，進(jìn)棧push操作和出棧pop操作是兩個(gè)基本的操作。A選項(xiàng)中第一組pushpop操作push A pop A 輸出 A，第二組pushpop操作push B pop B 輸出 B，第三組pushpop操作push C pop C 輸出 C，接著三個(gè)push操作，依次把ABC壓棧，三個(gè)pop操作反向輸出為CBA，滿足題目要求。類似的可以求出，選項(xiàng)B的結(jié)果為CBACBA，選項(xiàng)C的結(jié)果為CBABAC，選項(xiàng)D的結(jié)果為ABCCBA。

　　②、數(shù)據(jù)結(jié)構(gòu)

　　下列關(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è)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，分為最大堆和最小堆兩類。最大堆中根節(jié)點(diǎn)的值是整個(gè)堆中最大的，該屬性對于堆的分支也是成立的。最小堆中根節(jié)點(diǎn)的值是整個(gè)堆中最小的，該屬性對于堆的分支也是成立的。需要注意的是：堆首先是一個(gè)完全二叉樹，是二叉樹的推廣。堆的建立復(fù)雜度是O(n)，插入和刪除都可以在O(logn)時(shí)間內(nèi)完成。堆可以用于構(gòu)造優(yōu)先隊(duì)列，在操作系統(tǒng)中有著重要應(yīng)用。依據(jù)堆是一個(gè)完全二叉樹的性質(zhì)，選項(xiàng)A可以構(gòu)成成一個(gè)最大堆，31和53分別是根節(jié)點(diǎn)90的左右孩子，23和16分別是節(jié)點(diǎn)31的左右孩子，48是節(jié)點(diǎn)53的左孩子。依次類推，選項(xiàng)D是一個(gè)最小堆，選項(xiàng)B和選項(xiàng)C不滿足堆的假設(shè)條件。

　　③、算法

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

　　A：BC

　　B：AC

　　C：DF

　　D：CF

　　答案:D

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

【騰訊校招筆試題】相關(guān)文章：

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

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