腾讯2012年实习生笔试题

一、单向选择题
1、给定3个int类型的正整数x，y，z，对如下4组表达式判断正确的选项（）
    A. int a1=x+y-z; int b1=x*y/z;
    B. int a2=x-z+y; int b2=x/z*y;
    C. int c1=x<>z; int d1=x&y|z;
    D. int c2=x>>z<
    A. 一定等于a2            B. 一定定于b2        C. 一定等于c2        D. 一定等于d2
解析：A
　　一开始觉得A肯定不对，因为会溢出，但不知道其实正如微机原理课上原的，溢出会有标识位，连加减的时候会考虑到这个标识位的作用，这样A就对了。
　　
2、程序的完整编译过程分为是：预处理，编译，汇编等，如下关于编译阶段的编译优化的说法中不正确的是（）
    A. 死代码删除指的是编译过程直接抛弃掉被注释的代码；
    B. 函数内联可以避免函数调用中压栈和退栈的开销
    C. For循环的循环控制变量通常很适合调度到寄存器访问
    D. 强度削弱是指执行时间较短的指令等价的替代执行时间较长的指令
解析：A
　　在大多数的机器上，调用函数都要做很多工作：调用前保存寄存器，并在返回时恢复；复制实参；程序还必须转向一个新位置执行。内联函数避免函数调用的开销。所谓死代码就是其计算结果永远不会被使用的语句。所谓强度削弱，就是用一种（或一串）执行时间较短的操作去等价地代替一个操作。例如，乘以2的n次方运算可以用左移来替换（例如，X*8可替换为X<<3），因为在多数机器上，左移运算的速度比乘法运算的速度快。

3、如下关于进程的面熟不正确的是（）
    A. 进程在退出时会自动关闭自己打开的所有文件
    B. 进程在退出时会自动关闭自己打开的网络链接
    C. 进程在退出时会自动销毁自己创建的所有线程
    D. 进程在退出时会自动销毁自己打开的共享内存
解析：D
　　共享内存销毁了，会对其他正在使用这段内存的进程造成破坏。
　　
4、计算表达式x6+4x4+2x3+x+1最少需要做（）次乘法
    A）3        B）4        C）5        D）6
解析：A
　　原式=x^2 * (x^4 + 4 * x^2 + 2*x) + x + 1，x^2用一次乘法，x^4看成是(x^2)^2，这样用掉第二次乘法，外面的x^2 * () 是第三次乘法，所有常系数乘法都展开成连加。
　　
5、在如下8*6的矩阵中，请计算从A移动到B一共有多少种走法？要求每次只能向上挥着向右移动一格，并且不能经过P；
    

    A）492        B）494        C）496        D）498
解析：A
　　走到B共需要12步，其中7步必须向右，5步必须向上，但次序可以不同，因此是C(7,12)，要求P不能走，那么走到P的可能次数是C(3,6)，从P走到B的可能次数是C(4,6)，因此结果是C(7,12) – C(3,6)*C(4,6)=492。
　　
6、SQL语言中删除一个表的指令是（）
    A. DROP TABLE        B. DELETE TABLE        C. DESTROY TABLE        D. REMOVE TABLE
解析：A

7、某产品团队由美术组、产品组、client程序组和server程序组4个小组构成，每次构建一套完整的版本时，需要各个组发布如下资源。美术组想客户端提供图像资源（需要10分钟），产品组向client组合server提供文字内容资源（同时进行，10分钟），server和client源代码放置在不同工作站上，其完整编译时间均为10分钟切编译过程不依赖于任何资源，client程序（不包含任何资源）在编译完毕后还需要完成对程序的统一加密过程（10分钟）。可以请问，从要完成一次版本构建（client与server的版本代码与资源齐备），至少需要多少时间（）
    A）60分钟        B）40分钟        C）30分钟        D）20分钟
