2020年信奥赛C++提高组csp-s初赛真题及答案解析(选择题6-10)
2020年信奥赛C++提高组csp-s初赛真题及答案解析(选择题6-10)
第 6 题:下列哪些问题不能用贪心法精确求解?( )
A. 霍夫曼编码问题
B. 0-1 背包问题
C. 最小生成树问题
D. 单源最短路径问题
答案:B
解析:贪心法适用于具有最优子结构和贪心选择性质的问题。霍夫曼编码、最小生成树、单源最短路径(非负权)均可用贪心精确求解,而0-1背包问题贪心无法保证最优解。
第 7 题:具有 n个顶点,e条边的图采用邻接表存储结构,进行深度优先遍历运算的时间复杂度为( )。
A. O(n+e)
B. O( n 2 n^2