题型：单选题客观题分值2分难度：简单得分：2
1
应用Johnson法则的流水作业调度采用的算法是（ ）。
A
分支限界法
B
分治法
C
贪心算法
D
动态规划算法
学生答案：D
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
2
动态规划算法的基本要素为（ ）。
A
最优子结构性质与重叠子问题性质
B
重叠子问题性质与贪心选择性质
C
预排序与递归调用
D
最优子结构性质与贪心选择性质
学生答案：A
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
3
二分搜索算法是利用（ ）实现的算法。
A
回溯法
B
分治策略
C
动态规划法
D
贪心法
学生答案：B
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
4
下列不是动态规划算法基本步骤的是（ ）。
A
定义最优解
B
算出最优解
C
找出最优解的性质
D
构造最优解
学生答案：C
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
5
FIFO是（ ）的一搜索方式。
A
分治界限法
B
贪心法
C
回溯法
D
动态规划法
学生答案：A
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
6
秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？（ ）。
A
迭代
B
递归
C
模拟
D
分治
题型：单选题客观题分值2分难度：简单得分：2
7
k带图灵机的空间复杂性S(n)是指（ ）。
A
k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。
B
k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。
C
k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。
D
k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。
题型：单选题客观题分值2分难度：简单得分：2
8
最大效益优先是（ ）的一搜索方式。
A
贪心法
B
分支界限法
C
动态规划法
D
回溯法
题型：单选题客观题分值2分难度：简单得分：2
9
最长公共子序列算法利用的算法是（ ）。
A
动态规划法
B
回溯法
C
贪心法
D
分支界限法
题型：单选题客观题分值2分难度：简单得分：2
10
下列算法中通常以自底向上的方式求解最优解的是（ ）。
A
贪心法
B
动态规划法
C
备忘录法
D
回溯法
题型：单选题客观题分值2分难度：简单得分：2
11
衡量一个算法好坏的标准是（ ）。
A
运行速度快
B
占用空间少
C
代码短
D
时间复杂度低
题型：单选题客观题分值2分难度：简单得分：2
12
以下不可以使用分治法求解的是（ ）。
A
0/1背包问题
B
归并排序
C
选择问题
D
棋盘覆盖问题
题型：单选题客观题分值2分难度：简单得分：2
13
实现循环赛日程表利用的算法是（ ）。
A
分治策略
B
贪心法
C
动态规划法
D
回溯法
题型：单选题客观题分值2分难度：简单得分：2
14
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ ）。
A
重叠子问题
B
最优子结构性质
C
贪心选择性质
D
定义最优解
题型：单选题客观题分值2分难度：简单得分：2
15
实现最大子段和利用的算法是（ ）。
A
贪心法
B
分治策略
C
动态规划法
D
回溯法
题型：单选题客观题分值2分难度：简单得分：2
16
实现棋盘覆盖算法利用的算法是（ ）。
A
分治法
B
动态规划法
C
贪心法
D
回溯法
题型：单选题客观题分值2分难度：简单得分：2
17
实现合并排序利用的算法是（ ）。
A
贪心法
B
分治策略
C
回溯法
D
动态规划法
题型：单选题客观题分值2分难度：简单得分：2
18
下列是动态规划算法基本要素的是（ ）。
A
定义最优解
B
子问题重叠性质
C
构造最优解
D
算出最优解
题型：单选题客观题分值2分难度：简单得分：2
19
对线性表进行二分查找时，要求线性表必须（ ）。
A
以顺序方式存储，且结点按关键字有序排序
B
以链接方式存储
C
以顺序方式存储
D
以链接方式存储，且结点按关键字有序排序
题型：单选题客观题分值2分难度：简单得分：2
20
分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。
A
问题规模相同，问题性质不同
B
问题规模不同，问题性质相同
C
问题规模不同，问题性质不同
D
问题规模相同，问题性质相同
题型：单选题客观题分值2分难度：简单得分：2
21
所有的递归函数都能找到对应的非递归定义。
A
错误
B
正确
题型：单选题客观题分值2分难度：简单得分：2
22
定义递归函数时可以没有初始值。
A
错误
B
正确
题型：单选题客观题分值2分难度：简单得分：2
23
动态规划算法基本要素的是最优子结构。
A
错误
B
正确
题型：单选题客观题分值2分难度：简单得分：2
24
回溯法中限界函数的目的是剪去得不到最优解的子树。
A
正确
B
错误
题型：单选题客观题分值2分难度：简单得分：2
25
动态规划算法求解问题时，分解出来的子问题相互独立。
A
正确
B
错误
填空题
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
1
选择排序、插入排序和归并排序算法中， 算法是分治算法。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
2
若对一个问题的求解可转化为对其性质相同的子问题的求解，则称该问题满足 。
第1空分值：2分
题型：填空题主观题答案不允许乱序分值2分难度：一般得分：2
3
动态规划算法中存储子问题的解是为了
题型：填空题主观题答案不允许乱序分值2分难度：一般得分：2
4
随机算法的一个基本特征是对于同一组输入，不同的运行可能得到 的结果
题型：填空题主观题答案不允许乱序分值2分难度：一般得分：2
5
在快速排序、插入排序和合并排序算法中， 算法不是分治算法。
题型：填空题客观题答案不允许乱序分值6分难度：中等得分：6
6
下列是基于分治策略的二分查找算法的部分代码，请补全空格中的缺失代码。
int BinarySearch( int ArrayData[], int left, int right, int *x )
{ if ( left > right ) return -1;
int middle = ;
if ( *x == ArrayData[ middle ] ) return middle;
if ( *x > ArrayData[ middle ] )
return BinarySearch( );
else
return BinarySearch( );
}
第1空分值：2分
第2空分值：2分
第3空分值：2分
题型：填空题客观题答案不允许乱序分值4分难度：中等得分：2
7
下列是基于分治策略的快速排序算法的部分代码，请补全空格中缺失的代码。
template< class Type >
void QuickSort( Type a[], int p, int r )
{ if ( p < r )
{ int q = Partition( a, p, r );
; // 对左半段排序
; // 对右半段排序
}
}
第1空分值：2分
第2空分值：2分
简答题
题型：简答题主观题分值5分难度：中等得分：5
1
给出算法的定义。何谓算法的复杂性。计算下例在最坏情况下的时间复杂性。
for(j=1;j<=n;j++) (1)
for(i=1;i<=n;i++) (2)
{c[i][j]=0; (3)
for(k=1;k<=n;k++) (4)
c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)
题型：简答题主观题分值10分难度：困难得分：10
2
【算法设计题】炮弹一样的球状物体，能够堆积成一个金字塔，在顶端有一个炮弹，它坐落在一个4个炮弹组成的层面上，而这4个炮弹又坐落在一个9个炮弹组成的层面上，以此类推。写一个递归函数CannonBall，这个函数把金字塔的高度作为参数，并且返回它所包括的炮弹数量。函数必须按照递归方式实现，不可以使用迭代结构，例如while或for。
请给出具体实现代码。
学生答案：
代码详见附件
老师点评：
题型：简答题主观题分值15分难度：困难得分：14
3
【算法设计题】回溯法设计0/1背包问题的算法。
实例如：
给出具体实现代码。
学生答案：
代码详见附件
老师点评：
评论0