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

時間：2020-10-17 08:28:14 筆試題目我要投稿

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

　　想要進入騰訊工作，可是要參加筆試的。下面YJBYS小編為大家搜集的一篇“騰訊商業(yè)分析筆試題”，供大家參考借鑒，希望可以幫助到有需要的朋友!

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

　　一不定項選擇題(共25題，每題4分，共100分，少選、錯選、多選均不得分)

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

　　A.CFHGEBDA B.CDFEGHBA C.FGHCDEBA D.CFHGEDBA

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

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

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

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

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

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

　　3 下列排序算法中，哪些時間復(fù)雜度不會超過nlogn?(BC)

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

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

　　4 初始序列為1 8 6 2 5 4 7 3一組數(shù)采用堆排序，當(dāng)建堆(小根堆)完畢時，堆所對應(yīng)的二叉樹中序遍歷序列為：(A)

　　A.8 3 2 5 1 6 4 7

　　B.3 2 8 5 1 4 6 7

　　C.3 8 2 5 1 6 7 4

　　D.8 2 3 5 1 4 7 6

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

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

　　14 如果某系統(tǒng)15*4=112成立，則系統(tǒng)采用的是(A)進制。

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

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

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

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

　　A a(000) b(001) h(01) i(10) o(11)

　　B a(0000) b(0001) h(001) o(01) i(1)

　　C a(000) b(001) h(01) i(10) o(00)

　　D a(0000) b(0001) h(001) o(000) i(1)

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

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

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

　　A.EDCBA B.DECBA C.DCEAB D.ABCDE

　　沒啥好說的。

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

　　A 使用了局部變量

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

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

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

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

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

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

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

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

　　希爾排序，相同增量的數(shù)為一組進行簡單插入排序。步長為4也就是相隔的增量為4.第一組為QQR，剩余的為ADH，CFM，SXY。組內(nèi)排序可以得出答案。快速排序，相信大家都很熟悉了，只是以一個key為基準(zhǔn)這里選中了第一個元素，key左邊的元素都不大于key,右邊的都大于key。從后往前找第一個不大于key的元素，找到后從前往后找第一個大于key的，知道兩個指針相遇。結(jié)果也很好得出。

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

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

　　我的想法感覺比較笨，第一種：先對其中的一個進行排序，然后從一個未排序的集合中取出一個元素用折半查找的方法查找集合中有沒有這個元素。相應(yīng)的時間復(fù)雜度為：排序n*logn，查找的時間復(fù)雜度也為n*logn，整體上也是n*logn。這個時間復(fù)雜有待商榷的地方在于，排序的時間復(fù)雜度，若選取堆排序則平均復(fù)雜度為n*logn，如果選用其他的排序方法最壞的情況下不一定是這個復(fù)雜度。

　　第二種方法：利用Hash表，先將A構(gòu)造成一個Hash表，然后將B看做是待查找元素從Hash表里查找。Hash表的查找的時間復(fù)雜最壞為O(C)C為平均查找長度，構(gòu)造Hash表的時間復(fù)雜度也是常數(shù)級別的，平均為O(C)。

【騰訊商業(yè)分析筆試題】相關(guān)文章：

2017騰訊筆試題07-21

騰訊面試經(jīng)驗面試對答分析11-20