首页 > 学生作文 > 读后感 > 读后感800字 >

算法设计与分析（试题A卷）

由天下分享时间：2024/12/17 22:50:34 加入收藏我要投稿点赞

《算法设计与分析》课程试卷(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、计算一个算法时间复杂度通常可以计算、或计算步。

得分评卷人