算法与复杂度简单
哪种记号表示增长的上界？
- ABig Omega
- BLittle omega
- CBig O
- DBig Theta
显示提示
- “至多”。
- 两个错误答案已被划掉。剩下的两个中有一个是正确的。
显示答案和解析
为什么是这个答案
O 表示上界，Ω 表示下界，Θ 表示紧确界（tight bound）。
答案
C · Big O
数据结构与算法：练习题和考试题
大 O 表示法、常见算法的运行时间，以及数组、链表、树、哈希表和图之间的取舍。
速成包（PDF）公式表、方法步骤和附完整解答的练习题，可直接打印。
本课程的主题
数据结构与算法 考试技巧
- 嵌套循环要把迭代次数相乘；顺序执行的循环取较大的那一项。
- 掌握每种数据结构的查找、插入和删除的代价。
- 每一步把输入规模减半，得到对数时间。
例题详解
数据结构中等
在二叉最小堆中，extract-min 是如何工作的？
- A删除数组的最后一个元素
- B把最后一个元素移到根上，再将其下沉
- C删除根，并把所有元素左移一位
- D在所有叶子中查找新的最小值
显示提示
- 先保持树的完全性，再修正顺序。
- 两个错误答案已被划掉。剩下的两个中有一个是正确的。
显示答案和解析
为什么是这个答案
最后一个元素填补根上的空位，并与其较小的子节点交换，直到满足堆性质，耗时 O(log n)。
答案
B · 把最后一个元素移到根上，再将其下沉
练习方式
- “练习本课程”会混合出该课程所有主题的题目，就像真正的考试一样。
- 每道题的数值都不同，让你掌握方法，而不是记住答案。
- 卡住了？先打开一个小提示，需要时再查看完整解析。
- 模拟考试限时且没有提示，结束后你会得到分数和完整的回顾。