腾讯2016研发工程师笔试题（三）选择题知识点总结

1、选择第一题：

MVC框架指的是：模型(model)-视图(view)-控制器(controller)。

2、选择第二题：

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

知识整理：
先序遍历：根 -> 左子树 -> 右子树
中序遍历：左子树 -> 根 -> 右子树
后序遍历：左子树 -> 右子树 -> 根

解题步骤：
1、根据先序遍历，根节点为A ；A左子树是DBFE，右子树是C 。
2、根据先序遍历，A左子树中，B是A的左孩子 。
4、根据中序遍历，D是B的左孩子，EF是B的右子树 。
5、同上得树结构如图，后序遍历 DFEBCA 。

3、选择第三题：

有一个如下的结构体：

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

请问在64位编译器下用sizeof(struct A)计算出的大小是多少？ (答案：8+4+4+8=24)

4、选择第四题：

tcp连接断开的状态：FIN_WAIT_1 FIN_WAIT_2 TIME_WAIT

5、选择第五题：

关于ICMP协议的描述：ICMP协议用于控制数据报传送中的差错情况。

相关知识点总结：
RARP协议用于根据MAC地址查找对应的IP地址
NAT协议用于把公网的IP地址转换为私网的IP地址
DHCP协议用于集中管理网络中的IP地址分配

6、选择第六题：
有如下一个类似跳表的数据结构：

每层都是已经排好序的链表，level1层的链表有所有元素，levelN层的链表只有levelN-1的1半的元素，levelN层的结点指向levelN-1层中相同的结点。请问查找一个元素的时间复杂度是：O(logn)

分析：

二分查找时间复杂度计算： 
总共有n个元素， 
渐渐跟下去就是n,n/2,n/4,....n/2^k，其中k就是循环的次数 
由于n/2^k取整后>=1 
即令n/2^k=1 
可得k=log2n,（是以2为底，n的对数） 
所以时间复杂度可以表示O()=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的设备利用率为（）

本题考察的知识点是操作系统，没学过。答案是0.39

8、选择第八题：

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

分析： | 是位操作符 或 的意思。先把5和7转化为二进制 101 和 111，按位或就是 111 ，所以答案是7。

9、选择第九题：

下面代码的输出结果是多少？

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;
}

分析：int d=c*a*b++; 后缀自加运算符非优先级高于算术运算符，所以先执行b++，此时b的值为5，但b++的值仍然为4；
接着按自左向右的顺序执行cab++,等价于c*a(b++),即2104，所以结果为80.

本题考察 i++ 和 ++i 的区别：

++i 被称为前置版本递增运算符，这种形式的运算符首先将运算对象加1，然后把改变后的对象作为求值结果；
i++ 被称为后置版本递增运算符，它也会将运算对象加1，但是求值结果是运算对象改变前那个值得副本。

C++通常优先使用前置版本！！！

10、选择第十题：

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

#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;
}

分析：
0x20150810是十六进制数字 每一位占4bits，两个数字占一个字节。这个数字刚好占4个字节。 输出的时候，机器不同，会有大端小端。就是从左存，还是从右存。 20 15 08 10 这个好理解。 10 08 15 20 主要是反着存的时候，输出的时候按两个字节来取，08 10 20 15，前面的零自动忽略。

11、选择第十一题：

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

#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);
程序初始化的时候是根据在类中声明的顺序进行初始化。所以先给m_nFir赋值……一直到m_nThd = 3。
然后执行m_nFor = m_nThd。此时m_nFor和 m_nThd都是3。但是i = 4。
然后执行构造函数，m_nThd = 4。因为m_nFor是引用类型，所以m_nFor此时也变为4。
所以答案是1+2+4+4=11.

12、选择第十二题：

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

知识点总结：

作业归还分区，要调整空闲区表，把空闲区表调整成空闲区长度递减的次序排列登记。可变分区分配方式下，当收回主存时，应检查是否有与归还区相邻的空闲区，若有，则应合并成一个空闲区。

相邻可能有上邻空闲区、下邻空闲区、既上邻又下邻空闲区、既无上邻又无下邻空闲区四种情况。
有上邻空闲区，但无下邻空闲区。只修改上邻空闲区长度（为收回的空闲区长度与原上邻区长度之和），空闲区数不变
无下邻空闲区，但有下邻空闲区。改记录这个下邻空闲区记录的地址为收回空闲区的地址，长度为下邻空闲区的长度和收回空闲区的长度，空闲区数不变
有上邻空闲区，也有下邻空闲区。改记录上邻区记录的长度（为上邻区长度、下邻区长度和收回区长度之和），再把下邻区记录的标志位改为空，即空闲区数-1
无上邻空闲区，也无下邻空闲区。那么找一个标志位为空的记录，记下该回收区的起始地址和长度，且改写相应的标志位为未分配，表明该登记栏中指示了一个空闲区。 空闲区数+1

13、选择第十三题：

对于移动平均算法，是计算某变量之前n个数值的算术平均，它的空间复杂度是O(l)，时间复杂度是O(n)

分析：

任何一个算法不同情况下可能有多种解法，一般我们以时间复杂度为评判的话，就会用牺牲空间换时间。

这个算法最明显的有两种解法：

1.每次进来一个变量n，就遍历前面n个数，然后求和，再取平均，这样的话时间复杂度为O（n），空间为O(1)；

2.以空间换时间：从前往后没计算一次保留一次求和值到一个辅助空间，这样计算下一个的时候直接取得前一个和值加上当前数，再取平均得到当前平均，这样的话时间复杂度为O(1),空间为O(n)。

14、选择第十四题：

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

分析：
网速为100Mbps，电影1G为1GByte，先应该变为相同的单位。
1*1024MByte/(100/8) =81.92s 。这是最大速度了，所以大于这个时间都是合理的。

