void main(){

char a[4]={a,b,c,a}; perm(a,0,3); }

//集合划分问题2-7

思路：对于n个元素的集合，可以划分成由m(1=m=n)个子集构成的子集，如 {{1}，{2}，{3}，{4}}就是由4个子集构成的非空子集。假设f(n,m)表示将n个元素的集合划分成由m个子集构成的集合的个数，那么可以这样来看： 1)若m==1，则f(n,m)=1; 2)若n==m，则f(n,m)=1;

3)若非以上两种情况，f(n,m)可以由下面两种情况构成

a.向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；

b.向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。

??m??1||n??m??1f(n,m)????f?n?1,m?1??m*f?n?1,m??m?nm!?1?

//参考代码

#includestdio.h int f(int n,int m) {

if(m==1||n==m) return 1; else

return f(n-1,m-1)+f(n-1,m)*m; }

int main(void) {

int n;

while(scanf(%d,n)==1n=1) //按ctrl+break退出程序 {

int i;

int sum=0;

for(i=1;i=n;i++) {

sum+=f(n,i); }

printf(%d\\n,sum); }

return 0; }

【篇三：2013《计算机算法设计与分析》习题及答案】

ass=txt>2013 秋

《计算机算法设计与分析》习题及答案 一．选择题

1、二分搜索算法是利用（ a ）实现的算法。

a、分治策略 b、动态规划法c、贪心法 d、回溯法 2、下列不是动态规划算法基本步骤的是（ a ）。

a、找出最优解的性质b、构造最优解 c、算出最优解 d、定义最优解

3、最大效益优先是（ a ）的一搜索方式。

a、分支界限法b、动态规划法 c、贪心法 d、回溯法 4、在下列算法中有时找不到问题解的是（ b ）。

a、蒙特卡罗算法b、拉斯维加斯算法c、舍伍德算法d、数值概率算法

5. 回溯法解旅行售货员问题时的解空间树是（ a ）。

a、子集树 b、排列树 c、深度优先生成树 d、广度优先生成树 6．下列算法中通常以自底向上的方式求解最优解的是（ b ）。 a、备忘录法 b、动态规划法 c、贪心法 d、回溯法 7、衡量一个算法好坏的标准是（ c ）。

a 运行速度快 b 占用空间少 c 时间复杂度低 d 代码短 8、以下不可以使用分治法求解的是（ d ）。

a 棋盘覆盖问题 b 选择问题 c 归并排序 d 0/1背包问题 9. 实现循环赛日程表利用的算法是（ a ）。

a、分治策略b、动态规划法 c、贪心法 d、回溯法

10、下列随机算法中运行时有时候成功有时候失败的是（ c ） a 数值概率算法 b 舍伍德算法 c 拉斯维加斯算法 d 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ d ）。

a、广度优先 b、最小耗费优先 c、最大效益优先d、深度优先

12．下列算法中通常以深度优先方式系统搜索问题解的是（ d ）。 a、备忘录法b、动态规划法 c、贪心法 d、回溯法 13.备忘录方法是那种算法的变形。（ b ）

a、分治法 b、动态规划法 c、贪心法 d、回溯法

14．哈夫曼编码的贪心算法所需的计算时间为（ b ）。 a、o（n2n）b、o（nlogn） c、o（2n） d、o（n）

15．分支限界法解最大团问题时，活结点表的组织形式是（ b ）。 a、最小堆b、最大堆 c、栈 d、数组

16．最长公共子序列算法利用的算法是（ b ）。

a、分支界限法 b、动态规划法 c、贪心法 d、回溯法 17．实现棋盘覆盖算法利用的算法是（ a ）。 a、分治法 b、动态规划法 c、贪心法 d、回溯法 18.下面是贪心算法的基本要素的是（ c ）。

a、重叠子问题 b、构造最优解c、贪心选择性质d、定义最优解 19.回溯法的效率不依赖于下列哪些因素（ d ） a.满足显约束的值的个数b. 计算约束函数的时间 c.计算限界函数的时间 d. 确定解空间的时间 ）

a．递归函数 b.剪枝函数 c。随机数函数 d.搜索函数 21、下面关于np问题说法正确的是（ b ）

a np问题都是不可能解决的问题b p类问题包含在np类问题中 c np完全问题是p类问题的子集d np类问题包含在p类问题中 22、蒙特卡罗算法是（ b ）的一种。

a、分支界限算法b、概率算法 c、贪心算法 d、回溯算法 23.下列哪一种算法不是随机化算法（ c ）

a. 蒙特卡罗算法 b.拉斯维加斯算法 c.动态规划算法 d.舍伍德算法 24. （ d ）是贪心算法与动态规划算法的共同点。

a、重叠子问题 b、构造最优解 c、贪心选择性质 d、最优子结构性质

25. 矩阵连乘问题的算法可由（ b ）设计实现。

a、分支界限算法 b、动态规划算法 c、贪心算法 d、回溯算法 26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ a ）。

a、最小堆 b、最大堆 c、栈 d、数组

27、strassen矩阵乘法是利用（ a ）实现的算法。 a、分治策略 b、动态规划法 c、贪心法 d、回溯法 29、使用分治法求解不需要满足的条件是（ a ）。 a 子问题必须是一样的b 子问题不能够重复

c 子问题的解可以合并d 原问题和子问题使用相同的方法解 30、下面问题（ b ）不能使用贪心法解决。

a 单源最短路径问题b n皇后问题 c 最小生成树问题 d 背包问题 31、下列算法中不能解决0/1背包问题的是（ a ） a 贪心法 b 动态规划 c 回溯法 d 分支限界法

32、回溯法搜索状态空间树是按照（ c ）的顺序。

a 中序遍历 b 广度优先遍历 c 深度优先遍历 d 层次优先遍历 33、下列随机算法中运行时有时候成功有时候失败的是（ c ） a 数值概率算法 b 舍伍德算法 c 拉斯维加斯算法 d 蒙特卡罗算法 34．实现合并排序利用的算法是（ a ）。

a、分治策略b、动态规划法c、贪心法d、回溯法 35．下列是动态规划算法基本要素的是（ d ）。

a、定义最优解 b、构造最优解 c、算出最优解 d、子问题重叠性质

36．下列算法中通常以自底向下的方式求解最优解的是（ b）。 a、分治法 b、动态规划法 c、贪心法 d、回溯法 37．采用广度优先策略搜索的算法是（ a ）。

a、分支界限法b、动态规划法c、贪心法 d、回溯法 38、合并排序算法是利用（ a ）实现的算法。 a、分治策略b、动态规划法c、贪心法d、回溯法 39、在下列算法中得到的解未必正确的是（ b ）。

a、蒙特卡罗算法b、拉斯维加斯算法c、舍伍德算法d、数值概率算法

40、背包问题的贪心算法所需的计算时间为（b）

a、o（n2n） b、o（nlogn） c、o（2n） d、o（n） 41．实现大整数的乘法是利用的算法（ c ）。

a、贪心法b、动态规划法 c、分治策略 d、回溯法

42．0-1背包问题的回溯算法所需的计算时间为（ a ） na、o（n2） b、o（nlogn） c、o（2n） d、o（n） 43．采用最大效益优先搜索方式的算法是（ a ）。

a、分支界限法 b、动态规划法 c、贪心法 d、回溯法 44．贪心算法与动态规划算法的主要区别是（ b ）。

a、最优子结构b、贪心选择性质 c、构造最优解 d、定义最优解 45. 实现最大子段和利用的算法是（ b ）。

a、分治策略 b、动态规划法 c、贪心法 d、回溯法