西南科技大学试题单（J）
计算机学院:课程名称:《算法分析与设计》课程代码: 14314025命题单位:软件教研室
学院：________ 专业班级：_______学号：□□□□□□□□ 命题共2页第1 页
1、已知元素a，b，…，h依次有概率0.1，0.2，0.05，0.1，0.3，0.05，0.15，0.05，其余情况的概率为0，请建立其最优二叉搜索树。（10分）
2、用动态规划算法求下面网络的最短路：（10分）
2 4 1 5 3 8 5 7 6 4 9 6 6 8 9 4 5 5 7 3、有0-1背包问题如下：
n=6，c=20，P=（11，8，15，18，12，6），W=（5，3，2，10，4，2）。 试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。（12分）
4、试证明若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列，则用贪心算法可以找出其最优解。（12分）
5、考虑下面的用最少硬币个数找出n分钱的问题。（18分）
1）当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心算法找出n分钱，并证明算法能够产生一个最优解。
2）假设可使用的硬币面值是c0，c1，…，ck，其中，c是一个正整数且c>1，k≥1。证明在这种情况下贪心算法总能产生最优解。 3）给出一个贪心算法不能产生最优解的硬币面值组合。
6、在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。（12分）
7、设G是一个有n个顶点的有向图，从顶点i出发的边的最小费用记为min(i)，证明图G的所有前缀为x[1..i]的旅行售货员回路的费用至少为
?a?xj?2ij?1（12分） ，xj???min?xj?，其中，a(u，v)是边(u，v)的费用。
j?in
8、已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。（14分）
a b