腾讯2014校园招聘技术类笔试题详解

http://blog.csdn.net/silangquan/article/details/19977839

一、选择题

1、数据库表设计最合理的是

A.学生{id,name,age} ,学科{id,name} 分数{学生id,学科id,分数}

B.学生{id,name,age} ,分数{学生id,学科名称,分数}

C.分数{学生姓名,学科名称,分数}

D.学科{id,name},分数{学生姓名,学科id,分数}

解析:C,D肯定不对,B中将学科独立成一个表结构会更加清晰,一个实体对应一张表。

2、在数据库系统中,产生不一致的根本原因是

A.数据存储量太大 B.没有严格保护数据 C.未对数据进行完整性控制 D.数据冗余

解析:基本概念

3、15L和27L两个杯子可以精确地装()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'|ε 

解析: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、下列排序算法中,初始数据集合对排序性能无影响的是()

A.插入排序 B.堆排序 C.冒泡排序 D.快速排序

解析:插入和冒泡再原数据有序的情况下会出现性能的极端情况(O(n),O(n^2)).快速排序在对一个基本有序或已排序的数组做反向排序时,每次patition的操作,大部分元素都跑到了一遍,时间复杂度会退化到O(n^2)。

6、二分查找在一个有序序列中的时间复杂度为()

A.O(N)   B.O(logN)   C.O(N*N)  D.O(N*logN)

7、路由器工作在网络模型中的哪一层()?

A.数据链路层     B.物理层      C.网络层    D.应用层

解析:相关物理硬件和OSI协议层次的对应关系:

物理层           光纤、同轴电缆 双绞线 中继器和集线器 数据链路层   网桥、交换机、网卡 网络层           路由器 传输层           网关

8、对于满足SQL92标准的SQL语句:select foo,count(foo) from pokes where foo>10 group by foo having count(*)>5 order by foo,其执行顺序应该是()

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子句基于指定的条件对记录行进行筛选; 3)group by子句将数据划分为多个分组; 4)使用聚集函数进行计算; 5)使用having子句筛选分组; 6)计算所有的表达式;

7)使用order by对结果集进行排序。

只有select选出了相应的表 才能对其排序,删除之类的操作,因此 合理的答案应该为 from --where-- group by-- having --select-- order by

9.使用深度优先算法遍历下面的图,遍历的顺序为()

A.ABCDEFGHI       B.BCEHIFGDA     C.ABCEFHIGD    D.HIFEGBCDA

无答案

解析:

用邻接表的方式来表示图

A->B->C->D

B->

C->

D->E->F->G

E->

F->H->I

G->

H->

I->

图的深度优先搜索是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

所以正确的过程是 A->B->C->D->E->F->H->I->G

10.UNIX系统中,目录结构采用

A.单级目录结构   B.二级目录结构    C.单纯树形目录结构    D.带链接树形目录结构

11.请问下面的程序一共输出多少个“-”?

[cpp] view plaincopy

  1. #include <stdio.h>
  2. #include <sys/types.h>
  3. #include <unistd.h>  
  4. int main(void)  
  5. {  
  6. int i;  
  7. for(i=0; i<2; i++)  
  8.   {  
  9.        fork(); //复制父进程,调用一次,返回两次
  10.        printf("-"); //缓冲区数据
  11.    }  
  12. return 0;  
  13. }  

A.2个   B .4个   C.6个   D.8个

解析:

关键1.fock之后的代码父进程和子进程都会运行;

关键2.printf(“-”);语句有buffer,所以,对于上述程序,printf(“-”);把“-”放到了缓存中,并没有真正的输出,在fork的时候,缓存被复制到了子进程空间,所以,就多了两个,就成了8个,而不是6个。

12.请问下面的程序一共输出多少个“-”?

