腾讯校招笔试题

腾讯2015校招笔试题

　　①、数据结构

　　输入序列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正确。

【腾讯校招笔试题】相关文章：

腾讯校招面试常见问题11-29

腾讯2014校招非业务类笔试分享11-21

银行校招笔试题目11-21

搜狗2015校招笔试题11-22

腾讯笔试题 试题分享02-24

阿里巴巴校招笔试题，试题分享02-25

海康威视校招笔试题11-28

阿里巴巴校招笔试题11-29

阿里巴巴校招笔试题目11-29

浙商银行2014校招笔试题11-21