GESP-C++八级 题库
共 3 道题
· 按题型筛选,点「查看答案」核对解析
1
判断题
偏易
使用二叉堆优化的Dijkstra最短路算法,在某些特殊情况下时间复杂度不如朴素实现的O(V^2)。
A
对
B
错
答案与解析
正确答案:对
分析图的顶点数V与边数E的数量级关系;考察二叉堆优化Dijkstra中每次边松弛操作引起的堆操作次数与复杂度;计算二叉堆版本总时间复杂度O((V + E) log V);对比稠密图中E接近V^2时该表达式的增长趋势;比较朴素算法在所有情况下均保持O(V^2)的时间复杂度;考虑当E足够大时,(V + E) log V可能超过V^2;识别图结构中边密度对两种实现方式效率的影响机制。
2
判断题
偏易
求两个序列的最长公共子序列(LCS)时,使用滚动数组优化空间后,仍然可以还原出具体的LCS序列。
A
对
B
错
答案与解析
正确答案:错
使用动态规划求解最长公共子序列时,状态转移基于前一行或当前行的值更新。滚动数组通过只保存必要行(如当前行和上一行)来减少空间占用。还原具体LCS序列需回溯路径,可在计算过程中记录决策位置或利用原序列与滚动数组状态逆推匹配点。匹配字符的位置可通过比较当前状态与前一状态差异确定,逐步向前追踪至序列起始。此过程不依赖完整二维表,仅需当前维护的压缩状态及原始输入序列即可实现路径重建。
3
判断题
偏易
在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径,时间复杂度为O(v2),可进一步优化至O(e+vlog(v))。
A
对
B
错
答案与解析
正确答案:对
暴力枚举每个点,时间复杂度是O(v2);用优先队列每次找到距离最短的点,优先队列时间复杂度是O(logn),每个点和边都访问一次,所以时间复杂度是O(e+vlogv)。