首页 › 答案 › 标签 › 算法分析与设计

算法分析与设计

1给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。
2一个问题的同一实例可以有不同的表示形式
3同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
4问题的两个要素是输入和实例。
5算法与程序的区别是（）
6解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
7下面说法关于算法与问题的说法错误的是（）。
8下面关于程序和算法的说法正确的是（）。
9最大独立集问题和（）问题等价。
10给定两张喜欢列表，稳定匹配问题的输出是（）。
11问题变换的目的有（）。(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难解变易解（5）以上都是。
12按照霍纳法则，计算p(x)=anxn+an-1xn-1+…+a1x1+a0的数量级为____。
13时间复杂度是指算法最坏情况下的运行时间。
14f(n)=O(g(n))则f(n)2=O(g(n)2)
15f(n)=3n3+7n2+4nlogn=O（n2）
16如果一个算法是多项式时间算法，该算法是有效的,是好算法。
17从资源划分，算法的复杂度分为（）和（）。
18算法复杂度分析的两种基本方法为（）和（）。
190-1背包问题的枚举算法的时间复杂度为O（2n）
20增量构造法生成子集前需要对集合中元素从小到大排列。
21分块查找一般设分块的长度是n/2
22枚举法适用于问题的小规模实例。
23便于实现集合操作的子集生成算法是（）
24从所有候选答案中去搜索正确的解，这是（）算法。
25logn2=()(logn+5)
260-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
27分数拆分问题的枚举算法通过（）方法进行了优化。
28下面那些算法的时间复杂度为O（）?
29贪心算法总能找到可行解，但未必是最优解。
30贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
31问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
32如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。
33Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
34贪心算法基本要素有（）和最优子结构性质。
35下面不是证明贪心算法证明方法的有（）。
36未来与过去无关指的是（）的性质
37最小生成树问题可以使用的算法有（）
38区间问题包含（）
39正推是从小规模的问题推解出大规模间题的一种方法。
40一般来说，递归的效率高于递推。
41从大规模问题逐步化为小规模问题的算法是（）
42求解高阶递推方程一般使用（）迭代方法
43下面有关递归与迭代的说法错误的是（）
44递归函数的要素是（）
45递归变为非递归的方法有（）
46T(n)=T(n-1)+n，T(1)=1，则T(n)=（）
47递归一般用于解决问题有（）
48主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方程，则下列关于方程中的约束中不准确的是？
49分治法分解的子问题与原问题形式相同。
50N个元素排序的时间复杂度不可能是线性时间。
51三分法的判定树是三叉树。
52减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
53设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()法。
54堆排序的时间复杂度是O（）。
55以下不可以使用分治法求解的是（）。
56改进分治算法的方法有（）和改进划分的对称性。
57通过减少子问题个数，降低分治算法时间复杂度的有（）
58分治法在每一层递归上有三个步骤（）
59动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
600/1背包问题的动态规划算法是多项式时间算法。
61对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。
62Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
63含负权的最短路问题一般使用（）求解。
64动态规划算法的基本要素有（）和最优子结构性质。
65下面不是动态规划的基本方法有（）。
66最短路算法中适用于稀疏图的是（）
67动态规划算法的特点（）
68备忘录算法的特点（）
69回溯法是按广度优先策略搜索解空间树。
70死结点是正在产生儿子的结点。
71回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
72分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
73分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
74队列式分支限界法以最小耗费优先的方式搜索解空间树。
75优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
76下列算法中不能解决0/1背包问题的是
77分支限界法解旅行商问题时的解空间树是
78优先队列式分支限界法选取扩展结点的原则是
79用分支限界法设计算法的步骤是：
80分支限界法与回溯法的不同点是什么？
81FIFO是（）的搜索方式。
82网络流满足容量约束，但一般不满足流量守恒约束。
83设G=<V1,V2,E>为二分图,|V1|≤|V2|,M为G中一个最大匹配,且|M|=|V1|,则称M为G的完备匹配，也是最大匹配。
84存在割(A,B)使流值v(f)=割的容量cap(A,B)，则割(A,B)是最小割。
85给定连通图G,BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。
86有下界的流通问题不一定有可行流。
87Dinic算法的时间复杂度为（）
88如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有
89改进FF网络流算法，可以通过选择（）增广路，降低时间复杂度。
90带需求的流通必须满足供给和=需求和
91蒙特卡罗算法的结果肯定是一个正确解。
92Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。
93借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
94随机算法共同点是计算时间越多或运行次数越多,正确性越高
95增加拉斯维加斯算法的反复求解次数,可使求解无效的概率任意小。
96在下列算法中有时找不到问题解的是
97肯定获得可行解，但不一定是正确解的算法是
98在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（）对输入进行预处理。
99（）肯定获得最优解。
100给定问题p，若有算法A，存在一个常数K>=0，使得问题p的所有实例I，总有：|A(I)-OPT(I)|<=K,则称算法A为解答问题p的绝对近似算法。
‹1234›