来自 电脑系统 2019-09-11 14:01 的文章
当前位置: 金沙澳门官网网址 > 电脑系统 > 正文

金沙澳门官网网址:不定项选用题,编写翻译原

2017年1月27日19:05:28,今天是年三十,首先祝大家新年快乐,之前对自己要求过,每星期一篇面试题的博客,虽然今天心里有一万个不愿意写,也还是得写。这篇博客是 2016 腾讯软件开发面试题中不定项选择题集合中的 1 -12 题,其中后面的 13-25题在下周的博客中写,说明一下,这篇博客跟以往的每周一题有点不同,因为如果选择一两题,博客的边幅有点少,而且选择题相对来说,难度没那么大,更主要的是为了让大家全面的感受一下腾讯的面试题。

金沙澳门官网网址 ,1、已知一棵二叉树,如果先序遍历的节点顺序是: ADCEFGHB ,中序遍历是: CDFEGHAB ,则后序遍历结果为:

A. CFHGEBDAB. CDFEGHBAC. FGHCDEBAD. CFHGEDBA

  • 1956年,Chomsky建立形式语言的描述。
  • 通过对产生式的施加不同的限制,Chomsky把文法分为4种类型

知识点

 

对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式:

  首先定义一个产生式

  • 先序遍历若二叉树为空,则不进行任何操作:否则1、访问根结点。2、先序方式遍历左子树。3、先序遍历右子树。

  • 中序遍历 若二叉树为空,则不进行任何操作:否则1、中序遍历左子树。2、访问根结点。3、中序遍历右子树。

  • 后序遍历 若二叉树为空,则不进行任何操作:否则1、后序遍历左子树。2、后序遍历右子树。3、放问根结点。

  α→β

因此,根据题目给出的先序遍历和中序遍历,可以画出二叉树:

  • 0型文法定义:

金沙澳门官网网址 1二叉树遍历.png

0型文法(PSG): α∈(VN∪VT)* ,且至少含一个VN

最后结果选择: D

β∈(VN∪VT)*

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

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

对产生式没有任何限制

知识点

例如:A0→**A0 ,  A1→B

金沙澳门官网网址 2几种常见的数据结构操作性能.png

0型文法说明:

平衡二叉树的查找,插入和删除性能都是 O ,其中查找和删除性能较好;哈希表的查找、插入和删除性能都是 O ,都是最好的。所以最后的结果选择: CD

0型文法也称为短语文法。

3、下列排序算法中,哪些时间复杂度不会超过 nlogn?

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

      一个非常重要的理论结果是,0型文法的能力相当于图灵机(Turing)。或者说,任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。

知识点

      对0型文法产生式的形式作某些限制,以给出1,2和3型文法的定义。

金沙澳门官网网址 3几种常见的排序算法对比.png

(注意)

根据上图,观察平均情况,最好最差情况的时间复杂度基本可以知道答案了,最后结果选择: BC

文法G 定义为四元组(VN ,VT ,P,S)

4、初始序列为 1 8 6 2 5 4 7 3 一组数采用堆排序,当建堆完毕时,堆所对应的二叉树中序遍历序列为:

A. 8 3 2 5 1 6 4 7B. 3 2 8 5 1 4 6 7C. 3 8 2 5 1 6 7 4D. 8 2 3 5 1 4 7 6

¨VN :非终结符集

初始化序列:1 8 6 2 5 4 7 3,,小根堆就是要求结点的值小于其左右孩子结点的值,左右孩子的大小没有关系,那么小根堆排序之后为:1 2 4 3 5 6 7 8;

¨VT :终结符集

中序遍历:左根右,故遍历结果为:8 3 2 5 1 6 4 7

¨P :产生式集合(规则集合)

故最后选择的结果: A

¨S :开始符号(识别符号)

5、当 n = 5 时,下列函数的返回值是:

[cpp] view plaincopyint foo { ifreturn n; return foo+foo; } 

A.5B.7C.8D.1

 

这题只需把数代进去,就可以知道结果了,所以最后结果选: A

  • 1型文法(上下文有关文法context-sensitive):

金沙澳门官网网址 4递归.png

  对任一产生式α→β,都有|β|>=|α|, 仅仅 S→ε除外

6、 S 市 A ,B 共有两个区,人口比例为 3:5 ,据历史统计 A 区的犯罪率为 0.01% ,B 区为 0.015% ,现有一起新案件发生在 S 市,那么案件发生在 A 区的可能性有多大?

A.37.5%B.32.5%C.28.6%D.26.1%

  产生式的形式描述:α1Aα2→α1βα2 

这道题首先得了解犯罪率是什么?犯罪率就是犯罪人数与总人口数的比。因此可以直接得出公式:( 3 * 0.01% ) / ( 3 * 0.01% + 5 * 0.015% ) = 28.6%

  (其中,α1、α2、β∈(VN∪VT)*,β≠ε,A∈VN)

当然如果不好理解的话,我们可以实例化,比如 B 区假设 5000 人,A 区 3000 人,A 区的犯罪率为 0.01%,那么 A 区犯罪人数为 30 人,B 区的犯罪率为 0.015% ,那么 B 区的犯罪人数为 75 人 ,求发生在 A 区的可能性,就是说 A 区的犯罪人数在总犯罪人数的多少,也就是 30/=0.2857

  即:A只有出现在α1α2的上下文中,才允许用β替换。

当然,也可以回归到我们高中遗忘的知识:

  产生的语言称“上下文有关语言”

假设C表示犯案属性在A区犯案概率:P=0.01%在B区犯案概率:P=0.015%在A区概率:P=3/8在B区概率:P=5/8犯案概率:P=(3/80.01%+5/80.015%)根据贝叶斯公式:P = P / P = [P] / [ P+ P ] 也可以算出答案来

 

本文由金沙澳门官网网址发布于电脑系统,转载请注明出处:金沙澳门官网网址:不定项选用题,编写翻译原

关键词: