騰訊商業(yè)分析筆試題

Word第第頁騰訊商業(yè)分析筆試題一不定項(xiàng)選擇題(共25題，每題4分，共100分，少選、錯(cuò)選、多項(xiàng)選擇均不得分)

1已知一棵二叉樹，假如先序遍歷的節(jié)點(diǎn)挨次是：ADCEFGHB，中序遍歷是：CDFEGHAB，則后序遍歷結(jié)果為：(D)

A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA

先序遍歷：根左右，因此可以通過先序遍歷得到父子關(guān)系，即在前面確定是后面的父節(jié)點(diǎn)。中序遍歷：左根右，通過中序遍歷可以獲得某個(gè)節(jié)點(diǎn)的左右孩子(直接)，因此可以還原出這課二叉樹為：，得出這棵二叉樹后就可以推出它的后序遍歷。

2以下哪兩個(gè)數(shù)據(jù)結(jié)構(gòu)，同時(shí)具有較高的查找和刪除性能?(CD)

A.有序數(shù)組B.有序鏈表C.AVL樹D.Hash表

A和B沒什么可說的，DHash表的查找的時(shí)間冗雜度：不沖突時(shí)為O(1)，刪除也為O(1)，沖突時(shí)為O(C),O(C)都是常數(shù)量級(jí)別的。所以必選。

補(bǔ)充一下，在開放地址方法時(shí)不能物理刪除，只能做一個(gè)刪除標(biāo)記。若是鏈?zhǔn)降刂贩椒ǖ脑捒梢晕锢韯h除。

C平衡樹，平衡樹的查找的時(shí)間冗雜度：O(logn),刪除的時(shí)間冗雜度取決于是否還要調(diào)整，但即使調(diào)整時(shí)間冗雜為O(1).C也可以選。只要在logn級(jí)別的冗雜度都是比較高速的。

3以下排序算法中，哪些時(shí)間冗雜度不會(huì)超過nlogn?(BC)

A.快速排序B.堆排序C.歸并排序D.冒泡排序

堆排序的最好和最壞都是n*logn，歸并排序最好是O(n)，最壞是O(n*logn)因此BC沒問題。

4初始序列為18625473一組數(shù)采納堆排序，當(dāng)建堆(小根堆)完畢時(shí)，堆所對(duì)應(yīng)的二叉樹中序遍歷序列為：(A)

A.83251647

B.32851467

C.38251674

D.82351476

依據(jù)初始序列，建成的小根堆為：

對(duì)其進(jìn)行中序遍歷的結(jié)果為：83251647

14假如某系統(tǒng)15*4=112成立，則系統(tǒng)采納的是(A)進(jìn)制。

A.6B.7C.8D.9

依據(jù)進(jìn)制的定義可以得出若是x進(jìn)制的數(shù)，則個(gè)位的數(shù)字就是該數(shù)字，十位上的數(shù)字大小為a則為a*x，百位的為a*x^2.利用這個(gè)原理將上面的等式改為

2+x+x^2=4*(5+x)可以得出x=6.話說這道題和數(shù)據(jù)結(jié)構(gòu)沒什么關(guān)系吧，或許我的解法有問題。

15某段文本中各個(gè)字母消失的`頻率分別是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼編碼，則哪種是可能的編碼：(A)

Aa(000)b(001)h(01)i(10)o(11)

Ba(0000)b(0001)h(001)o(01)i(1)

Ca(000)b(001)h(01)i(10)o(00)

Da(0000)b(0001)h(001)o(000)i(1)

依據(jù)頻率可以得出一棵哈夫曼樹為：

可以得出a是一種答案。關(guān)鍵是構(gòu)建哈夫曼樹的過程，選出兩個(gè)最小頻率的節(jié)點(diǎn)，其父節(jié)點(diǎn)的值為左右孩子的和，再將這個(gè)父節(jié)點(diǎn)放入到原序列中再次選出兩個(gè)最小值的節(jié)點(diǎn)。假如得出的新節(jié)點(diǎn)不在最小的二個(gè)節(jié)點(diǎn)中，那么新選出的兩個(gè)節(jié)點(diǎn)要比這個(gè)新節(jié)點(diǎn)的深度大一即要在其下一層。如圖中的i節(jié)點(diǎn)和o節(jié)點(diǎn)。只要留意這個(gè)，這個(gè)題就沒什么問題了。

17一個(gè)棧的入棧序列是A,B,C,D,E，則棧的不行能的輸出序列是?(C)

A.EDCBAB.DECBAC.DCEABD.ABCDE

沒啥好說的。

21遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)肯定?(B)

A使用了局部變量

B有一個(gè)分支不調(diào)用自身

C使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù)

D沒有循環(huán)調(diào)用

遞歸函數(shù)要求有一個(gè)出口，即不在連續(xù)調(diào)用自身，這樣才能結(jié)束遞歸。

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

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

這個(gè)也沒什么可說的，只要明白歸并排序的方法就可以了。歸并的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，二路歸并就是說每次分的表為2或1。

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

希爾排序，相同增量的數(shù)為一組進(jìn)行簡(jiǎn)潔插入排序。步長(zhǎng)為4也就是相隔的增量為4.第一組為R，剩余的為ADH，CFM，SXY。組內(nèi)排序可以得出答案?？焖倥判颍湃未蠹叶己苁熳R(shí)了，只是以一個(gè)key為基準(zhǔn)這里選中了第一個(gè)元素，key左邊的元素都不大于key,右邊的都大于key。從后往前找第一個(gè)不大于key的元素，找到后從前往后找第一個(gè)大于key的，知道兩個(gè)指針相遇。結(jié)果也很好得出。

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

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

我的想法感覺比較笨，第一種：先對(duì)其中的一個(gè)進(jìn)行排序，然后從一個(gè)未排序的集合中取出一個(gè)元素用折半查找的方法查找集合中有沒有這個(gè)元素。相應(yīng)的時(shí)間冗雜度為：排序n*logn，查找的時(shí)間冗雜度也為n*logn，整體上也是n*logn。這個(gè)時(shí)間冗雜有待商榷的地方在于，排序的時(shí)間冗雜度，若選取堆排序則平均冗雜度為n*logn，假如選用其