2016 腾讯软件开发面试题(不定项选择题【1-12】)
1、已知一棵二叉树,如果先序遍历的节点顺序是: ADCEFGHB ,中序遍历是: CDFEGHAB ,则后序遍历结果为:( ) A. CFHGEBDA B. CDFEGHBA C. FGHCDEBA D. CFHGEDBA
知识点
对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式:
因此,根据题目给出的先序遍历和中序遍历,可以画出二叉树:
二叉树遍历.png
最后结果选择: D
2、下列哪两个数据结构,同时具有较高的查找和删除性能?( ) A. 有序数组 B. 有序链表 C. AVL 树 D. Hash 表
知识点
几种常见的数据结构操作性能.png
平衡二叉树的查找,插入和删除性能都是 O(logN) ,其中查找和删除性能较好;哈希表的查找、插入和删除性能都是 O(1) ,都是最好的。所以最后的结果选择: CD
3、下列排序算法中,哪些时间复杂度不会超过 nlogn?( ) A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序
知识点
几种常见的排序算法对比.png
根据上图,观察平均情况,最好最差情况的时间复杂度基本可以知道答案了,最后结果选择: 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 时,下列函数的返回值是:( )
123456 | [cpp] view plaincopyint foo(int n) { if(n<2)return n; return foo(n-1)+foo(n-2); } |
---|
A.5 B.7 C.8 D.1
这题只需把数代进去,就可以知道结果了,所以最后结果选: A
递归.png
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/80.01%+5/80.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.信号量
知识点
故最后选择的结果为: ABCD
8、静态变量通常存储在进程哪个区?( ) A.栈区 B.堆区 C.全局区 D.代码区
静态变量的修饰关键字:static,又称静态全局变量。故最后选择的结果为: C
9、查询性能( ) A. 在Name字段上添加主键 B. 在Name字段上添加索引 C. 在Age字段上添加主键 D. 在Age字段上添加索引
结果选: B
10、IP地址131.153.12.71是一个(B)类IP地址。 A.A B.B C.C D.D
知识点
IP地址分类.png
故将 131 转为二进制 :10000011,因此为 B 类 IP 地址,结果选 B
11、下推自动识别机的语言是:(C) A.0型语言 B.1型语言 C.2型语言 D.3型语言
知识点
这是有关编译原理的。
乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系,是由诺姆·乔姆斯基于1956年提出的。它包括四个层次:
正规语言类包含于上下文无关语言类,上下文无关语言类包含于上下文相关语言类,上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系,也就是说:存在递归可枚举语言不属于上下文相关语言类,存在上下文相关语言不属于上下文无关语言类,存在上下文无关语言不属于正规语言类。
四种类型的文法的主要特点:
四种类型的文法的主要特点.png
因此答案选择:B
12、下列程序的输出是:( )
1234567 | [cpp] view plaincopy#define add(a+b) a+b int main() { printf(“%dn”,5*add(3+4)); return ; } |
---|
A.23 B.35 C.16 D.19
因为我主要是 java 开发的,可是毕竟 c 和 c++ 都是大学的必修课,因此还是有点了解的。这里主要看清楚 define ,#define 的本质就是一个代换,题目 #define add(a+b) a+b
表明了 add(a+b) 替换成 a+b ,因此代码输出的那一行其实是 printf(“%dn”,5*3+4);
,所以最后的结果选择 D