解析：D
　　除了加密以外，剩下的事情在第一个10分钟内可以并发完成。
　　
8）如下关于编译链接的说法错误的是（）
    A. 编译优化会使得编译速度变慢
    B. 预编译头文件可以优化程序的性能
    C. 静态链接会使得可执行文件偏大
    D. 动态链接库会使进程启动速度偏慢
解析：D
　　静态链接：如果函数库的一份拷贝是可执行文件的物理组成部分
　　动态链接：如果可执行文件只是包含了文件名，让载入器在运行时能够导入程序所需要的函数库
　　静态链接的模块被链接编辑并载入以运行；
　　动态链接可执行文件比功能相同的静态链接可执行文件的体积小；

9）如下关于链接的说法错误的是（）
    A）一个静态库中不能包含两个同名全局函数的定义
    B）一个动态库中不能包含两个同名全局函数的定义
    C）如果两个静态库都包含一个同名全局函数，他们不能同时被链接
    D）如果两个动态库都包含一个同名全局函数，他们不能同时被链接
解析：C
    （解答参考网络）
    函数可以定义在3个地方1. 程序自身2. 静态库3. 动态库因为静态库是要链进程序的，所以函数定义在程序和静态库可以看成是一样的同名函数出现在程序和静态库中，链接时会报重定义的错误。同名函数出现在动态库中，编译链接都可以通过，但是调用会出问题，会出现覆盖问题。
    定义在这3个地方的函数，会调用哪个函数呢？
    1. 程序和静态库定义了同名函数，链接报错：重定义
    2. 程序或静态库定义的同名函数，会覆盖动态库中定义的函数
    3. 动态库中定义的同名函数，先链接覆盖后链接的函数

10）某火车站要通过一条栈道（先进后出）来调换进入车站的列车顺序，若进站的列车顺序为A、B、C，则下列哪个出站顺序不可能？（）
    A）ABC        B）ACB        C）CAB        D）CBA
解析：C

11）栈是一种智能在某一端插入和删除的特殊线性表，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，若6元素为A、B、C、D、E、F出栈顺序为B、D、C、F、E、A，则S栈的最小容量为（）
    A）3        B）4        C）5        D）6
解：A

12）找工作的季节马上就到了，很多同学去图书馆借阅《面试宝典》这本书，现在图书馆外有6名同学排队，其中3名同学要将手中的《面试宝典》还至图书馆，有3名同学希望从图书馆中可以借到《面试宝典》，若当前图书馆内已无库存《面试宝典》，要保证借书的3名同学可以借到书，请问这6位同学有多少种排队方式（）
    A）60        B）120        C）180        D）360
解析：卡特兰数：180
    Catalan数 C（2n , n）/( n+1 )   C(6,3)/4 = 55*3!*3! = 180

13）若完全二叉树的节点个数为2N-1，则叶节点个数为（）
    A）N-1        B）2×N        C）2N-1        D）2N
解析：
    结点拥有的子树数为结点的度
    证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：                    
                                                                    n=no+n1+n2 (式子1)　    
    另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：                    
                                                                    nl+2n2　　
    树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：                      
                                                                    n=n1+2n2+1 (式子2)　　
    由式子1和式子2得到：                      
                                                                    no=n2+1
    所以，n = n0 + n0 - 1 + 1 = 2n0

14）排序算法的稳定是指，关键码相同的记录排序前后相对位置不发生改变，下面哪种排序算法是不稳定的（）
　　A）插入排序        B）冒泡排序        C）快速排序        D）归并排序
解析：C

15）下列说法中错误的是：（）
    A）插入排序某些情况下复杂度为O（n）
    B）排序二叉树元素查找的复杂度可能为O（n）
    C）对于有序列表的排序最快的是快速排序
    D）在有序列表中通过二分查找的复杂度一定是O（n log2n）
解析：C

