《算法设计与分析》试卷及答案(2)
时间:2025-04-03
时间:2025-04-03
算法设计与分析考试复习试卷
C、最短路:1→4→6→9,耗费:12
D、最短路:4→6→9→10,耗费:13
二、填空(每空2分,共20分):
1、快速排序法的基本思想是重新排列关键字,把一个文件分成两个文件,使得第一个文件
中所有元素均小于第二个文件中的元素;然后再对两个子文件进行同样的处理。其算法如下:
算法(快速排序是一种递归算法):
Qsort(L,k,m)//L待排序序列,k、m是分类文件之首、末关键字(1,n)
Begin
if k < m then
begin
Split(L,k,m,i)//将L分组
Qsort(L,k,i-1)
Qsort(L,i+1,m)
end
end
Split(L,k,m,i) //将序列L进行分组
Begin
i=k,j=m,x=L(k)
while __________ do
begin
if j<>i then L(i)=L(j),i=i+1
while (L(i)<x) and (i<>j) do i=i+1
if i<>j then L(j)=L(i),j=j-1
end
__________
End
2、有设备更新问题如下所示,
五年内收益最大的设备更新策略的最大收益为__________。
3、已知作业队列及其所需要运行的时间为t1=2, t2= 5, t3= 8, t4= 1, t5= 5, t6= 1),
在三台处理器上运行,按贪心法调度总运行时间为__________,最佳运行时间为__________。
4、吉普车总装油量为500L,耗油量为1L/里,要自行设置燃料库穿越1000里的沙漠,使
用倒推法首先应共设置__________个站点,第一个距离起点__________里,存放__________L油,总耗油量达到最少,即_________L。
三、应用及问答题:
上一篇:不断提高自身素质