2017年1月27日19:05:28，今天是年三十，首先祝大家新年快乐，之前对自己要求过，每星期一篇面试题的博客，虽然今天心里有一万个不愿意写，也还是得写。这篇博客是 2016 腾讯软件开发面试题中不定项选择题集合中的 1 -12 题，其中后面的 13-25题在下周的博客中写，说明一下，这篇博客跟以往的每周一题有点不同，因为如果选择一两题，博客的边幅有点少，而且选择题相对来说，难度没那么大，更主要的是为了让大家全面的感受一下腾讯的面试题。
二、2016 腾讯软件开发面试题（不定项选择题【1-12】）1、已知一棵二叉树，如果先序遍历的节点顺序是： ADCEFGHB ，中序遍历是： CDFEGHAB ，则后序遍历结果为：（ ）
A. CFHGEBDA
B. CDFEGHBA
C. FGHCDEBA
D. CFHGEDBA
知识点
对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式：
先序遍历（根左右）
若二叉树为空，则不进行任何操作：否则
1、访问根结点。
2、先序方式遍历左子树。
3、先序遍历右子树。
中序遍历 （左根右）
若二叉树为空，则不进行任何操作：否则
1、中序遍历左子树。
2、访问根结点。
3、中序遍历右子树。
后序遍历 （左右根）
若二叉树为空，则不进行任何操作：否则
1、后序遍历左子树。
2、后序遍历右子树。
3、放问根结点。
因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树：
最后结果选择： D
2、下列哪两个数据结构，同时具有较高的查找和删除性能？（ ）
A. 有序数组
B. 有序链表
C. AVL 树
D. Hash 表
知识点
平衡二叉树的查找，插入和删除性能都是 O(logN) ，其中查找和删除性能较好；哈希表的查找、插入和删除性能都是 O(1) ，都是最好的。所以最后的结果选择： CD
3、下列排序算法中，哪些时间复杂度不会超过 nlogn？（ ）
A. 快速排序
B. 堆排序
C. 归并排序
D. 冒泡排序
知识点
根据上图，观察平均情况，最好最差情况的时间复杂度基本可以知道答案了，最后结果选择： BC
4、初始序列为 1 8 6 2 5 4 7 3 一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为：（ ）
A. 8 3 2 5 1 6 4 7
B. 3 2 8 5 1 4 6 7
C. 3 8 2 5 1 6 7 4
D. 8 2 3 5 1 4 7 6
初始化序列：1 8 6 2 5 4 7 3,，小根堆就是要求结点的值小于其左右孩子结点的值，左右孩子的大小没有关系，那么小根堆排序之后为：1 2 4 3 5 6 7 8；
中序遍历：左根右，故遍历结果为：8 3 2 5 1 6 4 7
故最后选择的结果： A
5、当 n = 5 时，下列函数的返回值是：（ ）
[cpp] view plaincopy int foo(int n) { if(n<2)return n; return foo(n-1)+foo(n-2); }A．5
B．7
C．8
D．1
这题只需把数代进去，就可以知道结果了，所以最后结果选： A
6、 S 市 A ，B 共有两个区，人口比例为 3：5 ，据历史统计 A 区的犯罪率为 0.01% ，B 区为 0.015% ，现有一起新案件发生在 S 市，那么案件发生在 A 区的可能性有多大？（ ）
A．37.5%
B．32.5%
C．28.6%
D．26.1%
这道题首先得了解犯罪率是什么？犯罪率就是犯罪人数与总人口数的比。因此可以直接得出公式：( 3 * 0.01% ) / ( 3 * 0.01% + 5 * 0.015% ) = 28.6%
当然如果不好理解的话，我们可以实例化，比如 B 区假设 5000 人，A 区 3000 人，A 区的犯罪率为 0.01%，那么 A 区犯罪人数为 30 人，B 区的犯罪率为 0.015% ，那么 B 区的犯罪人数为 75 人 ，求发生在 A 区的可能性，就是说 A 区的犯罪人数在总犯罪人数的多少，也就是 30/(30+75)=0.2857
当然，也可以回归到我们高中遗忘的知识：
假设C表示犯案属性
在A区犯案概率：P(C|A)=0.01%
在B区犯案概率：P(C|B)=0.015%
在A区概率：P(A)=3/8
在B区概率：P(B)=5/8
犯案概率：P(C)=（3/8*0.01%+5/8*0.015%)
根据贝叶斯公式：P(A|C) = P(A,C) / P(C) = [P(C|A) P(A)] / [ P(C|A) P(A)+ P(C|B) P(B) ] 也可以算出答案来
故，最后结果选择为： C
7、Unix系统中，哪些可以用于进程间的通信？（ ）
A．Socket
B．共享内存
C．消息队列
D．信号量
知识点