腾讯2012笔试题

参照来源:

http://www.cnblogs.com/jerry19880126/

http://blog.csdn.net/kingjinzi_2008/article/details/7785334

1、计算表达式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 * ()
是第三涂鸦乘法,所有常系数乘法都进行成连加

 

2、给得3单int类型的正整数x,y,z,对如下4组表达式判断对的抉择()

int a1=x+y-z; int b1=x*y/z;

int a2=x-z+y; int b2=x/z*y;

int c1=x<<y>>z; int d1=x&y|z;

int c2=x>>z<<y; int d2=x|z&y;

A、a1势必当a2

B、b1肯定定于b2

C、c1定当c2

D、d1一定当d2

A。

3、程序的一体化编译过程分成是:预处理,编译,汇编等,如下关于编译阶段的编译优化的传教遭到莫科学的凡()

A、死代码删除指的凡编译过程一直扔掉为诠释的代码;

B、函数内联可以免函数调用中压栈和退栈的开支

C、For循环的大循环控制变量通常十分合乎调度到寄存器访问

D、强度削弱是靠执行时比较短的一声令下等价的代表执行时比较丰富的通令

A。死代码是依赖永远不见面执行及之代码,不是注释,比如if(0){…},大括号里的即使是死代码。

4、如下关于进程的讲述不得法的凡()

A、进程在剥离时见面活动关闭自己打开的所有文件

B、进程在脱离时会见自行关闭自己打开的纱链接

C、进程在脱时会自动销毁自己创立的所有线程

D、进程在离时见面自动销毁自己打开的共享内存

D。共享内存销毁了,会针对另在使用这段内存的进程造成损坏。

 

5、在如下8*6底矩阵中,请计算从A移动至B一共有多少种走法?要求每次只能提高挥着往右侧移动一格,并且不能够经过P;

A、492

B、494

C、496

D、498

A。实际上是排列组合问题。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、动态链接库会使进程启动速度偏慢

B。优化编译

9、如下关于链接的传道似是而非的是()

A、一个静态库中无克包含两独同名全局函数的定义

B、一个动态库中莫可知包含两只同名全局函数的概念

C、如果个别独静态库都含有一个同名全局函数,他们无可知而为链接

D、如果少只动态库都带有一个同名全局函数,他们非克而让链接

C。静态库中编译器保证没有与名函数,两单静态库,编译完成后,会当不同类库,同名函数上丰富有些参数或者其他特定信息,从而以调用时分别,如果少只动态库都带有一个同名全局函数,他们非克而深受链接,因为全局函数是概念在类外的函数,成员函数就是概念在接近中的函数

10、排序算法的安静是指,关键码相同之笔录排序前后相对位置不出转移,下面哪种排序算法是免平稳的()

A、插入排序

B、冒泡排序

C、快速排序

D、归并排序

基础题,C。

11、下列说法遭到左的凡:()

A、插入排序某些情况下复杂度为O(n)

B、排序二叉树元素查找的复杂度可能也O(n)

C、对于有序列表的排序最抢之是快捷排序

D、在稳步列表中通过二分查找的复杂度一定是O(n log2n)

C。A当数码了有序时就是是O(n),B当数退化成线性表时(只来同等叉时)出现,C快排就对无序、随机行有优势。D是对的。

12、在先后设计着,要针对性有限只16K×16K的差不多精度浮点数二维数组进行矩阵求和经常,行优先读取和排优先读取的区分是()

A、没区别

B、行优先快

C、列优先快

D、2种读取方式速度也按机值,无法判定

B。

13、字符串www.qq.com所有非空子串(两独子串如果情节一致则独自算一个)个数是()

A、1024

B、1018

C、55

D、50

D.

14、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

15、操作系统的组成部分特地端口要呢特定的劳动做预留,必须使root权限才能够开拓的端口描述是的是()

A、端口号在64512-65535中的端口

B、所有小于1024之每个端口

C、RFC标准文档中早已宣示特定服务的连锁端口,例如http服务的80端口,8080端口等

D、所有端口还可免让权限限制打开

C。

16、找工作之季就就是到了,很多校友去图书馆借阅《面试宝典》这本开,现在图书馆外发生6叫做同学排队,其中3叫校友要拿手中的《面试宝典》还到图书馆,有3号称同班想于图书馆被可以借到《面试宝典》,若当前图书馆内既任库存《面试宝典》,要管借书的3称为同班可以借到开,请问这6位同学来微种排队方式()

A)60

B)120

C)180

D)360

C。卡特兰数,C(n,2n)/(n+1),n是入栈元素的个数,这里n=3,C(3,6)/4=5,同学相互是不同的,因此若都排一下,结果吧5*3!*3!=180

二、填空题

1、除了10进制、2进制之外,16进制表达式在计算机世界被呢时时以(例如各种字符集的定义描述),下式:(2012)10+(AF1)16的结果是(  
)(请用10进制表示)。

4813

2、ack(3 , 3)的实施结果是微?

int ack(int m,int n) 

    if(m == 0) 
        return n + 1; 
    else if(n == 0) 
        return ack(m-1,1); 
    else 
        return ack(m – 1 , ack(m , n-1)); 

 

