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

《腾讯2013校招笔试题(含答案).pdf》由会员分享，可在线阅读，更多相关《腾讯2013校招笔试题(含答案).pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、腾讯 2013 校园招聘技术类笔试题 一、选择题 1、数据库表设计最合理的是（A）A.学生id,name,age,学科id,name 分数学生 id，学科 id，分数 B.学生id,name,age,分数学生 id，学科名称，分数 C.分数学生姓名，学科名称，分数 D.学科id,name,分数学生姓名，学科 id，分数 解析：解析：C,D 肯定不对，B 中将学科独立成一个表结构会更加清晰，一个实体对应一张表。2、在数据库系统中，产生不一致的根本原因是（D）A数据存储量太大 B没有严格保护数据 C未对数据进行完整性控制 D数据冗余 解析：解析：基本概念 3、15L 和 27L 两个杯子可以精确地

2、装（C）L 水？A.53 B.25 C.33 D.52 解析：解析：设 A 杯 15L，B 杯 27L，用 A 打两次水，将 B 装满，最后 A 还剩 3L，将3L 水装至 B，还是用 A 打两次水，将 B 装满,最后 A 中有 6L，6+27=33.9,12,15.同理 4、考虑左递归文法 S-Aa|b、A-Ac|Sd|e，消除左递归后应该为（A）A.B.C.D.S-Aa|b S-Ab|a S-Aa|b S-Aa|b A-bdA|A A-bdA|A A-cdA|A A-bdA|A A-cA|adA|A-cA|adA|A-bA|adA|A-caA|dA|设A 杯15L，B杯2 7 L，用A 打

3、两次水，将B装满，最后A 还剩3L，将这3L倒入B，再将A 接满倒入B，此时B杯中有18 L水，将A 接满，则15+18=33L解析：解析：e 为空集，消除左递归，即消除 有 A-A*的情况，消除做递归的一般形式为 U=Ux1|U x2|y1|y2 U=y1U|y2 U U=x1U|x2U|e A=Ac|Aad|bd|e A=bdA|A A=cA|adA|e 5、下列排序算法中，初始数据集合对排序性能无影响的是（B）A插入排序 B堆排序 C冒泡排序 D快速排序 解析：解析：插入和冒泡再原数据有序的情况下会出现性能的极端情况（O(n)，O(n2)）.快速排序在对一个基本有序或已排序的数组做反向排

4、序时，每次patition的操作，大部分元素都跑到了一遍，时间复杂度会退化到 O(n2)。6、二分查找在一个有序序列中的时间复杂度为（b）A.O(N)B.O(logN)C.O(N*N)D.O(N*logN)7、路由器工作在网络模型中的哪一层（c）？A.数据链路层 B.物理层 C.网络层 D.应用层 解析：解析：相关物理硬件和 OSI 协议层次的对应关系：物理层 光纤、同轴电缆 双绞线 中继器和集线器 数据链路层 网桥、交换机、网卡 网络层 路由器 传输层 网关 8、对于满足 SQL92 标准的 SQL 语句：select foo,count(foo)from pokes where foo10

5、 group by foo having count(*)5 order by foo，其执行顺序应该是（A）A.FROM-WHERE-GROUP BY-HAVING-SELECT-ORDER BY B.FROM-GROUP BY-WHERE-HAVING-SELECT-ORDER BY C.FROM-WHERE-GROUP BY-HAVING-ORDER-BYSELECT D.FROM-WHERE-ORDER BY-GROUP BY-HAVING-SELECT 解析：解析：SQL Select 语句完整的执行顺序：1）from 子句组装来自不同数据源的数据；2）where 子句基于指定的条件

6、对记录行进行筛选；3）group by 子句将数据划分为多个分组；4）使用聚集函数进行计算；5）使用 having 子句筛选分组；6）计算所有的表达式；7）使用 order by 对结果集进行排序。只有 select 选出了相应的表 才能对其排序，删除之类的操作，因此 合理的答案应该为 from-where-group by-having-select-order by 使用深度有限算法遍历下面的图，遍历的顺序为（C）10UNIX 系统中，目录结构采用 B 单级目录结构 二级目录结构 单纯树形目录结构 带链接树形目录结构 A B C D E F H I G D11请问下面的程序一共输出多少个“

