Tencent 2016 研发工程师笔试题 + 答案解析

1. 我们常说的mvc框架是指的什么的? D

A. 模块(module)-视图(view)-组件(component)
B. 模型(model)-视图(view)-组件(component)
C. 模块(module)-视图(view)-控制器(controller)
D. 模型(model)-视图(view)-控制器(controller)

2. 对某二叉树进行先序遍历的结果是ABDEFC，中序遍历的结果是DBFEAC，则后序遍历的结果是（）

简单，考察点二叉树的遍历，直接出答案：DFEBCA

3. 有一个如下的结构体：

struct A{
 long a1;
 short a2;
 int a3;
 int *a4;
};

请问在64位编译器下用sizeof(struct A)计算出的大小是多少？A

A. 24
B. 28
C. 16
D. 18

解析：
第一个，8字节
第二个，2字节，加起来是10，是2的倍数，不用对齐
第三个，4字节，加起来是14，不是4的倍数，对齐到16
第四个，8字节，加起来是24，是8的倍数，不用对齐
所以一共是24字节
多看看就背住了：
32位编译器：32位系统下指针占用4字节
char ：1个字节
char（即指针变量）: 4个字节（32位的寻址空间是2^32, 即32个bit，也就是4个字节。同理64位编译器）
short int : 2个字节
int： 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 4个字节
long long: 8个字节
unsigned long: 4个字节
64位编译器：64位系统下指针占用8字节
char ：1个字节
char(即指针变量): 8个字节
short int : 2个字节
int： 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 8个字节
long long: 8个字节
unsigned long: 8个字节

4. 以下不属于tcp连接断开的状态是？C

TIME_WAIT
FIN_WAIT_1
SYNC_SENT
FIN_WAIT_2

SYNC_SENT是连接建立时的状态。

5. 下面关于ICMP协议的描述中，正确的是（C）

ICMP协议根据MAC地址查找对应的IP地址  RARP
ICMP协议把公网的IP地址转换为私网的IP地址  NAT
ICMP协议用于控制数据报传送中的差错情况  
ICMP协议集中管理网络中的IP地址分配  DHCP

解析：
ICMP是（Internet Control Message Protocol）Internet控制报文协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息
在IPv4协议中最常用的ICMP消息类型有以下几种:
•回显应答(类型0)和回显请求(类型8):这是Ping程序发送的信息。
•目标不可达(类型3)
•源抑制(类型4):这是一种用于通知发送者路由器或者主机出现阻塞现象的ICMP消息，发送者需要降低发送速度。
•重定向(类型5):这个消息用来向可以访问两台路由器的主机说“请使用另一台路由器”。
•路由器信息应答(类型9)和路由器信息请求(类型10)
•超时(类型11):这个消息有两种用途。第一，当超过IP生存期时向发送系统发出错误信息。第二，如果分段的IP数据报没有在某种时限内重新组合，这个消息将通知发送系统。

6. 有如下一个类似跳表的数据结构：每层都是已经排好序的链表，level1层的链表有所有元素，levelN层的链表只有levelN-1的1半的元素，levelN层的结点指向levelN-1层中相同的结点。请问查找一个元素的时间复杂度是：二分查找O(logn)

