选择题

a,b,c,d,e 对应出现的频率为4，6，11，13，15；以下符合哈夫曼编码的选项是？（）

A. a=000、b=01、c=001、d=10、e=11 B. a=000、b=001、c=01、d=10、e=11 C. a=010、b=001、c=01、d=11、e=10 D. a=000、b=10、c=001、d=11、e=01

链接：原题地址 来源：牛客网

答案：B

解题分析

解题分析转自 牛客网 ID名为 掌心里的小雨，若有侵权，请通告。

哈夫曼编码

哈夫曼编码的目的就是数据压缩，加密解密，将出现频率低的放在二叉树的靠最下面的层，从而使频率高的能被更快的找到，实现数据压缩的功能主要的编码过程是：1.由于题目中这个频率是排好序的，可以看做有序序列。先取两个最小（a,b）作为一个新结点n1的两个子结点，相对较小的是左孩子，新结点的频率就是a,b两个频率的相加，即4+6=10；然后将新结点n1替换a，b插入有序序列，整个就是{n1,c,d,e};然后再取最小的两个结点（n1,c），产生的新结点n2的频率为10+11=21，继续替换n1，c插入有序序列，整个就是{d,e,n2};然后再取最小的两个结点（d,e），产生的新结点n3的频率为13+15=28，继续替换d，e插入有序序列，序列就剩2个结点，小的作为左结点，大的是右节点，共同指向根结点T，最后哈夫曼树就可画出来了。最后将左分支改为0，右分支改为1，哈夫曼编码就是从树根到叶子所经过的0和1组成的，从这里可以看出，a的频率最低，出现在最低层的叶子结点，达到数据压缩的目的 *

---

对一棵先序遍历节点编号为12435678，中序遍历为42165738的二叉树，进行左子节点优先的广度优先遍历，搜索到编号为6的节点需要几次查询（）

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

答案：C

解题分析

先序遍历：根 —> 左 —> 右

中序遍历： 左 —> 根 —> 右

通过题目可知， 4 和 2 为根节点1 的左子树，其余的则为根节点1 的右子树，而通过中序的遍历规则可知，4为2的子孙，2为1的子孙。

然后是6，5，7，3，8为1的右子树，根据先序遍历可知，3为1的右子孙，而通过中序遍历则知道，5是3的左子孙，6 和 7 则为 5 的左右子孙，而 8 则为 3 的右子孙。

然后根据题意，左子树广度优先遍历，则遍历顺序是从根节点1开始逐层遍历：1，2，3，4，5，8，6，7，而子节点6则为第7个。

---

224个叶子节点的完全二叉树, 最多有几个结点（）

A. 447 B. 448 C. 449 D. 450

答案：B

解题分析

二叉树具有以下性质：

度为0的结点个数 = 度为 2 的节点个数 + 1， 即 n0 = n2 + 1（其中n0表示度为0的结点个数，n2表示度为2的结点个数）。注：二叉树的度代表某个结点的孩子或直接后继的个数。完全二叉树中度为1的结点要么0个，要么1个。二叉树结点的个数n = n0 + n1 + n2;

综合性质，结合题目有 n0 = 224, 故 224 = n2 + 1,得 n2 = 224 - 1 = 223 当为度1的结点不存在时，结点总数为n= n0 + n1 + n2 = 224 + 0 + 223 = 447 当为度1的结点存在时，结点总数为n = n0 + n1 + n2 = 224 + 1 + 223 = 448

故最多为448，选B

---

无限多水源 一个4L无刻度桶, 一个9L无刻度桶, 那么只利用这两个桶, 可以获得的水量有()

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

答案： A B C D

解题思路

A，装满9L，倒入4L桶两次即可。 B. 装满9L桶，倒入4L桶一次即可。 C. 装满两次4L桶，倒入9L桶即可。 D. 装满9L桶，倒入4L桶2次，剩1L，将1L倒入空的4L桶后，装满9L桶，倒入有1L桶装满，此时9L桶剩6L，继续倒入4L桶，则9L桶剩2L，将2L桶倒入4L桶，将9L桶装满即可。 参考图如下：

图片来源牛客网，侵权请通知

---

