这里回顾下第二门课的期末考试。

课程地址：https://www.coursera.org/specializations/algorithms

选择题 1

考虑边长非负的有向图$G=(V,E)$ 和两个不同的顶点$s,t$。让$P$表示$G$中$s$到$t$的最短的路径。如果我们在图中的每条边的长度上加$10$，那么：

  • 如果$P$只有一条边， $P$绝对是$s-t$最短路径

  • $P$可能会也可能不会保持最短$s-t$最短路径（取决于图）

  • $P$绝对是$s-t$最短路径

  • $P$绝对不是$s-t$最短路径

因为每条边都增加$10$，所以总长度为原长度加上边的数量乘以$10$，不难看出前两项正确

选择题 2

DFS的运行时间是多少，作为$n$和$m$的函数，如果是输入图$G=(V,E)$ ，图由邻接矩阵表示$n=|V|,m=|E|$?

  • $\theta(n+m)$
  • $\theta(n^2 \log m)$
  • $\theta(n^2)$
  • $\theta(n*m)$

每次要扫描和某个点相连的节点，判断是否有边存在，时间复杂度为$\theta(n^2)$，第三项正确

选择题 3

对于有$n$个元素的heap，Insert和Extract-Min的渐进运行时间分别是多少？（假设您有足够大的数组来容纳您所面临的插入。）

  • $\Theta(\log n)$和$\Theta(\log n)$
  • $\Theta( \log n)$和$\Theta(1)$
  • $\Theta(n)$和$\Theta( 1)$
  • $\Theta(1)$和$\Theta(\log n)$

由Heap的性质可知，第一项正确

选择题 4

在向有向图G添加一个额外边时，强连接组件的数量？

  • 不能减少超过$1$
  • 不能减少
  • 不能变
  • 可能会也可能不会保持不变（取决于图）

根据第一周最后一题可知，最后一项正确

选择题 5

以下哪项陈述适用？（照常$n$和$m$分别表示图形的顶点和边数。）[选中所有适用的。]

  • 广度优先搜索可用$O(m+n)$时间计算无向图的连通分量

  • 广度优先搜索可用$O(m+n)$时间计算最短路径（每个边都有单位长度）

  • 深度优先搜索可用$O(m+n)$时间计算有向图的强连通分量

  • 深度优先搜索可用$O(m+n)$时间计算有向无环图的拓扑排序

结论都正确，讲座中都有提到

选择题 6

有向图何时具有唯一的拓扑排序？

  • 其他选择都不正确

  • 每当它是一个完整的有向图

  • 每当它有一个唯一的循环

  • 每当它为有向非循环图

第一项正确， 其他几项不难举出反例

选择题 7

假设您使用排好序的数组（例如，从最大到最小）实现优先级队列的功能。

Insert和Extract-Min的最差运行时间分别是多少？（假设您有足够大的数组来容纳您所面临的插入。）

  • $\Theta(1)$和$\Theta(\log n)$
  • $\Theta(n)$和$\Theta(1)$
  • $\Theta(n)$和$\Theta( n)$
  • $\Theta(1)$和$\Theta(n)$

Insert需要移动后续的元素，最坏时间复杂度为$\Theta(n)$，Extract-Min直接弹出最后一个元素即可，最坏时间复杂度为$\Theta(1)$，第二项正确

选择题 8

计算机程序中的以下哪种模式表明堆数据结构可以提供显着的加速（检查所有适用的）？

  • 重复的最小计算
  • 重复查找
  • 重复的最大计算
  • 没有其他选择

由Heap的性质可知，第一项和第三项正确

选择题 9

计算机程序中的以下哪种模式表明哈希表可以提供显着的加速（检查所有适用的）？

  • 没有其他选择
  • 重复的最小计算
  • 重复的最大计算
  • 重复查找

由哈希表的性质可知，最后一项正确

选择题 10

关于Dijkstra的最短路径算法，以下哪些陈述适用于可能具有一些负边长的输入图？[检查所有适用。]

  • 保证终止
  • 它可能会也可能不会终止（取决于图表）
  • 它可能会或可能不会正确计算最短路径距离（从给定的源顶点到所有其他顶点），具体取决于图形
  • 它一定能正确计算最短路径距离（从给定的源顶点到所有其他顶点）

参阅第二周选择题4，5，第一项和第三项正确