腾讯2011.10.15校园招聘会笔试题 · IT公司笔试题集锦

转载请标明出处，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/6878287](http://blog.csdn.net/hackbuteer1/article/details/6878287) 1、下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（**B**） A、插入排序 **B、堆排序** C、冒泡排序 D、快速排序 2、以下关于Cache的叙述中，正确的是（**B**） A、CPU中的Cache容量应大于CPU之外的Cache容量 **B、Cache的设计思想是在合理成本下提高命中率** C、Cache的设计目标是容量尽可能与主存容量相等 D、在容量确定的情况下，替换算法的时间复杂度是影响Cache命中率的关键因素 3、数据存储在磁盘上的排列方式会影响I/O服务的性能，一个圆环的磁道上有10个物理块，10个数据记录R1------R10存放在这个磁道上，记录的安排顺序如下表所示： <table border="1" cellpadding="0" cellspacing="0" width="589"><tbody><tr><td>物理块</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>逻辑记录</td><td>R1</td><td>R2</td><td>R3</td><td>R4</td><td>R5</td><td>R6</td><td>R7</td><td>R8</td><td>R9</td><td>R10</td></tr></tbody></table> 假设磁盘的旋转速度为20ms/周，磁盘当前处在R1的开头处，若系统顺序扫描后将数据放入单缓冲区内，处理数据的时间为4ms（然后再读取下个记录），则处理这10个记录的最长时间为（**C**） A、180ms B、200ms C、204ms D、220ms 2+4+（（2+4）+2*8）*9=204 4、随着IP网络的发展，为了节省可分配的注册IP地址，有一些地址被拿出来用于私有IP地址，以下不属于私有IP地址范围的是（**C**） A、10.6.207.84 B、172.23.30.28 **C、172.32.50.80** D、192.168.1.100 私有IP地址共有三个范围段： A： 10.0.0.0~10.255.255.255 /8 　　B： 172.16.0.0~172.31.255.255 /12 　　C： 192.168.0.0~192.168.255.255 /16 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 依次进行取模运算求出哈希地址： <table border="1" cellpadding="0" cellspacing="0" width="591"><tbody><tr><td>A</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr><tr><td>记录</td><td>63</td><td>48</td><td> </td><td>38</td><td>25</td><td>74</td><td>52</td></tr><tr><td>查找次数</td><td>1</td><td>3</td><td> </td><td>1</td><td>1</td><td>2</td><td>4</td></tr></tbody></table> 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、下面程序的输出结果为多少？ ~~~ void Func(char str_arg[100]) { printf("%d\n",sizeof(str_arg)); } int main(void) { char str[]="Hello"; printf("%d\n",sizeof(str)); printf("%d\n",strlen(str)); char *p = str; printf("%d\n",sizeof(p)); Func(str); } ~~~ 输出结果为：6 5 4 4 对字符串进行sizeof操作的时候，会把字符串的结束符“\0”计算进去的，进行strlen操作求字符串的长度的时候，不计算\0的。数组作为函数参数传递的时候，已经退化为指针了，Func函数的参数str_arg只是表示一个指针，那个100不起任何作用的。 10、C++将父类的析构函数定义为虚函数，下列正确的是哪个？ A、释放父类指针时能正确释放子类对象 B、释放子类指针时能正确释放父类对象 C、这样做是错误的 D、以上全错 C++的多态肯定是使用父类的指针指向子类的对象，所以肯定是释放子类的对象，如果不使用虚函数的话，父类的指针就只能够释放父类的对象。 11、下列哪一个不属于关系数据库的特点？ A、数据冗余度小 B、数据独立性高 C、数据共享性好 D、多用户访问 12、下面程序的输出结果为多少？ ~~~ void Func(char str_arg[2]) { int m = sizeof(str_arg); //指针的大小为4 int n = strlen(str_arg); //对数组求长度，str_arg后面的那个2没有任何意义，数组已经退化为指针了 printf("%d\n",m); printf("%d\n",n); } int main(void) { char str[]="Hello"; Func(str); } ~~~ 输出结果为： 4 5 strlen只是对传递给Func函数的那个字符串求长度，跟str_arg中的那个2是没有任何关系的，即使把2改为200也是不影响输出结果的。。 13、typedef char *String_t; 和 #define String_d char * 这两句在使用上有什么区别？答：typedef char *String_t 定义了一个新的类型别名，有类型检查。而#define String_d char * 只是做了个简单的替换，无类型检查，前者在编译的时候处理，后者在预编译的时候处理。同时定义多个变量的时候有区别，主要区别在于这种使用方式String_t a,b; String_d c,d; a,b ,c都是char*类型，而d为char类型由于typedef还要做类型检查。。#define没有。。所以typedef比#define安全。。 14、到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？ 15、题目：已知rand7() 可以产生 1~7 的7个数（均匀概率），利用rand7() 产生rand10() 1~10（均匀概率）记住这道题重点是：均匀概率 ~~~ //rand7 产生的数概率是一样的,即1~7出现概率一样，由于我们对结果做了一定的筛选只能通过 1~5，而1~5出现的概率也是一样的，又由于范围为1~5 所以 temp1 出现 1~5的概率为1/5 ,同理后面的出现 temp2 的概率为 1/2 //首先temp1出现在1~5的概率为1/5，而temp2出现 1~2 的概率为1/2，也就是说 5*(temp2-1) 出现5或0的概率为1/2,所以假如你要得到1~5的数的话那么 5*（temp2-1）必须0，所以因为你要保证 5*（temp2-1）=0，这个概率只有1/2,再加上你前面指定1~5 的概率为1/5 ,所以结果为 1/5*1/2=1/10 int rand10() { int temp1; int temp2; do { temp1 = rand7(); }while(temp1>5); do { temp2 = rand7(); }while(temp2>2); return temp1+5*(temp2-1); } ~~~ 16、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。 17、对一个正整数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到1时操作停止，求经过9次操作变为1的数有多少个？第9次操作：结果1由2产生。1个被操作数 8：结果2只能由4产生。1个被操作数 7：结果4由8、3产生。2个 6：结果8由16、7产生；结果3由6产生。共3个 5：结果16由32、15产生；结果7由14产生；结果6由12、5产生。共5个… 每次操作，偶数（2除外）都由该数减1和该数的2倍得来，奇数只由该数的2倍得来各次操作的操作对象个数为：1，1，2，3，5，8，13，21，34，… 本题可以通过所给的变换规律，由易到难，确定操作可变为1的数组成斐波拉契数列，再根据所发现的规律求出经过9次操作变为1的数的个数。 18、OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。 ~~~ #define OFFSETOF(s,m) ((int)&(((s*)0)->m)) ~~~ 用地址零作为起始地址，强制转换成结构体类型，然后取出成员的地址，转换成int类型，就可以得到偏移量了。算法编程题： 1、给定一个字符串，求出其最长的重复子串。思路：使用后缀数组，对一个字符串生成相应的后缀数组后，然后再排序，排完序依次检测相邻的两个字符串的开头公共部分。这样的时间复杂度为：生成后缀数组 O(N) 排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N) 依次检测相邻的两个字符串 O(N * N) 总的时间复杂度是 O(N^2*logN), 转载请标明出处，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/6878287](http://blog.csdn.net/hackbuteer1/article/details/6878287)