牛客网-4 腾讯2016笔试题

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

已知关系：学籍(学号，学生姓名) PK=学号

成绩（科目号，成绩，学号） PK=科目代码，FK=学号

已有表记录如下，请给出能够插入的成绩记录

正确答案: B D

(1，99，2)

(5，68，1)

(3，70，3)

(7，45，null)

　　主键不重复不为空，外键是另一个表的主键，必须能够给找到，可以重复可以空！

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

正确答案: A B C 你的答案: A C (错误)

宏定义

模板

内联函数

递归

　　总之 模板会造成代码膨胀

    cout<<typeid(d).name()<<endl;
    cout<<typeid(double).name()<<endl;

　　typeid可提供运行时信息，name函数打印出类型的首字母

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

正确答案: A B D 你的答案: A B (错误)

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

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

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

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

这里注意D答案，小心被骗， int（12）是初始化了一个值为12的int整型。int[12]是初始化了12个变量的数组

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

正确答案: C D 你的答案: C (错误)

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

添加笔记
求解答(35)
收藏
纠错

本题知识点

网络基础

共有18条讨论添加解析

不吃葡萄皮

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

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

正确答案: A B C D 你的答案: A B C (错误)

IP

ICMP

ARP 已知ip地址求mac地址

RARP  已知mac地址求ip地址

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

正确答案: A B C 你的答案: A (错误)

epoll和select都是I/O多路复用的技术，都可以实现同时监听多个I/O事件的状态

epoll相比select效率更高，主要是基于其操作系统支持的I/O事件通知机制，而select是基于轮询机制

epoll支持水平触发和边沿触发两种模式

select能并行支持I/O比较小，且无法修改

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

正确答案: C 你的答案: 空 (错误)

7KB

8KB

9KB

16KB

根据题意当拥塞窗口为16kb的时候发生了超时，那么接下来sshthresh也就是慢启动门限被设置为 16/2=8。cwud报文段被重置为1，那么超时之后的4个rtt会在第四个rtt的时候执行慢kaishi + 1 = 9

拥塞避免和慢启动

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

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

正确答案: D

两者都属于自平衡二叉树

两者查找,插入，删除的时间复杂度相同

包含n个内部节点的红黑树的高度是O(log(n))

JDK的TreeMap是一个AVL的实现

关于红黑树和AVL树，来自网络：

1 好处及用途

红黑树并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

红黑树能够以 O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。

在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。

典型的用途是实现关联数组

2 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.

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)).

从1这点来看 红黑树是牺牲了严格的高度平衡的优越条件 为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

霍夫曼树必须是权值由小到大（由树叶到树根）！！！！

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

正确答案: D E 你的答案: E (错误)

10S

20S

40S

100S

200S

Pandora

交换机为独占带宽，即每个端口数据通过率为为最大100Mb/s。注意单位是Mb。因此最短时间为：

1GB/(100Mb/s)=1024MB/(12.5MB/s)=81.92s。

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

#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
",x.b,x.c);
    return 0;
}

正确答案: A C 你的答案: C (错误)

2015,810     大端big-endian

50810,201

810,2015 　　小端little-endian

20150,810

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

正确答案: C 你的答案: A (错误)

TIME_WAIT

FIN_WAIT_1

SYNC_SENT

FIN_WAIT_2

、
、、毕竟开始建立连接也不能算是断开的啊！！！！！！！

1.自身对其（截止的长度是自身类型长度的整数倍）
2.整体对齐 （最长的类型 或者 parama pack指定的字节数）