笔试题 天呢 真难！该怎么处理
笔试题 天呢 真难！！！！
前三道选二，思考题：
1.假设路由器中有n条系统路由，每个路由条目由目标IP和子网掩码组成，现在需要转发网络的数据，请设计一个高效的路由寻找算法。
2.Web Cache（网页内容查找），要把出现最多的网页的内容存在内存中，如果查不到内容，则放到磁盘里，如果磁盘满了，则把冷网页淘汰掉。请设计一个算法。
3.请设计一方案，尽可能短在10GB源串（数据保存在硬盘中）寻找某模式串（大小4KB）的最大匹配，在开始模式匹配前，可以对10GB数据进行分析处理，中间的分析数据可以存放在100MB左右的内存内。
二：算法基础题
1.有a,b,c,d,e五个袋子里面装了26个玻璃球，没有空的也没有相同玻璃球数量的袋子，已知道a+e,b+c,c+d都超过了11个玻璃球，而a +c小于11个玻璃球，请问有多少种可能的由小到大的组合？（例如1，3，5，7，10，但是1，5，3，7，10不是正确的组合）。解题空有6个空，但不一定都要填。
2.假设Hash函数是随机的，在n个桶中插入m个元素后平均占用多少个桶？（用数学表达式）
3.字符串匹配，例如，T=abcabaabcabac，P=abaa，则匹配位是3，请用伪代码写一下算法，并分析时间复杂度，看看是否可以再进一步优化。
4.已知道多边形的各个节点，这些节点连成了这个多边形，如何判断某一个点是否在这个多边形内呢？
5.有两堆球，每堆都有10个，每个都标有重量，请设计算法重新分配这两堆球，使得两堆球的总重量之差最小。
6.有1001个球，两人轮流拿，每次只能拿1、2或者4个，谁拿了最后的一次就算谁输，假设是你先拿，请问你有把握获胜么？如果有，你该怎么拿，如果没有，为什么？
选择题：
1.下面哪个结构，获得一个值最快？A.binary tree B.Hash table C.stack
2.对12354排序，哪种最快？A.快速排序 B.归并排序 C。冒泡排序 D。堆排序
3.(M)?(a++):(a--) 其中(M)等价于？ A.M==0 B.M==1 C.M!=0 D.M!=1
4.下面关于枚举变量的说法，哪些是对的？
A.枚举类型可以进行比较。
B.枚举类型可以赋值。
C.枚举类型可在定义同时制定其值。
D.枚举类型可以作常量使用。
5-6，两道常常的看程序判断运行结果题目咯
其中有一道是：
int a=2;
int function(int n){
int t=0;
if(n%2==0){
static int a=5;t+=a++;return t+a++;}
else{
static int a=4;t+=a++;return t+a++;}
}
void main(){
int s=0,i;
for(i=0;i<3;i+=2)
s+=function(i);
printf("%d",s);
}
------解决方案--------------------
算法基础题 1 a+b+c+d+e=26
又 a+e>11,b+c>11,c+d>11则a+b+c+d+e+c>33
所以有26+c>33 推出c>7,又a+c<11 推出a<4
------解决方案--------------------
------解决方案--------------------
算法基础题
2.假设Hash函数是随机的，在n个桶中插入m个元素后平均占用多少个桶？（用数学表达式）
不知道“Hash函数”在这里是什么意思（知道的请告诉我谢谢），我对题目改动如下：
在n个桶中随机放入m个元素后平均占用多少个桶？
解：
用一个接一个放的方式来解此题。
设放入m个元素后占用f(m)个桶。
m=1 显然f(1)=1
m=2 有1/n的概率f(m)还是1，有(n-1)/n的概率f(m)增加了1，所以 f(2) = [1/n] * f(1) + {[n-f(1)]/n} * [f(1)+1]
同理,f(m) = [1/n] * f(m-1) + {[n-f(m-1)]/n} * [f(m-1)+1] = [(n-1)/n]*f(m-1) + 1
当然这是在f(m-1)<n的情况下才成立。
由此式就可以很容易的得出最终的f(m) = [(n-1)/n]^(m-1) + [(n-1)/n]^(m-2) ; m>=2,f(m)<n
------解决方案--------------------
1.有a,b,c,d,e五个袋子里面装了26个玻璃球，没有空的也没有相同玻璃球数量的袋子，已知道a+e,b+c,c+d都超过了11个玻璃球，而a +c小于11个玻璃球，请问有多少种可能的由小到大的组合？（例如1，3，5，7，10，但是1，5，3，7，10不是正确的组合）。解题空有6个空，但不一定都要填。
根据我的计算这题无解:
依据
a+b+c+d+e=26 ---0
a+e>11 ---1
b+e>11 ---2
c+d>11 ---3
a+c<11 ---4
由1,2,3相加获得
a+b+c+d+e+c>33 ----5
在由0等量代换获得
26+c>33 ==>c>7
假定c=7,在根据e>d>c的条件假定
d=8,e=9
而根据目前假定的值
c+d+e=24
那么a+b=2,由于b>a的条件,则
a=0,b=2,但是abcde不为空,所以此题矛盾,无解
------解决方案--------------------
如果你剩6个给对方呢？？对方拿2个，剩4个给你，你必输。
我推算正确的应该是剩下3n+1的时候，此时拿的人必输。
3n时，拿2个必赢
3n-1时，拿1个或者4个必赢。
所以1001个球，可以拿1个或4个必赢
前三道选二，思考题：
1.假设路由器中有n条系统路由，每个路由条目由目标IP和子网掩码组成，现在需要转发网络的数据，请设计一个高效的路由寻找算法。
2.Web Cache（网页内容查找），要把出现最多的网页的内容存在内存中，如果查不到内容，则放到磁盘里，如果磁盘满了，则把冷网页淘汰掉。请设计一个算法。
3.请设计一方案，尽可能短在10GB源串（数据保存在硬盘中）寻找某模式串（大小4KB）的最大匹配，在开始模式匹配前，可以对10GB数据进行分析处理，中间的分析数据可以存放在100MB左右的内存内。
二：算法基础题
1.有a,b,c,d,e五个袋子里面装了26个玻璃球，没有空的也没有相同玻璃球数量的袋子，已知道a+e,b+c,c+d都超过了11个玻璃球，而a +c小于11个玻璃球，请问有多少种可能的由小到大的组合？（例如1，3，5，7，10，但是1，5，3，7，10不是正确的组合）。解题空有6个空，但不一定都要填。
2.假设Hash函数是随机的，在n个桶中插入m个元素后平均占用多少个桶？（用数学表达式）
3.字符串匹配，例如，T=abcabaabcabac，P=abaa，则匹配位是3，请用伪代码写一下算法，并分析时间复杂度，看看是否可以再进一步优化。
4.已知道多边形的各个节点，这些节点连成了这个多边形，如何判断某一个点是否在这个多边形内呢？
5.有两堆球，每堆都有10个，每个都标有重量，请设计算法重新分配这两堆球，使得两堆球的总重量之差最小。
6.有1001个球，两人轮流拿，每次只能拿1、2或者4个，谁拿了最后的一次就算谁输，假设是你先拿，请问你有把握获胜么？如果有，你该怎么拿，如果没有，为什么？
选择题：
1.下面哪个结构，获得一个值最快？A.binary tree B.Hash table C.stack
2.对12354排序，哪种最快？A.快速排序 B.归并排序 C。冒泡排序 D。堆排序
3.(M)?(a++):(a--) 其中(M)等价于？ A.M==0 B.M==1 C.M!=0 D.M!=1
4.下面关于枚举变量的说法，哪些是对的？
A.枚举类型可以进行比较。
B.枚举类型可以赋值。
C.枚举类型可在定义同时制定其值。
D.枚举类型可以作常量使用。
5-6，两道常常的看程序判断运行结果题目咯
其中有一道是：
int a=2;
int function(int n){
int t=0;
if(n%2==0){
static int a=5;t+=a++;return t+a++;}
else{
static int a=4;t+=a++;return t+a++;}
}
void main(){
int s=0,i;
for(i=0;i<3;i+=2)
s+=function(i);
printf("%d",s);
}
------解决方案--------------------
算法基础题 1 a+b+c+d+e=26
又 a+e>11,b+c>11,c+d>11则a+b+c+d+e+c>33
所以有26+c>33 推出c>7,又a+c<11 推出a<4
------解决方案--------------------
------解决方案--------------------
算法基础题
2.假设Hash函数是随机的，在n个桶中插入m个元素后平均占用多少个桶？（用数学表达式）
不知道“Hash函数”在这里是什么意思（知道的请告诉我谢谢），我对题目改动如下：
在n个桶中随机放入m个元素后平均占用多少个桶？
解：
用一个接一个放的方式来解此题。
设放入m个元素后占用f(m)个桶。
m=1 显然f(1)=1
m=2 有1/n的概率f(m)还是1，有(n-1)/n的概率f(m)增加了1，所以 f(2) = [1/n] * f(1) + {[n-f(1)]/n} * [f(1)+1]
同理,f(m) = [1/n] * f(m-1) + {[n-f(m-1)]/n} * [f(m-1)+1] = [(n-1)/n]*f(m-1) + 1
当然这是在f(m-1)<n的情况下才成立。
由此式就可以很容易的得出最终的f(m) = [(n-1)/n]^(m-1) + [(n-1)/n]^(m-2) ; m>=2,f(m)<n
------解决方案--------------------
1.有a,b,c,d,e五个袋子里面装了26个玻璃球，没有空的也没有相同玻璃球数量的袋子，已知道a+e,b+c,c+d都超过了11个玻璃球，而a +c小于11个玻璃球，请问有多少种可能的由小到大的组合？（例如1，3，5，7，10，但是1，5，3，7，10不是正确的组合）。解题空有6个空，但不一定都要填。
根据我的计算这题无解:
依据
a+b+c+d+e=26 ---0
a+e>11 ---1
b+e>11 ---2
c+d>11 ---3
a+c<11 ---4
由1,2,3相加获得
a+b+c+d+e+c>33 ----5
在由0等量代换获得
26+c>33 ==>c>7
假定c=7,在根据e>d>c的条件假定
d=8,e=9
而根据目前假定的值
c+d+e=24
那么a+b=2,由于b>a的条件,则
a=0,b=2,但是abcde不为空,所以此题矛盾,无解
------解决方案--------------------
如果你剩6个给对方呢？？对方拿2个，剩4个给你，你必输。
我推算正确的应该是剩下3n+1的时候，此时拿的人必输。
3n时，拿2个必赢
3n-1时，拿1个或者4个必赢。
所以1001个球，可以拿1个或4个必赢