浙江工业大学算法分析与设计-2022-2023 (2)期中试卷

浙江工业大学算法分析与设计-2022-2023 (2)期中试卷小花醉猫B站讲解视频一、单项选择题共25小题每小题3分共75分关于算法描述不正确的是A. 对于大型的软件系统尤其是数据量巨大的系统算法起着决定性作用。B. 算法是由若干条指令组成的有穷序列。C. 算法的性质包括零个或多个输入、至少一个输出、每条指令无歧义、指令的执行时间和指令执行次数不限。D. 程序和算法的区别是程序可以是无限循环而算法必须在有限步骤内结束。对于定义在正数集上的正函数f ( n ) 2 n 2 n log ⁡ n f(n)2n^{2}n\log nf(n)2n2nlogn下列关于其渐近复杂性表述正确的是A. 函数f ( n ) f(n)f(n)当充分大时没有上界。B. 函数g ( n ) n 3 log ⁡ n g(n)n^{3}\log ng(n)n3logn不是f ( n ) f(n)f(n)的上界。C.O ( f ( n ) ) n 2 O(f(n))n^{2}O(f(n))n2D.O ( f ( n ) ) n log ⁡ n O(f(n))n\log nO(f(n))nlogn关于递归概念描述不正确的是A. 递归算法是直接或间接调用自身的算法。B. 所有递归函数都能用非递归的方式定义。C. Fibonacci数列可用递归定义出来。D. 递归算法容易定义结构清晰但运行效率较低一般地其所耗费的计算时间和存储空间都要比非递归算法多。关于分治法描述不正确的是A. 分治法的基本思想是将规模较大的问题划分为规模较小的子问题来求解。B. 随机生成100个整数并存放在一个数组中然后从中指定一个整数则可用二分搜索算法在O ( log ⁡ n ) O(\log n)O(logn)的时间内找到该整数。C. 用分治法求解大整数乘法和Strassen矩阵乘法的基本思想均是通过合理的运算变换来减少乘法的次数。D. 合并排序和快速排序的平均时间复杂性均为O ( n log ⁡ n ) O(n\log n)O(nlogn)。关于动态规划描述不正确的是A. 动态规划也是将规模较大的问题划分为规模较小的子问题来求解但与分治法不同的是动态规划所划分出来的子问题相互不独立。B. 动态规划算法适用于求解最优化问题一般采用自底向上的方式来计算。C. 能用动态规划求解的问题就不能使用递归算法求解出来。D. 动态规划求解的问题具有最优子结构和重叠子问题性质。关于贪心算法描述正确的是A. 求解活动安排问题的贪心算法 GreedySelector 的时间复杂性为O ( n log ⁡ n ) O(n\log n)O(nlogn)。B. 哈夫曼编码是一种最优前缀码因此对于给定的字符集各字符编码是唯一的。C. 对于给定的一个带权有向图G ( V , E ) G(V,E)G(V,E)则可用 Dijkstra 算法求解出从指定源顶点到其他顶点的最短路长度。D. 背包问题可散装的贪心算法同样适用于求解0-1背包问题。假定T ( n ) 2 T ( n / 2 ) n T(n)2T(n/2)nT(n)2T(n/2)n,T ( 0 ) T ( 1 ) 1 T(0)T(1)1T(0)T(1)1以下表达式错误的是A.T ( n ) O ( n 2 ) T(n)O(n^{2})T(n)O(n2)B.T ( n ) Θ ( n log ⁡ n ) T(n)\Theta(n\log n)T(n)Θ(nlogn)C.T ( n ) Ω ( n 2 ) T(n)\Omega(n^{2})T(n)Ω(n2)D.T ( n ) O ( n log ⁡ n ) T(n)O(n\log n)T(n)O(nlogn)关于NP完全理论描述不正确的是A. NP类问题是指所有不可在多项式时间内求解的判定问题。B. P类问题是指所有可在多项式时间内求解的问题。C. 所有NP类问题都可在多项式时间内规约Reduction到某个NPC问题。D. 第一个NPC问题是SAT布尔可满足性问题由Cook提出。给定一个数组A其中元素为[23, 32, 45, 69, 72, 73, 89, 97]。下面哪一个算法使用最少的比较次数获得数组A的排序A. 选择排序B. 合并排序C. 插入排序D. 总使用最后一个元素作为基准元素(pivot)的快速排序对于任意无向连通带权图G ( V , E ) G(V,E)G(V,E)当G采用邻接矩阵存储时关于其最小生成树描述不正确的是A. 图G的最小生成树是唯一的。B. 对于图G可以采用 Prim 算法或 Kruskal 算法来求解其最小生成树。C. Prim 算法的复杂度为O ( n 2 ) O(n^{2})O(n2)n为图中顶点的数量。D. Kruskal 算法的复杂度为O ( e log ⁡ e ) O(e\log e)O(eloge)e为图中边的数量。利用动态规划求解矩阵连乘问题时其渐进时间复杂度为其中n表示矩阵个数A.O ( n ) O(n)O(n)B.O ( n log ⁡ n ) O(n\log n)O(nlogn)C.O ( n 2 ) O(n^{2})O(n2)D.O ( n 3 ) O(n^{3})O(n3)对于包含n个不同元素的给定线性序集现要查找其中第k小的元素下列描述正确的是A. 当k 1 k1k1或k n knkn时选择合适的算法可在O ( 1 ) O(1)O(1)的时间复杂度内求解。B. 使用线性时间选择 Select 算法求解的时间复杂度是O ( log ⁡ n ) O(\log n)O(logn)。C. 使用随机选择基准元素的快速排序最坏情况下也可在O ( n ) O(n)O(n)的时间复杂度内求解。D. 当k ≤ n log ⁡ n k \le n\log nk≤nlogn或k ≥ n − n log ⁡ n k \ge n-n\log nk≥n−nlogn时使用堆排序可在O ( n ) O(n)O(n)的时间复杂度内求解。关于贪心算法描述不正确的是A. 对于给定的带权有向图G ( V , E ) G(V,E)G(V,E)肯定可用 Dijkstra 算法求解出从指定源顶点到其他顶点的最短路长度。B. 对于活动安排问题在对活动进行结束时间的非减序排序后使用贪心算法 GreedySelector 求解的时间复杂性为O ( n ) O(n)O(n)。C. 哈夫曼编码是一种最优前缀码但对于给定的字符集各字符编码可以不唯一。D. 如果问题存在最优子结构性质那么可以尝试采用贪心算法求解该问题。关于最优装载问题描述不正确的是A. 最优装载问题是0-1背包问题的一个变形。B. 对于最优装载问题可能找不到一组可行解。C. 最优装载问题具有最优子结构性质。D. 对于最优装载问题其贪心策略是选择重量最轻的集装箱先装。关于动态规划描述不正确的是A. 动态规划也是将规模较大的问题划分为规模较小的子问题来求解但与分治法不同的是动态规划所划分出来的子问题相互独立。B. 动态规划算法一般采用自底向上的方式来计算。C. 使用动态规划求解最优二叉搜索树的算法时间复杂度是O ( n 3 ) O(n^{3})O(n3)n是序列元素数量。D. 动态规划求解的问题具有最优子结构和重叠子问题性质。散装背包问题可分割Fractional Knapsack贪心算法的时间复杂度为A.O ( n 2 ) O(n^{2})O(n2)B.O ( n log ⁡ n ) O(n\log n)O(nlogn)C.O ( 2 n ) O(2^n)O(2n)D.O ( n ) O(n)O(n)关于贪心算法描述不正确的是A. 贪心算法求解问题时可能存在多个贪心策略。B. 贪心算法能求得0/1背包问题的最优解。C. 贪心算法实现时常常利用堆结构存储数据。D. 问题存在最优子结构时可以考虑采用贪心算法求解该问题。关于动态规划算法描述不正确的是A. 动态规划算法的发明人是 R. Bellman。B. 利用动态规划求解0/1背包问题时其时间复杂度是伪多项式。C. 动态规划算法包含了穷举计算。D. 动态规划可以用于求解两个n × n n \times nn×n矩阵的相乘问题其时间复杂度为O ( n 2 ) O(n^{2})O(n2)。以下哪个算法不是贪心算法A. Dijkstra 最短路径算法B. Prim 最小生成树算法C. Kruskal 最小生成树算法D. Bellman-Ford 最短路径算法哈夫曼编码是可变字长编码的一种依据字符出现概率来构造异字头的平均长度最短的码字。假设现有n个不同的字符那么哈夫曼编码算法的时间复杂度是A.O ( n ) O(n)O(n)B.O ( n 2 ) O(n^{2})O(n2)C.O ( log ⁡ n ) O(\log n)O(logn)D.O ( n log ⁡ n ) O(n\log n)O(nlogn)已知各个矩阵A 1 , A 2 , A 3 , A 4 , A 5 A_1, A_2, A_3, A_4, A_5A1​,A2​,A3​,A4​,A5​及其维数为[ 30 × 10 , 10 × 25 , 25 × 15 , 15 × 20 , 20 × 30 ] [30\times10, 10\times25, 25\times15, 15\times20, 20\times30][30×10,10×25,25×15,15×20,20×30]。使用动态规划法求解矩阵连乘问题以下哪一个是最优结合结果A.( A 1 ( A 2 A 3 ) ( A 4 A 5 ) ) (A_1(A_2A_3)(A_4A_5))(A1​(A2​A3​)(A4​A5​))B.( ( A 1 ( A 2 A 3 ) ) ( A 4 A 5 ) ) ((A_1(A_2A_3))(A_4A_5))((A1​(A2​A3​))(A4​A5​))C.( A 1 A 2 ) ( ( A 3 A 4 ) A 5 ) (A_1A_2)((A_3A_4)A_5)(A1​A2​)((A3​A4​)A5​)D.( A 1 ( ( ( A 2 A 3 ) A 4 ) A 5 ) ) (A_1(((A_2A_3)A_4)A_5))(A1​(((A2​A3​)A4​)A5​))给定二叉搜索树各个节点的k e y [ 1 , 2 , 3 , 4 ] key[1,2,3,4]key[1,2,3,4]节点的权重w e i g h t [ 1 , 10 , 8 , 9 ] weight[1,10,8,9]weight[1,10,8,9]按照动态规划算法可以得到一颗权重累加和最小的最优二叉搜索树该最优二叉搜索树的累加权重值为A. 35B. 45C. 50D. 55贪心算法与动态规划算法的共同点A. 重叠子问题B. 构造最优解C. 最优子结构性质D. 贪心选择性质利用动态规划算法可求解2个长度为n的序列的最长公共子序列该算法的时间复杂度为A.O ( 1 ) O(1)O(1)B.O ( log ⁡ n ) O(\log n)O(logn)C.O ( n ) O(n)O(n)D.O ( n 2 ) O(n^{2})O(n2)给8个相同的硬币其中一个硬币很重还有一个平底天平。找到这枚重硬币最少需要几次测量A. 2B. 3C. 4D. 7二、程序分析填空题本题1小题共25分本题25分对于一个包含字符 A, B, C, D, E, G 的文件各字符出现概率如下字符ABCDEG概率0.30.20.150.10.150.1请使用哈夫曼算法构造各个字符的编码给出对应的哈夫曼树并计算出所有字符编码的平均码长。字符ABCDEG概率0.30.20.150.10.150.1参考编码码长哈夫曼树为平均码长为