15、选择第十五题：

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

16、选择第十六题：

某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是(高度等于其结点数)

分析：

原理如下：
先序遍历顺序是：M-L-R;
后序遍历顺序是：L-R-M;
可以看到，只有中间的结点（M）顺序变化了，左右结点相对位置是不变的。那可以推断出，要满足题意的话“二叉树的先序序列与后序序列正好相反”，说明整个二叉树左子树或者右子树有一个没有（遍历就成了，先：M-L ；后：L-M 或者 先：M-R ；后：R-M ）也就是必然是一条链。

17、选择第十七题：

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

分析：由依赖关系可以得出：J可以推导出F，F推导出G，H和J联合可以推导出I，即利用H和J可以推导出所有的字段。

18、选择第十八题：

win32系统里，下面几个sizeof的运行结果是（a=4,b=8,c=4）

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

分析：
int占4，a＝4
str［］代表char型数据，整个数组存‘Tencent\0’，长度为8，b＝8
32位机跟64位机的变量的差别主要在指针大小上，32位机指针长度为4，64位机指针长度为8，c＝4

19、选择第十九题：

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

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

20、选择第二十题：

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

分析：

8个顶点中选出3个点可以构建三角形，即可构建c(8,3)个三角形，其中C(8,3)=8!/3!(8-3)!=56，非等腰直角三角形每条边与对面下边的两个角组成的三角形。每条边2个，总共12条边，即212=24种情况，所以概率为24/56=3/7

21、选择第二十一题：

哈夫曼树(最优二叉树)：哈夫曼树构造离树根越近其权值越大。

22、选择第二十二题：

关于红黑树和AVL树：1、两者都属于自平衡二叉树；2,、两者查找,插入，删除的时间复杂度相同；3、包含n个内部节点的红黑树的高度是O(log(n))

23、选择第二十三题：

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

分析：

16KB超时，阈值变为8KB，客户端从1KB开始穿（执行快开始算法）
1RTT 结束，1KB->2KB
2RTT 结束，2KB->4KB
3RTT 结束，4KB->8KB（到达阈值，执行拥塞避免算法）
4RTT 结束，8KB->9KB

24、选择第二十四题：

关于epoll和select的区别：1、epoll和select都是I/O多路复用的技术，都可以实现同时监听多个I/O事件的状态；2、epoll相比select效率更高，主要是基于其操作系统支持的I/O事件通知机制，而select是基于轮询机制；3、epoll支持水平触发和边沿触发两种模式。

25、选择第二十五题：

Internet的网络层含有的协议是？IP ICMP ARP RARP

物理层 RJ45 CLOCK IEEE802.3 (中继器 集线器 网关)
数据链路层 PPP FR HDLC VLAN MAC (网桥 交换机)
网络层 IP ICMP ARP RARP OSPF IPX RIP IGRP (路由器)
传输层 TCP UDP SPX
会话层 NFS SQL NETBIOS RPC
表示层 JPEG MPEG ASII
应用层 FTP DNS Telnet SMTP HTTP WWW NFS

26、选择第二十六题：

以下是C++的不同数据类型值的比较语句，请问这些判断语句中作为条件部分的语句编写有问题的有:C
A. 如果变量bVar是布尔类型：if(false==bVar){doSomeThing();}
B. 如果变量nVar是int型：if(0==nVar){doSomeThing();}
C. 如果变量fVar为浮点型:if(0.02=fVar){doSomeThing();}
D. 如果变量sVar为字符串型：if（""==sVar){doSomeThing();}

分析：

选项Cif(0.02=fVar){doSomeThing();}中将比较相等符号==写成了赋值符号=；与此同时，浮点做相等比较不可以用==,应该用相减后的值是否在正负0.00000001之间来判断是否相等。

27、选择第二十七题：

TCP链接中主动断开链接netstat观察可能出现的状态流转是：
1、ESTABLISHED->FIN_WAIT_1->FIN_WAIT_2->TIME_WAIT->CLOSED 是正常的关闭过程
2、ESTABLISHED->FIN_WAIT_1->TIME_WAIT->CLOSED 是同时关闭可能出现的过程

28、选择第二十八题：

涉及到内存管理的代码段中，需要注意的是：new和delete搭配，malloc和free搭配，注意new int(12)和new int[12]的区别以及关于delete a和delete []a的区别。

29、选择第二十九题：

下面哪些特性可能导致代码体积膨胀:宏定义（本质是文本替换，肯定是可能导致代码体积膨胀）；模板（模板的调用，会根据调用的参数，生成模板对应的实际调用的函数体，如果调用的参数不同，会生成不同的代码，所以会导致代码膨胀）；内联函数（内联函数会拷贝至调用的位置，如果调用多次回导致代码膨胀）。

30、选择第三十题：

小明设计了如下的学籍管理系统：
已知关系：
学籍(学号，学生姓名) PK=学号
成绩（科目号，成绩，学号） PK=科目代码，FK=学号
已有表记录如下，请给出能够插入的成绩记录:BD

学籍表：

成绩：

A. (1，99，2)
B. (5，68，1)
C. (3，70，3)
D. (7，45，null)

分析：

定义：
主键 -- 唯一标识一条记录，不能有重复的，不允许为空
外键 -- 表的外键是另一表的主键 , 外键可以有重复的 , 可以是空值
索引 -- 该字段没有重复值，但可以有一个空值

作用：
主键 -- 用来保证数据完整性
外键 -- 用来和其他表建立联系用的
索引 -- 是提高查询排序的速度

个数：
主键 -- 主键只能有一个
外键 -- 一个表可以有多个外键
索引 -- 一个表可以有多个唯一索引

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