算法设计与分析试卷及答案

湖南科技学院二○ 年 学期期末考试
　信息计算科学专业 年级算法设计分析 试题
题 号

二
三
四
五



总分
统分
分










阅卷










复查




考试类型：开卷 试卷类型：C卷 考试时量：120 分钟
填空题（题3 分计30 分）
1 OΩθ表示函数fg间关系______________________________

2 算法时间复杂性算法时间复杂性阶__________________________
3 快速排序算法性取决______________________________
4 算法_______________________________________________________
5 问题解空间树进行搜索方法中活结点次机会成活结点_________________________
6 算法三种情况复杂性中操作性实际价值_____情况时间复杂性
7 Ω符号描述增长率限限阶越___________结果越价值
8 ____________________________问题动态规划算法求解前提
9 贪心选择性质指________________________________________________________ ____________________________________________________________
10 回溯法问题解空间树中______________策略根结点出发搜索解空间树

二简答题（题10分计30分）
1 试述回溯法基思想回溯法解题步骤






















2 8作业{12…8}2台机器M1M2组成流水线完成加工作业加工序先M1加工然M2加工M1M2加工作业i需时间分：
M1
10
2
8
12
6
9
4
14
M2
5
7
1
15
16
3
11
13
作业
1
2
3
4
5
6
7
8
出优调度方案第作业机器M1开始加工作业机器M2加工完成需时间少计算需少时间

答：

优调度方案










需少时间：_______________________





3 根优先队列式分支限界法求图中v1点v9点单源短路径请画出求优解解空间树求中间舍弃结点×标记获中间解结点单圆圈○框起（）优解双圆圈◎框起



































三算法填空（空2分计10分）
设R{r1 r2 rn}进行排列n元素中元素r1 r2 rn相试设计算法列出R排列出排列总数算法填写缺失语句
template
void Swap(Type &aType &b){
Type tb
________________ 1
at
}

template
bool ok(Type R[]int kint i){
if(i>k)
for(int tkt if( __________________) 2
return false
return true
}

template
void Perm(Type R[]int kint nint &sum){ n元素数sum记录排列总数
if(kn){
______________________ 3
for(int i1i cout<<___________________ 4
cout< }else{
for(int iki if(ok(Rki)){
Swap(R[k]R[i])
Perm(_________________________) 5
Swap(R[k]R[i])
}
}
}
四算法设计（计15分）
设n程序{1 2 3 n}存放长度L磁带程序i存放磁带长度Li1≤i≤n 程序存储问题求确定n程序磁带存储方案够磁带存储程序保证存储程序前提求磁带利率达
（1）出求解存储程序算法证明算法正确性
（2）出求解磁带利率达方案算法思路

































五算法设计（计15分）
通键盘输入高精度正整数n（n效位数≤240）掉中意s数字剩数字原左右次序组成新正整数定ns寻找种方案剩数字组成新
输入n178543s4结果13
⑴ 简述算法思路
⑵ 出算法（C++描述）
注：正整数n存字符串中例：
string n178543
nat(0) 返回字符串n第1字符
nerase(23) 删n中索引2开始3字符
解：
⑴算法思路











⑵算法
string MinNum(string nint s)
{

湖南科技学院二○ 年 学期期末考试
算法设计分析试题C答案
填空题（题3 分计30 分）
1 f(n)Ω(g(n))
2 3 划分称性
4 干条指令组成组成穷序列（解决问题种方法程）
5 分枝限界法 6 坏 7 高 8 优子结构
9 求问题整体优解通系列局部优选择贪心选择达
10 深度优先
二简答题（题10分计30分）
1
回溯法问题解空间树中深度优先策略根结点出发搜索解空间树算法搜索解空间树意点时先判断该结点否包含问题解果肯定包含跳该结点根子树搜索逐层祖先结点回溯否进入该子树继续深度优先策略搜索 5分
基步骤： 5分
① 针拨问题定义问题解空间
② 确定易搜索解空间结构
③ 深度优先方式搜索解空间搜索程中剪枝函数避免效搜索

2
优调度方案 （6分）
2
7
5
4
8
1
6
3
需少时间：73 （4分 前问正确前提方分）

3

错处扣1分
三算法填空（空2分计10分）
1 ba
2 R[t]R[i]
3 sum++
4 R[i]
5 Rk+1nsum

四算法设计（计15分）
贪心策略：短程序优先程序排序次选取程序总长度超磁盘容量求存储程序数m
采回溯法n程序中选取总长度m算法装载问题

五算法设计（计15分）
1 7分
逼目标选取贪心策略：步总选择剩数数字删高位低位序搜索位数字递增删数字否删第递减区间首字母然回串首述规删数字重复程s次剩数字串便总解
2 8分
string MinNum(string nint s)
{
while(s>0)
{
unsigned int i0 串首开始找
while(i i++
nerase(i1) 删字符串n中索引i字符
s
}
while(nlength()>1&&nat(0)＇0＇)
nerase(01) 删串首产生零
return n
}

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档