[cpp] view plaincopy

  1. #include <stdio.h>
  2. #include <sys/types.h>
  3. #include <unistd.h>  
  4. int main(void)  
  5. {  
  6. int i;  
  7. for(i=0; i<2; i++)  
  8.   {  
  9.        fork(); //复制父进程,调用一次,返回两次
  10.        printf("-\n"); //缓冲区数据
  11.    }  
  12. return 0;  
  13. }  

A.2个 B .4个 C.6个 D.8个

解析:printf("-\n")刷新了缓冲区

13.避免死锁的一个著名的算法是()

A.先入现出法     B.银行家算法    C.优先级算法    D.资源按需分配法

14.怎么理解分配延迟(dispatch lantency)

A.分配器停止一个进程到开启另一个进程的时间   B. 处理器将一个文件写入磁盘的时间

C. 所有处理器占用的时间                                        D.以上都不对

解析:分派程式停止某一个处理元使用中央处理器,并分派中央处理器给另一个处理元所需的时间,称为分派时间(Dispatch Latency)。

15.以下哪一个不是进程的基本状态?

A. 阻塞态      B.执行态     C.就绪态      D. 完成态

解析:进程状态转移图

1:就绪->执行, 当前运行进程阻塞,调度程序选一个优先权最高的进程占有处理机; 2:执行->就绪, 当前运行进程时间片用完; 3:执行->阻塞,当前运行进程等待键盘输入,进入了睡眠状态。 4:阻塞->就绪,I/O操作完成,被中断处理程序唤醒。

16.假定我们有3个程序,每个程序花费80%的时间进行I/O,20%的时间使用CPU。每个程序启动时间和其需要使用进行计算的分钟数如下,不考虑进程切换时间。

程序编号              启动时间                    需要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是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.5×2/0.36=2.78,此时2号进程的2分钟CPU时间也利用完了。 3号进程还需要0.4分钟的CPU利用时间。0.4/0.2 = 2 参考 - 操作系统多道编程

17.在所有非抢占CPU调度算法中,系统平均响应时间最优的是()

A.实时调度算法     B.短任务优先算法       C.时间片轮转算法       D.先来先服务算法

18.什么是内存抖动(Thrashing)?

A.非常频繁的换页活动                     B.非常高的CPU执行活动                     C.一个极长的执行进程                       D.一个极大的虚拟内存交换活动 解析:页面的频繁更换,导致整个系统效率急剧下降,这个现象称为内存抖动。 抖动一般是内存分配算法不好,内存太小引或者程序的算法不佳引起的页面频繁从内存调入调。

19. Belay's Anomaly 出现在哪里()

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

解析:Belady异常(Belady Anomaly):有些情况下,页故障率(缺页率)可能会随着所分配的帧数的增加而增加。

原因:因为使用了不恰当的演算法(如FIFO),虽然空间够多(frame够多),但因为总是选到不应该被swap的page,所以反而让page fault次数变多了。

20.下面的生产者消费者程序中,哪个不会出现死锁,并且开销最少?

解析:代码太多,不做 - -

二、填空题

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

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

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

[cpp] view plaincopy

  1. int* BinarySearch(int* arrayAddress, int arrayLength, int valueToSearch)  
  2. {  
  3. int head = 0 ;  
  4. int tail = arrayLength - 1;  
  5. while(head < tail)  
  6.     {  
  7.         mid = (head + tail)/2;  
  8. if(arrayAddress[mid] > valueToSeatcj)  
  9.             tail = mid - 1;  
  10. else
  11.             head = mid + 1;  
  12.     }  
  13. if(tail < arrayLength && arrayAddress[tail] == valueToSearch)  
  14. return &arrayAddress[tail];  
  15. else
  16. return NULL;  
  17. }  

tail = mid ;

head = mid + 1;

当你用head<tail 的时候 tail = mid,head =mid +1,当用head<= tail的时候,采用 tail = mid - 1,head =mid +1 多谢陈老湿纠正.

23.一个有N个正数元素的一维数组(A[0], A[1], A[2]...,A[N-1]), 求连续子数组和的最大值。

