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

　　二、填空題(共4題10個空，每空2分，共20 分)

　　1 設(shè)有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，請寫出按二路歸并方法對該序列進(jìn)行一趟掃描后的結(jié)果為DQFXAPBNMYCW。

　　2 關(guān)鍵碼序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長為4的Shell的排序法，則一趟掃描的結(jié)果是QACSQDFXRHMY;若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結(jié)果是FHCDQAMQRSYX。

　　注意：

　　對于Shell排序，如果當(dāng)前位置為i，且初始步長為4，那么相比較的是i和i+4。若不足的，則不進(jìn)行處理。

　　掃描一趟的意思就是說：Partition一次，那么就可以按照代碼進(jìn)行劃分就可以了。

　　3 二進(jìn)制地址為011011110000，大小為(4)10和(16)10塊的伙伴地址分別為：_________，_________。

　　4 設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得：二叉樹t中具有非空的左、右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2，NL,NR、N0都是全局量，且在調(diào)用count(t)之前都置為0。

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

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

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

　　解：

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

　　方法二：可以先進(jìn)行排序，然后設(shè)置兩個指針，進(jìn)行處理。