16）在程序设计中，要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和列优先读取的区别是（）
　　A）没区别        B）行优先快        C）列优先快    　D）2种读取方式速度为随机值，无法判断
解析：B
　　内存中数据可以“随机存取”：当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。相对的，读取或写入顺序访问（Sequential Access）存储设备中的信息时，其所需要的时间与位置就会有关系（如磁带）。
    
    本题关键是考抖动问题，如果按列访问就需要跳过很大一串内存地址  这样可能需求的内存地址不在当前页中  需要页置换  则需要硬盘IO  则较慢
　　
17）在下图的多边形ABCDE中从哪一点出发，可以遍历图上的每条边一次，而且仅遍历一次
    
    A. A点        B. B点        C. C点        D. D点
解：
    
18）字符串所有非空子串（两个子串如果内容相同则只算一个）个数是（）
    A）1024        B）1018        C）55        D）50
解析：D
　　长度1的子序列有10-2-1-1=6个，长度2子序列有9-1=8个，长度3有8个，长度4有7个…长度10有1个，加起来就是50。
　　
19）TCP的关闭过程，说法正确的是（）
    A）TIME_WAIT状态称为MSL（Maximum Segment Lifetime）等待状态
    B）对一个established状态的TCP连接，在调用shutdown函数之前调用close接口，可以让主动调用的一方进入半关闭状态
    C）主动发送FIN消息的连接端，收到对方回应ack之前不能发只能收，在收到对方回复ack之后不能发也不能收，进入CLOSING状态
    D）在已经成功建立连接的TCP连接上，如果一端收到RST消息可以让TCP的连洁端绕过半关闭状态并允许丢失数据。
解析：D
    //TIME_WAIT 是TCP链接断开时必定出现的状态，
    //TCP下每条连接都有一个属性叫做max segment lifetime，就是说该连接关闭后，要经过2*max segment lifetime的时间，才算是真正的被关闭，才能被重新建立，以防止这条链路上还有东西在传输
    //停留在TIME_WAIT状态的持续时间是最长分节生命周期(MSL)的两倍，有时候称之为2MSL

20）操作系统的一些特别端口要为特定的服务做预留，必须要root权限才能打开的端口描述正确的是（）
    A）端口号在64512-65535之间的端口
    B）所有小于1024的每个端口
    C）RFC标准文档中已经声明特定服务的相关端口，例如http服务的80端口，8080端口等
    D）所有端口都可以不受权限限制打开
解析：C

二、填空题
21）除了10进制、2进制之外，16进制表达式在计算机领域中也经常使用（例如各种字符集的定义描述），下式：(2012)10+(AF1)16的结果是（ 4813 ）（请用10进制表示）。

22）仔细阅读以下一段递归的函数定义：

in tack(int m,int n)
{
    if(m==0)
　　{
　　    return n+1;
　　}
　　Else if(n==0)
　　{
　　    return ack(m-1,1);
　　}
　　else
　　{
　　    retrun ack(m-1,ack(m,n-1));
　　}
}

    请问ack(3,3)的返回值是（ ）。

23）某互联网产品（例如，一款网络游戏）同时在线曲线（Average Concurrency Users，ACU）24小时数据如下图所示。现已知全天平均在线人数为5000人，玩家每次登陆后平均在线时长为2小时。请你估计一下，平均下来每分钟约有（ ）个玩家登录。
    

24）如下SQL语句是需要列出一个论坛版面第一页（每页显示20个）的帖子（post）标题（title），并按照发布（create_time）降序排列：
    SELECT title FROM post( order by )create_time DESC( limit )0,20

25）为了某项目需要，我们准备构造了一种面向对象的脚本语言，例如，对所有的整数，我们都通过Integer类型的对象来描述。在计算“1+2”时，这里的“1”，“2”和结果“3”分别为一个Integer对象。为了降低设计复杂度，我们决定让Integer对象都是只读对象，也即在计算a=a+b后，对象a引用的是一个新的对象，而非改a所指对象的值。考虑到性能问题，我们又引入两种优化方案：
    （1）对于数值相等的Integer对象，我们不会重复创建。例如，计算“1+1”，这里两个“1”的引用的是同一个对象——这种设计模式叫做（亨元模式）；
    （2）脚本语言解析器启动时，默认创建数值范围[1,32]的32个Integer对象。现在，假设我们要计算表达式“1+2+3+…+40”，在计算过程需要创建的Integer对象个数是（ 40 ）。