[cpp] view plaincopy

  1. int max(int a,int b)  
  2. int MaxSum(int *A, int length)  
  3. {  
  4. int nStart = A[0];  
  5. int nAll = A[0];  
  6. for(int i=1; i<lenght; i++)  
  7.     {  
  8.         nStart = max(nAll + A[i], 0);  
  9.             nAll = max(nAll, nStart);  
  10.     }  
  11. return nAll;  
  12. }  

nStart = max(nAll + A[i] , 0); nAll = max(nAll, nStart);

24. 请给出二叉树的前序遍历  abdefghc

25.最长递增子序列(LIS)表示在一个序列中,保持递增的最长子序列,比如(2,1,4,2,3,7,4,6)的LIS是{1,2,3,4,6},则LIS的长度是5.

对于一个有N个元素的序列,得到LIS的长度的最优时间复杂度是 O(nlogn) ,空间复杂度是o(n) 。

具体参考:

动态规划-最长上升子序列(LIS)

26.给一系列的数1,2,3,,,n(有序的)和一个栈(stack),这个栈无限大,将这n个数按照顺序放入栈中,但是随机的从栈中弹出,n=5,一共有多少中弹栈方式。42

解析:这是卡特兰数的典型应用。Catalan数的定义令h(1)=1,Catalan数满足递归式:h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1),n>=2该递推关系的解为:h(n) = C(2n,n)/(n+1),n=1,2,3,...(其中C(2n,n)表示2n个中取n个的组合数)

h(5) = C(10,5)/6 = 42

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

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

三、Web前端方向附加题 略

四、其他方向附加题

1.微博广告投放是腾讯收入来源之一,为了保证投放的广告对用户更有帮助,必须分析用户对什么最感兴趣。用户的每条微薄都可以拆分成几个关键字,腾讯微博每个月会收集到上T的关键字,请你分析出其中出现次数最多的十个关键字。

解析:先用Hashmap统计关键字的出现次数,再用“求最大的k个数”的方法,用堆来得到出现次数最大的10个关键字。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

服务网格 Pattern: Service Mesh

自从几十年前首次引入以来,我们了解到分布式系统能够实现我们之前甚至无法思考的用例,但它们也会引入各种新问题。

14520
来自专栏数据库新发现

思科CEO钱伯斯:我非常尊敬华为

--------------------------------------------------------------------------------...

32110
来自专栏進无尽的文章

益思维-早期苹果员工胸牌背面写的11条“成功法则”

早期苹果员工胸牌背面写的11条“成功法则”这个胸牌的背面写着11条成功法则,其中每一条文字都充满了正能量。从中我们可以看到一些触动人心的感觉。

9820
来自专栏计算机编程

2018-03-14 致敬霍金

  在黑洞领域,没有人知道这个怪兽是个什么东西,自从霍金给出“霍金辐射”与“奇点定理”过后,人们终于逐渐揭开了这宇宙中最为神秘的天体。在这里再次缅怀一下虽然坐着...

15320
来自专栏数据库新发现

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉 中广网 10月04日 09:48

19330
来自专栏黄成甲

怎样成为解决问题的高手(连载一)

什么是问题?一言以蔽之,问题来源于现实与目标的差距。因此,问题产生的原因可能是不清楚目标是什么;还可能是不知道差距产生的原因是什么;或者虽然知道差距产生的原因,...

35340
来自专栏知道一点点

20种新颖的按钮风格和效果【附源码】

Codrops 给我们分享了一组新鲜的按钮样式和效果的集合。它们中的大部分效果都使用了 CSS3 过渡和伪元素,他们都有一个共同点,那就是都具有简单性,没有太多...

16910
来自专栏黄成甲

怎样科学地和人相处?

按照约定俗成的说法,一般跟人打交道有两个规则,一个是“黄金法则”,一个是“白银法则”。黄金法则并不适合现代社会对陌生人使用。因为你觉得好的东西别人不一定觉得好。...

16020
来自专栏進无尽的文章

什么才是优秀的网站用户界面设计

16720
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

16030

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励