《算法分析与设计》期末试题及参考答案.docx
《《算法分析与设计》期末试题及参考答案.docx》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末试题及参考答案.docx（18页珍藏版）》请在冰点文库上搜索。
《算法分析与设计》期末试题及参考答案
《算法分析与设计》期末试题及参考答案
一、简要回答下列问题：
1.算法重要特性是什么？
1.确定性、可行性、输入、输出、有穷性
2.
2.算法分析的目的是什么？
2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.
3.算法的时间复杂性与问题的什么因素相关？
3.算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？
4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T（n）的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T（n）的数量级（阶）评价算法。
时间复杂度T（n）的数量级（阶）称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？
5.最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W（n）=max{T（n，I）},I∈Dn
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
A（n）=∑P（I）T（n，I）I∈Dn
6.简述二分检索（折半查找）算法的基本过程。
6.设输入是一个按非降次序排列的元素表A[i：
j]和x，选取A[（i+j）/2]与x比较，如果A[（i+j）/2]=x，则返回（i+j）/2，如果A[（i+j）/2]（i+j）/2-1]找x，否则在A[（i+j）/2+1：
j]找x。
上述过程被反复递归调用。
7.背包问题的目标函数和贪心算法最优化量度相同吗？
7.不相同。
目标函数：
获得最大利润。
最优量度：
最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？
有什么规定？
8.问题的解可以表示为n元组：
（x1,x2,……xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）（i9.回溯法的搜索特点是什么？
9.在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。
10.n皇后问题回溯算法的判别函数place的基本流程是什么？
10.将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。
11.为什么用分治法设计的算法一般有递归调用？
11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。
12.为什么要分析最坏情况下的算法时间复杂性？
、
12最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。
13.简述渐进时间复杂性上界的定义。
13.T（n）是某算法的时间复杂性函数，f（n）是一简单函数，存在正整数No和C，n〉No，有T（n）14.二分检索算法最多的比较次数？
14.二分检索算法的最多的比较次数为logn。
15.快速排序算法最坏情况下需要多少次比较运算？
15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。
16.贪心算法的基本思想？
16.是一种依据最优化量度依次选择输入的分级处理方法。
基本思路是：
首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。
如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
17.回溯法的解（x1,x2,……xn）的隐约束一般指什么？
17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。
18.阐述归并排序的分治思路。
18.讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。
如果分割后子问题还很大，则继续分治，直到一个元素。
19.快速排序的基本思想是什么。
19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。
所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。
之后重复上述过程，直到每一部分内只有一个记录为止。
20.什么是直接递归和间接递归？
消除递归一般要用到什么数据结构？
20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。
如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。
消除递归一般要用到栈这种数据结构。
21.什么是哈密顿环问题？
21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。
22.用回溯法求解哈密顿环，如何定义判定函数？
22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i]（i=1,2,…,k-1），且C（X[k-1],X[k]）≠∞，如果k=-1，则C（X[k],X[1]）≠∞。
23.请写出prim算法的基本思想。
23.思路是：
最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。
处理过程：
首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。
二、复杂性分析
1、MERGESORT（low，high）
iflowthenmid←（low，high）/2；
MERGESORT（low，mid）；
MERGESORT（mid+1，high）；
MERGE（low，mid，high）；
endif
endMERGESORT
答
2、procedureS1（P，W，M，X，n）
i←1;a←0
whilei≤ndo
ifW（i）>Mthenreturnendif
a←a+i
i←i+1;
repeat
end
解：
3.procedurePARTITION（m,p）
Integerm,p,i;globalA（m:
p-1）
v←A（m）;i←m
loop
loopi←i+1untilA（i）≥vrepeat
loopp←p-1untilA（p）≤vrepeat
ifithencallINTERCHANGE（A（i）,A（p））
elseexit
endif
repeat
A（m）←A（p）;A（p）←v
EndPARTITION
3解：
、最多的查找次数是p-m+1次
4.procedureF1（n）
ifn<2thenreturn
（1）
elsereturn（F2（2,n,1,1））
endif
endF1
procedureF2（i,n,x,y）
ifi≤n
thencallF2（i+1,n,y,x+y）
endif
return（y）
endF2
4、解：
F2（2，n,1,1）的时间复杂度为：
T（n）=O（n-2）;因为i≤n时要递归调用F2，一共是n-2次
当n＝1时F1（n）的时间为O
（1）
当n>1时F1（n）的时间复杂度与F2（2,n,1,1）的时间复杂度相同即为为O（n）
5.procedureMAX（A,n,j）
xmax←A
（1）;j←1
fori←2tondo
ifA（i）>xmaxthenxmax←A（i）;j←i;endif
repeat
endMAX
答案
5、
xmax←A
（1）;j←1时间为：
O
（1）
fori←2tondo循环最多n-1次
所以总时间为:
T（n）=O
（1）+（n-1）O
（1）=O（n）
6.procedureBINSRCH（A,n,x,j）
integerlow,high,mid,j,n;
low←1;high←n
whilelow≤highdo
mid←|_（low+high）/2_|
case
:
xhigh←mid-1
:
x>A（mid）:
low←mid+1
:
else:
j←mid;return
endcase
repeat
j←0
endBINSRCH
答案
6、log2n+1
三、算法理解
1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
各边的代价如下：
C（1,2）=3，C（1,3）=5，C（1,4）=2
C（2,6）=8，C（2,7）=4，C（3,5）=5，C（3,6）=4，C（4,5）=2，C（4,6）=1
C（5,8）=4，C（6,8）=5，C（7,8）=6
答案：
1、
Cost（4,8）=0
Cost（3,7）=C（7,8）+0=6，D[5]=8
Cost（3,6）=C（6，8）+0=5,D[6]=8
Cost（3,5）=C（5，8）+0=4D[7]=8
Cost（2,4）=min{C（4，6）+Cost（3,6）,C（4，5）+Cost（3,5）}
=min{1+5,2+4}=6D[4]=6
Cost（2,3）=min{C（3，6）+Cost（3,6）}
=min{4+5}=9D[3]=5
Cost（2,2）=min{C（2，6）+Cost（3,6）,C（2，7）+Cost（3,7）}
=min{8+5,4+6}=10D[2]=7
Cost（1,1）=min{C（1,2）+Cost（2,2）,C（1,3）+Cost（2,3）,C（1,4）+Cost（2,4）}
=min{3+10,5+9,2+6}=8
D[1]=4
1→4→6→8
2、写出maxmin算法对下列实例中找最大数和最小数的过程。
数组A=（48,12,61,3,5,19,32,7）
答案
2、写出maxmin算法对下列实例中找最大数和最小数的过程。
数组A=（）
1、48,12,61,3,5,19,32,7
2、48,1261,35,1932,7
3、48～61,12～319～32，5～7
4、61～323～5
5、613
3、给出5个数（3,6,9,1,7）,M=13，用递归树描述sumofsub算法求和数=M的一个子集的过程。
4、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。
A=（65,70,75,80,85,55,50,2）
5、归并排序算法对下列实例排序，写出算法执行过程。
A=（48,12,61,3,5,19,32,7）
5、
48,12,61,35,19,32,7
48,1261,35,1932,7
12,483,615,197,32
3,12,48,615,7,19，32
3,5,7,12，19，32，48,61
6、写出图着色问题的回溯算法的判断X[k]是否合理的过程。
6、
i←0
whileiifG[k,i]=1andX[k]=X[i]then
returnfalse
i←i+1
repeat
ifi=kthenreturntrue
7、对于下图，写出图着色算法得出一种着色方案的过程。
7、
K←1
X[1]←1,返回true
X[2]←1,返回false;X[2]←X[2]+1=2,返回true
X[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回true
X[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true
找到一个解（1，2，3，3）
8、写出第7题的状态空间树。
9、写出归并排序算法对下列实例排序的过程。
（6,2,9,3,5,1,8,7）
9、
调用第一层次6,2,9,35,1,8,7分成两个子问题
调用第二层次6,29,35,18,7分成四个子问题
调用第三层次62935187分成八个子问题
调用第四层次只有一个元素返回上一层
第三层归并2,63,91,57,8返回上一层
第二层归并2,3,6,91,5,7,8返回上一层
第一层归并1,2,3,5,6,7,8,9排序结束，返回主函数
10、写出用背包问题贪心算法解决下列实例的过程。
P=（18,12,4,1）
W=（12,10,8,3）
M=25
10、实例符合P（i）/W（i）≥P（i+1）/W（i+1）的顺序。
CU←25,X←0
W[1]x[1]←1;CU←CU-W[1]=13;
W[2]x[2]←1;CU←CU-W[2]=3;
W[3]>CU:
x[3]←CU/W[3]=3/8;
实例的解为：
（1，1，3/8，0）
11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。
解一共要要执行四次才能找到值为82的数。
12、使用prim算法构造出如下图G的一棵最小生成树。
dist（1,2）=6;dist（2,5）=3;dist（5,6）=6;dist（6,4）=2;dist（4,1）=5;
dist（1,3）=1;dist（2,3）=5;dist（3,4）=5;dist（3,6）=4;dist（5,3）=6
13、有如下函数说明
intf（intx,inty）
{
f=xMody+1;
}
已知a=10,b=4,c=5则执行k=f（f（a+c,b）,f（b,c））后，k的值是多少并写出详细过程。
K的值是5
14、McCathy函数定义如下：
当x>100时m（x）=x-10;
当x<=100时m（x）=m（m（x+11））;
编写一个递归函数计算给定x的m（x）值。
intm（intx）
{
inty;
if（x>100）return（x-100）;
else
{
y=m（x+11）;
return（m（y））;
}
}
15、设计一个算法在一个向量A中找出最大数和最小数的元素。
解
Voidmaxmin（A,n）
VectorA;
intn;
{
intmax,min,i;
max=A[0];min=A[0];
for（i=0;i<=n;i++）
if（A[i]>max）max=A[i];
elseif（A[i]printf（“max=%d,min=%d\n”,max,min）;
}
参考答案
三、算法理解
12．使用普里姆算法构造出如下图G的一棵最小生成树。
dist（1,2）=6;dist（2,5）=3;dist（5,6）=6;dist（6,4）=2;dist（4,1）=5;
dist（1,3）=1;dist（2,3）=5;dist（3,4）=5;dist（3,6）=4;dist（5,3）=6
四、设计算法
1.1.设有n项独立的作业{1,2,…,n},由m台相同的机器加工处理。
作业i所需要的处理时间为ti。
约定：
任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。
设计算法，并讨论是否可获最优解。
解：
对于处理机j，用S[j]表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号。
1）将作业按照t[1]≥t[2]≥……≥t[n]排序
2）S[1:
m]清零j←0//从第一个处理机开始安排
3）fori←1tondo//安排n个作业
j←jmodm+1//选下一个处理机
S[j]←S[j]+1;
P[j,S[j]]←i；
Repeat
2.2.设有n种面值为:
d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足
d1×Xi＋……dn×Xn=M，使得
Xi＋……Xn最小
请选择贪心策略，并设计贪心算法。
贪心原则：
每次选择最大面值硬币。
CU←M;i←1;X←0//X为解向量
WhileCU≠0do
X[i]←CUdivd[i]//X[i]为第i中硬币数
CU←CU-d[i]*X[i]
i←i+1;
repeat
3、3.有n个物品，已知n=7,利润为P=（10,5,15,7,6,18,3），重量W=（2,3,5,7,1,4,1），背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。
定义结构体数组G，将物品编号、利润、重量作为一个结构体：
例如G[k]={1,10,2}
求最优解，按利润/重量的递减序，有
{5,6,1,6}{1,10,2,5}{6,18,4,9/2}{3,15,5,3}{7,3,1,3}{2,5,3,5/3}{4,7,7,1}
算法
procedureKNAPSACK（P，W，M，X，n）
//P（1：
n）和W（1；n）分别含有按
P（i）/W（i）≥P（i+1）/W（i+1）排序的n件物品的效益值
和重量。
M是背包的容量大小，而x（1：
n）是解向量//
realP（1：
n），W（1：
n），X（1：
n），M，cu；
integeri，n；
X←0//将解向量初始化为零//
cu←M//cu是背包剩余容量//
fori←1tondo
ifW（i）>cuthenexitendif
X（i）←1
cu←cu-W（i）
repeat
endGREEDY-KNAPSACK
根据算法得出的解：
X=（1,1,1,1,1,0,0）获利润52，而解
（1,1,1,1,0,1,0）可获利润54
因此贪心法不一定获得最优解。
4．4.设计只求一个哈密顿环的回溯算法。
Hamiltonian（n）
{k←1;x[k]←0;
Whilek>0do
x[k]←x[k]+1;
whileB（k）=falseandx[k]≤ndo
x[k]←x[k]+1;repeat
Ifx[k]≤nthen
ifk=nthen{printx;return}
else{k←k+1;x[k]←0;}endif
elsek←k-1
endif
repeat
end
procedureB（k）
{G[x[k-1],x[k]]≠1thenreturnfalse;
fori←1tok-1do
ifx[i]=x[k]thenreturnfalse;endif
repeat
returntrue;
}
5．利用对称性设计算法，求n为偶数的皇后问题所有解。
procedureNQUEENS1（n）
a←0//计数器清零
X
（1）←0；k←1//k是当前行；X（k）是当前列//
Whilek>0do//对所有的行执行以下语句//
1）{X（k）←X（k）+1//移到下一列//
WhileX（k）≤nandnotPLACE（k）do
2）X（k）←X（k）十l
ifX（k）≤n
thenifk=n/
then
{print（X），a←a+1//找到一个解计数器a加1//
ifa=n/2thenreturn//找到n/2个解算法结束
3）else{k←k+1；X（k）←0；}
4）elsek←k－1//回溯//
}
endNQUEENS
升级会员 