【程序员面试题2016】腾讯企鹅

2024-03-13 05:30

本文主要是介绍【程序员面试题2016】腾讯企鹅,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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 时,下列函数的返回值是:( )

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、下列程序的输出是:( )

A.23
B.35
C.16
D.19

结果选择 D

这篇关于【程序员面试题2016】腾讯企鹅的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/803770

相关文章

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统? 在我参与的项目中,有使用过实时操作系统。实时操作系统(RTOS)在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中,需要对多个传感器的数据进行实时采集和处理,并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间,确保关键任务在规定的时间内完成。 使用实时操作系统的

一些其他面试题

阿里二面:那你来说说定时任务?单机、分布式、调度框架下的定时任务实现是怎么完成的?懵了。。_哔哩哔哩_bilibili 1.定时算法 累加,第二层每一个格子是第一层的总时间400 ms= 20 * 20ms 2.MQ消息丢失 阿里二面:高并发场景下引进消息队列有什么问题?如何保证消息只被消费一次?真是捏了一把汗。。_哔哩哔哩_bilibili 发送消息失败

zookeeper相关面试题

zk的数据同步原理?zk的集群会出现脑裂的问题吗?zk的watch机制实现原理?zk是如何保证一致性的?zk的快速选举leader原理?zk的典型应用场景zk中一个客户端修改了数据之后,其他客户端能够马上获取到最新的数据吗?zk对事物的支持? 1. zk的数据同步原理? zk的数据同步过程中,通过以下三个参数来选择对应的数据同步方式 peerLastZxid:Learner服务器(Follo

java常用面试题-基础知识分享

什么是Java? Java是一种高级编程语言,旨在提供跨平台的解决方案。它是一种面向对象的语言,具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么? Java的主要特点包括: 简单性:Java的语法相对简单,易于学习和使用。面向对象:Java是一种完全面向对象的语言,支持封装、继承和多态。跨平台性:Java的程序可以在不同的操作系统上运行,称为"Write once,

AIGC6: 走进腾讯数字盛会

图中是一个程序员,去参加一个技术盛会。AI大潮下,五颜六色,各种不确定。 背景 AI对各行各业的冲击越来越大,身处职场的我也能清晰的感受到。 我所在的行业为全球客服外包行业。 业务模式为: 为国际跨境公司提供不同地区不同语言的客服外包解决方案,除了人力,还有软件系统。 软件系统主要是提供了客服跟客人的渠道沟通和工单管理,内部管理跟甲方的合同对接,绩效评估,BI数据透视。 客服跟客人

【Kubernetes】常见面试题汇总(三)

目录 9.简述 Kubernetes 的缺点或当前的不足之处? 10.简述 Kubernetes 相关基础概念? 9.简述 Kubernetes 的缺点或当前的不足之处? Kubernetes 当前存在的缺点(不足)如下: ① 安装过程和配置相对困难复杂; ② 管理服务相对繁琐; ③ 运行和编译需要很多时间; ④ 它比其他替代品更昂贵; ⑤ 对于简单的应用程序来说,可能不

【附答案】C/C++ 最常见50道面试题

文章目录 面试题 1:深入探讨变量的声明与定义的区别面试题 2:编写比较“零值”的`if`语句面试题 3:深入理解`sizeof`与`strlen`的差异面试题 4:解析C与C++中`static`关键字的不同用途面试题 5:比较C语言的`malloc`与C++的`new`面试题 6:实现一个“标准”的`MIN`宏面试题 7:指针是否可以是`volatile`面试题 8:探讨`a`和`&a`

Laravel 面试题

PHP模块 PHP7 和 PHP5 的区别,具体多了哪些新特性? 性能提升了两倍 结合比较运算符 (<=>) 标量类型声明 返回类型声明 try…catch 增加多条件判断,更多 Error 错误可以进行异常处理 匿名类,现在支持通过new class 来实例化一个匿名类,这可以用来替代一些“用后即焚”的完整类定义 …… 了解更多查看文章底部链接 PHP7 新特性 为什么 PHP

【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念?

大家好,我是锋哥。今天分享关于 【说说 Redis 哈希槽的概念?】面试题,希望对大家有帮助; 说说 Redis 哈希槽的概念? Redis 集群没有使用一致性 hash,而是引入了哈希槽的概念,Redis 集群有 16384 个哈希槽,每个 key 通过 CRC16 校验后对 16384 取模来决定放置哪个槽, 集群的每个节点负责一部分 hash 槽。

【Kubernetes】常见面试题汇总(一)

目录 1.简述 etcd 及其特点? 2.简述 etcd 适应的场景? 3.简述什么是Kubernetes? 4.简述 Kubernetes和 Docker的关系? 1.简述 etcd 及其特点? (1)etcd 是Core0s 团队发起的开源项目,是一个管理配置信息和服务发现(service discovery)的项目,它的目标是构建一个高可用的分布式键值(keyvalue)数据