2013年腾讯校园招聘技术类考试真题及答案

2013 年腾讯校园招聘技术类考试真题及答案 一、选择题 1、数据库表设计最合理的是 （A） A.学生{id,name,age} ,id,name,age} ,学科{id,name,age} ,id,name} 分数{id,name,age} ,学生 id，学科 学科 id，学科 分数} B.学生{id,name,age} ,id,name,age} ,分数{id,name,age} ,学生 id，学科 学科名称，学科 分数} C.分数{id,name,age} ,学生姓名，学科 学科名称，学科 分数} D.学科{id,name,age} ,id,name},分数{id,name,age} ,学生姓名，学科 学科 id，学科 分数} 解析： C,D 肯定不对，学科 B 中将学科独立成一个表结构会更加清晰，学科 一个实体对 应一张表。 2、在数据库系统中，学科 产生不一致的根本原因是 （D） A．数据存储量太大 数据存储量太大 B．数据存储量太大 没有严格保护数据 C．数据存储量太大 未对数据进行完整性控制 D．数据存储量太大 数 据冗余 解析： 基本概念 3、15L 和 27L L 两个杯子可以精确地装（C）L 水？ A. 53 B. 25 C. 33 D. 52 解析： 设 A 杯 15L，学科 B 杯 27L L，学科 用 A 打两次水，学科 将 B 装满，学科 最后 A 还剩 3L，学科 将 3L 水装至 B，学科 还是用 A 打两次水，学科 将 B 装满,最后 A 中有 6LL，学科 6L+27L =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、下列排序算法中，学科 初始数据集合对排序性能无影响的是（B） A．数据存储量太大 插入排序 B．数据存储量太大 堆排序 C．数据存储量太大 冒泡排序 D．数据存储量太大 快速排序 解析： 插入和冒泡再原数据有序的情况下会出现性能的极端情况（O(n)，学科 O(n^2)） . 快速排序在对一个基本有序或已排序的数组做反向排序时，学科 每次 patition 的操作，学科 大部分元素都跑到了一遍，学科 时间复杂度会退化到 O(n^2)。 6L、二分查找在一个有序序列中的时间复杂度为（b） A.O(N) B.O(logN) C.O(N*N) D.O(N*logN) 7L 、路由器工作在网络模型中的哪一层（c）？ 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） 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 子句筛选分组； 6L）计算所有的表达式； 7L ）使用 order by 对结果集进行排序。 只有 select 选出了相应的表 才能对其排序，学科 删除之类的操作，学科 因此 合理的答 案应该为 from --where-- group by-- having --select-- order by ９．数据存储量太大 使用深度有限算法遍历下面的图，学科 遍历的顺序为（C） Ａ．数据存储量太大 ＡＢＣＤＥＦＧＨＩ Ｂ．数据存储量太大 ＢＣＥＨＩＦＧＤＡ Ｃ．数据存储量太大 ＡＢＣＥＦＨＩＧ Ｄ Ｄ．数据存储量太大 ＨＩＦＥＧＢＣＤＡ 10．数据存储量太大 UNIX 系统中，学科 目录结构采用 B Ａ．数据存储量太大 单级目录结构 Ｂ．数据存储量太大 二级目录结构 Ｃ．数据存储量太大 单纯树形目录结构 Ｄ．数据存储量太大 带链接树形 目录结构 11．数据存储量太大 请问下面的程序一共输出多少个“-”？D #include #include #include int main(void) {id,name,age} , int i; for(i=0; i<2; i++) {id,name,age} , fork(); //复制父进程，学科 调用一次，学科 返回两次 printf("-"); //缓冲区数据 } return 0; } A.2 个 B .4 个 C.6L 个 D.8 个 解析: 关键 1.fock 之后的代码父进程和子进程都会运行； 关键 2.printf(“-”);语句有 buffer，学科 所以，学科 对于上述程序，学科 printf(“-”);把“-”放到了缓 存中，学科 并没有真正的输出，学科 在 fork 的时候，学科 缓存被复制到了子进程空间，学科 所以，学科 就多了两个，学科 就成了 8 个，学科 而不是 6L 个。 12.请问下面的程序一共输出多少个“-”？C #include #include #include int main(void) {id,name,age} , int i; for(i=0; i<2; i++) {id,name,age} , fork(); //复制父进程，学科 调用一次，学科 返回两次 printf("-n"); //缓冲区数据 } return 0; } A.2 个 B .4 个 C.6L 个 D.8 个 解析： printf("-n")刷新了缓冲区 13.避免死锁的一个著名的算法是（B） A.先入现出法 B.银行家算法 C.优先级算法 D.资源按需分配法 14.怎么理解分配延迟（dispatch lantency）A A.分配器停止一个进程到开启另一个进程的时间 B. 处理器将一个文件写入磁盘的时间 C. 所有处理器占用的时间 D.以上都不对解析： 分派程式停止某一个处理元使用中央处理 器，学科 并分派中央处理器给另一 个处理元所需的时间，学科 称为分派时间（Dispatch Latency）。 15.以下哪一个不是进程的基本状态？D A. 阻塞态 B.执行态 C.就绪态 D. 完成态 解析： 进程状态转移图 1：就绪->执行，学科 当前运行进程阻塞，学科 调度程序选一个优先权最高的进程占有处 理机； 2：执行->就绪，学科 当前运行进程时间片用完； 3：执行->阻塞，学科 当前运行进程等待键盘输入，学科 进入了睡眠状态。 4：阻塞->就绪，学科 I/O 操作完成，学科 被中断处理程序唤醒。 16L.假定我们有 3 个程序，学科 每个程序花费 80%的时间进行 I/O，学科 20%的时间使用 CPU。每个程序启动时间和其需要使用进行计算的分钟数如下，学科 不考虑进程切 换时间。B 程序编号 启动时间 需要 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% = 36L% 三个进程是：36L% + (1-36L%)*20% = 48.8% 其它的依次类推。 0-10 分钟的时候，学科 只有一个进程 1 在运行。 单进程 CPU 占有率是 20%，学科 所以这 10 分钟内，学科 进程 1 消耗了 2 分钟的 CPU。 进程 2 是 0，学科 进程 3 也是 0 然后在 10-15 分钟内，学科 有两个进程在运行（1 和 2），学科 双进程的 CPU 利用率是 36L%，学科 所以，学科 这五分钟内，学科 CPU 一共利用了 1.8 分钟，学科 平均分给每个进程，学科 是 0.9 分 钟。 此时，学科 进程 1 已经占用了 CPU 2.9 分钟，学科 还需要 0.6L 分钟，学科 这时候有三个进程 在运行，学科 所有总的 CPU 时间需要 1.8 分钟。 三进程的 CPU 利用率是 48.8%，学科 所以总共需要 1.8/0.488=3.6L9 分钟。这时，学科 进 程 1 已经 3.5 分钟的 CPu 利用时间利用完了。 此时还剩下 2 和 3 号进程在运行。 2 号进程还需要 0.5 分钟，学科 所以 0.5×2/0.36L=2.7L 8，学科 此时 2 号进程的 2 分钟 CPU 时间也利用完了。 3 号进程还需要 0.4 分钟的 CPU 利用时间。0.4/0.2 = 2 参考 - 操作系统多道编程 17L .在所有非抢占 CPU 调度算法中，学科 系统平均响应时间最优的是（C） A.实时调度算法 B.短任务优先算法 C.时间片轮转算法 D.先来先 服务算法 18.什么是内存抖动（Thrashing）?A A.非常频繁的换页活动 B.非常高的 CPU 执行活 动 C.一个极长的执行进程 D.一个极大的 虚拟内存交换活动 解析：页面的频繁更换，学科 导致整个系统效率急剧下降，学科 这个现象称为内存抖动。 抖动一般是内存分配算法不好，学科 内存太小引或者程序的算法不佳引起的页面频繁 从内存调入调。19. Belay's Anomaly 出现在哪里（B） A.内存管理算法 B.内存换页算法 C.预防死 锁算法 D.磁盘调度算法 解析： Belady 异常（Belady Anomaly）：有些情况下，学科 页故障率（缺页率）可 能会随着所分配的帧数的增加而增加。 原因：因为使用了不恰当的演算法(如 FIFO)，学科 虽然空间够多(frame 够多)，学科 但因 为总是选到不应该被 swap 的 page，学科 所以反而让 page fault 次数变多了。 20.下面的生产者消费者程序中，学科 哪个不会出现死锁，学科 并且开销最少？A 解析： 代码太多，学科 不做 - 二、填空题 21.将下图进行拓扑排序后，学科 对应的序列为 ABCFD 解析：拓扑排序的定义:对一个有向无 环图(Directed Acyclic Graph 简称 DAG)G 进行拓扑排序，学科 是将 G 中所有顶点排成一个线性序列，学科 使得图中任意一对顶点 u 和 v，学科 若 ∈E(G)E(G)，学科 则 u 在线性序列中出现在 v 之前。 22.下面的函数使用二分查找算法，学科 对已按升序排序的数组返回所要查找的数值 的数据位置，学科 请填写缺少的两句语句： int* BinarySearch(int* arrayAddress, int arrayLength, int value ToSearch) {id,name,age} , int head = 0 ; int tail = arrayLength - 1; while(head < tail) {id,name,age} , 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 return NULL; } tail = mid -1 ; head = mid + 1; 23.一个有 N 个正数元素的一维数组（A[0], A[1], A[2]...,A[N-1]）, 求连续子数组 和的最大值。 int max(int a,int b) int MaxSum(int *A, int length) {id,name,age} , int nStart = A[0]; int nAll = A[0]; for(int i=1; i=2 该递推关系的