7、-”？D#include#include#include int main(void)int i;for(i=0;i2;i+)fork();/复制父进程，调用一次，返回两次 printf(-);/缓冲区数据 return 0;A.2 个 B.4 个 C.6 个 D.8 个 解析解析:关键 1.fock 之后的代码父进程和子进程都会运行；关键 2.printf(“-”);语句有 buffer，所以，对于上述程序，printf(“-”);把“-”放到了缓存中，并没有真正的输出，在 fork 的时候，缓存被复制到了子进程空间，所以，就多了两个，就成了 8 个，而不是 6 个。12.请问下面的程序一共

8、输出多少个“-”？C#include h t t p:/c o o l s h e l l.c n/a r t i c l e s/7 96 5.h t m l用p r i n t f()输出时是先输出到缓冲区，然后再从缓冲区送到屏幕上。输出到屏幕的条件：1.使用f f l u s h（s t d o u t）强制刷新。2.缓冲区已满。3.s c a n f()要在缓冲区里取数据时会先将缓冲区刷新。4.n,r 进入缓冲区时。5.线程结束的时候，如果该线程里也有p r i n t f(.);6.程序结束时。因此，在第一次f o r k 中，父进程和子进程的-均为输出，而是保存在缓冲区中，当第二次

9、f o r k 时，又被复制到了 新建的进程中，此时系统中共有4个进程，每个进程中都有两个-，因此共输出8 次。#include#include int main(void)int i;for(i=0;i执行，当前运行进程阻塞，调度程序选一个优先权最高的进程占有处理机；2：执行-就绪，当前运行进程时间片用完；3：执行-阻塞，当前运行进程等待键盘输入，进入了睡眠状态。4：阻塞-就绪，I/O 操作完成，被中断处理程序唤醒。16.假定我们有 3 个程序，每个程序花费 80%的时间进行 I/O，20%的时间使用CPU。每个程序启动时间和其需要使用进行计算的分钟数如下，不考虑进程切换时间。B 程序编号

10、启动时间 需要 CPU 时间（分钟）1 00:00 3.5 2 00:10 2 3 00:15 1.5 请问在多线程/进程环境下，系统的总响应时间是（）A.22.5 B.23.5 C.24.5 D.25.5 解答：解答：多道编程时 CPU 利用率的求法：只有一个进程的时候，CPU 利用率肯定是 20%。两个进程的时候：CPu 利用率是：20%+(1-20%)*20%=36%三个进程是：36%+(1-36%)*20%=48.8%其它的依次类推。0-10 分钟的时候，只有一个进程 1 在运行。单进程 CPU 占有率是 20%，所以这 10 分钟内，进程 1 消耗了 2 分钟的 CPU。进程 2 是

11、 0，进程 3 也是 0 然后在 10-15 分钟内，有两个进程在运行（1 和 2），双进程的 CPU 利用率是36%，所以，这五分钟内，CPU 一共利用了 1.8 分钟，平均分给每个进程，是 0.9 分钟。此时，进程 1 已经占用了 CPU 2.9 分钟，还需要 0.6 分钟，这时候有三个进程在运行，所有总的 CPU 时间需要 1.8 分钟。三进程的 CPU 利用率是 48.8%，所以总共需要 1.8/0.488=3.69 分钟。这时，进程 1 已经 3.5 分钟的 CPu 利用时间利用完了。此时还剩下 2 和 3 号进程在运行。2 号进程还需要 0.5 分钟，所以 0.52/0.36=2.

12、78，此时 2 号进程的 2 分钟 CPU时间也利用完了。3 号进程还需要 0.4 分钟的 CPU 利用时间。0.4/0.2=2 参考-操作系统多道编程 17.在所有非抢占 CPU 调度算法中，系统平均响应时间最优的是（C）A.实时调度算法 B.短任务优先算法 C.时间片轮转算法 D.先来先服务算法 18.什么是内存抖动（Thrashing）?A A.非常频繁的换页活动 B.非常高的 CPU 执行活动 C.一个极长的执行进程 D.一个极大的虚拟内存交换活动 解析：解析：页面的频繁更换，导致整个系统效率急剧下降，这个现象称为内存抖动。抖动一般是内存分配算法不好，内存太小引或者程序的算法不佳引起的

