2016 腾讯软件开发面试题(部分)

2016 腾讯软件开发面试题(不定项选择题【1-12】)

1、已知一棵二叉树,如果先序遍历的节点顺序是: ADCEFGHB ,中序遍历是: CDFEGHAB ,则后序遍历结果为:( ) A. CFHGEBDA B. CDFEGHBA C. FGHCDEBA D. CFHGEDBA

知识点

对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式:

  • 先序遍历(根左右) 若二叉树为空,则不进行任何操作:否则 1、访问根结点。 2、先序方式遍历左子树。 3、先序遍历右子树。
  • 中序遍历 (左根右) 若二叉树为空,则不进行任何操作:否则 1、中序遍历左子树。 2、访问根结点。 3、中序遍历右子树。
  • 后序遍历 (左右根) 若二叉树为空,则不进行任何操作:否则 1、后序遍历左子树。 2、后序遍历右子树。 3、放问根结点。

因此,根据题目给出的先序遍历和中序遍历,可以画出二叉树:

二叉树遍历.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.信号量

知识点

  1. 管道(Pipe)及有名管道(named pipe):管道可用于具有亲缘关系进程间的通信,有名管道克服了管道没有名字的限制,因此,除具有管道所具有的功能外,它还允许无亲缘关系进程间的通信;
  2. 信号(Signal):信号是比较复杂的通信方式,用于通知接受进程有某种事件发生,除了用于进程间通信外,进程还可以发送信号给进程本身;linux除了支持Unix早期信号语义函数sigal外,还支持语义符合Posix.1标准的信号函数sigaction(实际上,该函数是基于BSD的,BSD为了实现可靠信号机制,又能够统一对外接口,用sigaction函数重新实现了signal函数);
  3. 报文(Message)队列(消息队列):消息队列是消息的链接表,包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息,被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少,管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  4. 共享内存:使得多个进程可以访问同一块内存空间,是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制,如信号量结合使用,来达到进程间的同步及互斥。 信号量(semaphore):主要作为进程间以及同一进程不同线程之间的同步手段。
  5. 套接口(Socket):更为一般的进程间通信机制,可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的,但现在一般可以移植到其它类Unix系统上:Linux和System V的变种都支持套接字。

故最后选择的结果为: 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年提出的。它包括四个层次:

  • 0-型文法(无限制文法或短语结构文法)包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串,这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别,后者是前者的一个真子集,是能够被一个总停机的图灵机判定的语言。
  • 1-型文法(上下文相关文法)生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号,而 α, β 和 γ 是包含非终结符号与终结符号的字串;α, β 可以是空串,但 γ 必须不能是空串;这种文法也可以包含规则 S->ε ,但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
  • 2-型文法(上下文无关文法)生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号,γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
  • 3-型文法(正规文法)生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号;如果所有产生式的右侧都不含初始符号 S ,规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受,也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。

正规语言类包含于上下文无关语言类,上下文无关语言类包含于上下文相关语言类,上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系,也就是说:存在递归可枚举语言不属于上下文相关语言类,存在上下文相关语言不属于上下文无关语言类,存在上下文无关语言不属于正规语言类。

四种类型的文法的主要特点:

四种类型的文法的主要特点.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

原文发布于微信公众号 - Linyb极客之路(gh_c420b2cf6b47)

原文发表时间:2017-06-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

20700
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列一】 线性表

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

72530
来自专栏Linyb极客之路

Java开发者易犯错误Top10

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList,这不是java.util.ArrayList类,java.util.Array...

13240
来自专栏编程理解

数据结构(五):哈夫曼树(Huffman Tree)

哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。

30420
来自专栏Android开发指南

13:常用类

37880
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

22930
来自专栏开发与安全

数据结构:双向链表实现队列与循环链表

一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

29380
来自专栏Kevin-ZhangCG

Java集合总结

17820
来自专栏轮子工厂

深入理解Java中的List、Set与Map集合

12240
来自专栏决胜机器学习

PHP数据结构(十六) ——B树

PHP数据结构(十六)——B树 (原创内容,转载请注明来源,谢谢) 一、概述 B树在很多地方被称为“B-树”,因为B树的原英文名称为B-tre...

522110

扫码关注云+社区

领取腾讯云代金券