2016腾讯软件开发面试题(不定项选择题【13-25】)
腾讯.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）
<pre>
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. 观察者模式
