阿里云
发表主题 回复主题
  • 556阅读
  • 0回复

十月下旬腾讯,网易游戏,百度迅雷校园招聘笔试题集锦(第271-330题)(1)

级别: 论坛版主
发帖
82
云币
147





问题导读
1、如果给定一个字符串,求出其最长的重复子串的算法是什么?
2、调用push_back时,其内部的内存分配是如何进行的?
3、C++ STL中vector调用clear时,内部是如何具体实现的?

十月下旬腾讯,网易游戏,百度迅雷校园招聘笔试题集锦(第271-330题)(1)-贵州十月下旬


1.JPG (21.38 KB, 下载次数: 0)



下载附件

 保存到相册



2014-11-21 20:32 上传













假设磁盘的旋转速度为20ms/周,磁盘当前处在R1的开头处,若系统顺序扫描后将数据放入单缓冲区内,处理数据的时间为4ms(然后再读取下个记录),则处理这10个记录的最长时间为(C)

A、180ms                           B、200ms                          C、204ms                             D、220ms


4、随着IP网络的发展,为了节省可分配的注册IP地址,有一些地址被拿出来用于私有IP地址,以下不属于私有IP地址范围的是(C)(私网IP地址:10.0.0.0- 10.255.255.255 ;172.16.0.0 -   172.31.255.255;192.168.0.0-192.168.255.255。故选C)

A、10.6.207.84                              B、172.23.30.28                      C、172.32.50.80               D、192.168.1.100


5、下列关于一个类的静态成员的描述中,不正确的是(D)

A、该类的对象共享其静态成员变量的值                              B、静态成员变量可被该类的所有方法访问                 

C、该类的静态方法只能访问该类的静态成员变量                 D、该类的静态数据成员变量的值不可修改


6、已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key) = key%7计算散列地址,并散列存储在散列表A【0....6】中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(C)

A、1.5                  B、1.7                           C、2.0                       D、2.3


依次进行取模运算求出哈希地址:

十月下旬腾讯,网易游戏,百度迅雷校园招聘笔试题集锦(第271-330题)(1)-11月下旬旅游


1.JPG (20.21 KB, 下载次数: 0)



下载附件

 保存到相册



2014-11-21 20:33 上传










74应该放在下标为4的位置,由于25已经放在这个地方,所以74往后移动,放在了下标为5的位置上了。

由于是等概率查找,所以结果为:1/6*(1+3+1+1+2+4)= 2.0


7、表达式“X=A+B*(C--D)/E”的后缀表示形式可以为(C)

A、XAB+CDE/-*=                     B、XA+BC-DE/*=                      C、XABCD-*E/+=                         D、XABCDE+*/=


8、(B)设计模式将抽象部分与它的实现部分相分离。

A、Singleton(单例)                   B、 Bridge(桥接)                     

C、 Composite(组合)                                   D、 Facade(外观)


9、下面程序的输出结果为多少?


  1. void Func(char str_arg[100])  


  2. {  


  3.     printf("%d\n",sizeof(str_arg));  


  4. }  


  5.   


  6. int main(void)  


  7. {  


  8.     char str[]="Hello";  


  9.     printf("%d\n",sizeof(str));  


  10.     printf("%d\n",strlen(str));  


  11.     char *p = str;  


  12.     printf("%d\n",sizeof(p));  


  13.     Func(str);  


  14. }


复制代码



输出结果为:6   5     4      4


对字符串进行sizeof操作的时候,会把字符串的结束符“\0”计算进去的,进行strlen操作求字符串的长度的时候,不计算\0的。


数组作为函数参数传递的时候,已经退化为指针了,Func函数的参数str_arg只是表示一个指针,那个100不起任何作用的。


10、下面程序的输出结果为多少?


  1. void Func(char str_arg[2])  


  2. {  


  3.     int m = sizeof(str_arg);     //指针的大小为4  


  4.     int n = strlen(str_arg);     //对数组求长度,str_arg后面的那个2没有任何意义,数组已经退化为指针了  


  5.     printf("%d\n",m);  


  6.     printf("%d\n",n);  


  7. }  


  8. int main(void)  


  9. {  


  10.     char str[]="Hello";  


  11.     Func(str);  


  12. }


复制代码



输出结果为:      4         5


strlen只是对传递给Func函数的那个字符串求长度,跟str_arg中的那个2是没有任何关系的,即使把2改为200也是不影响输出结果的。。


11、到商店里买200的商品返还100优惠券(可以在本商店代替现金)。请问实际上折扣是多少?

算法编程题:

1、给定一个字符串,求出其最长的重复子串。

思路:使用后缀数组,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。

这样的时间复杂度为:


生成后缀数组 O(N)

排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)

依次检测相邻的两个字符串 O(N * N)

总的时间复杂度是 O(N^2*logN),


网易游戏2011.10.15校园招聘会笔试题

1、对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。


2、如果X大于0并小于65536,用移位法计算X乘以255的值为:-X+X<<8


X<<8-X是不对的,X<<8,已经把X的值改变了(订正:X<<8是个临时变量,不会改变X的值,就像a+1不会改变a一样)。


3、一个包含n个节点的四叉树,每个节点都有四个指向孩子节点的指针,这4n个指针中有   3n+1   个空指针。


4、以下两个语句的区别是:


  1. int *p1 = new int[10];  


  2. int *p2 = new int[10]();  


复制代码




