Google谷歌员工笔试试题及答案

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
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 (2)给出测试数据来证明程序运行的各种可能性。
2.给定一个数组 A，里面只出现 0-9 这 10 个数字，但不一定全部出现，然后给定一个 K 的值，求 A 中大于 K 的整数
当中最小的一个，并输出。例如 A={0，1}， k =12,则结果为 100. 请编程实现。
3.设 G 是一个无向加权图，每条边上设置一个权值，里面有 A、B 两个点，求由 A 点到 B 点的路径上边数不多于 M（给定的）时权数最小的路径和最小权数，不必写代码，但要求用尽量优的算法实现并分析时间复杂度。