7. 在一个单CPU的处理机中，有P1，P3，P5三个作业，有两个IO设备IO1，IO2，并且能够实现抢先式多任务并行工作的多道程序环境中，投入运行优先级由高到低P5，P1，P3三个作业，他们使用设备的先后顺序和占用设备的时间分别为：P1:IO2(10ms) CPU(10ms) IO1(30ms）CPU(10ms)P3:IO1(30ms) CPU(10ms) IO2(30ms）CPU(10ms)P5:CPU(20ms) IO1(30ms) CPU(10ms) IO2(15ms）忽略其他的时间损耗，3个作业投入到全部完成的情况下。请问下列哪些选项为IO2的设备利用率？E

0.55
0.26
0.48
0.5
0.39

因为是抢占式的，所以优先级最高的P5会优先执行，不用等待任何资源。
然后考虑P1，同一时刻CPU或者IO资源只能一个进程访问。

8. C语言里i=5,j=7,请问i|j等于多少？＝7

考察点：位操作
^异或（相同为0，不同为1）， ~取反
a^(~a) 得到一串1
x & (~0 << n) 将x的后n位清零
A异或0等于A呢,A异或1等于A非 A异或A = 0（都相同，各位都为0）

x & 0 = 0（与表示：都同时取值为1时,其逻辑乘积才等于1）
x & 1 = x
x & x = x

x | 0 = x （或表示，只要有一个为1，则结果为1） x | 1 = 1
x | x = x

9. 请选择下面代码的输出结果 80

int main(int argc,char*argv[])
{
    int a=10;
    int b=4;
    int c=a/b;
    int d=c*a*b++;
    std:cout<<d<<std::endl;
    return 0;
}

考察点：操作符优先级，整数除

10. 请问下列代码的输出结果有可能是哪些（AC）？

#include<stdint.h>
#include<stdio.h>
union X
{
    int32_t a;
    struct 
    {
        int16_t b;
        int16_t c;
    };
};
int main(){
    X x;
    x.a=0x20150810;
    printf("%x,%x\n",x.b,x.c);
    return 0;
}
2015,810
50810,201
810,2015
20150,810

32bit宽的数0x12345678
在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：
内存地址 0x4000 0x4001 0x4002 0x4003
存放内容 0x78 0x56 0x34 0x12
而在Big- endian模式CPU内存中的存放方式则为：
内存地址 0x4000 0x4001 0x4002 0x4003
存放内容 0x12 0x34 0x56 0x78

11. 如下代码，result变量的输出结果是多少？ 11

#include<iostream>
using namespace std;
int i=1;
class MyCls{
public:
    MyCls():m_nFor(m_nThd),m_nSec(i++),m_nFir(i++),m_nThd(i++){
        m_nThd=i;
    }
    void echo(){
        cout<<"result:"<<m_nFir+m_nSec+m_nThd+m_nFor<<endl;
    }
private:
    int m_nFir;
    int m_nSec;
    int m_nThd;
    int &m_nFor;
};
int main()
{
    MyCls oCls;
    oCls.echo();
    return 0;
}

解析：
首先要明白变量初始化的顺序是其声明的顺序,跟初始化列表中的顺序无关。所以变量的初始化顺序为m_nFir(i++)，m_nSec(i++)，m_nThd(i++)，&m_nFor(m_nThd);
i初始值为1，所以经过初始化列表初始化以后m_nFir=1，m_nSec=2，m_nThd=3，m_nFor为m_nThd的一个引用。

并且此时i的值为4，构造函数中执行语句m_nThd=i后，m_nThd=4,m_nFor是它的一个引用，自然值也为4。
输出结果m_nFir+m_nSec+m_nThd+m_nFor=1+2+4+4=11

12. 在动态分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需要修改空闲区表，造成空闲区数减1的情况是(D)

无上邻空闲区，也无下邻空闲区
有上邻空闲区，但无下邻空闲区
有下邻空闲区，但无下邻空闲区
有上邻空闲区，也有下邻空闲区
解析：
假设原本的空闲区表空闲区数目为n，注意系统收回的主存空间（已空闲）并没有被加入到空闲区表，所以空闲区数目仍为n。现在要进行空闲区与回收主存空间合并，只有将原本的空闲区中的2块合成1块，才会有数目减1的效果。

13. 对于移动平均算法，是计算某变量之前n个数值的算术平均，正确的说法是：A

空间复杂度是O(l)
空间复杂度是O(n)
空间复杂度是O(logn)
空间复杂度是O(nlogn)
解析：
任何一个算法不同情况下可能有多种解法，一般我们以时间复杂度为评判的话，就会用牺牲空间换时间。
这个算法最明显的有两种解法，
1.每次进来一个变量n，就遍历前面n个数，然后求和，再取平均，这样的话时间复杂度为O（n），空间为O(1)；
2.以空间换时间：从前往后没计算一次保留一次求和值到一个辅助空间，这样计算下一个的时候直接取得前一个和值加上当前数，再取平均得到当前平均，这样的话时间复杂度为O(1),空间为O(n).
附上一个解法：

import java.util.Scanner;  
  
public class RunningAverage {  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);      
      
        int N = Integer.parseInt(args[0]);  
          
        double[] ave = new double[N];  
        double sum = 0.0;  
        for(int i = 1; sc.hasNext(); i++) {  
            sum -= ave[i % N];  
            ave[i % N] = sc.nextDouble();  
            sum += ave[i % N];  
            if(i >= N) System.out.print(sum/N + " ");  
        }  
    }  
}

14. 某一速率为100M的交换机有20个端口，其一个端口上连着一台笔记本电脑，此电脑从迅雷上下载一部1G的电影需要的时间可能是多久？ DE

10S
20S
40S
100S
200S
交换机为独占带宽，
1G电影大小为:1GB=1024MB
带宽100M为100Mb=12.5MB

15. 在linux编程中，以下哪个TCP的套接字选项与nagle算法的开启和关闭有关？B

TCP_MAXSEG
TCP_NODELAY
TCP_SYNCNT
TCP_KEEPALIVE

解析：
Nagle算法的规则：
（1）如果包长度达到MSS，则允许发送；
（2）如果该包含有FIN，则允许发送；
（3）设置了TCP_NODELAY选项，则允许发送；
（4）未设置TCP_CORK选项时，若所有发出去的小数据包（包长度小于MSS）均被确认，则允许发送；
（5）上述条件都未满足，但发生了超时（一般为200ms），则立即发送。

16. 某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是(A)

高度等于其结点数
任一结点无左孩子
任一结点无右孩子
空或只有一个结点

考察点：树
只要是链，不一定非要无左孩子或无右孩子。即高度和结点数相等。

17. 已知关系R（F,G,H,I,J）及其上的函数相关性集合，F=(F->G,J->F,HJ->I),该关系的候选关键字是：B

FJ
HJ
HI
IJ
考察点：数据库
如果一个超关键字去掉其中任何一个字段后不再能唯一地确定记录，则称它为“候选关键字”（Candidate Key）。候选关键字既能唯一地确定记录，它包含的字段又是最精炼的。也就是说候选关键字是最简单的超关键字。

18. win32系统里，下面几个sizeof的运行结果是（D）

int intValue=1024;
char str[]="Tencent";
const char* ch=str;
sizeof(intValue)=__a___;
sizeof(str)=__b____;
sizeof(ch)=____c___;

a=1,b=1,c=1
a=4,b=4,c=4
a=4,b=7,c=4
a=4,b=8,c=4
解析：
首先int肯定是4不用说了，a＝4
第二个str［］代表char型数据，整个数组存‘Tencent\0’，所以长度为8，b＝8
第三个，32位机跟64位机的变量的差别主要在指针大小上，32位机指针长度为4，64位机指针长度为8，c＝4

19. 若系统中有五台打印机，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则在不发生死锁的情况下至多允许B个进程参与竞争

5
4
3
2
考察点：操作系统
哲学家就餐问题：当5个进程的时候如果都同时申请到了1台，就发生死锁了。如果是4个进程，那必然有一个能申请到2台。

20. 在正方体上任取三个顶点连成三角形，则所得的三角形是直角非等腰三角形的概率为？

1/14
4/7
2/7
3/7
解析：
共有8个顶点，总的有C（8,3）种选择。
直角非等腰：任取某一条边上的两点，取其以对角线为对面的那一条边上两个顶点的任意一个。一共有12条边x2种顶点=24
24/C(8,3)=24/56=3/7。

21. 以下哪个是由权值集合(16,8,4,2)构造的哈夫曼树(最优二叉树): A

解法1:
最优二叉树：将所给权集合（称为森林）按照从小到大顺序列举出来，如本题2,4,8,16；
第一步：将其中最小的两个数（2,4）作为同一父亲下的孩子，也就是叶，形成值为6的一个父结点；
第二步：此时剩下6,8,16三个数，重复步骤一，将6,8结合成又一个值为14的父结点；
第三步：将剩下的两个数连接到同一父节点下；
解法二：
最优二叉树，是指WPL（带权路径长度之和）最小
WPL(A)：161+82+23+34=50
WPL(B)：21+42+83+163=82
WPL(C)：161+42+83+23=54
WPL(D)：162+82+42+22=60
所以选A

21. 关于红黑树和AVL树，以下哪种说法不正确？

两者都属于自平衡二叉树
两者查找,插入，删除的时间复杂度相同
包含n个内部节点的红黑树的高度是O(log(n))
JDK的TreeMap是一个AVL的实现

解析：
红黑树和avl树都属于自平衡二叉树；
两者查找、插入、删除的时间复杂度相同；
包含n个内部结点的红黑树的高度是o(logn);
TreeMap是一个红黑树的实现，能保证插入的值保证排序

详细解析：

红黑树并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以 O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树的定义:
一棵AVL树满足以下的条件:
1>它的左子树和右子树都是AVL树
2>左子树和右子树的高度差不能超过1
从条件1可能看出是个递归定义,如GNU一样.

性质:
1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

23.

客户端C和服务器S之间建立一个TCP连接，该连接总是以1KB的最大段长发送TCP段，客户端C有足够的数据要发送。当拥塞窗口为16KB的时候发生超时，如果接下来的4个RTT往返时间内的TCP段的传输是成功的，那么当第4个RTT时间内发送的所有TCP段都得到了ACK时，拥塞窗口大小是：C
7KB
8KB
9KB
16KB

考察点：拥塞避免和慢启动
当拥塞发生时（超时或收到重复确认），慢启动门限ssthresh被设置为当前拥塞窗口cwnd大小（题目为16）的一半，即8。同时cwnd重置为1。新的数据被接收，则cwnd增加，规则为ssthresh之前，慢启动，即cwnd指数增长；到达ssthresh之后，拥塞避免，即cwnd加1。

详细参考

24. 关于epoll和select的区别，哪些说法是正确的？ABC

epoll和select都是I/O多路复用的技术，都可以实现同时监听多个I/O事件的状态
epoll相比select效率更高，主要是基于其操作系统支持的IO事件通知机制，而select是基于轮询机制
epoll支持水平触发和边沿触发两种模式
select能并行支持I/O比较小，且无法修改

select支持io较少，这个是根据操作系统支持的数量定的，不过记得那个数值可以用sysctl修改，所以觉得d不对。

25. Internet的网络层含有的协议是？

IP
ICMP
ARP
RARP

解析：
传输层协议：TCP、UDP、SCTP
网络层协议：IP、ARP、RARP、ICMP、IGMP、OSPF
应用层协议：http，FTP、SMTP、RIP、DNS
TCP（Transmission Control Protocol 传输控制协议）是为应用程序提供完整的传输服务的，是一个传输协议所以在传输层（Transport layer）而IP是网络传输时逻辑寻址用的，所以在网络层Network layer

26. 以下是C++的不同数据类型值的比较语句，请问这些判断语句中作为条件部分的语句编写有问题的有:CD

如果变量bVar是布尔类型：if(false==bVar){doSomeThing();}
如果变量nVar是int型：if(0==nVar){doSomeThing();}
如果变量fVar为浮点型:if(0.02=fVar){doSomeThing();}
如果变量sVar为字符串型：if（””==sVar){doSomeThing();}

