腾讯校园招聘笔试试题大全(3)

时间：2015-08-29 15:42:38 敏敏644由分享

　　二、填空题(共4题10个空，每空2分，共20 分)

　　1 设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，请写出按二路归并方法对该序列进行一趟扫描后的结果为DQFXAPBNMYCW。

　　2 关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是QACSQDFXRHMY;若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是FHCDQAMQRSYX。

　　注意：

　　对于Shell排序，如果当前位置为i，且初始步长为4，那么相比较的是i和i+4。若不足的，则不进行处理。

　　扫描一趟的意思就是说：Partition一次，那么就可以按照代码进行划分就可以了。

　　3 二进制地址为011011110000，大小为(4)10和(16)10块的伙伴地址分别为：_________，_________。

　　4 设t是给定的一棵二叉树，下面的递归程序count(t)用于求得：二叉树t中具有非空的左、右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2，NL,NR、N0都是全局量，且在调用count(t)之前都置为0。

typedefstructnode

{

intdata;

structnode*lchild,*rchild;

}node;

intN2,NL,NR,N0;

voidcount(node*t)

{

if(t->lchild!=NULL)

if(t->rchild!=NULL)N2++;

elseNL++;

elseif(t->rchild!=NULL)NR++;

elseN0++;

if(t->lchild!=NULL)count(t->lchild);

if(t->rchild!=NULL)count(t->rchild);

}/*callform:if(t!=NULL)count(t);*/

　　三、其他方向简答题(共2题，每题20分)，选作题，不计入总分)

　　1 请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出;当有人退出影响到用户的位置排名时需要及时反馈到用户。

　　2 A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

　　解：

　　方法一：用C++的容器set，不过该方法不适合于负数。

　　方法二：可以先进行排序，然后设置两个指针，进行处理。