腾讯.jpg

一、前言

前言.png

本来这篇文章打算在上一篇文章后一个星期就写完的，可是最近跟一个同学在讨论创业的事情，因此迟迟还没写完，拖到现在（2017年2月14日01:25:22），因此今晚必需赶出来。

二、2016 腾讯软件开发面试题（不定项选择题【13-25】）

13、浏览器访问某页面，HTTP 协议返回状态码为 403 时表示：（）
A. 找不到该页面
B. 禁止访问
C. 内部服务器访问
D. 服务器繁忙

这题直接给答案了，因为这是很基础的题目，无论是什么开发，都离不开网络了，而网络开发的核心就是 HTTP 协议，因此这是很基础的题目，在之前的文章中也有介绍过Android 网络框架_网络框架的核心Http协议，最后这题的答案选择为：B

14、如果某系统 15*4=112 成立，则系统采用的是（）进制。
A．6
B．7
C．8
D．9

这题因为是选择题，我们可以直接从 A 的选项开始，假设是 6 进制的，我们把等式 15 4 = 112 转为十进制，就是 11 4 = 44，最后验证等式是否成立，明显等式是成立的，因此答案已经出来了，选择 A 。

当然我们也可以假设是 X 进制，且我们知道 X 大于 5，则：（x+5）4 = xx +x +2，所以最后计算的结果也为 6

15、某段文本中各个字母出现的频率分别是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼编码，则哪种是可能的编码：（A）
A. a(001)    b(000)    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)

知识点

关于哈夫曼树的知识点很容易遗忘，因为对于我来说，用的还是比较少的，甚至说接触的也比较少。但是一些注意的知识点还是要记住的。

关于哈夫曼树的注意点：

1、满二叉树不一定是哈夫曼树

2、哈夫曼树中权越大的叶子离根越近（很好理解，WPL最小的二叉树）

3、具有相同带权结点的哈夫曼树不惟一

4、哈夫曼树的结点的度数为 0 或 2，没有度为 1 的结点。

5、包含 n 个叶子结点的哈夫曼树中共有 2n – 1 个结点。

6、包含 n 棵树的森林要经过 n–1 次合并才能形成哈夫曼树，共产生 n–1 个新结点

哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

例：如果需传送的电文为 ‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11，则上述电文便为 ‘00010010101100’（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。

好了，了解了相关的知识点，我们开始解题，首先，创建一个哈夫曼树，原则如下：

将每个英文字母依照出现频率由小排到大，最小在左，组成一个序列
每个字母都代表一个终端节点（叶节点），比较每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点，将两个字母从序列中删除，将生成的节点加入到字母队列中

重复前面两步，直到序列中没有字母为止

哈夫曼树.png

好了，创建了哈夫曼树，最后我们进行编码，编码的规则如下：

给霍夫曼树的所有左链结 '0' 与右链结 '1'
从树根至树叶依序记录所有字母的编码

因此最后的结果为：a(001)， b(000)，h(01)，i(10)，o(11)，选择 A

16、TCP 和 IP 分别对应了 OSI 中的哪几层？（）
A. Application layer
B. Presentation layer
C. Transport layer
D. Network layer

知识点

网络分层模型.gif

所以最后的答案为 CD

17、一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是？（）
A．EDCBA
B．DECBA
C．DCEAB
D．ABCDE

堆栈分别是先进后出,后进先出，

选项 a 是 abcde 先入栈,然后依次出栈,正好是 edcba
选项 b 是 abcd 先依次入栈,然后 d 出栈, e 再入栈, e 出栈
选项 c 是错误的,不可能 a 先出栈
选项 d 是 a 入栈,然后 a 出栈；b 再入栈, b 出栈.依此类推

最后的结果选择 C

18、同一进程下的线程可以共享以下？（）
A．stack
B．data section
C．register set
D．file fd

知识点

线程共享的内容包括：

进程代码段
进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)
进程打开的文件描述符、
信号的处理器、
进程的当前目录和
进程用户ID与进程组ID

线程独有的内容包括：

线程ID
寄存器组的值
线程的堆栈
错误返回码
线程的信号屏蔽码

所以选择为 BD

19、对于派生类的构造函数，在定义对象时构造函数的执行顺序为？（）
1：成员对象的构造函数
2：基类的构造函数
3：派生类本身的构造函数
A．123
B．231
C．321
D．213

这个很基础的编程问题了，选择 D

20、如何减少换页错误？（）
A. 进程倾向于占用CPU
B. 访问局部性（locality of reference）满足进程要求
C. 进程倾向于占用I/O
D. 使用基于最短剩余时间（shortest remaining time）的调度机制

知识点

换页错误又称缺页错误，当一个程序试图访问没有映射到物理内存的地方时，就会出现缺页错误，这时操作系统就要去虚拟内存中加载这块内存页。

减少换页错误的方法，即降低缺页中断率：

内存页框数。增加作业分得的内存块数。
页面大小。页面划分越大，中断率越低。
替换算法的优劣影响缺页中断次数
程序局部性。程序局部性好可减少缺页中断

因此选择 B

21、递归函数最终会结束，那么这个函数一定？（）
A. 使用了局部变量
B. 有一个分支不调用自身
C. 使用了全局变量或者使用了一个或多个参数
D. 没有循环调用

这题也是简单的编程知识题目，选择 B

22、编译过程中，语法分析器的任务是（B）
A. 分析单词是怎样构成的
B. 分析单词串是如何构成语言和说明的
C. 分析语句和说明是如何构成程序的
D. 分析程序的结构

知识点

词法分析（lexical analysis）

词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右的读取每个字符，然后根据构词规则识别单词。词法分析可以用lex等工具自动生成。

语法分析（syntax analysis）

语法分析是编译过程的一个逻辑阶段。语法分析在词法分析的基础上，将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断程序在结构上是否正确。

语义分析（semantic analysis）

属于逻辑阶段。对源程序进行上下文有关性质的审查，类型检查。如赋值语句左右端类型匹配问题。

所以 BCD 都属于词法分析，选择结果为 BCD

23、同步机制应该遵循哪些基本准则？（ABCD）
A．空闲让进
B．忙则等待
C．有限等待
D．让权等待

24、进程进入等待状态有哪几种方式？（D）
A. CPU调度给优先级更高的线程
B. 阻塞的线程获得资源或者信号
C. 在时间片轮转的情况下，如果时间片到了
D. 获得spinlock未果

25、设计模式中，属于结构型模式的有哪些？（BC）
A. 状态模式
B. 装饰模式
C. 代理模式
D. 观察者模式

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。