假如一个作业的页面走向是:1,2,3,4,2,1,5,2,1。当内存块数量为3时,请问LRU,FIFO这两种置换算法的缺页次数各是多少? ()

A. 7，5 B. 6，7 C. 3，6 D. 6，5

答案：B

解题思路

LRU：least recently used 内存为3，读 1，2，3，4，2，1，5，2，1 1，2，3为3次page fault 读4时，4取代1，page fault，内存为 4，2，3 读2时，2存在 读1时，1取代3，page fault，内存为4，2，1 读5时，5取代4，page fault，内存为5，2，1 读2时，2存在 读1时，1存在 总共6次缺页。

FIFO：First in Fist out 内存为3，读 1，2，3，4，2，1，5，2，1 1，2，3为3次page fault 读4时，4取代1，page fault，内存为 4，2，3 读2时，2已存在 读1时，1取代2，page fault，内存为4，1，3 读5时，5取代3，page fault，内存为4，1，5 读2时，2取代4，page fault，内存为2，1，5 读1时，1已存在 总共7次缺页。

---

按照二叉树的定义，4个节点的二叉树有多少种（）

A. 13 B. 14 C. 15 D. 16

答案：B

解题分析

根据二叉树的定义，n个节点的二叉树一共有（2*n)! / n! * (n+1)! 即 8！/ 4! * 5!

---

求递归方程T(n) = 4T(n/2) + n的解（）

A. O(n) B. O(n^2) C. O(n^3) D.O(logn)

答案：B

题目解析

主定理提供了分治方法带来的递归表达式的渐进复杂度分析

将规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d)

即 T(n) = a(n/b) + c(n^d)

若a = b ^d ,T(n) = O(n^dlog(n))

若a < b ^d,T(n) = O(n^d)

若a > b ^ d, T(n) = O(n^logb(a))

该题为 a = 4, b = 2, d = 1, a > 2，T(n) = O(n^log2(4)) = O(n^2)

---

下列关于动态规划算法说法错误的是（）

A. 动态规划关键在于正确地写出基本的递推关系式和恰当的边界条件

B. 当某阶段的状态确定后，当前的状态是对以往决策的总结并且直接影响未来的决策

C. 动态规划算法根据子问题具有重叠性，对每个子问题都只解一次

D. 动态规划算法将原来具有指数级复杂度的搜索算法改进具有多项式时间算法

答案：B

解题分析

动态规划：

递推关系式子问题重叠最优子结构

B中，动态规划只是说某阶段的最优解状态是对以往状态的总结并且影响未来的决策。而不是说所有的状态。

---

下列哪个不是队列的应用（）

A. 图的广度优先搜索 B. 设置打印数据缓冲区 C. 树的层次遍历 D. 中缀表达式转后缀表达式

答案:D

解题分析

后缀表达式也称逆波兰式，中缀转后缀是用栈实现的。

---

计算大于n(n>1)的最小的斐波那契数，以下划线出应填入

function f(n:int){ int[] a = new int[2]; a[0] = a[1] = 1; int i =1 ; while(true){ i = (i + 1)%2 a[i] = ______ If(a[i] > n){ return a[i] } } }

A. a[i] + a[i + 1] B. a[i % 2] + a[(i+1) %2 ] C. a[i] + a[i-1] D. a[i % 2] + a[(i-1) % 2]

答案：B

解题分析

因为题目创建的数组的大小为2，所以排除A、C 而在第一次while循环，i = 1, i = (i+1) % 2 = 0,而 i -1 会造成下标越界，所以排除D。

---

下面关于树的遍历算法说法错误的是？（）

A. 先序遍历属于广度优先遍历算法 B. 中序遍历属于广度优先遍历算法 C. 中序遍历属于深度优先遍历算法 D. 后序遍历属于深度优先遍历算法

答案：A、B

解题分析

树的层次遍历才属于广度优先遍历算法

---

高度为7的完全二叉树的节点总数不可能是（）

A. 128 B. 192 C. 255 D. 256

答案：D

解题分析

根据满二叉树节点的计算公式：N = 2^(n+1) - 1,可以算出，当高度为7时，二叉树最多有2^8 - 1 = 255个节点，最少有 2^ 7 = 128个。所以，在区间[128,255]内的选项都是正确的。