2014腾讯校园招聘实习技术类笔试题目

昨天参加了这次实习生笔试题，感觉考的不算难，但是有点广，数据结构、计算机操作系统、计算机网络等都有涉及。缺没有实际编码题目，看样子是面试的时候考察吧。其实基础扎实的话，应该不难。

答案都是自己解答和小伙伴探讨以及网上查的资料进行分析的，如有错误请留言拍砖！ 

(一)不定项选择题(25*4)

1.  使用深度优先算法遍历下图，遍历的顺序为（）

A ABCDEFG        B ABDCFEG

C ABDECFG        D  ABCDFEG

2.  输入序列ABCABC经过栈操作变成ABCCBA，下面哪些是可能的栈操作( )

A.      push pop push pop push pop pushpush push pop pop pop        //ABCCBA

B.     push push push push push push poppop pop pop pop pop        //CBACBA

C.     push push push pop pop pop pushpush pop pop push pop       //CBABAC

D.      push push push push pop pushpop push pop pop pop pop       //ABCCBA

3.  下列关键码序列哪些是一个堆( )

A. 90 31 53 23 16 48                B . 90 48 31 53 16 23 

C.  16 53 23 90 314                  D. 1631 23 90 53 48  

//48的左子节点为53，而该堆为大堆，违反其父节点都必须大于或等于其对应的子节点性质

//对于答案C:53右子节点为31，而该堆为小堆，违反其父节点都必须小于或等于其对应的子节点性质

//堆的性质，符合最大堆或者最小堆都行，如果大堆的话所有父节点都必须大于或等于其对应的子节点，

如果小堆的话，所有父节点都必须小于或等于其对应的子节点。  

堆是一棵完全二叉树，从上到下画好，进行对比就可以得到答案。

4. 稀疏矩阵压缩的存储方法是：（）

A 三元组 B 二维数组 C 散列 D 十字链表

//自己也忘记了少选了一个十字链表~晕,具体详细讲解可以查看下篇博文（网上搜的）

 //网搜资料     http://cc.sjtu.edu.cn/os/res/res6-5.asp    http://blog.sina.com.cn/s/blog_4c6403ed01000bbb.html（内容介绍） 

参考博文：  http://blog.sina.com.cn/s/blog_8d94fa6a01016q5b.html

20.二进制数01011011转化为十进制为（） 
A 103 B 91 C 171 D 71                       
21 版本控制软件是哪些（） 
A bugzilla B subversion C Git D loadrunner 
Loadrunner: 压力测试工具  

bugzilla ：追踪系统的软件，专门为Unix而定制 

22 Select A,B from Table1 where A between60 and 100 order by B，下面哪些优化sql性能（） 
A 字段A 建立hash索引，字段B btree索引 
B 字段A 建立hash索引，字段B不建立索引 
C 字段A 建立btree索引，字段B不建立索引    
D 字段A 不建立 索引，字段B建立btree索引 
//数据库内部采用的是B-Tree结构方便查询一个区间段的值，适合进行区间索引（自认）

23 数据索引的正确是（） 
A 1个表只能有一个聚族索引，多个非聚族索引 
B 字符串模糊查询不适合索引     //自认为B是对的，但是不确定，待解答 
C 哈希索引有利于查询字段用于大小范围的比较查询 
D 多余的索引字段会降低性能 
24 CPU与外设的传输数据的方式是（） 
A 程序方式 B 中断 C DMA D 通道方式 

//参考文章：http://cs.xiyou.edu.cn:84/wjyl/OnlineClass/7.2.html

http://wenku.baidu.com/view/e2f8690ebb68a98271fefa0c.html 
25 式子7*15=133成立，则用的是几进制（） 
A  6      B 7       C 8         D 9   //7*15(转十进制为13)=133(转十进制64+24+3=91) 
（二）填空题 
26. MySQL中表test选择10条到20条记录的语句是（）

select * from test limit 10,20;     //不会MySQL,忘记关键字limit写错了。 
27. 若信号S为9，则S经过15次P和14次V，S为（） 
8     每P一次减一，没V一次加一。相当于一个容器（S)，进去一个（P）容量就少一个，出来一个（V)容量就多一个。 
28. 页面走向：4 3 2 1 4 3 5 4 3 2 1 5 4，当分配的内存物理快数4(开始为装入)，采用LRU淘汰算法，产生多少次缺页（）

