资源描述
、简答题(1题4分，2题4分，3题6分，共14分)1 什么是算法？什么是程序？。2算法的特点是什么？3给出算法复杂度计量符号0和的定义。二、算法复杂度计算(10分)已知某算法耗时为t m),且满足如下递归方程T(n) 0(1)n 12T(n/2) O(n) n1试计算该算法的时间复杂度T (n)o三、对于分治法，试解答：(1、2题各5分，3题8分，共18分)1 分治法的基本思想什么？2试给出分治法的一般算法设计模式，用伪代码描述或详述解题步骤。3设n个不同的整数排好序后存于T0.n-1中。若存在一个下标i, 0Wi0, wi0, vi0,求n元(M向量(x1,x2,，xn),使得n目标函数 max ViXi约束条件/ 1nWiXic,/ 1用动态规划方法可以求解0-1背包问题x,请回答下列问题：/0,1,1/ n(1) 证明该问题具有最优子结构性质；设 m(i,j)为背包容量为j,可选择物品为i+时0/背包问题的最优解，给出计算m(i, j)的递归式。五、对于贪心算法，试解答：(1题3分,1 贪心选择性质是什么？2题10分，共13分)2 程序存储问题:设有n个程序1,2,.,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li,1ino编程任务：对于给定的n个程序存放在磁带上的长度，编写算法计算磁带上最多可以存储的程序数。六、对于回溯和分支限界法，试解答：(1题5分，2题2分，3题6分，4题12分，共25分)1 试述回溯法的基本思想。2写出回溯法的两种解空间树。3常见的分支限界法有几种？它们的区别是什么？4假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量 M = 150:使用回溯方法求解此背包问题请写出状态空间搜索树。物品ABCDEFG35306050401025价值10403050354030、简答题(1题4分，2题4分，3题6分，共14分)1 算法是指解决问题的一种方法或一个过程。【2分】程序是算法用某种程序设计语言的具体实现【2分】2算法的特点：(1) 确定性：算法的每一种运算必须有确切的定义，无二义性。【1分】(2) 有限性：算法中每条指令的执行次数、每条指令的执行时间都是有限的。H分】(3) 输入：有0个或者多个输入。【1分】(4) 输出：有1个或者多个输出。【1分】3算法复杂度计量符号 0和的定义：(1) QgS) = f(n) |存在正常数 咏 门0使得对所有n门0有：0) cg(n)，记为 )=O(g(n),或说 R/7)的阶不高于gS)的阶当n 时。【3分】(2) (g(n) = f(n)存在正常数咏nO使得对所有门nO有：0 cg(n)A/Q为 “)=9(门)，或说R门)的阶不低于gS)的阶当 n 时。3分】二、算法复杂度计算(10分)原式等价于T(n)=2T(n/2)+n2 2 2递推得:2T(n/2)=2(2T(n/2 )+n/2)=2 T(n/2 )+nT(n)= T(n/2+2n又有:2 T(n/2 )=2 T(n/2 )+n22平n/2)羊3n【2分】故 T(n)= 23T(n)=2T(n/2k)+kn【4分】令k=logn,即riV刃得：T(n)=nT(1)+nlogn=O(nlogn) 4分三、对于分治法，试解答：(1、2题各5分3题8分，共18分)1 分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题然后将各子问题的解合并得到原问题的 解。【5分】2分治法的一般算法设计模式(伪代码描述)divide-and-conquer(P)if (| P | = no) adhoc(P);divide P into smaller subinstances Pi, P2,Pk; 【2分】tor (i=1,i=k, i+)yi=divide-and-conquer (Pi);return merge(yiyk);【3分】 3. templateint Search(Type aQJnt n)Int 1=0; int r=n-1;while (r = l)int m = (l+r)/2;if (m = = am) return m;if (m am) r = m-1; else I = m+1;return -1;【5分】四、对于动态规划算法，试解答：(1题4分，2题6分，3题10分，共20分)1 动态规划算法的两个基本要素：最优子结构性质、子问题的重叠性质【2分】问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。【2分】递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。【2分】2.动态规划基本步骤：(D找出最优解的性质，并刻画其结构特征。(2) 递归地定义最优值。(3) 以自底向上的方式计算最优值。(4) 根据计算最优值时得到的信息，构造最优解。【4分】3.(1)设(y1, y2,，yn)是所给(M背包问题的一个最优解，贝lj(y2,，yn)是下面对应问题 的最优解nmax wxii 2WiXi C W1X1,i 2Xi 0,1,2n否则，设(z2, _zn)是最优解，贝IJ(y1,z2,原问题的更优解，而(y1, y2, yn)不是最优解。矛盾证毕。【5分】maxm(i 1, j), m(i m(i 1,j)【5分】1, j - wi) vi j w i0 j wi五、对于贪心算法，试解答：(1题3分，2题10分，共13分)1 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。【3分】2. int store(int xQJnt n, int I)X为程序长度数组，n为要存储的程序个数，I为磁带长度；int i=0; sum=O ;sort(xQ.n) /先对程序长度数组排序，结果存在x中【3分】while(in)sum=sum+xi;if(sum=l) i+; 2分】elsereturn i; 只存储前i个最短的【3分】/whilereturn n;/所有的程序都能存储【2分】评分说明：算法不一定要求完全相同，只要思路正确，可以酌情给分。六、对于回溯和分支限界法，试解答：(1题5分，2题2分，3题6分，4题12 分，共25分)回溯法的基本思想是：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函【5分】数的深度优先生成法称为回溯法。2回溯法的两种解空间树：子集树和排列树【2分】3常见的两种分支限界法：队列式(FIFO)分支限界法-将活结点表组织成一个队列，按照先 进先出(FIFO)原则选取下一个结点为扩展结点；优先队列式分支限界法-将活结点表组织 成一个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。【6分】105 CM,4,0,弓,0)4解：按照单位效益从大到小依次排列这 7个物品为：FBGDECA.将它们的序号分别记 为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求 得：40407 ,0,0)305035 150 115404040305030 1501157 ,0)60190.6258177.5 (U.1,1,0,12c. 40403050 10d 40303530 150167.560-4)4040175503530 150 13060f 4040170.7150351015013035g. 4040 50 30160(1,1,0,1,0,1,0)h. 40403530 10 150 140倔加叫异i. 403050j. 403050125167.5 (1,0J,1,1,60 12,0)3530 150 145157.5 (oj.i.u1235 15601，o)X1xi 0XsX6X7X3X2X2xjX4 0XsX5在Ch处获得该问题的最优解为(1,1,1,1,0,0,1),背包效益为 170。F、B、G、D、A时达到最大效益,为170,重量为150。即在背包中装入物品【12分】、简答题（1题4分，2题5分，3题6分，共15分）1 什么是算法？什么是程序？2算法的特点是什么？3给出算法复杂度计量符号0和的定义。二、对于分治法，试解答：（1、2题各10分，共20分）1. 给出利用分治策略的二分搜索技术的算法。2对数组A=13, 27, 31, 1. 26, 23, 4,用无递归的合并排序法将其排成递增序。（给出解题过程）。三、对于动态规划算法，试解答：（1、2题各6分，3题10分，共22分）1 动态规划算法的两个基本要素，每个要素的含义是什么？2. 写出动态规划算法解题的基本步骤。3写出流水作业调度问题的Johnson不等式。用语言描述流水作业调度问题的Johnson算法。四、对于贪心算法，试解答：（1题3分，2题6分，3题11分共20分）1 贪心选择性质是什么？2背包问题与0-1背包问题的不同点是什么?用贪心算法解背包问题的贪心策略是什么？3写出用贪心算法解背包问题的基本步骤和具体算法。五、对于回溯和分支限界法，试解答：（1题2分，2题10分，共12分）1写出回溯法的两种解空间树。2写出用回溯法搜索两种解空间树的算法框架。六、对于分支限界法，试解答：（1题5分，2题6分，共11分）1 常见的分支限界法有几种？它们的区别是什么？2给出图示4个城市旅行售货员问题分支限界法求解，要求使用优先队列式解法，给出搜索过程和所有最优解。543 20 4 4个城市旅行售货员问颍、简答题(1题4分，2题5分，3题6分，共15分)1 算法是指解决问题的一种方法或一个过程。【2分】程序是算法用某种程序设计语言的具体实现【2分】2算法的特点：(1) 确定性：算法的每一种运算必须有确切的定义，无二义性。【1分】(2) 可行性：算法所描述的每一步必须是基本的、有意义的；而是算法执行的结果要能达到预期的目的。【1分】(3) 有穷性：一个算法必须在执行有穷步之后终止，即必须在有限的时间内完成。1分】(4) 输入：有0个或者多个输入。【1分】(5) 输出：有1个或者多个输出。【1分】3算法复杂度计量符号O和的定义： O(gS)=：)|存在正常数cW门0使得对所有门门0有：0 cg(n),记为)=O(g(n),或说 R/?)的阶不高于gS)的阶当 n 时。【3分】(2) 9(门)二 ) |存在正常数曲no使得对所有门门0有：0 cg(n)为 “)=(gS),或说R门)的阶不低于g(c)的阶当 n 时。3分】二、对于分治法，试解答：(1、2题各10分，共20分)1 二分搜索算法：设给定已按升序排好序的n个元素aO:n-1,现要在这n个元素中找出一特定元素xotemplateint BinarySearch(Type aQ, const Type& x, int I, int r)while (r = l)int m = (l+r)/2;if (x = am) return m;if (x minbj,ai.则称作业i和j满足Johnson不等式。【4分】 流水作业调度问题的Johnson算法：令 A/i / | a, b,N2/1 a/ b; 2分将Ni中作业依a的非减序排序;将N2中作业依bi的非增序排【2分】(3)Ni中作业接N2中作业构成满足Johnson法则的最优调度。2分】四、对于贪心算法，试解答：(1题3分，2题6分，3题11分共20分)1 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。【3分】2背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，【3分】用贪心算法解背包问题的贪心策略：将物品单位重量的价值排序，将尽可能多的单位重量价值高的物品装入背包。【3分】3贪心算法解背包问题的基本步骤：【5分】(1) 计算每种物品单位重量的价值vi/wi(2) 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。(3) 若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。(4) 依此策略一直地进行下去，直到背包装满为止。具体算法：【6分】void Knapsack(int n.float M,float v.float w,float x)Sort(n,v,w);int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (in) output(x);elsefor (int i=0;in) output(x);elsefor (int i=t;i=n;i+) swap(xt, xi);if (legal(t) backtrack(t+1);swap(xt, xi);六、对于分支限界法，试解答：（1题5分，2题6分，共11分）常见的两种分支限界法：队列式（FIFO）分支限界法-将活结点表组织成一个队列，按照先 进先出（FIFO）原则选取下一个结点为扩展结点；优先队列式分支限界法-将活结点表组织 成一个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。【5分】 2.优先队列搜索过程用极小堆实现。D,E插入堆中，E为堆顶。E为T, I插入堆，H为堆顶。扩展H后J.得到另一个解(1. 4, 2, 3, 1) (6分)优先级为结点的当前费用。开始从结点B和空堆开始c C, 下一个扩展结点，J, K插入堆中，堆顶为D.扩展D, I 得到一个解(X 3, 2, 4, 1),费用为25O下一步扩展 费用也为25 (2分)。继续直到队列为空，没有更好的解、简答题(1题4分，2题4分，3题6分，共14分)1 算法的特点是什么？2给出算法渐进复杂性的定义。3给出算法复杂度计量符号0和的定义。二、算法复杂度计算(10分)已知某算法耗时为T (n),且满足如下递归方程T(n) 0(1)n 04T(n 1)0(1) n 0试计算该算法的时间复杂度T (n)o三、对于分治法，试解答：(1题5分，2题8分，共13分)1 试给出分治法的一般算法设计模式，用伪代码描述或详述解题步骤。2设n个不同的整数排好序后存于T0.n-1中。若存在一个下标i, 0Wi0, wi0, vi0,求n元0-1向量(x1, x2,，xn),使得目标函数max ViXii 1约束条件nWiXiG/ 1Xi 0,1,1/用动态规划方法可以求解0-1背包问题.伍明该问题具有最优子结构性质。五、对于贪心算法，试解答：(1题6分，2题10分，共16分)1. 写出贪心算法的两个重要性质及其定义。2. 程序存储问题:设有 n个程序1,2,，n要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li,1ino编程任务：对于给定的n个程序存放在磁带上的长度，编写算法计算磁带上最多可以存储的程序数。六、对于回溯和分支限界法，试解答：（1题6分，2题6分，3题10分，共22分）1写出用回溯法搜索子集树和排列树的算法框架。2常见的分支限界法有几种？它们的区别是什么？3给出图示 4个城市旅行售货员问题分支限界法求解，要求使用优先队列式解法，画出解空间树，写出搜索过 程和所有最优解。假设第1个城市为出发城市，优先级为结点的当前费用。凶255,043 20 44个城市旅行售货员问题、简答题(1题4分，2题4分 3题6分，共14分) 1 算法的特点：(1) 确定性：算法的每一种运算必须有确切的定义，无二义性。【1分】(2) 有限性：算法中每条指令的执行次数、每条指令的执行时间都是有限的。H分】(3) 输入：有0个或者多个输入。【1分】(4) 输出：有1个或者多个输出。【1分】2算法的渐近复杂性：对于 T(n),如果存在t(n),当n 时，仃(n)-t(n)/T(n) 0,称t(n) 是T(n)的渐近性态，或为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n) 略去低阶项留下的主项。【4分】3 算法复杂度计量符号O和的定义：n 门0有：0 f(n) cg(n)，记为时。【3分】门0有：0 cg(ri)彳”弓为f(n)时。【3分】(D o(gS)二心)|存在正常数 咖 门o使得对所有 二O(g(/7),或说 4门)的阶不高于g()的阶当 n(2)9(门)= “) |存在正常数讶QnO使得对所有门二 9S),或说4门)的阶不低于gS)的阶当n二、算法复杂度计算(10分)原式等价于T(k)=4T(k-1)+12递推得:4T(k-1)=4(4T(k-2)+1)=4 T(k-2)+42T(k)= 4 T(k-2)+4 +1又有:4 T(k-2)=4 T(k-3)+4【5分】2n(k-3)+4 +4+12故 T(k)=4砒=%)+43+4+仁0(；)【5分】三、对于分治法，试解答：(1题5分，2题8分，共13分)分治法的一般算法设计模式(伪代码描述)divide-and-conquer(P)if (| P | = no) adhoc(P);divide P into smaller subinstances Pi, P2,，Pk;【2分】for (i=1,i=k, i+)yi=divide-and-conquer (Pi);return merge(yi,，yk);【3分】2. templateint Search(Type aQJnt n)Int l=0; int r=n-1;while (r = l)int m = (l+r)/2;if (m = = am) return m;if (m am) r =; else I = m+1;return -1;【8分】 四、对于动态规划算法，试解答：(1题4分，2题6分，3题10分，4题5分, 共25分)1动态规划基本步骤：(1) 找出最优解的性质，并刻画其结构特征。(2) 递归地定义最优值。(3) 以自底向上的方式计算最优值。(4) 根据计算最优值时得到的信息，构造最优解。【4分】2最长公共子序列问题的最优子结构性质：设序列X=x1,x2.,xm和丫二y1,y2,yn的最长公共子序列为Z二0,z2,zk,则 若xm=yn,则zk=xm=yn,且zk堤和yn-4的最长公共子序列。(2) 若xmHyn且zkHxm,则Z是xm-1和丫的最长公共子序列。(3) 若xmHyn且zkHyn,则Z是X和yn1的最长公共子序列。【6分】3求解矩阵为：凶-1h3410150330405203603303018040【4分】【4分】 因此，最佳乘积序列为(A1A2) (A3A4).共执行乘法405次。【2分4设(y1, y2,，yn)是所给0/背包问题的一个最优解,则(y2,，yn)是下面对应问题的 最优解max ViXii 2WiXi c mxi,Xi 0,1,2/n否则，设(z2,zn)是最优解 则(y4,z2,zn)是原问题的更优解,而(y1,y2,yn) 不是最优解。矛盾证毕。【5分】五、对于贪心算法，试解答：(1题6分，2题10分，共16分)1 贪心算法的两个重要性质及其定义。最优子结构性质和贪心选择性质问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。【6分】2. int store(int x,int n, int I)x为程序长度数组，n为要存储的程序个数，I为磁带长度；int i=0： sum=0 ;sort(xD.n) /先对程序长度数组排序，结果存在x中【3分】while(in)sum=sum+xi;if(sumn) output(x);elsefor (int i=0;in) output(x);elsefor (int i=t;i0,存在正数和n0 0使得对所有n n0有：0f(n)cg(n)二、对于分治法，试解答：(1题10分，2题9分，共19分)1 二分搜索算法：设给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素X。templateint BinarySearch(Type af con st Type& x, int I, int r)while (r = l)int m = (l+r)/2;if (x = am) return m;if (x minbj,ai,则称作业i和j满足Johnson不等式。 流水作业调度问题的Johnson算法：令AA /1 a. b, N2 /1 a/ b(2) 将Ni中作业依a的非减序排序；将N2中作业依bi的非增序排(3) Ni中作业接N2中作业构成满足Johnson法则的最优调度。四、对于贪心算法，试解答：(1题6分，2题6分，3题10分共22分)1 写出贪心算法的两个重要性质及其定义。最优子结构性质和贪心选择性质问题的最优解包含看其子问题的最优解.这种性质称为最优子结构性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选 择)来达到。2写出用Prim算法求解最小生成树问题的基本思想和算法描述。基本思想：在保证连通的前提下依次选出权重较小的n- 1条边。G二(V,E)为无向 连通带权图，令V二1,2,n。设置一个集合S,初始化S=1. T二。贪心策略：如果v-s中的顶点j与S中的某个点i连接，且(i, j)是E中的权重最小的边，则选择j (将j加入S),并将(i,j)加入T中。重复执行贪心策略，直至 v-s为空。Void (intn, Type*c)T=0;S二；While(S!=V) (i, j)二iGS且jWV-S的最小权边;T二TU(i, j)；S二SUj；3. 已知字母集c1, c2, c3, c4, c5, c6, c7, c8 ,频率 5, 25,3,6, 10, 11,36,4,则Huffman 树为01001a39610101172225360 101C2C7710111101C5C6013456C3 C8C1 C4Huffman编码为1-c3c4c5c6c7c801101000000111001010110001总码数为 4*5 + 2 ”25+ 4 ”3 + 4 ”6 + 310+ 3笛+ 2 ”36+ 4 4= 257 (10分)五、对于回溯和分支限界法，试解答：(1题6分，2题6分，3题12分，共24分)1 递归回溯void backtrack (in11)if (tn) output(x);elsefor (int i=f(n,t);i0) if(f(n,t)=g(n,t)for (int i=f(n,t);i=g(n,t);i+) xt=h(i);if (constraint(t)&bound(t) if (solution(t) output(x);else t+;else t-;2常见的两种分支限界法：队列式(FIFO)分支限界法-将活结点表组织成一个队列，按照 先进先出(FIFO)原则选取下一个结点为扩展结点；优先队列式分支限界法-将活结点表组 织成一个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。3解：按照单位效益从大到小依次排列这7个物品为：FBGDECA.将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求 得：a . 4040 30 50 35 150 115190.625(1,1,1,1,7,0,0)408b. 40403050301501157.0)60c404030 5010d%4030353015010516i7?560e 4040503530150130560f4040503510150130170.7135177.512(U,1,ox ,o)X1Xi 0Xi 1X2aX4XJ 0g. 40 40 50 30 160h. 4040 35 30 10 150146.85(1J,0,1,0,1,0)Xs35140i.403050(1,0,1,U,3530 15060125j. 40 30 501.0)35 30 150 14560167,o) xp12157.5 (ojjj;12xs 1xs 0e gX6 0在处获得该问题的最优解为(1,1,1,1,0,0,1).背包效益为170.即在背包中装入物品F、B、G、D、A时达到最大效益：为170;重量为150.
展开阅读全文