算法设计与分析课程试题一 一、选择题 1．选出不是算法所必须具备的特征（ ）。 A有穷性 B确切性 C高效性 D可行性 2．下列（ ）不是衡量算法的标准。 A 时间效率 B 空间效率 C 问题的难度 D 适应能力 3．与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为（ ）。 n n A x(n)=2B x(n)=2-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-元组（x，x，x，x，﹒﹒﹒，x，x）; 1122nnＢ、回溯法的解必须满足一组综合的约束条件，称为解函数； Ｃ、满足显示约束的所有元组不能确定一个可能的解空间, Ｄ、隐式约束描述了元组中元素x必须彼此相关的情况。 i二、填空 1．算法区别于程序： 。 2．递推公式x(n)=x(n-1)+n,x(0)=0，x(n)= 。 333．．按分治策略求解棋盘覆盖问题时，对于如图1所示的2×2的特殊棋盘，共需要____个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况。 1 2 3 4
5 6 7 8 + + - + - + 1 2 + 3 4 + - - - - + 5 6 - + + + - 7
- + + - - + - 8 - - + 图1 棋盘覆盖 图2
符号三角形 4．对下述五个文件用贪心方法进行最优
归并：文件x，x，x，x和x分别有18，24，8，123456和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分钱，并证明算法能够产生一个最优解。
算法试卷
