发布时间 : 星期三 文章算法设计与分析（试题A卷）更新完毕开始阅读
《算法设计与分析》课程试卷(A)
答卷说明：1、考试方式 闭卷
2、满分100分
题号 分数 一 二 三 四 五 六 七 总分 总分人
得分 评卷人
一、单项选择题（每小题3分，共30分）
1、动态规划算法的基本要素为（ ）。 A、最优子结构性质与贪心选择性质 B、重叠子问题性质与贪心选择性质 C、最优子结构性质与重叠子问题性质 D.、预排序与递归调用
2、算法分析中，记号O表示（ ），记号?表示（ ），记号?表示（ ）。 A、渐进下界 B、渐进上界 C、非紧上界 D、紧渐进界 E、非紧下界 3、以下关于渐进记号的性质是正确的有：（ ） A、f(n)??(g(n)),g(n)??(h(n))?f(n)??(h(n)) B、f(n)?O(g(n)),g(n)?O(h(n))?h(n)?O(f(n)) C、O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D、f(n)?O(g(n))?g(n)?O(f(n))
4、下列算法中通常以自底向上的方式求解最优解的是（ ）。
四川师范大学成教×××专业×××层次半脱产形式期末考试期末试卷第1页( 共6页)
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
5、衡量一个算法好坏的标准是（ ）。
A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码段 6、实现棋盘覆盖算法利用的算法是（ ）。 A、分治法
B、动态规划法
C、贪心法
D、回溯法
7、下面关于NP问题说法正确的是（ ）。 A、NP问题都是不可能解决的问题 B、P类问题包含在NP类问题中 C、NP完全问题是P类问题的子集 D、NP类问题包含在P类问题中
8、矩阵连乘问题的算法可由（ ）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 9、（ ）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质
D、最优子结构性质
10、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（ ） A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); 四川师范大学成教××专业××层次××形式期末考试 ××试卷 第2页( 共6页)
move(n,a,b); hanoi(n-1, C, B, A); }
C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } D. void hanoi(int n, int C, int A, int B) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 得分 评卷人
二、填空题（每空2分，共18分）
1、下面程序段的所需要的计算时间为 。 Int MaxSum(int n, int *a, int &besti, int &bestj) {
int sum=0;
for(int i=1;i<=n;i++){ int thissum=0;
for(int j=i;j<=n;j++){ This sum+=a[j]; if(thissum>sum) {
四川师范大学成教×××专业×××层次半脱产形式期末考试期末试卷第3页( 共6页)
}
}
}
sum=this sum; besti=i; bestj=j; }
return sum;
2、算法的复杂性有 复杂性和 复杂性之分。 3、程序是 用某种程序设计语言的具体实现。 4、算法是指解决问题的 或 。
5、从分治法的一般设计模式可以看出，用它设计出的程序一般是 。 6、计算一个算法时间复杂度通常可以计算 、 或计算步。
得分 评卷人
三、证明题（每小题10分，共20分）
1、举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
2、求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)})
四川师范大学成教××专业××层次××形式期末考试 ××试卷 第4页( 共6页)