算法试卷.doc

算法设计与分析课程试题一一、选择题1选出不是算法所必须具备的特征（ ）。A有穷性 B确切性 C高效性 D可行性2下列（ ）不是衡量算法的标准。A 时间效率 B 空间效率 C 问题的难度 D 适应能力3与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为（ ）。A x(n)=2n B x(n)=2n-1 C x(n)=2n+1 D x(n)=n!4二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（ ）。A 1个 B 2个 C 6个 D 8个5下列是动态规划算法基本要素的是（ ）。A 最优子结构 B构造最优解 C 贪心选择因子 D界限函数6（ ）算法应用到广度优先遍历策略。 A 分支界限法 B 动态规划法 C分治法 D回溯法7Prim算法求最小生成树采用的是（ ）算法思想。 A 贪心算法 B 动态规划法 C 回溯法 D 蛮力法11三个盘子的汉诺塔，至8对于凸集下列说法正确的是（ ）。A 凸集中的所有点都属于凸包； B 凸集中任意两点的连线都在凸中；C 凸集中任意两点的连线都不在凸集中；D一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中少9对多段图问题描述不正确的是：；、多段图是一个无向图、可用向前处理法；、可用向后处理法；、可用分治法解决。10以下对回溯法描述正确的是：；、解必须表示成一个2n-元组（x1，x1，x2，x2，xn，xn）;、回溯法的解必须满足一组综合的约束条件，称为解函数；、满足显示约束的所有元组不能确定一个可能的解空间,、隐式约束描述了元组中元素xi必须彼此相关的情况。二、填空1算法区别于程序： 。2递推公式x(n)=x(n-1)+n,x(0)=0，x(n)= 。3按分治策略求解棋盘覆盖问题时，对于如图1所示的2323的特殊棋盘，共需要_个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况。12345678+ + - + - + + - - - - +- + + + - + + - + - -+12345678图1 棋盘覆盖图2 符号三角形4对下述五个文件用贪心方法进行最优归并：文件x1，x2，x3，x4和x5分别有18，24，8，6和28个记录；则文件移动的最少次数为： 。5常见的智能算法有 、 、 、 。三、简答题：1简述算法的复杂性分析主要是分析算法的什么耗费情况以及算法的时间复杂度用什么计量？2简述贪心算法、动态规划和分治算法的基本思想。3对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或或，并简述理由。(1) (2) (3) 4试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。三、应用题1试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。2用动态规划算法求下面网络的最短路：3已知元素a，b，h依次有概率0.1，0.2，0.05，0.1，0.3，0.05，0.15，0.05，其余情况的概率为0，请建立其最优二叉搜索树。（10分）4考虑下面的用最少硬币个数找出n分钱的问题。1）当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心算法找出n分钱，并证明算法能够产生一个最优解。2）假设可使用的硬币面值是c0，c1，ck，其中，c是一个正整数且c1，k1。证明在这种情况下贪心算法总能产生最优解。给出一个贪心算法不能产生最优解的硬币面值组合。算法设计与分析课程试题二一、选择题1选出不是算法所必须具备的特征（ ）。A输入输出性 B确定性 C可行性 D高效性2下列函数关系随着输入量增大增加量最快的是（ ）。A nlogn B3n3 C3n+2 D n!3下列程序段的算法时间复杂度是（ ）for (i=1;i=n;i+)for (j=1;i=m;m+) for (j=1;i=k;k+) S;A O(kn2) B O(km2) C O(m+n+k) D O(mnk)4N个盘子的汉诺塔，至少要执行移动操作次数为（ ）。A N次 B N2次 C logN次 D 2N-1次5以下描述是有关算法设计的基本步骤：问题的陈述 算法分析 模型的拟制 算法的实现算法的详细设计 文档的编制，应与其它环节交织在一起其中正确的顺序是（ ）。A、 B、 C、 D、6一个四城市的旅行售货员问题，其解空间的深度为（ ）。A 3 B 4 C 5 D 67下列是动态规划算法基本要素的是（ ）。A 最优子结构 B构造最优解 C 贪心选择因子 D界限函数8Floyd算法属于（ ）。A 贪心算法 B概率算法 C回溯法 D分支限界法9（ ）算法应用到广度优先遍历策略。 A 分支界限法 B 动态规划法 C分治法 D回溯法10下列算法不是智能算法（ ）。A 粒子群 B 枚举法 C模拟退火 D分支限界二、填空14n2,logn,3n,20n,2,n2/3,n!按渐近阶从低到高顺序排序： 、 、 、 。2一个具有n个圆盘的Hanoi塔，至少移动_次圆盘才能达到目标状态。3对于问题状态S，由根到S的那条路径确定了这个解空间中的一个元组，那么状态S称为 。4Strassen矩阵乘法可以利用_算法实现.5二分检索平均情况下不成功检索的时间复杂度为： _ 。6有设备更新问题如下所示，五年内收益最大的设备更新策略的最大收益为_。7. 概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到_（完全不同/基本近似）的效果求解时间甚至是所得的结果。概率算法大致可以分为四类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。其中_算法用于求解问题的准确解但此解未必正确如素数测试问题，而_算法不会得到不正确的解，但该算法可能找不到问题的解如整数因子分解问题；_算法则常用于求解数值问题的近似解；_算法主要体现在设法消除算法最坏情形下的复杂性余特殊实例之间的关联性，如引入随机方法的快速排序算法。三、应用题。1对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或或，并简述理由。(1) (2) (3) 2请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。3试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。4求生成树和最小耗费生成树：5试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：，对于给定的两个整数和，要求用最少的变换和变换次数将变为。算法设计与分析课程试题三一、选择题1、以下描述正确的是：；、（logn）（n1/2）（n2）（10n）；、（n2 /logn）（n（ logn）2）（n2）（10n）；、算法可分为多项式时间算法和指数时间算法；、如果f(n)cg(n)，则记为f(n)(g(n)。2若f(n)=2n3+3n，g(n)=100n2+2n+100，则f=O(g)为（ B ）。 A 真 B 假 C 无法确定 D均不是3Fibonacci数列第5项为（）。A 3 B 5 C 8 D 134设作业数量，作业长度分别为（1，2，4）（，）。那么将他们放在磁带（）上时，则最佳的放置顺序为：；、，；、，；、，；、，。5下列问题一般不采用分治法的是：；、检索；、选择；、极值； 、15迷。6一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（ ）。A 1个 B 2个 C 6个 D 8个7下列问题中具有多项式解法的是（ ）。A背包问题 B生成排列序列问题 C n个元素的排序问题 D 集合的幂集问题8排列问题属于（ ）。A 可解问题 B不可解问题 C P问题 D NP问题9对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。A、回溯法 B、分支限界法C、回溯法和分支限界法 D、回溯法求解子集树问题1012个金币中有一枚是假币，至少需要称量的次数是（ ）。A 0 B 1 C 3 D 4二、填空1算法的五个重要特性是：_、_、_、_、_。2用贪心方法求解背包问题的约束条件是：_。3设有n个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。如果n=2k，循环赛最少需要进行_天；如果n=2k+1，循环赛最少需要进行_天。其中，k为正整数。4用分支限界法求解0-1背包问题时，对于每个物品j有重量wj和价值vj，考虑当前物品i，已装入背包中物品的重量和价值分别为cw、cv，剩余物品的价值上界为urv，剩余容量为c，目前已有的最优价值为bestp，则当左儿子满足约束条件_属于可行结点时，就将它加入活结点队列中；当右儿子满足上界条件_时才将它加入活结点队列中。5快速排序法的基本思想是重新排列关键字，把一个文件分成两个文件，使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。其算法如下：算法（快速排序是一种递归算法）：Qsort(L,k,m)/L待排序序列，k、m是分类文件之首、末关键字(1,n)Beginif k m thenbeginSplit(L,k,m,i)/将L分组Qsort(L,k,i-1)Qsort(L,i+1,m)endendSplit(L,k,m,i) /将序列L进行分组Begini=k,j=m,x=L(k)while _ dobeginwhile _ do j=j-1if ji then L(i)=L(j),i=i+1while (L(i)x) and (ij) do i=i+1if ij then L(j)=L(i),j=j-1end_End7已知作业队列及其所需要运行的时间为t1=2， t2= 5， t3= 8， t4= 1， t5= 5， t6= 1），在三台处理器上运行，按贪心法调度总运行时间为_，最佳运行时间为_。吉普车总装油量为500L，耗油量为1L/里，要自行设置燃料库穿越1000里的沙漠，使用倒推法首先应共设置_个站点，第一个距离起点_里，存放_L油，总耗油量达到最少，即_L。三、解答题1证明：O(f)+O(g)=O(f+g) 2求下列函数的渐近表达式： 3n2+10n; 21+1/n;3分别用快速分类法、归并分类法把元素序列（3，1，4，1，5，9，6，5，3，5，8，9，7）分类，并分析每种情况下的比较次数。四、编程与求解1、（编程）。做一个“二分”检索程序，它将原集合分成和大小的两个集合，并求出这种算法时间复杂度。2、（求解）用动态规划的方法求解下述背包问题：效益（11，21，31，33，43），重量（1，11，21，23，33），背包可承重量45，5。3、在下列数据上模拟快速排序过程。 （4，5，6，7，8，4）4、有以下7个作业，他们的效益值和期限分别为（p1，p2，p3，p4，p5，p6，p7）（3，5，20，18，1，6，30）和（d1，d2，d3，d4，d5，d6，d7）（1，3，4，3，2，1，2），利用贪心算法求解改作业排序问题的最优解。（写清楚关键步骤）5、试用动态