解析：
c选项，float有精度问题，尾数不精确，比较会出问题
d选项，字符串比较，一般用strcmp（str1，str2），直接用==比较两个字符串，应该比较的是字符串的首地址是否相等，那就不是真正的字符串比较了

27. TCP链接中主动断开链接netstat观察可能出现的状态流转是：CD

ESTABLISHED->CLOSE_WAIT->TIME_WAIT->CLOSED
ESTABLISHED->TIME_WAIT->CLOSE_WAIT->CLOSED
ESTABLISHED->FIN_WAIT_1->FIN_WAIT_2->TIME_WAIT->CLOSED
ESTABLISHED->FIN_WAIT_1->TIME_WAIT->CLOSED

解析：
跳过FIN_WAIT_2,证明被动方也完成了数据传输任务，直接把ACK和FIN一起发给了主动方，因此主动方从FIN_WAIT_1直接跳过FIN_WAIT_2进入TIME_WAIT

28. 以下涉及到内存管理的代码段中，有错误的是：ABD

1
2
3

int *a=new int(12);
//..... 
free(a);

int *ip=static_cast<int*>(malloc(sizeof(int)));
*ip=10;
//.....
delete ip;

1
2
3

double *a=new double[1];
//.... 
delete a;

int *ip=new int(12);
for(int i=0;i<12;++i){
ip[i]=i;
}
delete []ip;

