期中测试题答案 | 这些问题，你都答对了吗？

你好，我是胡光。今天，我来公布一下选择题和主观题的答案。

选择题

1.下面这些对于堆的描述中，错误的选项是（）

A. 由于堆可以存储在一个数组中，所以堆属于一种线性结构

B. 堆分为大顶堆与小顶堆，大顶堆的堆顶是最大值

C. 在一个数组上，建立一个堆的时间复杂度不可能低于 O(nlogn)

D. 对顶堆主要可以解决动态查找中位数的问题

解析：A/C

A 中，堆属于树形结构，一个数据结构属于什么结构，看的是思维逻辑结构中的样子，而不是代码实现中的样子。

C 中，线性建堆法的时间复杂度为 O(n)

2.关于快速排序优化中的“基准值选取优”的说法，错误的是（）

A. 三点取中法的优化，是概率性优化，程序是否展现出优化效果，要看具体的数据分布

B. 三点取中法的优化，可以保证在所有数据上，都能展现出优化以后的好效果

C. 基准值选取优化，根本目的是为了让程序实现更简单

D. 基准值选取优化，根本目的是为了稳定住快速排序的时间复杂度，使其在最差的情况下，也能表现良好

解析：B/C

A、B 是一组，A 中的说法是对的，三点取中法是否展现出优化效果，要看具体的数据分布。

C、D 是一组，D 中的说法是对的，根本目的是为了稳定住快速排序的时间复杂度，可以从快速排序的时间复杂度推导入手理解。

3.关于归并排序的说法中，错误的是（）

A. 归并排序和快速排序一样，最坏时间复杂度是 $O(n^2)$，最好是 $O(nlogn)$

B. 归并排序最好、最坏、平均时间复杂度都是 $O(nlogn)$

C. 归并排序和快速排序一样，都属于稳定排序，相同值排序以后，相对位置保持不变

D. 归并排序和快速排序不一样，快速排序属于稳定排序，归并排序属于非稳定排序

解析：A/C/D

A、B 是一组，B 中说的是对的，归并排序最好、最坏、平均时间复杂度都是 $O(nlogn)$。

C、D 看似是一组，可 C、D 中说得都是错的。快速排序是非稳定排序，归并排序是稳定排序。所谓稳定或者不稳定，是指排序以后，相同大小的元素的相对位置是否发生改变。

主观题

1. 请阐述 Top-k 的解法。按照你的理解，分情况讨论。

解析：以下是我想到的4类情况。

1. 数据是整型，数据范围很小，符合计数排序需要的数据特点时，采用计数排序进行统计。时间复杂度 O(n)。
2. 数据不符合计数排序特殊时，当数据量 n 很小，内存存得下的时候，可以考虑使用快速选择算法，解决 Top-K 问题。时间复杂度为 O(n)。
3. 数据不符合计数排序特殊时，当数据量 n 很大，内存存不下时，可 k 很小，内存存的下的时候，维护大小为 k 的小顶堆即可以解决问题。时间复杂度为 O(nlogk)。
4. 数据不符合计数排序特殊时，当数据量 n 很大，内存存不下，k 也很大的时候，可以考虑直接采用归并排序，从而得到 Top-k 数字。时间复杂度为 O(nlogn)。

2. 请说出 4 种生活中需要排序的具体场景。

解析：以下是我给出的4种示例情况

1. 照集体照的时候，老师都会按照身高对所有同学进行排序，最终目的是为了让照片效果更好。
2. 销售在客户跟进的时候，会根据意向程度对客户列表排序，目的是为了精力价值最大化。
3. 在工作的时候，我们按照工作的紧急重要程度对工作排序，目的是为了明确做事顺序。
4. 各省市经济发展状况公布时，会按照 GDP 排序，目的是更清楚地展现本年度全国经济发展状况。

好了，这节课就到这里，我们下节课见。