騰訊校園招聘筆試試題大全(3)
二、填空題(共4題10個(gè)空，每空2分，共20 分)
1 設(shè)有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，請(qǐng)寫(xiě)出按二路歸并方法對(duì)該序列進(jìn)行一趟掃描后的結(jié)果為DQFXAPBNMYCW。
2 關(guān)鍵碼序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長(zhǎng)為4的Shell的排序法，則一趟掃描的結(jié)果是QACSQDFXRHMY;若采用以第一個(gè)元素為分界元素的快速排序法，則掃描一趟的結(jié)果是FHCDQAMQRSYX。
注意：
對(duì)于Shell排序，如果當(dāng)前位置為i，且初始步長(zhǎng)為4，那么相比較的是i和i+4。若不足的，則不進(jìn)行處理。
掃描一趟的意思就是說(shuō)：Partition一次，那么就可以按照代碼進(jìn)行劃分就可以了。
3 二進(jìn)制地址為011011110000，大小為(4)10和(16)10塊的伙伴地址分別為：_________，_________。
4 設(shè)t是給定的一棵二叉樹(shù)，下面的遞歸程序count(t)用于求得：二叉樹(shù)t中具有非空的左、右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0。N2，NL,NR、N0都是全局量，且在調(diào)用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);*/ |
三、其他方向簡(jiǎn)答題(共2題，每題20分)，選作題，不計(jì)入總分)
1 請(qǐng)?jiān)O(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)，能夠讓每個(gè)進(jìn)入隊(duì)伍的用戶都能看到自己在隊(duì)列中所處的位置和變化，隊(duì)伍可能隨時(shí)有人加入和退出;當(dāng)有人退出影響到用戶的位置排名時(shí)需要及時(shí)反饋到用戶。
2 A，B兩個(gè)整數(shù)集合，設(shè)計(jì)一個(gè)算法求他們的交集，盡可能的高效。
解：
方法一：用C++的容器set，不過(guò)該方法不適合于負(fù)數(shù)。
方法二：可以先進(jìn)行排序，然后設(shè)置兩個(gè)指針，進(jìn)行處理。
騰訊校園招聘筆試試題大全(3)