9     
LRU:最近最少使用淘汰算法：

就像排队，被叫到但是队中没有就缺了，被叫到的队中有则不缺，再把其放在队尾，继续叫号。（被叫到的也可以进行加权，按权值来淘汰）

29. 评估算法优势，通常从（）和（）两个方面考察

时间复杂度   空间复杂度 
30. G是一个邻接表，以V1为起点，深度优先遍历序列V1V2V3V6V5V4，从V1开始的广度优先遍历序列是（） 

V1 V2 V5 V4 V3 V6

//以前记得的，现在忘记了，自己做错了，很自然的就写成了V1 2  5 4  6 3

参考文章： 图的邻接表和邻接矩阵

31.20*20*20的魔法，8000个小正方体，如果剥取最外一层，还剩下多少个方块（）

//个人见解： 先忽略上下两个面，前后左右四个面的话就是上下全部占用就是20个，左右的话占用一边就是19个，然后前后左右是4个就是：19*20*4

现在来考虑上下两面，此时四边都被占用了，前后两边减二，左右两边减二就是18*18 ，然后上下两个面就是：18*18*2

结果为20*20*20-(19*20*4+18*18*2)=8000-2168=5832

大神给的解答就是18*18*18=5832 ，不明觉厉！ 
32.  
（1）如果A投硬币是正面的，B给A  1美金 
（2）如果A投的是反面，就再投，为正面，B给A 2美金 
（3）如果还是反面，就再投，为为正面，B给A 4 美金 
（4）假设A投的是反面，就投到正面为止，B就给A 的2的（n-1）次方 
如果A、B玩这样的硬币游戏，A至少要给B多少钱B才不会亏钱（） 
此题还真不会做，有待大家解答。只明了不管是哪一次停止，按概率算的话，给出的钱都是1/2: 第n次结束的概率为1/2的n方，而给的钱为2的n-1方

两者相乘就等于1/2 

33.左轮枪，左轮枪，有6个弹巢，两颗子弹放进相邻的弹巢，拨动转轮，然后拿着这把枪朝我自己扣动，但我还活着，现在轮到你了，你有两种选择 
（1）在扣动一次转轮，把枪对准自己，扣动扳机 
（2）不拨动转轮，直接对准自己，扣动扳机 
假设你还不想死，你选择哪种（）原因（）

选第二种     概率1/2>1/4 或者1/3>1/4

经过我和同门小伙伴讨论得出第二种爆头的概率为1/4，文字不好解释额，假设第一个子弹的位置为1，第二个子弹的位置为2则第一个人没有爆头的 弹巢 就为3、4、5、6 ，

现在如果为3，则下一 弹巢为4不爆头

现在如果为4，则下一 弹巢为5不爆头

现在如果为5，则下一弹巢为6不爆头

现在如果为6，则下一弹巢为1爆头

可知爆头概率为1/4

第一种的话有两种争论，拨动转轮到底是拨动一格还是拨动一下转n圈，就像电视上面的一样。这两种情况有待商榷，没有抓住出题者的意图。

假设为第一种转动一格。那么还是按照上面的来分析:

所以这种情况下面爆头概率非常高为1/2

假设为第二种转动n圈，回到随机位置，这种就比较好考虑了，就是6个里面有两个爆头，概率为1/3

提交的时候遇到这个问题，是不是有点坑爹啊，呵呵，看来网络环境还是要大家来维系。 
附加题： 
34.描述mapreduce的执行过程，最好用画图的方式表示。 
参考解答：http://liouwei20051000285.blog.163.com/blog/static/252367420116125223809/

35．数据库A的ID从20120120300001到20120120399999，更新ID从00001到99999，递增加1，不重复，不间断(并保持高并发的性能)

也不是很清楚当时就写了设置ID为主键，保证其唯一约束。还有就是以日期找到当天是否数据库中已有当天的ID,没有设为00001，

有的话就找到当天最大的那一个然后加1为对应的主键。保持高并发性，不知道怎么做。还是必须得加锁一条一条插入吧。待大家解答。