5、计算机在内存中存储数据时使用了大、小端模式,请分别写出A=0X123456在不同情况下的首字节是,大端模式:0X12           小端模式:0X56           X86结构的计算机使用  小端    模式。


一般来说,大部分用户的操作系统(如windows, FreeBsd,Linux)是小端模式的。少部分,如MAC OS,是大端模式 的。


6、在游戏设计中,经常会根据不同的游戏状态调用不同的函数,我们可以通过函数指针来实现这一功能,请声明一个参数为int *,返回值为int的函数指针:

  1. int (*fun)(int *)

复制代码




7、在一冒险游戏里,你见到一个宝箱,身上有N把钥匙,其中一把可以打开宝箱,假如没有任何提示,随机尝试,问:

(1)恰好第K次(1=<K<=N)打开宝箱的概率是多少。

(2)平均需要尝试多少次。


百度2011.10.16校园招聘会笔试题
一、算法设计

1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。


2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。


3、C++ STL中vector的相关问题:

    (1)、调用push_back时,其内部的内存分配是如何进行的?

    (2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作?

二、系统设计

正常用户端每分钟最多发一个请求至服务端,服务端需做一个异常客户端行为的过滤系统,设服务器在某一刻收到客户端A的一个请求,则1分钟内的客户端任何其它请求都需要被过滤,现知每一客户端都有一个IPv6地址可作为其ID,客户端个数太多,以至于无法全部放到单台服务器的内存hash表中,现需简单设计一个系统,使用支持高效的过滤,可使用多台机器,但要求使用的机器越少越好,请将关键的设计和思想用图表和代码表现出来。

三、求一个全排列函数:

如p([1,2,3])输出:

[123]、[132]、[213]、[231]、[321]、[323]

求一个组合函数

如p([1,2,3])输出:

[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]

这两问可以用伪代码。


迅雷2011.10.21笔试题

1、下面的程序可以从1....n中随机输出m个不重复的数。请填空


  1. knuth(int n, int m)


  2. {


  3.          srand((unsigned int)time(0));


  4.        for (int i=0; i<n; i++)


  5.           {


  6.                  if (            )


  7.                   {


  8.                                 cout<<i<<endl;


  9.                                                          ;


  10.                    }


  11.           }


  12. }


复制代码



分别为:rand()%(n-i)<m  和 m--;


2、以下prim函数的功能是分解质因数。请填空


  1. void prim(int m, int n)


  2. {


  3.     if (m>n)


  4.     {


  5.         while (            ) n++;


  6.                                        ;


  7.        prim(m,n);


  8.        cout<<n<<endl;


  9.     }


  10. }


复制代码



分别为:m%n  和 m/=n


3、下面程序的功能是输出数组的全排列。请填空


  1. void perm(int list[], int k, int m)


  2. {


  3.     if (            )


  4.     {


  5.         copy(list,list+m,ostream_iterator<int>(cout," "));


  6.         cout<<endl;


  7.         return;


  8.     }


  9.     for (int i=k; i<=m; i++)


  10.     {


  11.         swap(&list[k],&list[i]);


  12.                                          ;


  13.         swap(&list[k],&list[i]);


  14.     }


  15. }


复制代码



分别为:k==m 和 perm(list,k+1,m)


二、主观题:

1、(40分)用户启动迅雷时,服务器会以uid,login_time,logout_time的形式记录用户的在线时间;用户在使用迅雷下载时,服务器会以taskid,start_time,finish_time的形式记录任务的开始时间和结束时间。有效下载时间是指用户在开始时间和结束时间之间的在线时间,由于用户可能在下载的时候退出迅雷,因此有效下载时间并非finish_time 和 start_time之差。假设登录记录保存在login.txt中,每一行代表用户的上下线记录;下载记录保存在task.txt中,每一行代表一个任务记录,记录的字段之间以空格分开。计算每个用户的有效下载时间和总在线时间的比例。注意:请尽量使用STL的数据结构和算法


2、(60分)在8X8的棋盘上分布着n个骑士,他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次,可以从中间像8个方向移动(当然不能走出棋盘),请计算n个骑士的最早聚会地点和要走多少天。要求尽早聚会,且n个人走的总步数最少,先到聚会地点的骑士可以不再移动等待其他的骑士。

从键盘输入n(0<n<=64),然后一次输入n个骑士的初始位置xi,yi(0<=xi,yi<=7)。屏幕输出以空格分隔的三个数,分别为聚会点(x,y)以及走的天数。






本文转载自:http://blog.csdn.net/v_july_v/article/details/6880698

作者:结构之法 算法之道


发表主题 回复主题
« 返回列表
«12345678910»
共10页
上一主题下一主题

限100 字节
如果您在写长篇帖子又不马上发表,建议存为草稿
 
验证问题: 阿里云官网域名是什么? 正确答案:www.aliyun.com
上一个 下一个
      ×
      全新阿里云开发者社区, 去探索开发者的新世界吧!
      一站式的体验,更多的精彩!
      通过下面领域大门,一起探索新的技术世界吧~ (点击图标进入)

      版权声明

      开发者论坛为你提供“十月下旬腾讯,网易游戏,百度迅雷校园招聘笔试题集锦(第271-330题)(1)”的内容,论坛中还有更多关于 散列函数分离散列函数族传递字符串数组的问题字符型指针数组标签最长为10个字符 的内容供你使用,该内容是网友上传,与开发者论坛无关,如果需要删除请联系zixun-group@service.aliyun.com,工作人员会在5个工作日内回复您。