西南交通大学2015－2016学年第(一) 学期考试试卷
课程代码3244152课程名称算法分析与设计考试时间120分钟
阅卷教师签字：
填空题（每空1分，共15分）
1、 2、 3、 4、 5、
程序是（1） 用某种程序设计语言的具体实现。 矩阵连乘问题的算法可由（2）设计实现。
从分治法的一般设计模式可以看出，用它设计出的程序一般是（3）。 大整数乘积算法是用（4）来设计的。
贪心算法总是做出在当前看来（5） 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（6） 。 6、 7、 8、
回溯法是一种既带有 （7） 又带有 （8） 的搜索算法。
平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的（9） 类型。 在忽略常数因子的情况下，O 、Ω和Θ提供了算法运行时间的一个上界。 9、
密封装订线密封装订线密封装订线
算法的“确定性”指的是组成算法的每条(11)是清晰的，无歧义的。
10、 问题的(12) 是该问题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13) ，它们规定了解决某一特定类型问题的 (14) 。 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) 。
班 级学 号姓 名
选择题（每题2分，共20分）
1、
二分搜索算法是利用（ ）实现的算法。
A 、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、
衡量一个算法好坏的标准是（ ）。
A 、运行速度快 B、占用空间少 C、 时间复杂度低 D、代码短 3、
能采用贪心算法求最优解的问题，一般具有的重要性质为：（） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4、
常见的两种分支限界法为（）
A 、广度优先分支限界法与深度优先分支限界法； B 、队列式（FIFO ）分支限界法与堆栈式分支限界法； C 、排列树法与子集树法；
D 、队列式（FIFO ）分支限界法与优先队列式分支限界法； 5、
实现循环赛日程表利用的算法是（ ）。 A 、分治策略 C 、贪心法 6、
B 、动态规划法
D、回溯法
回溯法的效率不依赖于下列哪些因素（ ） A. 满足显约束的值的个数 C. 计算限界函数的时间
B. 计算约束函数的时间 D. 确定解空间的时间
7、 使用分治法求解不需要满足的条件是（ ）。 A 、 子问题必须是一样的B 、 子问题不能够重复
C 、 子问题的解可以合并D 、 原问题和子问题使用相同的方法解
8、 实现合并排序利用的算法是（）。 A 、分治策略
B 、动态规划法
C 、贪心法 D、回溯法
9、 背包问题的贪心算法所需的计算时间为（）
A 、O （n2n ） B、O （nlogn ） C、O （2n ） D、O （n ）
10、 广度优先是（）的一搜索方式。
A 、分支界限法 B、动态规划法 C、贪心法 D、回溯法
三、 算法及程序分析（共25分）。
1．阅读下面的程序，按要求回答问题：（共10分） #include
#include
int vis[101][101]; int map[101][101];
int R,C;
int dp(int i , int j ) ； int main() {
int i,j,ans,max;
scanf("%d%d",&R,&C); for (i=0;i
scanf("%d",&map[i][j]); max = 0;
for (i=0;i
memset(vis[i],-1,sizeof (vis[i])); for (j=0;j
ans = dp(i,j);
if (ans>max) max = ans; } }
printf("%d\n",max); return 0; }
int dp(int i , int j ) {
int max = 0;
if (vis[i ][j ]>0)
return vis[i ][j ]; if (i -1>=0) if (map[i -1][j ]
max = dp(i -1, j );
if (i +1
if (map[i +1][j ]
max = dp(i +1,j );
if (j -1>=0)
if (map[i ][j -1]
max = dp(i , j -1);
if (j +1
if (map[i ][j +1]
max = dp(i , j +1);
return vis[i ][j ] = max+1; }
（1） 该程序采用什么算法？（2分）
（2） 设R=5,C=5,map的值如下所示时程序执行结束之后max 的值是多少？（共 123 106574205 301115 2512231314 20
1418
1619
1530
（2）上述程序的时间复杂度是多少？（共3分）
5分）
．阅读下面的程序，按要求回答问题。（共15分） typedef struct SqList{
int *r; int Length; }SqList;
void HeapSort(SqList *H) {
int i; int rc;
for(i=H->Length/2;i>0;--i)
HeapAdjust(H,i,H->Length); for(i=H->Length;i>1;--i){ rc=H->r[1];
H->r[1]=H->r[i]; H->r[i]=rc;
HeapAdjust(H,1,i-1); }
return; }
void HeapAdjust(SqList *H,int s, int m) {
int rc,rm; int j;
rc=H->r[s];
for(j=2*s;j
if(jr[j]r[j+1]) ++j;
if(rc>=H->r[j]) break; rm=H->r[s];
H->r[s]=H->r[j]; H->r[j]=rm; s=j; }
H->r[s]=rc; return; }
（1） 该程序采用什么算法? （2分）
（2） 设传递给函数void HeapAdjust(SqList *H,int s, int m)H->Length: 8
H->r: {15, 18,16,32,14,45,78,30,43}
的参数如下：2
s=1 m=8
请问程序函数执行后H->r的值。 （共5分）
（3）该程序的时间复杂度是多少，写出求解过程。（共8分）
四、 算法描述题（共20分）。
1、已知某仓库有若干件商品，每件商品的重量为Wi, 价值为Vi 。某货车能装载的最大重量为W ，请将仓库中的部分商品装载到货车中，使其总价值最大。要求每件商品只能装载1件，且所有货物的总重量不能超过货车的总装载量。
（1）用文字描述采用动态规划算法求解上述问题的步骤。（6分） （2）用文字描述采用回溯法求解上述问题的步骤。（6分）
（3）若仓库中有8件商品，货车能装载的最大重量为5000公斤，每件商品的重量及价值如下表所示，请用图的形式描述采用分支限界法求解该问题时堆的变化过程。（共8分）
五、 算法设计及实现(共20分)
1、设某校最多有200门可选课程，而每个学生每学期最多可以选2门课程。在期末考试时，每天考试可安排在上午1次，下午1次，请编写程序求所有学生考试完所选课程需要安排的最少的考试次数。（共20分）
输入：输入的第一行包含两个整数n 和m ，n 表示可选课程的数量，m 表示学生的人数。下面的m 行，每行有两个整数，分别表示每个学生所选的两门课程的编号。比如：
4 5 1 2 2 3 3 4 1 4 2 4
输出：输出1行，即所有学生考试完所选课程所需要的最少考试次数。
西南交通大学2015－2016学年第(一) 学期考试试卷
课程代码3244152课程名称算法分析与设计考试时间120分钟
阅卷教师签字：
填空题（每空1分，共15分）
1、 2、 3、 4、 5、
程序是（1） 用某种程序设计语言的具体实现。 矩阵连乘问题的算法可由（2）设计实现。
从分治法的一般设计模式可以看出，用它设计出的程序一般是（3）。 大整数乘积算法是用（4）来设计的。
贪心算法总是做出在当前看来（5） 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（6） 。 6、 7、 8、
回溯法是一种既带有 （7） 又带有 （8） 的搜索算法。
平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的（9） 类型。 在忽略常数因子的情况下，O 、Ω和Θ提供了算法运行时间的一个上界。 9、
密封装订线密封装订线密封装订线
算法的“确定性”指的是组成算法的每条(11)是清晰的，无歧义的。
10、 问题的(12) 是该问题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13) ，它们规定了解决某一特定类型问题的 (14) 。 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) 。
班 级学 号姓 名
选择题（每题2分，共20分）
1、
二分搜索算法是利用（ ）实现的算法。
A 、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、
衡量一个算法好坏的标准是（ ）。
A 、运行速度快 B、占用空间少 C、 时间复杂度低 D、代码短 3、
能采用贪心算法求最优解的问题，一般具有的重要性质为：（） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4、
常见的两种分支限界法为（）
A 、广度优先分支限界法与深度优先分支限界法； B 、队列式（FIFO ）分支限界法与堆栈式分支限界法； C 、排列树法与子集树法；
D 、队列式（FIFO ）分支限界法与优先队列式分支限界法； 5、
实现循环赛日程表利用的算法是（ ）。 A 、分治策略 C 、贪心法 6、
B 、动态规划法
D、回溯法
回溯法的效率不依赖于下列哪些因素（ ） A. 满足显约束的值的个数 C. 计算限界函数的时间
B. 计算约束函数的时间 D. 确定解空间的时间
7、 使用分治法求解不需要满足的条件是（ ）。 A 、 子问题必须是一样的B 、 子问题不能够重复
C 、 子问题的解可以合并D 、 原问题和子问题使用相同的方法解
8、 实现合并排序利用的算法是（）。 A 、分治策略
B 、动态规划法
C 、贪心法 D、回溯法
9、 背包问题的贪心算法所需的计算时间为（）
A 、O （n2n ） B、O （nlogn ） C、O （2n ） D、O （n ）
10、 广度优先是（）的一搜索方式。
A 、分支界限法 B、动态规划法 C、贪心法 D、回溯法
三、 算法及程序分析（共25分）。
1．阅读下面的程序，按要求回答问题：（共10分） #include
#include
int vis[101][101]; int map[101][101];
int R,C;
int dp(int i , int j ) ； int main() {
int i,j,ans,max;
scanf("%d%d",&R,&C); for (i=0;i
scanf("%d",&map[i][j]); max = 0;
for (i=0;i
memset(vis[i],-1,sizeof (vis[i])); for (j=0;j
ans = dp(i,j);
if (ans>max) max = ans; } }
printf("%d\n",max); return 0; }
int dp(int i , int j ) {
int max = 0;
if (vis[i ][j ]>0)
return vis[i ][j ]; if (i -1>=0) if (map[i -1][j ]
max = dp(i -1, j );
if (i +1
if (map[i +1][j ]
max = dp(i +1,j );
if (j -1>=0)
if (map[i ][j -1]
max = dp(i , j -1);
if (j +1
if (map[i ][j +1]
max = dp(i , j +1);
return vis[i ][j ] = max+1; }
（1） 该程序采用什么算法？（2分）
（2） 设R=5,C=5,map的值如下所示时程序执行结束之后max 的值是多少？（共 123 106574205 301115 2512231314 20
1418
1619
1530
（2）上述程序的时间复杂度是多少？（共3分）
5分）
．阅读下面的程序，按要求回答问题。（共15分） typedef struct SqList{
int *r; int Length; }SqList;
void HeapSort(SqList *H) {
int i; int rc;
for(i=H->Length/2;i>0;--i)
HeapAdjust(H,i,H->Length); for(i=H->Length;i>1;--i){ rc=H->r[1];
H->r[1]=H->r[i]; H->r[i]=rc;
HeapAdjust(H,1,i-1); }
return; }
void HeapAdjust(SqList *H,int s, int m) {
int rc,rm; int j;
rc=H->r[s];
for(j=2*s;j
if(jr[j]r[j+1]) ++j;
if(rc>=H->r[j]) break; rm=H->r[s];
H->r[s]=H->r[j]; H->r[j]=rm; s=j; }
H->r[s]=rc; return; }
（1） 该程序采用什么算法? （2分）
（2） 设传递给函数void HeapAdjust(SqList *H,int s, int m)H->Length: 8
H->r: {15, 18,16,32,14,45,78,30,43}
的参数如下：2
s=1 m=8
请问程序函数执行后H->r的值。 （共5分）
（3）该程序的时间复杂度是多少，写出求解过程。（共8分）
四、 算法描述题（共20分）。
1、已知某仓库有若干件商品，每件商品的重量为Wi, 价值为Vi 。某货车能装载的最大重量为W ，请将仓库中的部分商品装载到货车中，使其总价值最大。要求每件商品只能装载1件，且所有货物的总重量不能超过货车的总装载量。
（1）用文字描述采用动态规划算法求解上述问题的步骤。（6分） （2）用文字描述采用回溯法求解上述问题的步骤。（6分）
（3）若仓库中有8件商品，货车能装载的最大重量为5000公斤，每件商品的重量及价值如下表所示，请用图的形式描述采用分支限界法求解该问题时堆的变化过程。（共8分）
五、 算法设计及实现(共20分)
1、设某校最多有200门可选课程，而每个学生每学期最多可以选2门课程。在期末考试时，每天考试可安排在上午1次，下午1次，请编写程序求所有学生考试完所选课程需要安排的最少的考试次数。（共20分）
输入：输入的第一行包含两个整数n 和m ，n 表示可选课程的数量，m 表示学生的人数。下面的m 行，每行有两个整数，分别表示每个学生所选的两门课程的编号。比如：
4 5 1 2 2 3 3 4 1 4 2 4
输出：输出1行，即所有学生考试完所选课程所需要的最少考试次数。