10月15日深信服笔试

时间:2021-01-06 14:39:54
去到的时候,人特多,很多有收到通知的都还没位置坐,最后才多申请了间教室给他们
也没有草稿纸。。。
我们算法的试题有4页,软件开发的有5页,由于算法的比较难,所以允许我们15分钟内换试题。
我看了下,还行,选择题基本都会做,大题最后一道更是我的得意题目:博弈。
于是我就不换了,静下心来做。
还行,半小时做了选择题,15分钟做了最后一道大题,20分钟思考了一道逻辑题,15分钟做了唯一一道写代码题,字符串匹配的,然后其他的每一道都不花超过5分钟了,随便写点思路下去就OK了,所以最终结果是全部做了,虽然只是马虎应付,还是很有快感的。
最后剩下二十分钟就填完了,看着周围的人还有些空白呢,我拿起本子来,把整张试卷的大多数题目抄了下来,下面就给大家参考下:
前三道选二,思考题:
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);
}
好像题目大概是这样,主要考察全局变量和static变量,以及++的概念,具体答案因为数值问题我就不太清楚了。