算法复习资料(中文版).doc

一，选择题1，下列公式可被视为一个计算三角形面积的一面正数X，Y和Z的长度的算法？（）（一）=L（L - X）（L- Y）（L- Z），其中L =（X，Y，Z）/ 2（二），S = 1/2 yzsinA，其中A是双方Y和Z之间的角度（三），S = 1/2 XH，其中h是高度基地x（四）以上都不可以被认为是算法2，在功能的四对，对有增长的顺序不同？（）（一）（N31）5n和（N7 N）（二）log22n和log2n2（三）log10n和LN（四）5N- 1和5N13，关于渐近符号下面的描述哪些是正确的？（）（一）为O（F（N）的所有功能，具有较大的增长相同的顺序为F（N）（二）（F（n）的增长相同的顺序为F（N）的所有功能设置（三）（F（N）是所有功能的设置相同或较小的增长为F的顺序（N）（四）以上都不是正确的4，多少比较会受到蛮力字符串匹配算法的搜索模式=“00. .0（M - 1个）”，在文本=“00. .0（N个)?()（一）（1纳米）米（B）1纳米（三）（NM）M（四）纳米5，关于归并排序和快速排序的以下断言哪个是假？（）（一）在最好的情况下，合并排序的时间效率是（nlogn）（二）快速排序在最坏情况下的时间效率是O（nlogn）（三）合并排序在最坏情况下的时间效率是（nlogn）（四）在平均情况下的快速排序的时间效率是（nlogn）6，下列哪项是堆？（）10754681112224455577887，以下问题不能使用广度优先搜索算法解决？（）（一）找到两个给定一个图的顶点之间的数量最少的边的路径（b）检查图acyclicity（c）寻找一个无向图的关节点（d）检查图的连通8，下面的算法属于可变大小减少技术（？）（一）二进制搜索（二）插值搜索（三）顺序搜索（d）俄罗斯农民的方法followting算法计算二项式系数是最有效的呢？（9）（a）适用于动态规划算法（b）申请递归的fomulaC组（n，K）= C（N- 1，K- 1）+（N - 1，K）N K0C组（n，0）= C（N，N）= 0（三）利用公式C（N，K）= N!/ K!（N- K）！（d）使用公式C（N，K）= N（N - 1）. .（N - K +1）/ K!10，下列哪项是真的吗？（）（一）如果e是一个连接加权图的最低weighe边缘，必须至少有一个最小生成树的图的树边之间。（二）如果连接的加权图的边权重是不是所有不同，图中必须有一个以上的最小生成树。（C）如果e是一个连接加权图的最低weighe边缘，它必须成为每个树图的最小生成树的边缘。（四）以上都不是正确的。二，填空题（1）给定一个recourrence T（N）+ N 2=9T（n / 3的），T（1）= 3，增长recourrence is_的解决方案roder。（使用的渐近符号）（2）一个djacency基质and_are两个数据结构来存储或代表图。（3）大街的矩阵乘法算法is_乘法。（4）有三个减少和征服技术的变化;减少一个常数,_可变大小的减少。（5）以下的有向图is_ lopological秩序。（6）N =47的约瑟夫问题的解决方案是J（N）=_.（7）有三种不同类型的变换而治之的技术:_, Represention变化和减少问题。（8）申请荷马的规则来评价多项式P（X）=3X4- X 32X 2 x在一个特定的X5的乘法总数is_。 0 0 1 0 0 0 0 1（9）鉴于以下的邻接矩阵定义有向图 0 1 0 0 0 0 0 0它的传递闭包是_。（10）贪婪的做法表明，贪婪选择的每一步，构建一个解决方案通过一个步骤的顺序，必须作出的选择feasiable，局部最优和_。3。对于下列每个问题，给出一个简短和准确的答案，在答题簿上。（1）确定以下排序算法是稳定的算法，哪些不是稳定的算法：选择排序，合并排序，冒泡排序，插入排序和快速排序，并解释为什么。（2）总体规划确定的非递归算法的效率分析。（3）四种类型描述分类DFS（深度优先搜索）算法的有向图，如何检查的有向图的acyclicity的边缘。4.For每个下面的问题，回答一个合适的答案的答题簿上。（1）假设x是一个正整数，n是2的乘方，使用蛮力方法，divede和征服，技术，减少由一个技术，并减少一半技术，分别计算X N确定每种技术和指出该技术是最有效的乘法。（2）动态规划方法解决0-1 knaspsack问题。背包问题的实例如下表。你需要：（1）推导的递推公式V I，J;（2）填写的V，并计算出最佳的解决方案项目设置表（假设的VI，J。最佳的解决方案，以一个0-1背包问题，即适合capactity J.背包的第i个项目的最有价值的一个子集的值的实例的值） Itme weight value 1 2 $24 2 1 $20 3 3 $50 容量W=5 4 2 $30 （3）解决高斯消元以下的系统。 X1+2 X23 X3=9 2X1+ X2 + X3= 4 X1 - X2-3 3=6（4）申请Dijkstn的算法来计算一个给定的源顶点的单源最短路