|
本帖最后由 凌波微燕 于 2009-7-29 11:02 编辑
9.22晚上，Google到中山大学南校区的小礼堂举行了宣讲会和笔试。以下是笔试题的大概内容，我只是凭借记忆写下来而已。
题型：9道单选题+3道算法题
一。单选题（不一定按照原来的顺序）
1.以下存储设备速度最快的是（）
A 内存 B硬盘 C寄存器 D。。。（忘了）
2.以下不适合作为虚拟内存页面调度的算法是（）
A 先进先出 B后进先出 C最少不使用 D随机调度
3.x=-54，整数都以两个16进制数表示，问一下不正确的是（）
A x的补码是0xCA
B x/2的补码是0x？？（忘了）
C2x的补码是0x？？ （忘了）
Dx向右移动一位后的补码是0x？？（忘了）
4.在24x+15y所表示的正整数集合里（x，y都是整数），按照由小到大的顺序排列，那么第23个数是多少（）
A 23
B 65
C和D都忘了。
5.设一个硬币抛出正面和反面的概率相等，抛10次 ** 现5次正面和5次反面的概率是p，抛10万次 ** 现5万次正面和5万次反面的概率是q，问（）
A p>q B p=q C p<q D 无法确定
6.汉诺塔问题，设有3个柱子，标记为1，2，3号，现有10个盘子（编号由上到下为abcd。。。j），现要把盘子按照原来的顺序搬到3号柱子，问第20个步骤是什么？有选项，不过全忘了，因为好长。
7.有4个相同的节点，用它们构建二叉树，问能有多少棵？（对称的算两棵）
A 10 B 17 C和D忘了
二算法题
1.
(1)给一个字符串，要你统计里面的ACII码的频数，其中大写的字母算作小写字母来统计，输出的时候这样输出：假如字符串是bbCca* ，则输出b：2 C：2 a：1 *：1，按字母首次出现的顺序输出。给出一个c函数的形式为void calc（char* input，int len），你也可以用你喜欢的语言去写。
(2)给出测试数据来证明程序运行的各种可能性。
2.给定一个数组A，里面只出现0-9这10个数字，但不一定全部出现，然后给定一个K的值，求A中大于K的整数当中最小的一个，并输出。例如A={0，1}， k =12,则结果为100. 请编程实现。
3.设G是一个无向加权图，每条边上设置一个权值，里面有A、B两个点，求由A点到B点的路径上边数不多于M（给定的）时权数最小的路径和最小权数，不必写代码，但要求用尽量优的算法实现并分析时间复杂度。
| 
/1 
发表于 2008-9-23 08:46
