西南交通大学2015 — 2016学年第(一)学期考试试卷
课程代码 3244152课程名称 算法分析与设计
考试时间 120分钟
阅卷教师签字： __________________________________
填空题(每空1分，共15分)
1、 程序是 (1)
用某种程序设计语言的具体实现。
2、 矩阵连乘问题的算法可由
(2)
设计实现。
3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是
(3)
4、 大整数乘积算法是用 (4) 来设计的。
5、 贪心算法总是做出在当前看来
(5) 的选择。
也就是说贪心算法并不从整体最优
考虑，它所做出的选择只是在某种意义上的
(6) o
6、 回溯法是一种既带有
(7)
又带有 (8)
的搜索算法。
7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9)
类型
8、 在忽略常数因子的情况下，0、门和0三个符号中，
(10)
提供了算法运行时
间的一个上界。
9、 算法的“确定性”指的是组成算法的每条
(11)
是清晰的，无歧义的。
10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。
11、 算法就是一组有穷
(13)，它们规定了解决某一特定类型问题的
(14) o
12、 变治思想有三种主要的类型：实例化简，改变表现，
(15) o
、
___________________________________________________________________________________ L
线订装封密
线订装封密
、
__________________ 二 线订装封密
级班
选择题(每题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、分治策略
B、动态规划法
C、贪心法
D、回溯法
6、回溯法的效率不依赖于下列哪些因素（）
A. 满足显约束的值的个数
B. 计算约束函数的时间
C. 计算限界函数的时间
D. 确定解空间的时间
7、
A、子问题必须是一样的
C、子问题的解可以合并
8、实现合并排序利用的算法是（
A、分治策略
B、动态规划法B、子问题不能够重复
D、原问题和子问题使用相同的方法解）。
C、贪心法
D、回溯法
使用分治法求解不需要满足的条件是（
A、O (n2n)
B、O (nlogn )
C、O (2n)
10、广度优先是( )的一搜索方式。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
三、算法及程序分析(共25分)。
1 •阅读下面的程序，按要求回答问题：(共10分)
#i nclude <stdio.h>
#i nclude <stri ng.h>
in t vis[101][101];
int map[101][101];
int R,C;
int dp(int i,int j);
int mai n()
{
int i,j,a ns,max;
sca nf("%d%d",&R,&C);
for(i=0;i<R;i++)
for(j=0;j<C;j++)
sca nf("%d",&map[i][j]);
max = 0;
for(i=0;i<R;i++){
memset(vis[i],-1,sizeof(vis[i]));
for(j=0;j<C;j++){
ans = dp(i,j);
if(an s>max) max = ans;
}
}
prin tf("%d\n",max);
return 0;
}
int dp(i nt i,i nt j)
{
int max = 0;
if(vis[i][j]>0)
return vis[i][j];
if(i-1>=0)
if(map[i-1][j]<map[i][j]) if(max<dp(i-1,j))
max = dp(i-1,j); if(i+1<R)
if(map[i+1][j]<map[i][j]) if(max<dp(i+1,j))
max = dp(i+1,j);
if(j-1>=0)
if(map[i][j-1]<map[i][j])
if(max<dp(i,j-1))
max = dp(i,j-1);
if(j+1<C)
if(map[i][j+1]<map[i][j])
if(max<dp(i,j+1))
max = dp(i,j+1);
retur n vis[i][j] = max+1;
}
(1) 该程序采用什么算法？( 2分)
(2) 设R=5,C=5,map的值如下所示时程序执行结束之后 max的值是多少？(共5分)
(2)上述程序的时间复杂度是多少？(共 3分)
2 . 阅读下面的程序，按要求回答问题。
(共15分)
typedef struct SqList{
int *r;
int Len gth;
}SqList;
void HeapSort(SqList *H)
{
int i;
int rc;
for(i=H->Le ngth/2;i>0;--i)
HeapAdjust(H,i,H->Le ngth);
for(i=H->Le ngth;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;jv=m;j*=2){
if(j<m && H->r[j]<H->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;。