《算法设计与分析》试卷及答案(2)

时间: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。

三、应用及问答题:

《算法设计与分析》试卷及答案(2).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219