期中测试 | 一套习题，测出你的掌握程度

胡光

你好，我是胡光。今天，我们来进行一场期中考试，共有 3 道选择题和 2 道主观题，希望你能好好思考，下节课我来公布答案。
选择题1. 下面这些对于堆的描述中，错误的选项是（）
A. 由于堆可以存储在一个数组中，所以堆属于一种线性结构
B. 堆分为大顶堆与小顶堆，大顶堆的堆顶是最大值
C. 在一个数组上，建立一个堆的时间复杂度不可能低于 O(nlogn)
D. 对顶堆主要可以解决动态查找中位数的问题
2. 关于快速排序优化中的“基准值选取优”的说法，错误的是（）
A. 三点取中法的优化，是概率性优化，程序是否展现出优化效果，要看具体的数据分布
B. 三点取中法的优化，可以保证在所有数据上，都能展现出优化以后的好效果
C. 基准值选取优化，根本目的是为了让程序实现更简单
D. 基准值选取优化，根本目的是为了稳定住快速排序的时间复杂度，使其在最差的情况下，也能表现良好
3. 关于归并排序的说法中，错误的是（）
A. 归并排序和快速排序一样，最坏时间复杂度是 O(n2)，最好是 O(nlogn)
B. 归并排序最好、最坏、平均时间复杂度都是 O(nlogn)

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文是一场期中考试，共包括3道选择题和2道主观题。选择题涉及堆、快速排序和归并排序等算法知识，考察读者对这些知识的掌握程度。主观题则要求读者阐述Top-k的解法以及生活中需要排序的具体场景。通过这场考试，读者可以检验自己对算法知识的掌握情况，同时也可以加深对Top-k解法和排序场景的理解。整体来说，本文通过考试形式，帮助读者巩固和应用所学的算法知识，是一篇具有实用性和教育性的技术文章。

该试读文章来自《常用算法 25 讲》，如需阅读全部文章，
请先通过赠一得一解锁课程

赠一得一

登录后留言

全部留言(1)

最新
精选

我来也
选择题: 1. A 堆是树型数据结构 2. B C b. 只是大概率并不能保证所有 c. 基准值选取优化实现也并不简单啊 3. A C D a. 归并排序时间复杂度最好最坏都是O(nlogn) c. 快速排序不是稳定排序 d. 快排是不稳定排序而归并是稳定排序主观题: 1. Top-K的两种解法 [https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/] a：堆，时间复杂度 O(nlogk) b：快排变形，（平均）时间复杂度 O(n) 在原始数据量不大，且提前可以确定长度，且可以修改原数据时，可以考虑快排。否则，还是选择堆排序。 2. 生活中需要排序的具体场景 a. 麻将或扑克中根据牌面值按顺序排序 b. 小时候做操时都是按身高依次排序 c. 考试成绩排名时需要根据分数高低排序 d. 就医时会根据挂号的编号依次就诊
2020-10-04
2
5

收起评论