西南科技大学试题单(J).doc

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