北师大0512算法分析与设计在线作业Word文档格式.docx

1、第3题（2.5分）备忘录方法的递归方式是：自顶向下自底向上和动态规划算法相同非递归的C第4题（2.5分）回溯法的求解目标是找出解空间中满足约束条件的：所有解一些解极大解极小解A贪心算法和动态规划算法共有特点是：贪心选择形函数哈夫曼编码是：定长编码变长编码随机编码定长或变长编码B第7题（2.5分）多机调度的贪心策略是：最短处理时间作业优先随机调度最优调度第8题（2.5分）程序可以不满足如下性质： （ ）零个或多个外部输入至少一个输出指令的确定性指令的有限性第9题（2.5分）用分治法设计出的程序一般是：递归算法动态规划算法贪心算法回溯法采用动态规划算法分解得到的子问题：相互独立与原问题相同相互依赖

2、相互独立且与原问题相同第11题（2.5分）回溯法搜索解空间的方法是：深度优先广度优先最小耗费优先随机搜索第12题（2.5分）拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：所需时间变化一定找到解找不到所需的解性能变差贪心算法能得到：全局最优解0-1背包问题的解背包问题的解无解能求解单源最短路径问题的算法是：分支限界法动态规划线形规划蒙特卡罗算法第15题（2.5分）快速排序算法和线性时间选择算法的随机化版本是：舍伍德算法拉斯维加斯算法数值随机化算法第16题（2.5分）动态规划算法解各个子问题的方法是:随机选择自底向上或自顶向下回溯法解园排列问题的解空间树是：子集树排列树二叉树多

3、叉树用分治法求平面最接近点对问题时采用的著名原理是：鸽舍原理牛顿原理线性规划原理分支限界法搜索解空间的方式是：随机以上都不是采用如下随机方法计算 值：随机投点法舍伍德法拉斯维加斯法单纯形法下面是描述算法复杂度的有：时间复杂度二分法随机化算法下面不属于单纯形法步骤是：选入基变量选离基变量做转轴变化第23题（2.5分）、快速排序和线性时间选择的随机化版本是：蒙特卡罗用回溯法解旅行售货员问题时生成的解空间树是：用回溯法解0-1背包问题时生成的解空间树是：用分支限界法解布线问题时的解空间是：图第27题（2.5分）跳跃表是采用哪种随机化算法设计的：第28题（2.5分）合并排序和快速排序都采用的策略是：分

4、治下面不属于单纯形法的步骤的是：作转轴变化找最优子结构Kruskal算法能解以下问题：单源最短路径n后问题最小生成树装载问题第31题（2.5分）贪心算法解各个子问题的方法是：第32题（2.5分）用回溯法解旅行售货员问题时生成的树是：在n后问题中任意两个皇后能放在：同一行同一列同一斜线以上都不行第34题（2.5分）第35题（2.5分）用贪心算法解单源最短路径问题时采用的算法是：Dijkstra算法Prime算法Kruskal算法在用动态规划解流水作业调度时的最优调度法则是：算法与程序的区别在于：输入输出第38题（2.5分）从分治法的一般设计模式可以看出，用它设计的程序一般是：顺序选择循环递归回溯法的解空间是在搜索过程中：动态产生静态产生无解空间动态或者静态产生第40题（2.5分）分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：