解析：
new 和delete 配套使用 free和malloc配套使用.
c中a是一个数组，应该用delete []a，但是在基本类型数组来说，delete a和delete []a的效果是一样的。如果，a是一个自定义对象的数组，那么只能用delete []a。
关于D，注意new int(12)和new int[12]的区别。new int(12)是生成了一个值为12的int变量，new int[12]才是生成一个大小为12的数组。所以，delete []ip是错误的，D错。

29. 下面哪些特性可能导致代码体积膨胀:ABC

宏定义
模板
内联函数
递归

解析：
A选项宏定义本质是文本替换，肯定是可能导致代码体积膨胀的
B选项模板在编译时生成对应的类/函数，所以也是可能的。
C选项重点解释，内联也是在编译时替换，所以也可能导致代码体积膨胀。
但是注意了：
若这个函数被调用了一次，那么内联直接被插入到函数调用出，就直接没有了这个函数符号了，若加上优化，这一句代码可能会被优化没有，所以，也可能使代码体积减小。
D选项是容易爆栈，不是代码区。

30.小明设计了如下的学籍管理系统：

已知关系：学籍(学号，学生姓名) PK=学号
成绩（科目号，成绩，学号） PK=科目代码，FK=学号
已有表记录如下，请给出能够插入的成绩记录

(1，99，2)
(5，68，1)
(3，70，3)
(7，45，null)

成绩表中主键是“PK=科目代码”，所以科目代码要唯一，所以可排除AC；在数据库完整性里有说：外键必须可以找到或者为空，所以 B是可以的，而D为空，所以也满足。故选BD