美团研发岗笔试真题练习（选择题）_现有二叉搜索树(bst)前序遍历结果序列为abdefgc,中序遍历结果序列为debgfac,请问

一、

1. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是？
   答： 3个。
   笔记：栈是后进先出，队列是先进先出。画个图，十分明了。
   
2. 现有二叉搜索树（BST）前序遍历结果序列为abdefgc，中序遍历结果序列为debgfac，请问后序遍历结果序列?
   
   答： 如图所示为 defgbca。
   笔记：
   （1）前序：中左右
   （2）中序：左中右
   （3）后续：左右中
3. 以下设计模式中，哪一项不属于结构性模式？
   A 适配器模式
   B 代理模式
   C 命令模式
   D 装饰模式
   答： 选C。
   笔记：设计模式（Design pattern）代表了最佳的实践 ，通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。结构型模式共七种：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。From 设计模式归类图。
   
4. 下面哪个是版本控制工具？
   A safari
   B svn
   C git
   D xcode
   答： BC。
   笔记： 版本控制工具主要有三个：CVS、SVN,Git。 可以把一个版本控制系统（缩写VCS）理解为一个“数据库”，在需要的时候，它可以帮你完整地保存一个项目的快照。当你需要查看一个之前的快照（称之为“版本”）时，版本控制系统可以显示出当前版本与上一个版本之间的所有改动的细节。目的：做数据备份、版本管理。提高代码质量、提高协同/多人开发效率、明确分工责任、凡是需要持续修改的文档资料都可以进行版本管理。
   Git： Git是目前世界上最先进的分布式版本控制系统，使用Git和Gitlab搭建版本控制环境是现在互联网公司最流行的版本控制方式。Git是一个免费的开源分布式版本控制系统，旨在快速高效地处理从小型到大型项目的所有事务。Git易于学习，占用内存小，具有闪电般快速的性能。Github地址：https://git-scm.com/
   SVN: TortoiseSVN是一款非常易于使用的跨平台的 版本控制/版本控制/源代码控制软件。
   CVS: CVS是版本控制系统，是源配置管理（SCM）的重要组成部分。使用它，您可以记录源文件和文档的历史记录。老牌的版本控制系统，它是基于客户端/服务器的行为使得其可容纳多用户，构成网络也很方便。这一特性使得CVS成为位于不同地点的人同时处理数据文件（特别是程序的源代码）时的首选。
5. 下面哪些机制可以用于进程间通信？
   A Socket
   B Named pipe
   C Named event
   D Critical Section
   E Shared memory
   F Virtual memory
   答： ABE。
   笔记： 进程间的通信指的是：在不同进程之间传播或者交换信息。 进程间通信都有：1.管道（pipe）及有名管道（named pipe） 2.信号（signal）3.消息队列（message queue）4.共享内存（shared memory） 5.信号量（semaphore）6.套接字（socket）。

二、

1. 单选题：在OSI参考模型 中，物理层的作用是？
   A 建立和释放连接
   B 透明地传输比特流
   C 在物理实体之间传送数据帧
   D 发送和接受用户数据
   答： 选择B
   笔记： OSI参考模型是指开放系统互连参考模型（Open System Interconnection），共七层。1~7从低往上依次为：
   物理层： 通过媒介传输比特,确定机械及电气规范（比特Bit）

   数据链路层： 将比特组装成帧和点到点的传递（帧Frame）

   网络层： 负责数据包从源到宿的传递和网际互连（包PackeT）

   传输层： 提供端到端的可靠报文传递和错误恢复（段Segment）

   会话层： 建立、管理和终止会话（会话协议数据单元SPDU）

   表示层： 对数据进行翻译、加密和压缩（表示协议数据单元PPDU）

   应用层： 允许访问OSI环境的手段（应用协议数据单元APDU）

2. 不定项选题。在C++STL中常用的容器和类型，下面哪些支持下标"[]"运算？
   A vector
   B list
   C deque
   D map
   E set
   F unordered_map
   G unordered_set
   H stack
   I string
   答： 选择ACDFI。
   笔记： STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。 STL 是 C++ 标准库的一部分，不用单独安装。deque 为双向队列，支持快速随机访问，在头尾位置插入或删除速度很快” ，因此deque支持索引[]运算。

3. 单选题
   在以下协议中，那个协议与其他协议是不属于同一类的( B )
   A FTP
   B ICMP
   C TELNET
   D SMTP
   E DNS
   答： 除B外其它都是应用层协议。
   笔记：
   FTP（File Transfer Protocol）： 文件传送协议，这是应用层协议；
   ICMP（Internet Control Message Protocol）：网际控制报文协议，是互联网的标准协议；
   TELNET：远程终端协议，是TCP/IP协议中的一员，应用层的协议。
   SMTP：简单邮件传送协议，基于TCP/IP的应用层协议。
   DNS：域名系统服务协议，在Internet上将域名和ip地址对应起来的一种协议，可以使用户更加方便的访问互联网，而不用记住很多很长的ip地址。
   选择B的原因呢是：
   网络层： IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP。
   传输层： UDP协议、TCP协议、SPX。
   应用层： FTP（文件传送协议）、Telenet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议， SNMP协议， TFTP、Telnet、WWW、NFS。
   怎么感觉这全是计算机网络的知识！！

4. 单选题
   从2到5中选两个数，第一个数较大，将两数之和告诉甲，两数之差告诉乙，两个人根据自己手上的数都算不出来答案，求这两个数分别是多少？
   A 4，3
   B 5，3
   C 5，2
   D 4，2
   答： A 甲知道和为7，可推得是：2与5、3与4。 乙知道差为1，可推得是：2与3、3与4、4与5。 都不能单独确定。
   笔记： 答题时分别写出甲能推出的结果和乙能推出的结果，然后求交集。

