填空题共

西南科技大学试题单（A）

计算机学院:课程名称:《算法分析与设计》课程代码: 14314025命题单位:软件教研室

学院：________ 专业班级：_______学号：□□□□□□□□ 命题共2页第1 页

一、填空题(共 18分)

1．算法的五个重要特性是：________、_________、_________、_________、_________。 2．采用二分检索算法从以下数据7，10，17，19，23，54，73中检索数据8需要划分___次。

3．用贪心方法求解背包问题的约束条件是：_____________________________。

23

4．计算时间O(1)，O(logn) ，O(n) ，O(nlogn) ，O(n) ，O(n)的升序排列为：________。 5．在利用回溯法求解问题时都要求所有的解满足一组综合约束条件，这些约束条件可分为两种类型__________、___________。

二、计算题

1．在下列数据上模拟快速排序过程。（12分） （40，50，55，60，65，40） 2．有以下5个作业，他们的效益值和期限分别为（p1,p2,p3,p4,p5）=(3,5,20,18,6)，（d1,d2,d3,d4,d5）=（1，2，3，1，2），利用贪心算法求解改作业排序问题的最优解。（写清楚关键步骤）（13分） 3、已知有如下多段图，求从源点1到汇点12的最短路径。（写出求解步骤）（15分）

4．已知有物品5个，物品的重量分别为（w1,w2,w3,w4,w5）=(10,15,20,25,30)，效益值分别为（p1,p2,p3,p4,p5）=(20,21,30,35,30)，背包可承受的重量M=45。

4 2 6 3 1 4 4 4 8 3 3 2 5 7 6 6 3 9 9 4 10 12 7 5 3 3 11 5 8

（1）如果装包时可以将某一物品的一部分装包，利用贪心方法求解获得最优效益值的装包策略。（12分） （2）如果装包时某一物品要么将物品全部装包，要么不装，利用动态规划方法求解获得最优效益值的装包策略。（15分）

5．一个由设备D1,D2,D3串联成的三级系统，每一级可以由多台同一设备组成。每台设备的成本分别为15元，25元，30元，可靠性分别为0.7，0.8，0.9。若总投资不超过105元，求解此时系统的最佳构造和可靠性。（15分）

本文来源：https://www.bwwdw.com/article/gekt.html