习题1
1.
图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现
在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，
图是这条河以及河上的两个岛和七座桥的草
图。请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行
2， 经过七座桥，且每次只经历过一次 3， 回到起点
该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n
2.循环直到r=0 ??m=n ???n=r ??r=m-n 3?输出m
3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。
编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。
#include
int main() {
double value=0;
图 七桥问题
for(int n=1;n<=10000 ;++n)
{
value=value*10+1;
if(value%2013==0)
{
cout<<"n至少为:"< break; } }计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值 #include using namespace std; int main () { double a,b; double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来 第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥 一共用时19小时 9．欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动？为什么？ 设最初两个数较大的为a, 较小的为b ，两个数的最大公约数为factor 。 则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor 个。 如果a/factor 是奇数，就选择先行动；否则就后行动。 习题2 1．如果T 1(n )=O (f (n ))，T 2(n )=O (g (n ))，解答下列问题： （1）证明加法定理：T 1(n )＋T 2(n )=max{O (f (n )), O (g (n ))}； （2）证明乘法定理：T 1(n )×T 2(n )=O (f (n ))×O (g (n ))； （3）举例说明在什么情况下应用加法定理和乘法定理。 ,（1） （2） （3）比如在 for （f(n)） { for(g(n)) } 中应该用乘法定理 如果在“讲两个数组合并成一个数组时”，应当用加法定理 2．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？ （1） 完成的是1-n 的平方和 基本语句：s+=i*i ，执行了n 次 时间复杂度O （n ） （1）int Stery(int n) { int S = 0; for (int i = 1; i <= n; i++) S = S + i * i; return S; } （2）int Q(int n) { if (n == 1) return 1; else return Q(n -1) + 2 * n - 1; } （2） （2）完成的是n 的平方 基本语句：return Q(n -1) + 2 * n – 1，执行了n 次 时间复杂度O （n ） 3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。 （1） 基本语句2*i 基本语句y = y + i * j 执行了2/n 次 一共执行次数=n/2+n/2=O （n ） （2） 基本语句m+=1执行了(n/2)*n=O(n*n) 4. 使用扩展递归技术求解下列递推关系式： （1）?? ?>-==1 )1(314 )(n n T n n T （2） ?? ?>+==1 )(211)(n n n T n n T (1) int T(int n) { if(n==1) return 4; else if(n>1) return 3*T(n-1); } (2) int T(int n) { if(n==1) return 1; else if(n>1) return 2*T(n/3)+n; } 5. 求下列问题的平凡下界，并指出其下界是否紧密。 （1）求数组中的最大元素； （2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的； （4）生成一个具有n 个元素集合的所有子集 (1) Ω(n) 紧密？ (2) Ω(n*n) （1）for (i = 1; i <= n; i++) if (2*i <= n) for (j = 2*i; j <= n; j++) y = y + i * j ； （2）m = 0; for (i = 1; i <= n; i++) for (j = 1; j <= 2*i; j++) m=m+1; (3)Ω(logn+n)（先进行快排，然后进行比较查找） (4)Ω(2^n) 7．画出在三个数a, b, c中求中值问题的判定树。 8．国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，……，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢？ #include using namespace std; int main() { long double result=1; double j=1; for(int i=1;i<=64;++i) { j=j*2; result+=j; j++; } cout< return 0; } 习题3 1．假设在文本"ababcabccabccacbab"中查找模式"abccac"，写出分别采用BF算法和KMP 算法的串匹配过 式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。 #include using namespace std; int main() { int n;数字游戏。把数字1,2,…,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中（即排除运算式中一位数为1的平凡情形）。 ??×?＋???÷?－?? = 0 5. 设计算法求解a n mod m，其中a、n和m均为大于1的整数。（提示：为了避免a n 超出int型的表示范围，应该每做一次乘法之后对n取模） #include using namespace std; int square(int x) { return x*x; } 设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。 7.设计算法，在数组r[n]中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include using namespace std; void deletere(int a[],int N) { int b[100]={0}; int i,k; k=0; static int j=0; for(i=0;i b[a[i]]++; for(i=0;i<100;i++) { if(b[i]!=0) { if(b[i]==2) { k++; } a[j]=i; j++; } } for(i=0;i cout< } int main() { int a[]={1,2,1,3,2,4}; deletere(a,6); return 0; } 设表A={a1, a2, …, a n}，将A拆成B和C两个表，使A中值大于等于0的元素存入表 B ，值小于0的元素存入表 C ，要求表B 和C 不另外设置存储空间而利用表A 的空间。 荷兰国旗问题。要求重新排列一个由字符R , W , B （R 代表红色，W 代表白色，B 代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R 都排在最前面，W 排在其次，B 排在最后。为荷兰国旗问题设计一个算法，其时间性能是O (n )。 设最近对问题以k 维空间的形式出现，k 维空间的两个点p 1=(x 1, x 2, …, x k )和p 2=(y 1, y 2, …, y k )的欧几里德距离定义为：∑== k i i i -x y p p d 1 2 21) (),(。对k 维空间的最近对问题设计 蛮力算法，并分析其时间性能。 11．设计蛮力算法求解小规模的线性规划问题。假设约束条件为：（1）x +y ≤4；（2）x +3y ≤6；（3）x ≥0且y ≥0；使目标函数3x +5y 取得极大值。 #include int main() { int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0<=4;++x0) { for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0) temp=3*x0+5*y0; if(temp>=summax) { summax=temp; x=x0;1.1.11.1.2变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变位词。例如，eat 和tea 是变位词。 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O (n )。 O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知，时间复杂度可达到O(n); 3.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。 不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。 4. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。 归并排序： 第一趟：（5,3）（1,9）； 第二趟：（3,5,1,9）； 第三趟：（1,3,5,9）； 快速排序： 第一趟：5（,3,1,9）；设计分治算法求一个数组中的最大元素，并分析时间性能。 设计分治算法，实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。 设计递归算法生成n个元素的所有排列对象。 #include using namespace std; int data[100]; 设计分治算法求解一维空间上n个点的最近对问题。 参见4.4.1最近对问题的算法分析及算法实现 9. 在有序序列(r1, r2, …, r n)中，存在序号i（1≤i≤n），使得r i=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。 设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。 12. 设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，使得| S1|=| S2|=n/2，且两个子集元素之和的差达到最大。 设a1, a2,…, a n是集合{1, 2, …, n}的一个排列，如果i 循环赛日程安排问题。设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次。 采用分治方法。 将2^k选手分为2^k-1两组，采用递归方法，继续进行分组，直到只剩下2个选手时，然后进行比赛，回溯就可以指定比赛日程表了 15. 格雷码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为23的格雷码为(000, 001, 011, 010, 110, 111, 101, 100)。设计分治算法对任意的n值构造相应的格雷码。 矩阵乘法。两个n×n的矩阵X和Y的乘积得到另外一个n×n的矩阵Z，且Z ij 满足（1≤i, j≤n），这个公式给出了运行时间为O(n3)的算法。可以用分 治法解决矩阵乘法问题，将矩阵X和Y都划分成四个n/2×n/2的子块，从而X和Y的乘积可以用这些子块进行表达，即 从而得到分治算法：先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、CF、DH，然后再花费O(n2)的时间完成加法运算即可。请设计分治算法实现矩阵乘法，并分析时间性能。能否再改进这个分治算法？ 习题5 1.下面这个折半查找算法正确吗？如果正确，请给出算法的正确性证明，如果不正确，请 说明产生错误的原因。 int BinSearch(int r[ ], int n, int k) { int low = 0, high = n - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (k < r[mid]) high = mid; else if (k > r[mid]) low = mid; else return mid; } return 0; } 错误。 正确算法： int BinSearch1(int r[ ], int n, int k) { int low = 0, high = n - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (k < r[mid]) high = mid - 1; else if (k > r[mid]) low = mid + 1; else return mid; } return 0; } 2.请写出折半查找的递归算法，并分析时间性能。 求两个正整数m和n的最小公倍数。（提示：m和n的最小公倍数lcm(m, n)与m和n 的最大公约数gcd(m, n)之间有如下关系：lcm(m, n)=m×n/gcd(m, n)） 插入法调整堆。已知（k1, k2, …, k n）是堆，设计算法将（k1, k2, …, k n, k n+1）调整为堆（假设调整为大根堆）。 参照： void SiftHeap(int r[ ], int k, int n) { int i, j, temp; i = k; j = 2 * i + 1; 设计算法实现在大根堆中删除一个元素，要求算法的时间复杂性为O(log2n)。 计算两个正整数n和m的乘积有一个很有名的算法称Array为俄式乘法，其思想是利用了一个规模是n的解和一个规 模是n/2的解之间的关系：n×m＝n/2×2m（当n是偶数） 或：n×m＝(n-1)/2×2m＋m（当n是奇数），并以1×m＝ m作为算法结束的条件。例如，图给出了利用俄式乘法计 算50×65的例子。据说十九世纪的俄国农夫使用该算法并 因此得名，这个算法也使得乘法的硬件实现速度非常快， 因为只使用移位就可以完成二进制数的折半和加倍。请设 计算法实现俄式乘法。 拿子游戏。考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有n根火柴，两个玩家轮流拿走1，2，3或4根火柴，拿走最后一根火柴的玩家为获胜方。请为先走的玩家设计一个制胜的策略（如果该策略存在）。 如果桌上有小于4根的火柴，先手必胜，如果是5根，先手必输；依次类推，同理15、20、25…….都是必输状态；所有每次把对手逼到15、20、25…….等必输状态，就可以获胜。 9. 竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛的n个选手，每个内部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的根结点就代表了淘汰赛的冠军。请回答下列问题： （1）这一系列的淘汰赛中比赛的总场数是多少？ （2）设计一个高效的算法，它能够利用比赛中产生的信息确定亚军。 （1）因为n人进行淘汰赛，要淘汰n-1人，所有要进行n-1场比赛。 （2） 10. 在120枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，最坏情况下，能不能只比较5次就检测出这枚假币？ 将120枚平均分为三组，记为：A，B，C；先将A,B比较，如果A,B重量不同（假如B比A重），再将B与C比较，如果B，C相同，则A有假币；如果B,C不同，再将A,C比较， 如果A,C相同，则B有假币；如果A,C不同，则B有假币；如果A,B相同，则C有假币； 习题6 1.动态规划法为什么都需要填表？如何设计表格的结构？ 在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构； 设计表格，以自底向上的方式计算各个子问题的解并填表。 2. 对于图所示多段图，用动态规划法求从顶点0到顶点12的最短路径，写出求解过程。 图第2题图 将该多段图分为四段； 首先求解初始子问题，可直接获得： d(0, 1)=c01＝5(0→1) d(0, 2)=c02＝3(0→1) 再求解下一个阶段的子问题，有： d(0,3)= d(0, 1)+ c13 =6(1→3) d(0,4)=min{d(0,1)+ c14 ,d(0,2)+ c24}=8(1→4) 。。。。。。。。（以此类推） 最短路径为：0→1→3→8→11→12 3．用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为(3, 2, 1, 4,5)，价值分别为(25, 20, 15, 40, 50)，背包容量为6。写出求解过程。 (x1, x2,x3,x4,x5) →(1,1,1,0,0)(过程略) 4. 用动态规划法求两个字符串A="xzyzzyx"和B="zxyyzxz"的最长公共子序列。写出求解过程。 略 5. 给定模式"grammer"和文本"grameer"，写出动态规划法求解K-近似匹配的过程。 略 6. 对于最优二叉查找树的动态规划算法，设计一个线性时间算法，从二维表R中生成 最优二叉查找树。 7. Ackermann 函数A (m , n )的递归定义如下： ?? ? ?? >>--=>-=+=0 ,0))1,(,1(0,0) 1,1(01),(n m n m A m A n m m A m n n m A 设计动态规划算法计算A (m , n )，要求算法的空间复杂性为O (m )。 考虑下面的货币兑付问题：在面值为(v 1, v 2, …, v n )的n 种货币中，需要支付y 值的货币，应如何支付才能使货币支付的张数最少，即满足 y v x n i i i =∑=1 ，且使∑=n i i x 1 最小（x i 是非负整 数）。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。 #include int a[N][M]; int value[M]; using namespace std; int main() { while(true) { int i,j,k; int x,y,z; cout<<"输入货币种类的个数："< cout<<"从小到大输入货币的价值，其中第一个必须为一："< for(i=1;i<=x;i++)多边形游戏。多边形游戏是一个单人玩的游戏，开始时有一个由n 个顶点构成的多边形，每个顶点具有一个整数值，每条边具有一个运算符“＋”或“×”。游戏规则是每次选择一条边e 以及和e 相关联的两个顶点i 和j ，用一个新的顶点k 取代边e 、顶点i 和j ，顶点k 的整数值是顶点i 和j 的整数值通过边e 上的运算符计算得到的结果。当所有边都删除时，游戏结束，游戏的得分就是所剩顶点的整数值。设计动态规划算法，对于给定的多边形计算最高得分。 习题2-1 求下列函数的渐进表达式： 3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。 解答：3n^2+10n=O(n^2), n^2/10+2^n=O(2^n), 21+1/n=O(1), logn^3=O(logn), 10log3^n=O(n). 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。 解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2 习题2-4 (1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？ (2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？ (3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？ 解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6 (2)n1^2=64n^2得到n1=8n (3)由于T（n)=常数，因此算法可解任意规模的问题。 习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：n'=100n n'^2=100n^2得到n'=10n n'^3=100n^3得到n'=4.64n n'!=100n!得到n' 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题 #include 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 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. 回溯法解TSP问题时的解空间树是（ 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、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 一、选择题（多选） 1.算法必须满足哪些条件？ 算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足条件： (1)输入：有零个或多个由外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 2.哪些问题比较适合用递归算法？ 阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的递归算法）：（1）二分搜索技术、（2）大整数的乘法、（3）Strassen 矩阵乘法、（4）棋盘覆盖、（5）合并排序、（6）快速排序、（7）线性时间选择、（8）最接近点对问题、（9）循环赛日程表 3. 哪些问题比较适合用贪心算法？ （1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）单源最短路径（5）最小生成树（6）多机调度问题 4. 哪些问题比较适合用回溯法？ （1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题 二、概念题 1.递归的概念是什么？ 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。2.什么是0-1背包问题？ 给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。该问题被称为0-1背包问题。 3.什么是哈夫曼编码，它有什么优缺点？ 由哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼编码是广泛地用于数据文件压缩。用于数据的无损耗压缩。其压缩率通常在20%～90%之间。 优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。 4.什么是图的m着色问题？ 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2的顶点着有不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 5.什么是单源最短路径问题？ 《算法设计与分析》课程实验与设计 福州大学王晓东 第1章算法引论 算法实现题1-1 统计数字问题 算法实现题1-2 字典序问题 算法实现题1-3 最多约数问题 算法实现题1-4 金币阵列问题 算法实现题1-5 最大间隙问题 第2章递归与分治策略 算法实现题2-1 输油管道问题 算法实现题2-2 众数问题 算法实现题2-3 邮局选址问题 算法实现题2-4 马的Hamilton周游路线问题 算法实现题2-5 半数集问题 算法实现题2-6 半数单集问题 算法实现题2-7 士兵站队问题 算法实现题2-8 有重复元素的排列问题 算法实现题2-9 排列的字典序问题 算法实现题2-10 集合划分问题 算法实现题2-11 集合划分问题2 算法实现题2-12 双色Hanoi塔问题 算法实现题2-13 标准2维表问题 算法实现题2-14 整数因子分解问题 算法实现题2-15 有向直线2中值问题 第3章动态规划 算法实现题3-1 独立任务最优调度问题 算法实现题3-2 最少硬币问题 算法实现题3-3 序关系计数问题 算法实现题3-4 多重幂计数问题 算法实现题3-5 编辑距离问题 算法实现题3-6 石子合并问题 算法实现题3-7 数字三角形问题 算法实现题3-8 乘法表问题 算法实现题3-9 租用游艇问题 算法实现题3-10 汽车加油行驶问题 算法实现题3-11 圈乘运算问题 算法实现题3-12 最少费用购物 算法实现题3-13 最大长方体问题 算法实现题3-14 正则表达式匹配问题 算法实现题3-15 双调旅行售货员问题 算法实现题3-16 最大k乘积问题 算法实现题3-17 最小m段和问题 算法实现题3-18 红黑树的红色内结点问题 第4章贪心算法 算法实现题4-1 会场安排问题 算法实现题4-2 最优合并问题 算法实现题4-3 磁带最优存储问题 算法实现题4-4 磁盘文件最优存储问题 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析王晓东
《计算机算法设计与分析》习题及答案
算法设计与分析考试题及答案
算法设计与分析试卷A及答案
算法设计与分析课后部分习题答案
算法设计与分析考试题及答案
算法设计与分析课程设计(完整版)
算法设计与分析试卷及答案
算法设计与分析试卷(2010)
算法设计与分析第2版王红梅胡明习题答案
算法设计与分析试卷及答案
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
算法设计与分析复习题
《算法设计与分析》课程实验与设计 福州大学 王晓东
算法设计与分析习题解答
算法设计与分析试题与答案
相关主题
文本预览