61。耐心,ack(1,x)=2+x,ack(2,x)=3+x*2,ack(3,0)=5,ack(3,1)=ack(3,0)*2+3=13,ack(3,2)=ack(3,1)*2+3=29,ack(3,3)=ack(3,2)*3+2=61。

3、某互联网产品(例如,一放缓网络游戏)同时在线曲线(Average Concurrency
Users,ACU)24钟头数如下图所示。现已经清楚全天平均在线人数为5000人数,玩家每次登陆后平均在线时长为2钟头。请而估计一下,平均下来每分钟光景来(        
)个玩家登录。

4、如下SQL语句是待列有一个论坛版面第一页(每页显示20单)的帖子(post)标题(title),并随公布(create_time)降序排列:

SELECT title FROM post( )create_time DESC( )0,20

ORDER BY; LIMIT, 推荐SQL《学习指南》 

5、为了有型要,我们准备构造了一如既往种面向对象的脚本语言,例如,对有的平头,我们且经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独数之靶子急需创造。

6、甲、乙两单人口于玩猜数字游戏,甲随机写了一个数字,在[1,100]间隔内,将以此数字写于了同样摆张上,然后乙来猜。
使乙猜的数字偏小的话,甲会提示:“数字偏小”
假若乙猜的数字偏老的口舌,甲以后即令再也不会提示了,只会答应“猜对 或 猜错”
叩问: 乙至少猜 多少坏  猜可以精确猜出这个数字,在这种政策下, 
乙猜的率先只数字是 。

14差,第一次猜测数字也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)。

http://blog.csdn.net/kingjinzi_2008/article/details/7785334

引入;

同样道关于动态规划的面试题——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]));
关押出来了并未,其实最终便是采取动态规划来化解此问题。
下是友好管写的C++代码:
[cpp] view plaincopy
#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不好肯定能找来临界楼层。

 

7、仔细阅读以下函数

Int fuc(int m,int n)

{

if(m%n)==0

{

return n;

}

else

{

       return fuc(n,m%n)

}

}

恳请问func(2012,2102)的结果是(              )。

2。递归。,其实就是伸手最小公倍数,

加分题:

1、给一定一个数组a[N],我们想组织数组b[N],其中b[i]=a[0]*a[1]*…*a[N-1]/a[i]。在构造过程:
勿允行使除法;
渴求O(1)空间复杂度和O(n)时间复杂度;
除去整套历计数器与a[N]
b[N]他,不可采用初的变量(包括仓库临时变量、对空中与大局静态变量等);
伸手用程序实现并略描述。

请参考http://www.mianwww.com/html/2012/11/17098.html,有恢宏思路,值得学习、。

继承观察b[i]的布局发现,b[i]可形容成BaBb,其中Ba=a[0]*a[1]…*a[i-1],Bb=a[i+1]*a[i+2]…*a[n-1],自然之就联想到了独家从头跟尾巴全历a[n]计算Ba,Bb的方法

 

2、20世纪60年间,美国心理学家米尔格兰姆设计了一个有关信件实验。米尔格兰姆将信随即发送给住在美国各个城市的同等有居民,信中描绘有一个波士顿股票经纪人的名,并求各级名收信人把当下封信依托于协调看是较接近这名叫股票经纪人的心上人。这员情人接到信后再行管信教依托于他以为重新类似就名股票经纪人的意中人。最终,大部分信件都寄予到了这名股票经纪人手中,每封信平均经受6.2词到达。于是,米尔格兰姆提出六度分割理论,认为世界上无限制两个人口里建立联系最多特需要6独人。

只要QQ号大概发生10亿单注册用户,存储在一千高机械上的关系数据库中,每令机器存储一百万个用户及其的挚友信息,假设用户之平均好友个数大约为25口左右。

第一讯问:请您计划一个方案,尽可能快的测算存储任意两单QQ号之间是否六度(好友是1渡过)可达到,并得出这简单各用户六度可及的语,最差是屡屡可达成。

仲提问:我们期待获得平均每个用户之n度好友个数,以充实对用户更多之垂询,现在只要各级令机器一样秒钟可以回去一千长条查询结果,那么当10龙之光阴外,利用被有之硬件规格,可以统计出用户的最为多累好友个数?如果期望赢得更强之平均n度好友个数,可以什么改进方案?

3、段页式虚拟存储管理方案的特点。

空间浪费多少、存储共享容易、存储保护容易、能动态连接。
段页式管理是段式管理和页式管理结合而变成,兼闹段式和页式管理之亮点,每一样段分成多页,再遵照页式管理,页间不求连续(能动态连接);用分段方法分配管理作业,用分页方法分配管理内存(空间浪费多少)。

段页式管理使用二维地址空间,如段号(S)、页号(P)和页内单元号(D);系统建有限布置表每一样功课一样张段表,每一样段建立平等布置页表,段表指出该段的页表在内存中之职务;地址变换机构类似页式机制,只是前面增加一件段号。所以存储共享容易、存储保护容易。