5. 不定项选题
   选项中哪些是SQL的DML语句？
   A select
   B insert
   C alter
   D delete
   E create
   答： BD。
   笔记： SQL还没有系统学过。关于这部分知识如图所示：
   DML（data manipulation language）是数据操纵语言：它们是UPDATE、INSERT、DELETE。

6. 不定项选题
   对于以下用数组存储的二叉树A B C D E采用中序和前序遍历的结果是（CA）
   A. A B D E C
   B. D E B C A
   C. D B E A C
   D. C E D B A
   答： 说实话有点看不懂。有人说是：以数组存储，是按照层次序来保存的。 所以A在第一层BC在第二层DE在第三层。So：
   

7. 单选题。以下属于网络层协议的是？
   A SSH
   B RIP
   C RTP
   D UDP
   答： 选B。 网络层： IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP。太多了。

8. 单选题
   如果第一组2个数字之和为9825，那么第二组的2个数字之和为多少？第一组6128+9091；第二组：8159+1912。
   A 10071
   B 4677
   C 4678
   D 8679
   答：D。把数字给上下左右颠倒过来：6128+9091–>>8219+1606=9825所以8159+1912–>>6518+2161=8679。
   这个操作简直神了！考逻辑的吧！

9. 不定项选题
   机器学习中做特征选择时，可能用到的方法有？
   A 卡方
   B 信息增益
   C 平均互信息
   D 期望交叉熵
   答：全选。这题怎么看怎么感觉超纲了。

笔记： 常见的六种特征选择方法：

• DF(Document Frequency) 文档频率
  DF:统计特征词出现的文档数量，用来衡量某个特征词的重要性

• MI(Mutual Information) 互信息法
  互信息法用于衡量特征词与文档类别直接的信息量。
  如果某个特征词的频率很低，那么互信息得分就会很大，因此互信息法倾向”低频”的特征词。
  相对的词频很高的词，得分就会变低，如果这词携带了很高的信息量，互信息法就会变得低效。

• (Information Gain) 信息增益法
  通过某个特征词的缺失与存在的两种情况下，语料中前后信息的增加，衡量某个特征词的重要性。

• CHI(Chi-square) 卡方检验法
  利用了统计学中的”假设检验”的基本思想：首先假设特征词与类别直接是不相关的
  如果利用CHI分布计算出的检验值偏离阈值越大，那么更有信心否定原假设，接受原假设的备则假设：特征词与类别有着很高的关联度。

• WLLR(Weighted Log Likelihood Ration)加权对数似然

• WFO（Weighted Frequency and Odds）加权频率和可能性

10. 单选题。SNMP所采用的传输层协议是什么？
    A UDP
    B ICMP
    C TCP
    D IP
    答： SNMP：简单网络管理协议，使用UDP 161端口

三、

1. 当使用美团团购购买套餐后，后台发生了哪些业务流程？
   答：
   1).通过域名，dns解析到对应ip，请求网关，通过负载均衡和转发请求到对应服务器
   2).三次握手，请求购买套餐接口，查询用户token是否有效，数据库数据是否有库存，是否符合情况
   3).符合接口逻辑，返回success，并通过kafka等消息将操作 发送给别的服务
   4).将返回数据返回给浏览器，浏览器解析html代码，呈现用户
2. 当用户第一次打开并登陆外卖App后会看到App的首页，打开和登陆外卖App的过程中发生了哪些具体的动作行为以及可能导致的缺陷？
   答：
   1). 首次打开App，App会进行应用的初始化和相关数据的加载。 可能的缺陷包括启动闪退，打开过程加载时间过长，App启动过程的界面显示错误 ；
   2). 登陆App的过程中会进行用户名和密码的校验，以及根据分控策略阻止异常账号的登陆。 可能的缺陷包括用户名密码未加密存储和显示，账户登陆异常信息提示错误 ；
   3). App首页加载： 用户位置定位，根据用户位置展示附近商圈的外卖门店信息。 可能的缺陷包括用户位置定位失败或者错误，外卖门店信息加载失败和错误，网络加载失败等。
3. 当使用美团App扫描美团单车上的二维码后，发生了什么？
   答：
   1). 二维码识别：开锁url、车辆id等
   2). 网络通信和页面渲染
   3). 业务逻辑判断：车锁状态正常、账户余额充足、用户身份正常、用户GPS位置正常
   4). 执行开锁、计费开始
4. 当前的移动互联网产品，大都为以移动App形式呈现的一个典型的Client/Server或客户/服务器的体系结构：用户通过UI操作触发移动用户端发送一个网络请求给后台服务，众多后台微服务以及各种数据存储相互协作，得到用户想要的信息，并发送回移动应用端。移动端根据接收到的响应，展示不同的信息给用户。
   假设当你在移动App中，点击一个按钮，比方说，美团的登陆按钮，如果从移动App的界面看起来，任何事情都没有发生，你将如何分析定位问题大致发生在什么地方？
   答：
   设备问题：
   1、网络延迟，响应没有及时出现，超时
   2、手机卡顿，出现死机现象
   3、响应被中断
   程序问题：
   1、按钮的监听事件未正确调用，或者干脆就没有添加监听
   2、监听确认被调用，但监听过程出现错误或异常，例如参数传输失败。
   3、前端调用接口错误，如后端出现运行时异常，没有给出相应的提示消息