EMC面试题--2006-05

　　先说我还没完全解决的题目：

　　(1)关于操作系统中cache的管理。规则是先舍弃使用次数最多的cache块。共有大约1000块cache。要求设计一个数据结构来支持以下操作，以使每种操作都能达到o(1)的时间复杂度。（n表示正在使用的cache块，N表示cache的数量）

　　1.n<N时，需要使用一个cache。

　　2.访问cache，包括访问后的调整。

　　3.n=N时，需要使用一个cache。

　　(2)这个是笔试时的题目，我没搞定。

　　比较S1和S2的大小：

　　S1 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ......

　　S2 = 根号（10/16）

　　下面是在提示下做出来的题目：

　　(1)一个N*N的对称矩阵，每行每列都是数字1~N的一种全排列。例如：

　　1 2 1 2 3

　　2 1 2 3 1

　　　　　　　　　　　　　3 1 2

　　注意，3*3矩阵的一条对角线也是1、2、3的一个全排列，而2*2的矩阵则不是。请问，什么样的N，能使N*N的矩阵在满足题目条件的情况下必然有一条对角线是1~N的一个全排列。

　　A.3的幂

　　B.奇数

　　C.除了2以外的质数

　　D.N=3

　　E.以上全对

　　提示：做一个小游戏，两人轮流在一个圆桌上放硬币，不准重叠。谁没法再放下一个硬币时算输。请问第一个人如何做才能确保胜利？最后桌上的硬币数量是奇是偶？