腾讯2013校招笔试题(含答案)(2)

19. Belay's Anomaly 内存换页算法： 先进先出页面置换算法（FIFO）：选择最早进入内存的页面置换 最近最久未使用页面置换算法（LRU）：选择最近一段时间内最长时间没有被访问的页面置换 最优淘汰算法（OPT）：选择最长一段时间内不会被访问的页面进行置换，需要先将程序执行一遍，获得页面的使用情况。性能最好，但不容出现在哪里（B）易事先，一般用来评价其他页面置换算法的好坏

A.内存管理算法 B.内存换页算法 C.预防死锁算法 D.磁盘调度算法

解析： Belady异常（Belady Anomaly）：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。 使用先进先出页面置换算法容易出现该问题原因：因为使用了不恰当的演算法(如FIFO)，虽然空间够多(frame够多)，但因为总是选到不应该被swap的page，所以反而让page fault次数变多了。

20.下面的生产者消费者程序中，哪个不会出现死锁，并且开销最少？A 解析： 代码太多，不做 - -

二、填空题

21.将下图进行拓扑排序后，对应的序列为 ABCFD

输出当前无入边的结点，在删除一个结点时，将该结点的出边也一同删除。

腾讯2013笔试题,试题中原作者已给出答案,但感觉有些答案不正确,做了相应修改,仅供参考

解析： 拓扑排序的定义:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。

22.下面的函数使用二分查找算法，对已按升序排序的数组返回所要查找的数值的数据位置，请填写缺少的两句语句：

int* BinarySearch(int* arrayAddress, int arrayLength, int valueToSearch)

{

int head = 0 ;

int tail = arrayLength - 1;

while(head < tail)

{

mid = (head + tail)/2;

if(arrayAddress[mid] > valueToSeatcj)

tail = mid - 1;

else

head = mid + 1;

}

if(tail < arrayLength && arrayAddress[tail] == valueToSearch) return &arrayAddress[tail];

else

腾讯2013笔试题,试题中原作者已给出答案,但感觉有些答案不正确,做了相应修改,仅供参考

return NULL;

}

腾讯2013笔试题,试题中原作者已给出答案,但感觉有些答案不正确,做了相应修改,仅供参考

return 1;

for (int i=1; i<=n; i++)

{

sum += GetPopNum(i-1)*GetPopNum(n-i);

}

return sum;

}

腾讯2013笔试题,试题中原作者已给出答案,但感觉有些答案不正确,做了相应修改,仅供参考

27.请给出表达式 a + b*(c-d)/e-f 的逆波兰式。abcd-*e/+f-

解析： 先画出式子的二叉树，再写出后序遍历的结果。

三、Web前端方向附加题 略

四、其他方向附加题

1.微博广告投放是腾讯收入来源之一，为了保证投放的广告对用户更有帮助，必须分析用户对什么最感兴趣。用户的每条微薄都可以拆分成几个关键字，腾讯微博每个月会收集到上T的关键字，请你分析出其中出现次数最多的十个关键字。 解析: 先用Hashmap统计关键字的出现次数，再用“求最大的k个数”的方法，用堆来得到出现次数最大的10个关键字。 初始创建大小为10的最小堆，当堆顶的数小于选取的数时，

两数交换，再将该堆调整为最小堆。

最终堆中的数据即为出现次数最多的十个关键字

腾讯2013笔试题,试题中原作者已给出答案,但感觉有些答案不正确,做了相应修改,仅供参考

2.腾讯新闻首页改版之后，为了精确掌握改版效果，需要准实时统计每篇文章的IP数量，即从文章发表之后，有多少个不同的ip的用户读过这篇文章。每个用户访问请求都会被web服务器解析，并实时传输到后台统计系统，请逆设计该“后台统计系统”，以完成统计。