Aug.Day09 8.15总结

【初赛复习进行中】

一、单项选择题

Wrong Problems:

1.以下不属于面向对象程序设计语言的是（ ）。

A. C++

B. Python

C. Java

D. C (正确)

分析：

面向对象程序设计语言：JavaScript, C++, Java, Python, Swift, Go, C#。

面向过程程序设计语言：C, Pascal。

错误原因：没有牢固掌握面向对象和过程语言的例子 绝对不是想成了编译性和解释性语言。

---

4.以比较作为基本运算，在 $N$ 个数中找出最大数，最坏情况下所需要的最少的比较次数为（ ）。

A. $N^2$

B. $N$

C. $N-1$ （正确）

D. $N+1$

分析：

一棵树如果有 $n$ 个节点，那么这棵树只能有 $n-1$ 条边。

所以共有 $m$ 条边，那么则需要减去 $m-(n-1)=m-n+1$ 条边。

错误原因：粗心大意，想的是 D, 写的是 C。

---

8.如果一棵二叉树只有根节点，那么这棵二叉树高度为 $1$。请问高度为 $5$ 的完全二叉树有（ ）种不同的形态？

A. $16$ (正确)

B. $15$

C. $17$

D. $32$

分析：

满二叉树：指除叶子结点外，每个节点都有两个子节点的二叉树。

完全二叉树：指一棵满二叉树，从右至左只有最后一层的节点缺失且没有中断。也就是对于一棵深度为 $k$ 的满二叉树（根节点深度为 $1$），如果最后一层在最右边缺失了 $0$ 个，$1$ 个，$2$ 个......$2^{k-1} - 1$ 个节点，就是深度为 $k$ 的完全二叉树。而本题要求深度为 $5$，那么总数则是 $2^{5-1}-1+1=2^4=16$ 种可能性。

错误原因：没有想到满二叉树也是完全二叉树。

---

10.$6$ 个数，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ）种。

A. $10$

B. $15$ (正确)

C. $30$

D. $20$

分析：

排列组合问题。

排列：在 $n$ 个数中选 $m$ 个，区分顺序，记作 $A^m_n$，$A^m_n=\dfrac{n!}{(n-m)!}$。

组合：在 $n$ 个数中选 $m$ 个，不区分顺序，记作 $C^m_n$，$C^m_n=C^{n-m}_n=\dfrac{n!}{m! \times (n-m)!}$。

本题要求在 $6$ 个人中分出 $3$ 组，那么第 $1$ 组就是在 $6$ 个人中选 $2$ 个人，为 $C^2_6=15$，第二组是在 $4$ 个人中选 $2$ 个人，为 $C^2_4=6$，剩下在 $2$ 人中选 $2$ 人就没得选。但是这里考虑了组别的情况，所以还要去掉组别，也就是 $A^3_3=6$，最终答案为 $C^2_6 \times C^2_4 \div A^3_3=15 \times 6 \div 6=15$ 种。

错误原因：对排列组合掌握不扎实，基本都忘记公式了。

---

11.在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

A. 枚举

B. 贪心 (正确)

C. 递归

D. 动态规划

分析：

哈夫曼树是每次挑出权重最小的两个点建树，建好后将两个数的和放回去供下次再取，所以很明显，是贪心。

错误原因：没有复习 都忘记哈夫曼树是什么了直到看讲义才想起来。

---

12.由 $1,1,2,2,3$ 这五个数字组成不同的三位数有（ ）种。

A. $18$ (正确)

B. $15$

C. $12$

D. $24$

分析：

暴力枚举即可。

错误原因：没有好好枚举或是写出公式，去做后面的去了 一定要细心惹qwq。

---

14. 以 $a$ 为起点，对右边的图进行深度优先遍历，则 $b$、$c$、$d$、$e$ 四个点中有可能作为最后一个遍历到的点的个数为（ ）。

A. $1$

B. $2$ (正确)

C. $3$

D. $4$

分析：

深度优先遍历是一条路走到黑。

如果开始往左边走，那么路径是 $a \to b \to d \to b \to a \to c \to e$，结束点为 $e$。往右边走则是 $a \to c \to e \to c \to d \to c \to a \to b$，结束点为 $b$，两种可能，选 B。

错误原因：没有理清深度优先遍历的遍历顺序，导致以为 $c$ 也有可能。

---

15.有四个人要从 $A$ 点坐一条船过河到 $B$ 点，船一开始在 $A$ 点。该船一次最多可坐两个人。已知这四个人中每个独自坐船的过河时间分别为 $1,2,4,8$，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 $B$ 点（包括从 $B$ 点把船开回 $A$ 点的时间）。

A. $14$

B. $15$ (正确)

C. $16$

D. $17$

分析：

本题是一道思维题，正确答案是 $15$，过程如下：

1：$| \ 1,2,4,8 \ | \ | \ \phi \ |$

都在点 $A$。

2：$| \ 4,8 \ | \ | \ 1,2 \ |$

$1,2$ 去往点 $B$，总用时 $2$。

3：$| \ 1,4,8 \ | \ | \ 2 \ |$

$1$ 回来，总用时 $2+1=3$。

4：$| \ 1 \ | \ | \ 4,8,2 \ |$

$4,8$ 过去，总用时 $3+8=11$。

5：$| \ 1,2 \ | \ | \ 4,8 \ |$

$2$ 回来，总用时 $11+2=13$。

6：$| \ \phi \ | \ | \ 1,2,4,8 \ |$

$1,2$ 过去，总用时 $13+2=15$，所有人都在点 $B$，且是最优方案。

错误原因：没有想到中途可以换人回来，认为最少是 $8+4+1+1+2=16$ 时间。