解析：
　　1到7以及他们的和是不用创建的，从8开始，28（是1到7的和）+8=36，36需要创建，36+9=45，45需要创建…依次类推，在加数是32之前（含32）需要创建的对象是32-8+1=25，某数+32=某数之后33至40所表示的加数也要创建，这样有8个加数 + 8个和，共有16个数需要创建，注意，加数中包含36，这个我们已经创建了，所以有25+8+8-1=40个数的对象需要创建。


26）A、B两人玩猜字游戏，游戏规则如下：
　　A选定一个 [1,100]之间的数字背对B写在纸上，然后让B开始猜；
　　如果B猜的偏小，A会提示B这次猜的偏小；
　　一旦B某次猜的偏大，A就不再提示，此次之后B猜的偏小A也不会再提示，只回答猜对与否。
　　请问：B至少要猜（ ）次才能保证猜对？在这种策略下，B第一次猜测的数字是（ ）。
解析：
　　第一次猜测数字为14。思想是：每次猜大后，尝试猜测的总次数是相等的。第一次猜测时，在1到100之间选择某个数N1后，有三种情况，一是直接选中了，这个概率比较小，对研究没有意义，二是选择偏大了，这时不再提示了，只能在1至N1-1之间一个一个地选了，三是选择偏小了，这时还有提示，可以继续在[N1+1,100]中选择另外的数N2。可以知道，若第一次就猜错了，那么尝试总次数是N1-1+1=N1次（因为是在[1,N1-1]之间逐一取值，且N1本身用掉一次），若第一次猜得偏小，但第二次猜大了，尝试总次数是[N1+1,N2-1]的元素个数加2（加2是N2和N1本身猜用掉一次），即为N2-N1+1次，根据思想“每次猜错后，尝试猜测的总次数相等”，有N1=N2-N1+1，可知N2=2N1-1，增量为N1-1。类似地，前两次猜得偏小，但第三次猜大，尝试总次数为[N2+1,N3-1]的元素个数加3，即N3-N2+2，那么有N3-N2+2=N1，N3=N2+N1-2，增量为N1-2……依此类推，增量是随着猜测次数的增加而逐1地减少。设最后一次猜测为k，则Nk=N1+(N1-1)+(N1-2)+…1，Nk是等于或大于100的第一个数，根据等差数列求和公式可以算出N1=14，N2=27，N3=39…（14,27,39,50,60,69,77,84,90,95,99）。
    ——————————————————————————————————————
    答案：猜测序列是14,、27、39、50、60、69、77、84、90、95、99因为无论第几次猜大了，最终的总次数总是14。     这个题目类似于一道Google面试题 ：  扔玻璃球求最高楼层。。
    一道关于动态规划的面试题——Google面试题：扔玻璃珠某幢大楼有100层。
    你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。首先，为了保存下一颗玻璃珠自己玩，就采用最笨的办法吧：从第一层开始试，每次增加一层，当哪一层扔下玻璃珠后碎掉了，也就知道了。不过最坏的情况扔的次数可能为100。
    当然，为了这一颗玻璃珠代价也高了点，还是采取另外一种办法吧。随便挑一层，假如为N层，扔下去后，如果碎了，那就只能从第一层开始试了，最坏的情况可能为N。假如没碎，就一次增加一层继续扔吧，这时最坏的情况为100-N。也就是说，采用这种办法，最坏的情况为max{N, 100-N+1}。之所以要加一，是因为第一次是从第N层开始扔。不过还是觉得不够好，运气好的话，挑到的N可能刚好是临界楼层，运气不好的话，要扔的次数还是很多。不过回过头看看第二种方式，有没有什么发现。假如没摔的话，不如不要一次增加一层继续扔吧，而是采取另外一种方式：把问题转换为100-N，在这里面找临界楼层，这样不就把问题转换成用递归的方式来解决吗？
    看下面：
    假如结果都保存在F[101]这个数组里面，那么：
    F[N]=100-N，
    F[100]=min（max（1，1+F[N-1]），max（2，1+F[N-2]），……，max（N-1，1+F[1]））;
    看出来了没有，其实最终就是利用动态规划来解决这个问题。

