腾讯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
试设计一个内存分配器,要求尽可能对用户的请求分配成功,写出你使用到的数据结构,分配算法和回收算法