《算法分析与设计》课后作业

算法分析与设计各章课后作业第一章 课后作业1. 设某算法在输入规模为n时的计算时间为T(n)=10*2n。若在甲台计算机上实现并完成该算法的时间为t秒，现有一台运行速度是甲的64倍的另一台计算机乙，问在乙计算机上用同一算法在t秒内能解决的问题的规模是多大？ 2.按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？第二章 课后作业1. 用展开法求解下列递推关系：T(n)=，写出T(n)的大O记号表示。2. 下面是实现在a0<=a1<=<=an-1中搜索x的二分搜索算法，请根据二分搜索技术在下划线处填充语句。算法描述如下：template<class Type>public static int BinarySearch(int a, int x, int n) /在a0<=a1<=<=an-1中搜索 x/ 找到x时返回其在数组中的位置，否则返回-1int left = 0; int right = n - 1;while ( ) int middle = ;if(x = amiddle) return ;if(x > amiddle) left = middle + 1;else right= ;return -1; / 未找到x 第三章 课后作业1、选择题。（1）下列算法中通常以自底向上的方式求解最优解的是（      ）。A、备忘录法B、动态规划法C、贪心法D、回溯法（2）备忘录方法是那种算法的变形。（ ）A、分治法 B、动态规划法C、贪心法D、回溯法（3）矩阵连乘问题的算法可由（         ）设计实现。A、分支界限算法     B、动态规划算法    C、贪心算法    D、回溯算法2计算题。设有0-1背包问题，物品个数n=5，背包容量c=10，物品的重量w=(w1,w2,w3,w4,w5）=2,2,6,5,4，物品的价值v=(v1,v2,v3,v4,v5)=6,3,5,4,6。利用动态规划算法，求出不超过背包容量，怎样选择物品，使得装入背包中物品的总价值最大。说明：表1就是计算m(i,j)。m(i,j)为最优值（即价值总和最大），它表示背包容量为j，可选择物品为i,i+1,n时0-1背包问题的最优值。请填写表1中空缺的内容，并给出最优值和选择哪些物品。表1 动态规划算法求0-1背包的过程（即计算mij） ji0123456789105000066666640000666661030000666661020033669910111006669121515第四章 课后作业1、选择题。（1）下面是贪心算法的基本要素的是（            ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解（2）（     ）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质（3）下面问题（ ）不能使用贪心法解决。A、单源最短路径问题 B、N皇后问题 C、最小花费生成树问题 D、背包问题2、对于字符集合M=A,B,C,D,E,F，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。第五章 课后作业1、选择题。（1）回溯法解旅行售货员问题时的解空间树是（       ）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树（2）下列算法中通常以深度优先方式系统搜索问题解的是（     ）。A、备忘录法B、动态规划法C、贪心法D、回溯法（3）下面哪种函数是回溯法中为避免无效搜索采取的策略（       ）。A递归函数B.剪枝函数 C。随机数函数D.搜索函数2、回溯法中常见的两类典型的解空间树是哪些，请简述之。第六章 课后作业1、选择题。（1）广度优先是（           ）的一搜索方式。A、分支界限法      B、动态规划法    C、贪心法    D、回溯法（2）采用最大效益优先搜索方式的算法是（          ）。A、分支界限法B、动态规划法C、贪心法D、回溯法（3）分支限界法解旅行售货员问题时，活结点表的组织形式是（        ）。A、最小堆B、最大堆 C、栈D、数组2、填空题。（1）分支限界法主要有 分支限界法和 分支限界法。（2）使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 ，只使用约束条件进行裁剪的是 。（3）以广度优先或以最小耗费方式搜索问题解的算法称为 。第七章 课后作业1、选择题。（1）蒙特卡罗算法是（  ）的一种。A、分支界限算法      B、概率算法    C、贪心算法    D、回溯算法（2）下列哪一种算法不是随机化算法（   ）。A. 蒙特卡罗算法B. 拉斯维加斯算法C.动态规划算法D.舍伍德算法（3）下列随机算法中运行时有时候成功有时候失败的是（ ）。A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法2、填空题。（1）拉斯维加斯算法找到的解一定是 。（2）数值概率算法常用于 的求解。（3）利用概率的性质计算近似值的随机算法是_数值概率算法，运行时以一定的概率得到正确解的随机算法是_蒙特卡罗算法_。（4）拉斯维加斯算法找到的解一定是_ _。