1算法就是一组有穷的

1算法就是一组有穷的 第一章 绪 论 一 填空 1(算法就是一组有穷的 ， 它们了解决某一特定类型问的 2..算法具备五个重要特性: 、 、 、 、 3. 要制定一个算法，一般要经过 、 、 、 、 等阶段。 4. 算法的复杂性是 的度量，是评价算法优劣的重要依据。 5(一个算法的复杂性的高低体现在运行该算法所需要的 的多少上。 6(计算机的资源，最重要的是 和 资源。因而，算法的复杂性有 和 之分。 7. 算法的时间复杂性函数用T(n)表示，它是 的函数。 8. T(n)中的n对于不同的问题，有不同的表现形式。指出下列问题中n的计量。 1) 在数组中找值为c的分量 ， n表示 2) 两个矩阵相乘 , n表示 3) 一个数表的排序，n表示 4) 遍历一棵二叉树，n表示 9.最坏情况下的时间复杂性定义: 10. 平均情况下的时间复杂性定义: 11.最具有可操作性和实际价值的是 复杂性。教材中没有特殊说明时，T(n)一般指的就是 。 12(f(n)=O(g(n))表示 当且仅当存在正的常数C和N，使得对于所有的n ，有f(n) 。 0 13. 写出下列f(n)的渐进性态: 1) f(n)=C，为常数:f(n)= O( )。 0 2) f(n)= 3n+2:f(n)= O( )。 n3) f(n)= 6×2+n:f(n)= O( )。 4) f(n)= nlog n:f(n)= O( )。 二 算法复杂性 1. 已知不重复且已经按从小到大排好的m个整数的数组A[L(m](为简单起 k见，设m,2，k是一个确定的非负整数)。对于给定的整数c，要求寻找一个下标i，使得A[i]=c,若找不到，则返回一个0。算法如下: procedure search( c) /*c是整型数 */ { i?0; j?l; while A[j]r then 10 for to by-l do 11 ; 12 repeat 13 ;k?k+1 14 endif 15 repeat 16 end JS 二 设计算法 n a,L1(有n 个程序和长度为L的磁带，程序i的长度为a，已知，求最i,i,1i优解(x，x ，...，x，…， x)，x =0，1, x =1，表示程序i存入磁带，x =0，i2iniii n xa,L表示程序i不存入磁带，满足，且存放的程序数目最多。 ,ii,1i 2.有n 个活动争用一个活动室。已知活动i占用的时间区域为[s，f )，活动i,jii相容的条件是:sj?f ，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的iiii活动编号活动，求一个相容的活动子集，且安排的活动数目最多。 第四章 动态规划 一. 填空 1.最优化原理:无论过程的 是什么，其余的决策都必须相对于初始决策所产生的状态 。 2(最优子结构性质: 。 3.子问题重叠性质:每次产生的子问题并不总是 ，有些子问题被 。 4(多段图动态规划算法 procedure FGRAPH(E，k，n，P) 1 real COST(n)，integerD(n一1)，P(k)，r，j，k，n 2 ; 3 for to 1 by,1do 4 设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最小值 5 COST(j)? ; 6 ; 7 repeat 8 P(1)?1; ; 9 for do 10 P(j)?D ( P(j-1) ) 11 repeat 12 end FGRAPH 二(回答问题 1.写出0/1背包问题的递推式，并简述其表述的意义。 2.写出多段图的向后递推式，并简述其表述的意义。 三.解题 1.有一多段图如图所示，按算法4.1的步骤求出最短路经及其代价。 2 5 21 6 4 2 3 1 8 3 2 8 4 1 3 6 10 5 6 2 2 9 7 7 9 4 7 2. 已知有3个物品:(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容积M=20，根据0/1背包动态规划的递推式求出最优解。 第五章 回溯法 一.回答问题 1. 简述 回溯法的基本思路。 2(什么是显约束条件，什么是隐式约束条件, 3(以一棵深度为3的3叉树为例，说明代约束条件的深度优先过程。 高度为n=3，m=3的状态空间树 i 4(说明N皇后的解向量所表示的意义。 5(N皇后算法的过程PLACE(k)的功能。并分析最坏情况下的时间复杂性。 6(说明子集和数问题的回溯法所用的约束条件为什么提高了搜索效率。 二，设计算法 1(写出0/1背包问题的递归形式的回溯算法。 2(写出子集和数的非递归形式的算法。 第6章 分枝-限界法 一. 回答问题 1. 简述FIFO检索和LIFO检索 , 2(代价估值函数 (X)的定义。 c 3(最小代价搜索( LC检索)的基本思想。 4(用最小代价搜索法解9宫问题，代价估值函数是如何选取的, 5(怎样判断LC-找到的答案结点是最小成本的答案节点?为什么, 6(分枝—限界算法的上界函数的作用是什么, 二(根据分枝—限界算法基本过程，求解0/1背包问题。已知，n=3，M=20，(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10)。