腾讯2012.9.23校园招聘会笔试题
1 表的设计最合理
数据库里面 一般是 学生，学科，分数 分开放。
因此A合理
2 数据库系统产生不一致的根本原因
数据库完整性是为了保证由授权用户对数据库所做的修改不会影响数据一致性的损失
觉得C合理
3 15L和27升两个杯子可以精确装多少水
15和27 升水 可以装出 3升水
27 + 3 +3 因此33合理
4 做递归文法 S->Aa|b A ->Ac | Sd |e
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
因此选A
5 排序算法中，初始数据集 对性能无影响
插入排序肯定有影响
快排当然有影响
冒泡排序 时间复杂度稳定在o(n2)有序的话，只会减少交换的次数
堆排序 时间复杂度稳定在O(nlogn)如果是已建好的堆，也只是减少交换的次数。
这道题目的答案 我选的堆排序。
6 二分有序数组查找
时间复杂度 O(logn)
7 路由器 当然包含网络层，链路层，和物理层。
主要作用就是选路和转发，当然网络层
8 select foo,count(foo) from pokes where foo>10 group by foo having count(*)>5 order by foo
SQL Select语句完整的执行顺序：
1、from子句组装来自不同数据源的数据；
2、where子句基于指定的条件对记录行进行筛选；
3、group by子句将数据划分为多个分组；
4、使用聚集函数进行计算；
5、使用having子句筛选分组；
6、计算所有的表达式；
7、使用order by对结果集进行排序。
因此 合理的答案应该为 from --where-- group by-- having --select-- order by
9 使用深度优先遍历算法 遍历下图，遍历顺序
这道题目 我咋看不出来 那个解呢。
如果深度的话 A B C D E F H I G
广度的话 A B C D E F G H I
所以 不清楚意思
10 unix系统 ，目录结构 带链接的树形目录是对的
11 fork问题 酷壳里面的问题。
printf("-");和printf("-\n");有很大区别
\n强制每个进程输出，而没有的话，先缓存
显然 输出四个 -- 为8
12 输出 6个- 为6
13 银行家算法避免死锁很基本的
14 分配延迟 一般指进程切换时间 在进程调度哪里 只有A
15 很简单 完成态没有
16 开始 任务 1： cpu 3.5分钟 io 14分钟
任务 2 ： 10分钟后 cpu 2 分钟 io 8分钟
任务3 ： 15分钟后 cpu 1.5分钟 io 6分钟
压力大，多道程序设计的概念忘记了
查了资料 io 花费p 则多道程序 cpu占用率 为 1-p^n只有 多个都处于等待才不是cpu时间
因此 分析过程如下
0-10分钟 cpu时间 10*0.2 = 2
10-15分钟 cpu利用率为 1-0.8^2 = 0.36 所以这 5分钟里面 cpu时间 为 0.36*5 =1.8
15 -之后 cpu利用率 1-0.8^3 = 0.488
0-10提供2分钟cpu时间
10-15 提供1.8分钟cpu时间
15 -18.7 提供1.8分钟cpu
18.7-21.5提供 1分钟cpu
21.5-23.5提供0.4分钟cpu时间
选B
17题 平均响应时间最优 感觉时间片轮转算法 ，我感觉是SJF
后面看书
18 题 内存抖动 平凡换页
19题 Belady异常（Belady Anomaly）：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。
内存换页吧
20题 虽然题目比较长不懂哪个 有人选A
21题 拓补排序 ABCFD
22题 二分比较简单
tail=mid
head = mid+1
23 题
nStart = max(nStart+A[i],0);
nAll = max(nAll,nStart);
24 前序遍历
abdefghc
25 第一项O(nlogn)。空间复杂度一般要O(n)。这个题我的博客另一篇文章中有讲到。
26 这是不太会，我算的65，有人这么算的一个卡特兰数 10！/5!*5! - 10！/4！*6！=42
27 逆波兰式 abcd-*e/+f-
三 附加题一的想法
大文件TOP(K)问题
今天我做的是易迅网，再次考到了这些题目。2012.10.26
- 1楼hhj1988481小时前
- [code=plain]nn[/code]