#include<iostream>
using namespace std;

int dp[101] = { 0 };

void solve()
{
    int i , j , k;
    for(i = 2 ; i < 101 ; ++i)
    {
        dp[i] = i;
        for(j = 1 ; j < i ; ++j)
        {
            k = (j>=(1 + dp[i-j])) ? j : (1 + dp[i-j]);
            if(dp[i] > k)
                dp[i] = k;
        }
    }
}

int main(void)
{
    dp[0] = 0 , dp[1] = 1;
    solve();
    printf("%d\n",dp[100]);
    return 0;
}

    输出结果为14。也就是说，最好的方式只要试14次就能够得出结果了。
    答案是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。
    证明如下：
    1、第一次抛棋子的楼层：最优的选择必然是间隔最大的楼层。比如，第一次如果在m层抛下棋子，以后再抛棋子时两次楼层的间隔必然不大于m层（大家可以自己用反证法简单证明）；
    2、从第二次抛棋子的间隔楼层最优的选择必然比第一次间隔少一层，第三次的楼层间隔比第二次间隔少一层，如此，以后每次抛棋子楼层间隔比上一次间隔少一层。（大家不妨自己证明一下）
    3、所以，设n是第一次抛棋子的最佳楼层，则n即为满足下列不等式的最小自然数：  不等式如下：  1+2+3+...+(n-1)+n  >=   100由上式可得出n=14即最优的策略是先从第14层抛下，最多抛14次肯定能找出临界楼层。

27）仔细阅读以下函数
    

Int fuc(int m,int n)
{
　　if(m%n)==0
　　{
　　return n;
　　}
　　else
　　{
　　    return fuc(n,m%n)
　　}
}

    请问func(2012,2102)的结果是（ ）。
　　
三 、加分题
28）给定一耳光数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：
　　要求O（1）空间复杂度和O（n）的时间复杂度；
　　除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）；
　　程序（主流编程语言任选）实现并简单描述。
解析：
    这个比较简单，略。

29）20世纪60年代，美国心理学家米尔格兰姆设计了一个连锁信件实验。米尔格兰姆把信随即发送给住在美国各城市的一部分居民，信中写有一个波士顿股票经纪人的名字，并要求每名收信人把这封信寄给自己认为是比较接近这名股票经纪人的朋友。这位朋友收到信后再把信寄给他认为更接近这名股票经纪人的朋友。最终，大部分信件都寄到了这名股票经纪人手中，每封信平均经受6.2词到达。于是，米尔格兰姆提出六度分割理论，认为世界上任意两个人之间建立联系最多只需要6个人。
　　假设QQ号大概有10亿个注册用户，存储在一千台机器上的关系数据库中，每台机器存储一百万个用户及其的好友信息，假设用户的平均好友个数大约为25人左右。
　　第一问：请你设计一个方案，尽可能快的计算存储任意两个QQ号之间是否六度（好友是1度）可达，并得出这两位用户六度可达的话，最短是几度可达。
　　第二问：我们希望得到平均每个用户的n度好友个数，以增加对用户更多的了解，现在如果每台机器一秒钟可以返回一千条查询结果，那么在10天的时间内，利用给出的硬件条件，可以统计出用户的最多几度好友个数？如果希望得到更高的平均n度好友个数，可以怎样改进方案？