13、页面频繁从内存调入调。19.Belays Anomaly 出现在哪里（B）A.内存管理算法 B.内存换页算法 C.预防死锁算法 D.磁盘调度算法 解析：解析：Belady 异常（Belady Anomaly）：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。原因：因为使用了不恰当的演算法(如 FIFO)，虽然空间够多(frame 够多)，但因为总是选到不应该被 swap 的 page，所以反而让 page fault 次数变多了。20.下面的生产者消费者程序中，哪个不会出现死锁，并且开销最少？A 解析：解析：代码太多，不做-二、填空题 21.将下图进行拓扑排序后，对应的序列为

14、 ABCFD 使用先进先出页面置换算法容易出现该问题内存换页算法：先进先出页面置换算法（FIFO）：选择最早进入内存的页面置换 最近最久未使用页面置换算法（LRU）：选择最近一段时间内最长时间没有被访问的页面置换 最优淘汰算法（O PT）：选择最长一段时间内不会被访问的页面进行置换，需要先将程序执行一遍，获得页面的使用情况。性能最好，但不容易事先，一般用来评价其他页面置换算法的好坏输出当前无入边的结点，在删除一个结点时，将该结点的出边也一同删除。解析：解析：拓扑排序的定义:对一个有向无环图(Directed Acyclic Graph 简称 DAG)G进行拓扑排序，是将 G 中所有顶点排成一个

15、线性序列，使得图中任意一对顶点 u和 v，若 E(G)，则 u 在线性序列中出现在 v 之前。22.下面的函数使用二分查找算法，对已按升序排序的数组返回所要查找的数值的数据位置，请填写缺少的两句语句：int*BinarySearch(int*arrayAddress,int arrayLength,int valueToSearch)int head=0;int tail=arrayLength-1;while(head valueToSeatcj)tail=mid-1;else head=mid+1;if(tail arrayLength&arrayAddresstail=valueToSe

16、arch)return&arrayAddresstail;else return NULL;tail=mid-1;head=mid+1;23.一个有 N 个正数元素的一维数组（A0,A1,A2.,AN-1）,求连续子数组和的最大值。int max(int a,int b)int MaxSum(int*A,int length)int nStart=A0;int nAll=A0;for(int i=1;i=2 该递推关系的解为：h(n)=C(2n,n)/(n+1)，n=1,2,3,.（其中 C(2n,n)表示 2n 个中取 n 个的组合数）h(5)=C(10,5)/6=42 令s u m 为以第

17、i 个元素结尾的最长子序列的值，取值有两种情况：1、当a i a i-1时，s u m =s u m+1 2、当a i =a i-1时，s u m =1i n t G e t LIS(i n t *a r r,i n t n)i f (a r r =NU LL|n =0)r e t u r n -1;i n t n Su m =1;i n t n M a x =1;f o r (i n t i=1;i a r r i-1)n Su m+;e l s e n Su m =1;n M a x =n M a x n Su m?n M a x:n Su m;r e t u r n n M a x;i

18、n t G e t Po p Nu m(i n t n)i n t s u m =0;i f (n =0|n =1)r e t u r n 1;f o r (i n t i=1;i =n;i+)s u m +=G e t Po p Nu m(i-1)*G e t Po p Nu m(n-i);r e t u r n s u m;27.请给出表达式 a+b*(c-d)/e-f 的逆波兰式。abcd-*e/+f-解析：解析：先画出式子的二叉树，再写出后序遍历的结果。三、Web 前端方向附加题 略 四、其他方向附加题 1.微博广告投放是腾讯收入来源之一，为了保证投放的广告对用户更有帮助，必须分析用户

19、对什么最感兴趣。用户的每条微薄都可以拆分成几个关键字，腾讯微博每个月会收集到上 T 的关键字，请你分析出其中出现次数最多的十个关键字。解析解析:先用 Hashmap 统计关键字的出现次数，再用“求最大的 k 个数”的方法，用堆来得到出现次数最大的 10 个关键字。初始创建大小为10 的最小堆，当堆顶的数小于选取的数时，两数交换，再将该堆调整为最小堆。最终堆中的数据即为出现次数最多的十个关键字2.腾讯新闻首页改版之后，为了精确掌握改版效果，需要准实时统计每篇文章的IP 数量，即从文章发表之后，有多少个不同的 ip 的用户读过这篇文章。每个用户访问请求都会被 web 服务器解析，并实时传输到后台统计系统，请逆设计该“后台统计系统”，以完成统计。