算法试卷.doc
8页
算法设计与分析课程试题一一、选择题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回溯法7．Prim算法求最小生成树采用的是（ ）算法思想 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所示的23×23的特殊棋盘，共需要 ____个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况 12345678 + + - + - + ++ - - - - +- + + + -- + + -- + -- -+1 2 3 4 5 6 7 8 图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是一个正整数且c>1，k≥1。
证明在这种情况下贪心算法总能产生最优解给出一个贪心算法不能产生最优解的硬币面值组合 算法设计与分析课程试题二一、选择题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)4．N个盘子的汉诺塔，至少要执行移动操作次数为（ ）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界限函数8．Floyd算法属于（ ）A 贪心算法 B概率算法 C回溯法 D分支限界法9．（ ）算法应用到广度优先遍历策略 A 分支界限法 B 动态规划法 C分治法 D回溯法10．下列算法不是智能算法（ ）A 粒子群 B 枚举法 C模拟退火 D分支限界二、填空1．4n2,logn,3n,20n,2,n2/3,n!按渐近阶从低到高顺序排序： 、 、 、 。
2．一个具有n个圆盘的Hanoi塔，至少移动___________次圆盘才能达到目标状态3．对于问题状态S，由根到S的那条路径确定了这个解空间中的一个元组，那么状态S称为 4．Strassen矩阵乘法可以利用__________算法实现.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)｜≡c｜g(n)｜，则记为f(n)＝Ｏ(g(n))2．若f(n)=2n3+3n，g(n)=100n2+2n+100，则f=O(g)为（ B ） A 真 B 假 C 无法确定 D均不是3．Fibonacci数列第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．对问题的解空间树进行搜索的方法中，一个活结点最多。
