斯坦福算法专项课程Course2 Final Exam

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

课程地址: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,第一项和第三项正确