算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
1
算法设计与分析试题
一、 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
2beg
221
323ad
821
2cfh
解:用V表示已经找到最短路径的顶点，V表示与V中某个顶点相邻接且不在121
V中的顶点;E表示加入到最短路径中的边，E为与V中的顶点相邻接且距离最1121
短的路径。【1分】
步骤 V V E E 1212
{a} {b} {} {ab} 1.
2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh} 8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上
每步2分】
结果:从a到h的最短路径为，权值为18。【1分】 abdfegh,,,,,,
求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a
循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点
对之间的最短路径。【2分】
二、 假设有7个物品，它们的重量和价值如下表所示。若这些物品
均不能被分割，且背包容量M,150，使用回溯方法求解此背包问题。
请写出状态空间搜索树。
1
物
A B C D E F G
品
重3365412
量 5 0 0 0 0 0 5
价1435343
值 0 0 0 0 5 0 0
解:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1,7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】
ax,11x,01ajx,12x,02aix,13
ax,03x,14x,04
ade
x,14x,0x,054
behx,15x,0x,065egcx,06x,07fQ1【状态空间搜索树及其计算过程17分，每个节点1分】
150115,7a( 4040305035190.625，，，，，,(1,1,1,1,,0,0)408
150115,7b. 4040305030177.5，，，，，,(1,1,1,1,0,,0)6012
c( 4040305010170，，，，,(1,1,1,1,0,0,1)
150105,3d. 4040303530167.5，，，，，,(1,1,1,0,1,,0)604
2
150130,1e. 4040503530175，，，，，,(1,1,0,1,1,,0)360
150130,f. 44040503510170.71，，，，，,(1,1,0,1,1,0,)357
g. 40405030160，，，,(1,1,0,1,0,1,0)
150140,2 h. 4040353010146.85，，，，，,(1,1,0,0,1,1,)357
150125,5i. 4030503530167.5，，，，，,(1,0,1,1,1,,0)6012
150145,1j. 4030503530157.5，，，，，,(0,1,1,1,1,,0)6012
在Q处获得该问题的最优解为，背包效益为170。即在背包中装入(1,1,1,1,0,0,1)1
物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】
()k三、 已知，k=1，2，3，4，5，6，r=5，r=10，r=3，Aa,()123kijrr*ii，1
r=12，r=5，r=50，r=6，求矩阵链积A×A×A×A×A×A的最佳1234564567
求积顺序。(要求:给出计算步骤)
解:使用动态
规划
污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文
算法进行求解。
求解矩阵为:【每个矩阵18分】
1 2 3 4 5 6 1 0 150 330 405 1655 2010 2 0 360 330 2430 1950 3 0 180 930 1770 4 0 3000 1860 5 0 1500 6 0
1 2 3 4 5 6 1 0 1 2 2 4 2 2 0 2 2 2 2 3 0 3 4 4 4 0 4 4 5 0 5 6 0
因此，最佳乘积序列为(AA)((AA)(AA))，共执行乘法2010次。【结论2123456
分】
3
四、回答如下问题:
(1) 什么是算法,算法的特征有哪些,
(2) 什么是P类问题,什么是NP类问题,请描述集合覆盖问题
的近似算法的基本思想。
解:(1)算法是解决某类问题的一系列运算的集合【2分】。具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出【8分】。
(2)用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题【2分】。用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。【2分】
集合覆盖问题的近似算法采用贪心思想:对于问题
，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。【6分】
五、排序和查找是常用的计算机算法。按照要求完成以下各题:
(1) 对数组A={15，9，115，118，3，90，27，25，5}，使用合
并排序方法将其排成递减序。
(2) 若改变二分搜索法为三分搜索法，即从一个递减序列A中
nnn寻找元素Z，先与元素比较，若，则在前面个[]A[]ZA,[]333
2nn元素中寻找Z;否则与比较，总之使余下的序列为个A[][]33
元素。给出该方法的伪代码描述。
(3) 使用上述算法对(1)所得到的结果搜索如下元素，并给出
搜索过程:118，31，25。
解:(1)第一步:15 9 115 118 3 90 27 25 5
第二步:15 9 118 115 90 3 27 25 5
第三步:118 115 15 9 90 27 25 3 5
第四步:118 115 90 27 25 15 9 3 5
第五步:118 115 90 27 25 15 9 5 3【5分，每步1分】 (2)输入:递减数组A[left:right]，待搜索元素v。【1分】
4
输出:v在A中的位置pos，或者不在A中的消息(-1)。【1分】 步骤:【8分】
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
first=left+(right-left+1)/3;
second=left+(right-left+1)/3*2;
if (v==A[first]) return first;
else if (v>A[first]) right=first-1;
else if (v==A[second]) return second;
else if (v>A[second]) {left=first+1;right=second-1;}
else left=second+1;
}
return -1;
}
)搜索118:118>27，所以right,3;118>115，所以right,1;118,118，(3
找到。【2分】
搜索31:31>27，所以right,3;31<90，所以left=4，结束，未找到。【2分】
:9<25<27，所以left=5，right=6;25,25，找到。【1分】 搜索25
六、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M,150，如果使用贪心方法求解此背包问题，请回答:(20分)。
(4) 对各个物品进行排序时，依据的标准都有哪些,
(5) 使用上述标准分别对7个物品进行排序，并给出利用各个
顺序进行贪心求解时获得解。
(6) 上述解中哪个是最优的,
物
A B C D E F G
品
重3365412
5
量 5 0 0 0 0 0 5
价1435343
值 0 0 0 0 5 0 0
解:(1)标准:重量、价值和单位价值。【3分，每个1分】
(2)使用重量从小到大:FGBAEDC。得到贪心解为:FGBAE全部放入，而D放入20%，得到价值为165。【5分】
使用价值从大到小:DFBEGCA，得到贪心解为:DFBE全部放入，而G放入80%，得到价值为:189。【5分】
使用单位价值从大到小:FBGDECA，得到贪心解为:FBGD全部放入，而E放入87.5%，得到价值为190.625。【5分】
(3)显然使用单位价值作为标准得到的是最优解。【2分】
七、多段图问题:设G,(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集V:，其中，V和V分别只有一1,,iki1k个顶点s(称为源)和一个顶点t(称为汇)，图中所有的边(u,v)，
，。求由s到t的最小成本路径。(25分) uV,vV,ii，1
(7) 给出使用动态规划算法求解多段图问题的基本思想。
(8) 使用上述方法求解如下多段图问题。
V1V2V3V4V5
24669225943477st17310212113
451112
861185
解:(1)基本思想:设P(i,j)是从Vi中的节点j到汇点t的最小成本路径，Cost(i,j)是其成本。则Cost(i,j)=min{c(j,h)+Cost(i+1,h)|hV,(j,h)E},,。边界条i+1
6
件是(1)若h=t，则Cost(h,t),0;(2)Cost(k-1,j),c(j,t)。【10分】 (2)求解过程可以表示为:【6分，每个节点0.5分】
V1V2V3V4V5
7,77,104,12246692259,6942,123416,2/377st1731021218,81135,104511121,1215,8
8611857,10/11
其中每个节点标示的序偶(p,q)中，p表示节点到t的成本，q表示后继节点的编号。从而，最优路径为:1,2,7,10,12和1,3,6,10,12，成本为16。【4分】
八、设x、x、x是一个三角形的三条边，而且x+x+x=14。请问有123123多少种不同的三角形,给出解答过程。
解:由于x、x、x是三角形的三条边，从而x+x>x，|x-x|max) max=A[i];
if (A[i] bestw) bestw = wt;
// 加入活结点队列
if (i < n) Q.Add(wt);
}
// 检查右儿子结点
if (Ew + r > bestw && i < n)
Q.Add(Ew); // 可能含最优解
Q.Delete(Ew); // 取下一扩展结点
解:斜线标识的部分完成的功能为:提前更新bestw值;
这样做可以尽早的进行对右子树的剪枝。具体为:算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
10
为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。
十二、简要回答下列问题:
1.算法重要特性是什么, 算法分析的目的是什么,算法的时间复杂性与问题的什么因素相关,
2.什么是哈密顿环问题,用回溯法求解哈密顿环，如何定义判定函数,
答:1.(1)确定性、可实现性、输入、输出、有穷性，(2)分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法，(3)算法的时间复杂性与问题的规模相关，是问题大小n的函数;
2.(1)哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置，(2)当前选择的节点X[k]是从未到过的节点,即X[k]?X[i](i=1,2,„,k-1)，且C(X[k-1], X[k])??，如果k=-1，则C(X[k], X[1]) ??。
十三、简要回答下列问题:
1. 快速排序的基本思想是什么。
2. 什么是直接递归和间接递归,消除递归一般要用到什么数据结
构,
答:1.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。
2..在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，
11
Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。
十四、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
2 5
1 3 6 8
4 7
各边的代价如下:
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
解: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=4 D[7]=8
Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}
= min{1+ 5, 2+4}=6 D[4]=6 Cost(2,3)= min{C(3，6)+ Cost(3,6) }
= min{4+5}=9 D[3]=5 Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}
= min{8+5, 4+6}=10 D[2]=7
Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+
12
Cost(2,4)}
= min{3+10, 5+9,2+6}= 8 D[1]=4
1?4?6?8
十五、写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7) 解:写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=()
1、 48,12,61,3, 5,19,32,7
2、48,12 61,3 5,19 32,7
3、 48,61, 12,3 19,32，5,7
4、 61,32 3,5
、 61 3 5
十六、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。
A=(65,70,75,80,85,55,50,2) 解:第一个分割元素为65
(1) (2) (3) (4) (5) (6) (7) (8) i p
65 70 75 80 85 55 50 2 2 8
65 2 75 80 85 55 50 70 3 7
65 2 50 80 85 55 75 70 4 6
65 2 50 55 85 80 75 70 4 6
55 70 75 80 85 65 50 2
十七、一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=，车加满油后可行驶m公里，出发之前d,d,？,d,s12n
13
汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少,
给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优
化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。
解:贪心选择策略:从起点的加油站起每次加满油后不加油行驶尽可能远，直
至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。
算法 MINSTOPS
输入:A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶
的公里数m，存储各加油站离起点A的距离的数组d[1..n]。
输出:从A地到B地的最少加油次数k以及最优解x[1..k](x[i]表示第i
次加油的加油站序号)，若问题无解，则输出no solution。
d[n+1]=s; //设置虚拟加油站第n+1站。
for i=1 to n
d[i]>m then if d[i+1]-
output “no solution”; return //无解，返回
end if
end for
k=1; x[k]=1 //在第1站加满油。
s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离
i=2
while s1s1 then //以汽车的当前油量无法到达第i+1站。
k=k+1; x[k]=i //在第i站加满油。
s1=d[i]+m //刷新s1的值
end if
i=i+1
end while
output k, x[1..k]
MINSTOPS
最坏情况下的时间复杂性:Θ(n)
14
浙公网安备 33021202002483