下面是出国留学网小编整理提供的腾讯商业分析笔试题,欢迎阅读。
一 不定项选择题(共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 ...