算法设计与分析试题2013A

诚信保证

本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号：

西北工业大学考试试题（卷）

2012－2013学年第2 学期

开课学院 计算机学院 课程 算法设计与分析 学时 48

2. 命题教师和审题教师姓名应在试卷存档时填写。 共 2 页 第 1 页

西北工业大学命题专用纸 (1) 编写算法求解图中从顶点 0 到其它各顶点的最短路径(10 分) ; (2) 编写算法实现求解 Fibonacci 数(10 分) ; (3) 编写快速排序算法对 21、25、49、25、16、8 按照递增顺序排序，并给出排序过程(10 分) ; (4) 编写算法求解装载问题，问题描述如下： 有两艘船，载重量分别是 c1、 c2,有 n 个集装箱，集装箱 i 的重量是 wi (i=1…n),且所有集装箱 的总重量不超过 c1+c2。确定是否有可能将所有集装箱全部装入两艘船(10 分) 。

三、描述题(12 分) (1) 请简述动态规划算法的设计步骤(6 分) ; (2) 请简述回溯法的基本思想(6 分) ; 四、设计题(18 分) (1) n 个人均需要接受一项服务，第 i 个人需要服务的时间是 ti(0<i<=n),请设计一种算法，求出一 个排列顺序，使每个人等候时间的总和最小(8 分)。 (2) 在 3×3 的棋盘，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字，不同棋子上标的数字不 相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个 初始状态 S0 和一个目标状态 Sg,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤 (10 分) 。 2 1 7 S0 2 1 7 Sg 6 8 3 4 5 6 8 3 4 5

教务处印制

共 2 页

第 2 页