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

华南农业大学期末考试试卷（A卷） 200学年第学期　 考试科目：　算法分析设计　 考试类型：（卷）　　　考试时间：　120　分钟 学号 姓名 年级专业 题号 一 二 三 总分 得分 评阅人 一、选择题（0分，每题分） 、odd (n) 当n是奇数时返回true，否则返回false， while ( n 1) if ( odd (n) ) n = 3 * n + 1; else n = n / 2; 请问该算法所需计算时间的下界是 D 。 A．Ω（2n） B．Ω（nlog n） C．Ω（n！） D．Ω（logn） 2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻， i 1 2 3 4 5 6 7 8 9 10 s（i） 0 3 1 5 3 5 2 8 8 6 f（i） 6 5 4 9 8 7 13 12 11 10 同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足 B 位客户的需求。 P104 A．3 B．4 C．5 D．6 3、 B 来消除或减少问题的好坏实例间的这种差别。 A．数值概率算法 B．舍伍德算法 C．拉斯维加斯算法 D．蒙特卡罗算法 4、将一个正整数n表示成一系列正整数之和， n = n1 + n2 + … +nk（其中，n1≥n2≥ … ≥nk≥1，k≥1） 正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）= C 。 A．q（8，8） B．1 + q（9，9） P12 C．2 + q（10，8） D．A，B，C都正确 5、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 B 。 A．n! B．2n C．2n+1-1 D． P140 6、 A 。 A．（4k – 1）/3 B．2k /3 C．4k D．2k 7、当输入规模为n时，算法的是 。A．T（n）= T（n – 1）+1，T（1）＝1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 8、给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1] = 1，m[i]（1 i ≤ n）为 A 。i 1） C．m[i] = 1 + max{0，m[k] （A[k] ≤ A[i]，1≤k i ）} D．m[i] = max{0，m[k]（A[k] A[i]，1≤k i ）} 设表示：从左向右扫描过来直到以元素结尾的序列，获得的最长上升子序列的长度，且子序列包含元素（）。 即，是从，……到中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。 最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1=i=n} 例如，对于序列：4 2 6 3 1 5 2 i 1 2 3 4 5 6 7 array 4 2 6 3 1 5 2 f(i) 1 1 2 2 1 3 2 9、有9个村庄，其坐标位置如下表所示： i 1 2 3 4 5 6 7 8 9 x（i） 1 2 3 4 5 6 7 8 9 y（i） 1 2 3 4 5 6 7 8 9 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 C 才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0） B．（4.5，4.5） C．（5，5） D．（5，0） 10、关于回溯算法和分支限界法，以下 A 是不正确描述。 A．回溯法中【应为分支限界法】，每个活结点只有一次机会成为扩展结点 B．分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中 C．回溯法采用深度优先的结点生成策略 D．分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略 11、一个算法应该包含如下几