[数据结构与算法] 算法分析与设计

文章目录

算法与程序的区别是
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
判断_问题的两个要素是输入和实例。
对近似递增序列的线性表从小到大排序，使用哪种方法好？
多选_顺序查找适合的数据结构是（）
f(n)=3n^3+7n^2+4nlogn =O（____）
?选择排序的时间复杂度是O（____）
贪心算法基本要素有（）和最优子结构性质。
使目标函数最大（小）的解是问题的
原问题的最优解包含其子问题的最优解是贪心算法的（）性质。
判断_贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
单选_下面**不是**证明贪心算法证明方法的有（）。
?把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是
多选_最小生成树问题可以使用的算法有（）
判断_?贪心算法总能找到可行解，但未必是最优解。
判断_问题的可行解是满足约束条件的解
未来与过去无关指的是（）的性质
对于稠密图，使用（）算法计算MST更适合
判断_哈夫曼编码的平均码长最小
下面有关递归与迭代的说法错误的是
多选_递归一般用于解决问题有（）：
递归和递推的区别
判断_一般来说，递推的效率高于递归,因此将递归转化为递推
判断_每个递归算法原则上总可以转换成与它等价的迭代算法，反之不然。
多选_递归变为非递归的方法有（）
插入排序最好的情况是O(___)
?从大规模问题逐步化为小规模问题的算法是（）
多选_递归函数的要素是（）
多选_归变为非递归的方法有（）
判断_?尾递归中的递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。
堆排序的时间复杂度是（）
对线性表进行折半查找最方便的数据结构是（)
多选_分治法所能解决的问题一般具有（）特征.
多选_改进分治算法的方法有（）
判断_分治与递归都是从大规模问题逐步化为小规模问题，因此分治算法经常使用递归实现。
判断_分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。
判断_?随机快速排序的时间是O（n^2）
判断_两个有序数组合并的时间不会超过两个数组的长度和。
设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )法。
找n个元素的中位数的分治算法的时间复杂度为O(___).
多选_减治法常见的形式有（)
判断_改进子问题合并的时间复杂度可以减少分治算法的时间。
合并排序的时间复杂度是（）
大整数乘法分治算法的时间为O（）
多选_通过减少子问题个数，降低分治算法时间复杂度的有（）
分治法分解的子问题与原问题形式相同。
判断_?任何排序算法至少需要O(nlog n)次比较。
判断_分治法将原问题分解为若干个规模较小、相互独立、**完全相同**的子问题。
判断_给定n个元素，找其中位数的时间是O（n）
动态规划方法使用（）计算方式。
?确定第 i 阶段的收益函数和从第1阶段出发到第i 阶段末所获得收益的最优值，建立动态规划基本方程。这种方法是（）
Floyd算法的复杂度为O（）
多选_最短路算法中适用于稠密图的是（）
多选_下面哪些问题的动态规划算法的时间复杂度为Q(mn)？
?DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度
判断_状态转移方程表示状态间的递推关系，也是子问题间的递推关系。
判断_硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。
判断_动态规划计算树上的最大独立集时，从叶子开始，先计算子树，逐步计算到根节点
下面不是动态规划的基本方法有（）。
多选_备忘录算法的特点（）
多选_备忘录与递归算法的相同点是（）
判断_动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
判断_?0-1背包问题的动态规划算法可以使用一维数组实现。
判断_硬币问题本质上是DAG上的最长路径和最短路，且给出起点和终点。
含负权的最短路问题一般使用（）求解。
下面不是动态规划的基本方法有（）。
多选_动态规划算法的特点（）
多选_OPT(i，w): 从1-i个物品中选择，放入容量为w的背包时的最大价值。这是（）问题动态规划算法的递推函数。
判断_最优子结构是问题能用动态规划算法求解的前提。
判断_贪心和递推算法是线性解决问题，动态规划则是全面分阶段地解决问题。
下面哪种函数是回溯法中为避免无效搜索采取的策略（）
多选_回溯法的效率依赖于下列哪些因素（）
多选_?回溯法的两种解空间树为
判断_?回溯法是按广度优先策略搜索解空间树。
判断_好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
多选_问题的状态生成法有（）
判断_回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
判断_装载问题，当所给的问题规模为n时，通常有2^n个叶结点。
判断_回溯算法用限界函数剪去得不到最优解的子树。
?合并排序算法是利用（）实现的算法
下列不是动态规划算法基本步骤的是（）
下列算法中通常以自底向上的方式求解最优解的是（）
备忘录方法是那种算法的变形（）
最长公共子序列算法利用的算法是（）
?贪心算法与动态规划算法的主要区别是（）
?（）是贪心算法与动态规划算法的共同点
矩阵连乘问题的算法可由（）设计实现
?下列是动态规划算法基本要素的是（）
归并排序
- 在归并排序算法中，若每次分解将长度为 n 的数组分为两段，长度分别为 n-1 和 1，此时归并排序算法的时间复杂度为____
- 在归并排序算法中，若每次分解将长度为 n 的数组分为四段长度为 n/4 的子数组进行递归，此时归并排序算法的时间复杂度为____
- 归并排序的最好情况时间复杂度为____
分治法时间复杂度计算公式

算法与程序的区别是

解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明

判断_问题的两个要素是输入和实例。

对近似递增序列的线性表从小到大排序，使用哪种方法好？

多选_顺序查找适合的数据结构是（）

f(n)=3n³⁺⁷ⁿ2+4nlogn =O（____）

?选择排序的时间复杂度是O（____）

贪心算法基本要素有（）和最优子结构性质。

使目标函数最大（小）的解是问题的

原问题的最优解包含其子问题的最优解是贪心算法的（）性质。

判断_贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。

单选_下面不是证明贪心算法证明方法的有（）。

?把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是

多选_最小生成树问题可以使用的算法有（）

判断_?贪心算法总能找到可行解，但未必是最优解。

判断_问题的可行解是满足约束条件的解

未来与过去无关指的是（）的性质

对于稠密图，使用（）算法计算MST更适合

判断_哈夫曼编码的平均码长最小

下面有关递归与迭代的说法错误的是

多选_递归一般用于解决问题有（）：

递归和递推的区别

递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题是逆向的。

递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。