试题纸（A卷）
课程名称： 算法设计分析 适专业年级： 2008级计算机电
考生学号： 考 生 姓 名：
………………………………………………………………………………………………………………………
题号
二
三
四
总分
分数
填空题（10空×2分20分）
1 算法运行时占机器资源量称算法复杂性包括（ ）（ ）
2 算法运行时间n2+n+1时n2+n+1n2数量级相等称n2算法（ ）
3 项式A(n)amnm+…+ a2n2+ a1n+ a0界（ ）
4 递算法设计关键找出（ ）（ ）
5 （ ）问题贪婪算法动态规划方法求解前提
6 拆半查找合排序二叉树遍历等算法中均采（ ）策略
7 回溯算法尝试搜索算法中基种算法采种（ ）思想作控制结构
8 分支限界法解决布线问题时问题解空间搜索尝试结束标志（ ）
二 判断题（10题×2分20分）
1 c正常数O(cf(n))O(f(n))
2 情况坏情况均情况时间复杂度中操作性实际价值均情况时间复杂度
3 递函数找应非递定义
4 算法程度取决问题中数采数结构
5 迭代模型通规模问题解逐步求解规模问题解正递算法设计相反
6 贪婪算法解决零钱兑换问题时总找问题优解
7 适动态规划算法解决问题应该具优化原理子问题重叠
8 深度优先搜索算法搜索问题解方案
9 解决马遍历问题采回溯法解空间树搜索采广度优先搜索方式
10 分支限界法求解目标找出满足约束条件解满足约束条件解中找出某目标函数值达极极解
三 简答题（3题×6分18分）
1叙述分治算法动态规划算法基思想较两种算法异
2算法设计实际应中遇问题分4类：判定性问题计算问题优化问题构造性问题请指出递法递推法贪婪算法分治法动态规划法搜索算法适合解决问题
3简述回溯法求解问题般步骤
四 程序填空题（6空×3分18分）
1 找出n然数(123…n)中取r数组合例n4r3时组合：
4 3 2
4 3 1
4 2 1
3 2 1
算法请填空
void comb(int nint r)
{
int ij
for(in ① i)
{
②
if(r>1)
③
else
{
for(ja[0] j>0 j)
printf(3da[j])
printf(＼n)
}
}
}
2 走迷宫问题迷宫许方格构成矩形方格中墙（ 1表示）路（0表示）走迷宫方格左右四方邻方格然穿墙设迷宫入口左角(11)出口右角(88)根定迷宫找出条入口出口路径
数结构：数组maze[8][8]存放迷宫数组fx[4]{1100}fy[4]{0011}模拟左右搜索时标变化程迷宫原存储空间置元素值1时标识已访问该方格数组做队存储空间队中成员三：行号列号前方格队列中标
struct {int xypre}sq[100]
search()
{ qh0 qe1
maze[1][1] ④
sq[1]pre0 sq[1]x1 sq[1]y1
while( ⑤ )
{ qhqh+1
for(k1k<4k++)
{ isq[qh]x+fx[k]
jsq[qh]y+fy[k]
if (check(ij)1) check()检查该方格否行
{ ⑥
sq[qe]xi sq[qe]yj sq[qe]preqh
maze[i][j]1
if(sq[qe]x8 and sq[qe]y8)
{ out() return} out ()输出找路径
}
}
}
print(No avaliable way)
}
五 算法设计题（2题×12分24分）
1输入高精度数s长整数c 求s×c精确值
2图示数塔顶部出发结点选择左走右走直走底层求找出条路径路径数值
08级算法设计分析（A卷）答案
填空题（10空×2分20分）
1 时间复杂度 空间复杂度
2 渐时间复杂度时间复杂度
3 nm
4 递关系（递方程） 递终止（边界）条件
5 效性
6 分治算法
7 走掉头
8 搜索达b结点 活结点队列空
二 判断题（10题×2分20分）
15
√
×
×
√
√
610
×
×
√
×
√
三 简答题（3题×6分18分）
1 答：两者递算法思想应根策略找出规模问题规模子问题间关系直规模子问题容易解决规模子问题解逐步导出问题解
分治法解决问题特征：
1)问题规模缩定程度容易解决
2)问题分解干规模较相似问题该问题具优子结构性质
3)利该问题分解出子问题解合该问题解
4)该问题分解出子问题相互独立子问题间包含公子问题
问题满足1234条时采分治法满足123条时采动态规划方法
2递推法递法适合解决判定性问题计算问题
贪婪算法分治法 动态规划法 适合解决优化问题
贪婪算法分治法 搜索算法 适合解决 构造性问题
3回溯法包含问题解解空间树中深度优先策略根结点出发搜索解空间树算法搜索解空间树结点时总先判断该结点否满足问题约束条件果满足进入该子树继续深度优先策略进行搜索否搜索该结点根子树逐层祖先结点回溯
四 程序填空题（6空×3分18分）
1
i>r
a[r]i
comb(i1r1)
2
1
qh<>qe
qeqe+1
五 算法设计题（2题×12分24分）
1
main( )
{
long bcd int a[256]ijn char s1[256]
input(s1c)
nstrlen(s1)
d0
for(i0jn1i { b(s1[j]48)*c+d
a[i]b10
db10
}
while(d0)
{ a[n]d10
dd10
n++
}
for(in1i>0i)
print(a[i])
}
2
main( )
{ int a[50][50][3]ijn
print( ＇please input the number of rows＇)
input(n)
for(i1i for(j1j { input(a[i][j][1])
a[i][j][2]a[i][j][1]
a[i][j][3]0
}
for(in1i>1i)
for(j1j>i j++)
if(a[i+1][j][2]>a[i+1][j+1][2])
{ a[i][j][2]a[i][j][2]+a[i+1][j][2]
a[i][j][3]0
}
else
{ a[i][j][2]a[i][j][2]+a[i+1][j+1][2]
a[i][j][3]1
}
print(maxa[1][1][2])
j1
for(i1i{ print(a[i][j][1]>’)
jj+a[i][j][3]
}
print(a[n][j][1])
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
课程名称： 算法设计分析 适专业年级： 2008级计算机电
考生学号： 考 生 姓 名：
………………………………………………………………………………………………………………………
题号
二
三
四
总分
分数
填空题（10空×2分20分）
1 算法运行时占机器资源量称算法复杂性包括（ ）（ ）
2 算法运行时间n2+n+1时n2+n+1n2数量级相等称n2算法（ ）
3 项式A(n)amnm+…+ a2n2+ a1n+ a0界（ ）
4 递算法设计关键找出（ ）（ ）
5 （ ）问题贪婪算法动态规划方法求解前提
6 拆半查找合排序二叉树遍历等算法中均采（ ）策略
7 回溯算法尝试搜索算法中基种算法采种（ ）思想作控制结构
8 分支限界法解决布线问题时问题解空间搜索尝试结束标志（ ）
二 判断题（10题×2分20分）
1 c正常数O(cf(n))O(f(n))
2 情况坏情况均情况时间复杂度中操作性实际价值均情况时间复杂度
3 递函数找应非递定义
4 算法程度取决问题中数采数结构
5 迭代模型通规模问题解逐步求解规模问题解正递算法设计相反
6 贪婪算法解决零钱兑换问题时总找问题优解
7 适动态规划算法解决问题应该具优化原理子问题重叠
8 深度优先搜索算法搜索问题解方案
9 解决马遍历问题采回溯法解空间树搜索采广度优先搜索方式
10 分支限界法求解目标找出满足约束条件解满足约束条件解中找出某目标函数值达极极解
三 简答题（3题×6分18分）
1叙述分治算法动态规划算法基思想较两种算法异
2算法设计实际应中遇问题分4类：判定性问题计算问题优化问题构造性问题请指出递法递推法贪婪算法分治法动态规划法搜索算法适合解决问题
3简述回溯法求解问题般步骤
四 程序填空题（6空×3分18分）
1 找出n然数(123…n)中取r数组合例n4r3时组合：
4 3 2
4 3 1
4 2 1
3 2 1
算法请填空
void comb(int nint r)
{
int ij
for(in ① i)
{
②
if(r>1)
③
else
{
for(ja[0] j>0 j)
printf(3da[j])
printf(＼n)
}
}
}
2 走迷宫问题迷宫许方格构成矩形方格中墙（ 1表示）路（0表示）走迷宫方格左右四方邻方格然穿墙设迷宫入口左角(11)出口右角(88)根定迷宫找出条入口出口路径
数结构：数组maze[8][8]存放迷宫数组fx[4]{1100}fy[4]{0011}模拟左右搜索时标变化程迷宫原存储空间置元素值1时标识已访问该方格数组做队存储空间队中成员三：行号列号前方格队列中标
struct {int xypre}sq[100]
search()
{ qh0 qe1
maze[1][1] ④
sq[1]pre0 sq[1]x1 sq[1]y1
while( ⑤ )
{ qhqh+1
for(k1k<4k++)
{ isq[qh]x+fx[k]
jsq[qh]y+fy[k]
if (check(ij)1) check()检查该方格否行
{ ⑥
sq[qe]xi sq[qe]yj sq[qe]preqh
maze[i][j]1
if(sq[qe]x8 and sq[qe]y8)
{ out() return} out ()输出找路径
}
}
}
print(No avaliable way)
}
五 算法设计题（2题×12分24分）
1输入高精度数s长整数c 求s×c精确值
2图示数塔顶部出发结点选择左走右走直走底层求找出条路径路径数值
08级算法设计分析（A卷）答案
填空题（10空×2分20分）
1 时间复杂度 空间复杂度
2 渐时间复杂度时间复杂度
3 nm
4 递关系（递方程） 递终止（边界）条件
5 效性
6 分治算法
7 走掉头
8 搜索达b结点 活结点队列空
二 判断题（10题×2分20分）
15
√
×
×
√
√
610
×
×
√
×
√
三 简答题（3题×6分18分）
1 答：两者递算法思想应根策略找出规模问题规模子问题间关系直规模子问题容易解决规模子问题解逐步导出问题解
分治法解决问题特征：
1)问题规模缩定程度容易解决
2)问题分解干规模较相似问题该问题具优子结构性质
3)利该问题分解出子问题解合该问题解
4)该问题分解出子问题相互独立子问题间包含公子问题
问题满足1234条时采分治法满足123条时采动态规划方法
2递推法递法适合解决判定性问题计算问题
贪婪算法分治法 动态规划法 适合解决优化问题
贪婪算法分治法 搜索算法 适合解决 构造性问题
3回溯法包含问题解解空间树中深度优先策略根结点出发搜索解空间树算法搜索解空间树结点时总先判断该结点否满足问题约束条件果满足进入该子树继续深度优先策略进行搜索否搜索该结点根子树逐层祖先结点回溯
四 程序填空题（6空×3分18分）
1
i>r
a[r]i
comb(i1r1)
2
1
qh<>qe
qeqe+1
五 算法设计题（2题×12分24分）
1
main( )
{
long bcd int a[256]ijn char s1[256]
input(s1c)
nstrlen(s1)
d0
for(i0jn1i
a[i]b10
db10
}
while(d0)
{ a[n]d10
dd10
n++
}
for(in1i>0i)
print(a[i])
}
2
main( )
{ int a[50][50][3]ijn
print( ＇please input the number of rows＇)
input(n)
for(i1i
a[i][j][2]a[i][j][1]
a[i][j][3]0
}
for(in1i>1i)
for(j1j>i j++)
if(a[i+1][j][2]>a[i+1][j+1][2])
{ a[i][j][2]a[i][j][2]+a[i+1][j][2]
a[i][j][3]0
}
else
{ a[i][j][2]a[i][j][2]+a[i+1][j+1][2]
a[i][j][3]1
}
print(maxa[1][1][2])
j1
for(i1i
jj+a[i][j][3]
}
print(a[n][j][1])
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
