2011-10-15腾讯校园招聘笔试题目与参考答案

1，下列排序算法中，初始数据集的排序程序对算法性能无影响的是（）

A，插入排序B，堆排序 C，冒泡排序，D，快速排序

 答案：B，冒泡的复杂度恒定为O(n^2)，插入排序最差是O(n^2)，最优化为O(n);堆排序建堆的时间是O(n)，但是，排序的过程是O(nlogn)，固定不变;

冒泡排序虽然大家都认为是O(n^2)，但是，优化的冒泡是使用一个flag的，如果flag不变，说明不需要 再交换元素了,最优可以到O(n)，快速排序不解释，最差的情况每一次只分出一个元素，最差是O(n^2)，最优的时候是O(nlogn)

2，关于cache的描述中，以下说法正确的是（）

CPU内的Cache容量应该大于CPU外的Cache容量

Cache的设计思想是在合理成本下提高命中率

Cache的设计目标是容量尽可能地与主存储容量相当

在容量确定的情况下，替换算法的时间复杂度是影响Cache命中的关键因素

答案：B，Cache一般比较小，但是，速度会更快，CPU内的Cache容量显然小于CPU外的，其设计原理是利用程序的局部性原理，即一断数据现在被访问，可能一会又会被访问，目标是提高数据的访问速度，其命中率的关键因素与替换算法有关系，而不是替换算法的复杂度

3，数据存储在磁盘上的方式直接影响IO性能，现在假设一个磁道有10个物理块，一批数据的存储如下：

磁盘的转速度是20ms/R，这批数据一次只能被处理一个记录，把这个记录读到缓冲区里面，再处理，处理一个记录需要4ms，起始时磁头位于R1，问把这10个记录全部完需要多少时间。（）

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

答案：C，要知道的是磁片会一直转，当第一个记录被处理完是，磁片已经转到R4这个地方了（读需要2ms，处理需要4ms），下一个记录是R2，为了读取R2，磁片必需转过R5，R6…R10再到R2。一直这样算下去，结果是204。

4，以下不是私有IP的是（）

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

答案：C有地址有以下三断

10.0.0.0~10.255.255.255         192.168.0.0~192.168.255.255

172.160.0~172.31.255.255

5，下列关于一个类的静态成员的描述中，不正确的是（）

A、该类的对象共享其静态成员变量的值

B、静态成员变量可被该类的所有方法访问

C、该类的静态方法只能访问该类的静态成员变量

D、该类的静态数据成员变量的值不可修改

答案：D，静态变量（static变量）是一个类的变量，是这个类所有的对象公共的，这个类的所有函数都可以访问与修改（如果是const就算了），因此选D

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

A，.5            B，7     C，2.0 D，2.3

答案：C，

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

由于是等概率查找，所以结果为：1/6*（1+3+1+1+2+4）= 2.0

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

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

答案C，后缀是波兰表达式，前缀是逆波兰表达式，这个最好搞清楚一下，还要搞清楚他们与二叉树的访问的关系。

8，（）设计模式将抽象部分与它的实现部分相分离。

A， Singleton（单例）          B， Bridge（桥接）

C， Composite（组合）        D，Facade（外观）

答案B，在Singleton的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案；

在软件系统中，某些类型由于自身的逻辑，它具有两个或多个维度的变化，那么如何应对这种“多维度的变化”？如何利用面向对象的技术来使得该类型能够轻松的沿着多个方向进行变化，而又不引入额外的复杂度？这就要使用Bridge模式。

组合设计模式不解释，就是包含

外观设计模式有个最大的特点将细粒度的对象包装成粗粒度的对象，应用程序通过访问这个外观对象，来完成细粒度对象的调用，外观模式一般是分布式应用和系统架构中的应用服务层的设计中常用的方式

9，下面程序的输出结果为多少？

 void Func(charstr_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

注意当数组传给函数的时候（函数调用），会退化成指针，指针与机器的位数有关，32位系统是32bit，64位系统是64bit，sizeof应用在字符串身上的时候要计算在后面加的一个’\0’，比如，sizeof(“A\0B\0”)应该是5，因为最后还会加一个0，但是，strlen却是碰到0就结束，因此strlen(“A\0B\0”)应该是1.

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

 void Func(charstr_arg[2])

 {

 int m = sizeof(str_arg);

 int n = strlen(str_arg);

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

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

 }

intmain(void)

{

charstr[]="Hello";

 Func(str);

 } 

答案：输出结果为：4  5，数组传递给函数的时候会退化成指针，在函数原型里面看到char x[10]和char x[90]一样，都当成char *处理，strlen会一直数，直到‘\0‘为止。

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

答案：5折，n元最后可以买2n元的东西，首先，n元可以获取n/2的优惠券，继续是n/4的优惠券...最后一直可以买到2n元的东西，果断5折