腾讯2011暑期实习（技术类）笔试题

20道选择题，每题3分，共60分

内容涉及：1道概率论题目、数据结构与算法、操作系统、计算机网络

1 概率计算题：4个电阻A、B、C和D，B与C并联后又与A和D串联。

已知B,C,A的可靠性分别为0.7, 0.7, 0.9，问：为了使整个电路的可靠性

不小于0.95，D的可靠性至少为多少？

 

2 MD5算法产生的密钥有多少个比特？

 

3 已知一个序列的前4趟排序结果，问用的是什么排序方法？

 

4 对一个序列使用快速排序，第一趟的结果是什么？

 

5 给定学生和成绩的数据库表，写一个sql语句求出每门课程的平均分

 

6 TCP socket连接完毕后，关于send和recv函数的说法，哪个是正确的？

有可能客户端两次send过去的数据，recv一次就接受完了

 

7 操作系统的经典题目，根据逻辑地址和页表寄存器计算出物理地址

 

8 给出A，B，C三个任务的优先级，cpu使用时间，IO设备使用时间，采用

抢占式调度算法，计算：3个任务执行的过程中，cpu的空闲时间有多少秒

 

9 最小生成树算法，给出11个村庄和两两之间的距离，求一个修路方案，

既能保证任何两个村庄都能连接，又要修路的总长度最小

 

10 huffman编码问题，给出5个关键词的频率，求最短带权路径长度

 

11 中缀表达式转后缀表达式

 

12 把森林转化成孩子兄弟表示法的二叉树

 

13 下列关于cache的说法不正确的是

cache能提高主存的容量

 

14 下列关于http协议的说法不正确的是

http协议是网络层上的协议

 

15 好吧，之后5题记不起来了。。。

 

程序填空题，2道大题，总共10空，没空4分，共40分

1 创建链表和反转链表，比如A->B->C->D反转成D->C->B->A

2 简单计算器的实现

 

附加题

手机和很多嵌入式设备内存容量有限，内存的分配是一个很大的问题，现在又一个手机，8M的内存，

已知各种大小的分配频率为：

16B以下           100K

16B~32B         50K

32B~64B         32K

64B~128B       16K

128B~256B     8K

256B~512B     4K

1K                    2K

试设计一个内存分配器，要求尽可能对用户的请求分配成功，写出你使用到的数据结构，分配算法和回收算法