网课题库

拓扑排序的时间复杂度是O( )‍ 答案:  m+n


拓扑排序的时间复杂度是O( )‍

答案:  m+n

本门课程完整答案：点击这里，查看 算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033

相关试题


‏动态规划计算最长不降子序列的时间是O（） ‍

答案:  n^2


‏拓扑排序的结果是一个顶点序列，顶点间存在先序关系。​

答案:  正确


‍嵌套矩形问题本质上求DAG上的最长路径，但没有给出起点和终点。‍

答案:  正确


‎反推求解嵌套矩形问题，很难打印字典序最小的方案。​

答案:  错误


  硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。​

答案:  正确


DAG图最长路的正推关系是 L(j) = 1 + max {L(i) : (i， j) 为边} ‌

答案:  正确

7.7 知识梳理


‏Floyd算法的复杂度为O（）‌

答案:  n^3


如果图中存在负环，那么从s到t没有最短路。 ‏

答案:  正确


Bellman算法的计算时间为Q(mn)， 空间为 Q(n^2)，可以求最短路，也可求最长路。   ‏

答案:  正确


​SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。‏

答案:  正确


‌Floyd算法可以构造无向或有向加权图（包含长度为负的回路）的完全最短路径‌

答案:  错误


‎SPFA算法计算时，如果一个顶点入队列的次数超过n，则存在负权回路。​

答案:  正确


动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到根节点。‎

答案:  正确

7.8 知识梳理


‍LCS问题的不同子问题个数为 O（）‌

答案:  mn

‏序列  算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第14张. 设LCS(X， Y)=算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第15张。若算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第16张则算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第17张，且算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第18张是算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第19张和算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第20张的最长公共子序列。

​
答案:  正确

‎给定串算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第21张 ， 一个比对M是有序对 算法分析与设计(山东财经大学) 中国大学mooc答案满分完整版章节测验 m289033第22张的集合，每一项至多参与一个配对，并且允许交叉。 

‍
答案:  错误


‎动态规划方程中子问题个数为n^t，依赖的子问题个数为n^e， 则算法的时间复杂度为n^(t+e)   ‏

答案:  正确


‍序列的编辑距离是间隔的惩罚值和错配的惩罚值之和。​

答案:  正确


‌动态规划方程M[i，j]=min(M[k]+wk)， 1≤i≤k≤j≤n， 则算法的时间复杂度为n^2 ‌

答案:  错误

 

320 321 322 … 338 下一页

渝ICP备2022003152号-5

渝公网安备 50011202503438号