腾讯商业分析笔试题

腾讯商业分析笔试题

　　想要进入腾讯工作，可是要参加笔试的。下面YJBYS小编为大家搜集的一篇“腾讯商业分析笔试题”，供大家参考借鉴，希望可以帮助到有需要的朋友!

　　一 不定项选择题(共25题，每题4分，共100分，少选、错选、多选均不得分)

　　1 已知一棵二叉树，如果先序遍历的节点顺序是：ADCEFGHB，中序遍历是：CDFEGHAB，则后序遍历结果为：(D)

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

　　先序遍历：根左右，因此可以通过先序遍历得到父子关系，即在前面肯定是后面的父节点。中序遍历：左根右，通过中序遍历可以获得某个节点的左右孩子(直接)，因此可以还原出这课二叉树为：，得出这棵二叉树后就可以推出它的后序遍历。

　　2 下列哪两个数据结构，同时具有较高的查找和删除性能?(CD)

　　A.有序数组 B.有序链表 C.AVL树 D.Hash表

　　A和B没什么可说的，DHash表的查找的时间复杂度：不冲突时为O(1)，删除也为O(1)，冲突时为O(C),O(C)都是常数量级别的。所以必选。

　　补充一下，在开放地址方法时不能物理删除，只能做一个删除标记。若是链式地址方法的话可以物理删除。

　　C平衡树，平衡树的查找的时间复杂度：O(logn),删除的时间复杂度取决于是否还要调整，但即使调整时间复杂为O(1).C也可以选。只要在logn级别的复杂度都是比较高速的。

　　3 下列排序算法中，哪些时间复杂度不会超过nlogn?(BC)

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

　　堆排序的最好和最坏都是n*logn，归并排序最好是O(n)，最坏是O(n*logn)因此BC没问题。

　　4 初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为：(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

　　根据初始序列，建成的小根堆为：

　　对其进行中序遍历的结果为：83251647

　　14 如果某系统15*4=112成立，则系统采用的是(A)进制。

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

　　根据进制的定义可以得出若是x进制的数，则个位的数字就是该数字，十位上的数字大小为a则为a*x，百位的为a*x^2.利用这个原理将上面的等式改为

　　2+x+x^2 = 4*(5+x)可以得出x=6.话说这道题和数据结构没什么关系吧，或许我的解法有问题。

　　15 某段文本中各个字母出现的`频率分别是{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)

　　根据频率可以得出一棵哈夫曼树为：

　　可以得出a是一种答案。关键是构建哈夫曼树的过程，选出两个最小频率的节点，其父节点的值为左右孩子的和，再将这个父节点放入到原序列中再次选出两个最小值的节点。如果得出的新节点不在最小的二个节点中，那么新选出的两个节点要比这个新节点的深度大一即要在其下一层。如图中的i节点和o节点。只要注意这个，这个题就没什么问题了。

　　17 一个栈的入栈序列是A,B,C,D,E，则栈的不可能的输出序列是?(C)

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

　　没啥好说的。

　　21 递归函数最终会结束，那么这个函数一定?(B)

　　A 使用了局部变量

　　B 有一个分支不调用自身

　　C 使用了全局变量或者使用了一个或多个参数

　　D 没有循环调用

　　递归函数要求有一个出口，即不在继续调用自身，这样才能结束递归。

　　二、填空题(共4题10个空，每空2分，共20 分)

　　1 设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，请写出按二路归并方法对该序列进行一趟扫描后的结果为DQFXAPBNMYCW。

　　这个也没什么可说的，只要明白归并排序的方法就可以了。归并的含义是将两个或两个以上的有序表组合成一个新的有序表，二路归并就是说每次分的表为2或1。

　　2 关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是QACSQDFXRHMY;若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是FHCDQAMQRSYX。

　　希尔排序，相同增量的数为一组进行简单插入排序。步长为4也就是相隔的增量为4.第一组为QQR，剩余的为ADH，CFM，SXY。组内排序可以得出答案。快速排序，相信大家都很熟悉了，只是以一个key为基准这里选中了第一个元素，key左边的元素都不大于key,右边的都大于key。从后往前找第一个不大于key的元素，找到后从前往后找第一个大于key的，知道两个指针相遇。结果也很好得出。

　　三、其他方向简答题(共2题，每题20分)，选作题，不计入总分)

　　2 A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

　　我的想法感觉比较笨，第一种：先对其中的一个进行排序，然后从一个未排序的集合中取出一个元素用折半查找的方法查找集合中有没有这个元素。相应的时间复杂度为：排序n*logn，查找的时间复杂度也为n*logn，整体上也是n*logn。这个时间复杂有待商榷的地方在于，排序的时间复杂度，若选取堆排序则平均复杂度为n*logn，如果选用其他的排序方法最坏的情况下不一定是这个复杂度。

　　第二种方法：利用Hash表，先将A构造成一个Hash表，然后将B看做是待查找元素从Hash表里查找。Hash表的查找的时间复杂最坏为O(C)C为平均查找长度，构造Hash表的时间复杂度也是常数级别的，平均为O(C)。