騰訊校園招聘筆試試題大全(3)

　　二、填空題(共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。

　　三、其他方向簡答題(共2題，每題20分)，選作題，不計入總分)

　　1 請設計一個排隊系統，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出;當有人退出影響到用戶的位置排名時需要及時反饋到用戶。

　　2 A，B兩個整數集合，設計一個算法求他們的交集，盡可能的高效。

　　解：

　　方法一：用C++的容器set，不過該方法不適合于負數。

　　方法二：可以先進行排序，然后設置兩個指針，進行處理。