2024 模拟初赛

假设有一组字符{g，h，i，j，k，l}，它们对应的频率分别为$8$%，$14$%，$17$%，$20$%，$23$%，$18$%。以下（）是字符g，h，i，j，k，l分别对应的一组哈夫曼编码。

A.g：$1100$，h：$1101$，i：$111$，l：$10$，k：$00$，j：$01$

B.g：$0000$，h：$001$，i：$010$，l：$011$，k：$10$，j：$11$

C.g：$111$，h：$110$，i：$101$，l：$100$，k：$01$，j：$00$

D.g：$110$，h：$111$，i：$101$，l：$100$，k：$0$，j：$01$

解析：

一道记忆题，哈夫曼编码的值有可能会变，但长度不会变，哈夫曼树如下：

         100
       0/   \1
      42     58
    0/ \1   0/ \1
   20  22   23  35
     0/  \1   0/  \1
     8   14   17   18

长度分别为：$3$，$3$，$3$，$2$，$2$，所以选C。

错误原因：

没有想到，哈夫曼编码的值有可能会变，但长度不会变的规律，导致看哪一个都不是正确答案，就蒙了一个。

---

从$2$至$8$的$7$个整数中随机取$2$个不同的数，这两个数互质的概率为（）。

A.$1/6$

B.$1/3$

C.$1/2$

D.$2/3$

解析：

一道枚举题，枚举内容如下：

• $2$开头：$23，25，27$

• $3$开头：$34，35，37，38$

• $4$开头：$45，47$

• $5$开头：$56，57，58$

• $6$开头：$67$

• $7$开头：$78$

而一共有$21$种（自己枚举）选法，满足条件的有$3+4+2+3+1+1=14$个，约分后为$2/3$，所以选D。

错误原因：

直接算成不互质的概率了。

---

以下（）的算法典型地使用了分治法的思想来解决问题。

A.线性搜索

B.快速排序

C.冒泡排序

D.插入排序

解析：

一道记忆题，线性搜索属于线性查找，不可能使用了分治法的思想来解决问题。

冒泡排序与插入排序都是$O(n^2)$的，也不可能使用了分治法的思想来解决问题。

而快速排序是$O(nlog(n))$，原理是选择一个枢纽元素，将小于枢纽元素的放在左边，大于枢纽元素的放在右边，再递归对左右两个部分进行快速排序，直到排序完成。从上面加粗的话来说，快速排序就是使用了分治法的思想来解决问题。所以选B。

错误原因：

粗心大意，想的是B，写的是D。

谢谢