Google 笔试01

题型：9道单选题+3道算法题

    
一。单选题1.以下存储设备速度最快的是（）
A 内存 B硬盘 C寄存器
    
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.设G是一个无向加权图，每条边上设置一个权值，里面有A、B两个点，求由A点到B点的路径上边数不多于M（给定的）时权数最小的路径和最小权数，不必写代码，但要求用尽量优的算法实现并分析时间复杂度。

3.

设计一个cache系统．
１）列出设计时需要考虑的几个问题；
２）设计出数据结构和主要函数的为代码
３）描述你所使用的调度算法，并分析；
４）设计分布式cache系统，并说明其扩展性