2008.1算法设计与分析课程期末试卷.doc

华南农业大学期末考试试卷（A卷）2007学年第一学期 考试科目：算法分析与设计考试类型：（开卷）考试时间：120分钟学号 姓名 年级专业 题号一二三总分得分评阅人一、选择题（20分，每题2分）1、void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 上述算法的时间复杂度为 。AO（2n）BO（nlog n）C（n！）D（nn）2、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 来消除或减少问题的好坏实例间的这种差别。（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法3、对于下列二分搜索算法，正确的是 。（A）public static int binarySearch(int a, int x, int n) int left = 0, right = n-1;while(left amiddle) left = middle;else right = middle; /whilereturn 1;（B）public static int binarySearch(int a, int x, int n)int left = 0, right = n-1;while(left+1 != right)int middle = (left + right) / 2;if(x = amiddle) left = middle;else right = middle;/whileif(x = aleft) return left;else return 1;（C）public static int binarySearch (int a, int x, int n)int left = 0, right = n-1;while(left right-1)int middle = (left + right) / 2;if(x 0 & x = a0)int left = 0, right = n-1;while(left right)int middle = (left + right + 1) / 2;if(x m）。对于多级调度问题，使用以下哪种贪心策略比较合适 。（A） 作业从小到大依次分配给空闲的机器（B） 作业从大到小依次分配给空闲的机器（C） 每个机器分配一样的作业数（D） 使用以上几种贪心策略都能找到最优解，所以都合适7、使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为 。（A）10（B）11（C）500（D）10008、设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为 。（A）1 （n=1 | m=1）q(n, n) （n m 1）（B） 1 （n=1 | m=1）q(n, n) （n m 1）（C） 1 （n=1 | m=1）q(n, n) （n m 1）(D) 0 （n 1 & m = 1）1 （n=1）q（n，m）=q(n, n) （n m 1）9、一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N-2个三角形，这称为凸N边形的一种三角剖分。例如N5时，共有以下5种三角剖分：当N8时，总共有 种三角剖分。（A）8（B）132（C）14（D）14010、给定6个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。这家医院应建在小区 ，才能使距离医院最远的小区到医院的路程最短？ABCDEF6132216103（A）A （B）B （C）C （D）E二、简答题（30分，每题6分）1、 试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？2、 给定n件物品和一个背包，物品i的重量是wi，体积是vi（wi，vi均为整数），价值是pi；背包的容量为C，容积为D。一件物品只能整个放进背包中或不放进背包中，也不允许重复放入。0-1背包问题问应如何选择装入背包的物品，使得装入背包中的物品不超过背包容量容积限制，并且物品的总价值最大？设m(i，j，k)是背包容量为j，容积为k，可选择物品为1，2，i时0-1背包问题的最优值，请给出计算m(i，j，k)的递归关系式。3、 如下图，图中的5个顶点为某乡的5个村，图的边代表公路，现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线，才能使所用的电线最少？请列出一种使用电线最少的架线方案（要求给出求解过程）。4、 请解释什么是P问题，NP问题以及NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题。5、 有4个矩阵A1，A2，A3，A4，其中Ai与Ai1是可乘的，i = 1，2，3，连乘积为A1A2A3A4。 在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个，并请把所有的子问题列出来。三、算法设计题（50分，每题10分）1、【查找第k最小元】给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。2、【最长单调上升子序列】给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。3、【旅行规划】G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。请设计一个算法使到G先生旅行的费用最省（这里的旅行费用指的是加油的总花费）。4、【符号三角形问题】下图是由14个“+”和14个“”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“”。在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“”的个数相同。请针对符号三角形问题设计一个尽可能高效的算法。5、【放苹果】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种