《算法设计与分析2014试题A卷》由会员分享，可在线阅读，更多相关《算法设计与分析2014试题A卷（2页珍藏版）》请在金锄头文库上搜索。
1、诚信保证本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考 场规则，诚实做人。 本人签字： 编号： 西北工业大学考试试题（卷）西北工业大学考试试题（卷）20132014 学年第 二 学期开课学院 计算机学院 课程 算法设计与分析 学时 32 考试日期 2014.6.30 考试时间 2 小时 考试形式 闭卷 考生班级学 号姓 名一、简答题（每小题一、简答题（每小题 8 8 分，共分，共 4040 分）分） 1.写出回溯算法的一般模式。 2.分治算法的基本思想是什么？ 3.什么是最优子结构性质？ 4.请简述广度优先搜索算法的基本思想。 5 简述分治法与动态规划算法的区别于共同点？ 二、算法设
2、计（二、算法设计（ 每题每题 1010 分分 共共 3030 分）分） 1.用贪心算法解决活动安排问题：设有待安排的 10 项活动，都要使用某一公共资源，每项活 动的开始时间和结束时间如下表所示：I12345678910开始时间309110112534结束时间861341312310592、请设计一个高效的算法实现计算 fibonacci 序列3、编写快速排序算法对 21、24、48、25、16、8 按照递增顺序排序，并给出排序过程三、应用题（三、应用题（ 每题每题 1515 分分 共共 3030 分）分） 1、最长公共子序列若给定的序列 X = x1,x2,xm,则另一序列 Z = z1,z
3、2,zk是 X 的子序 列是指存在一个严格递增下标序列i1,i2,ik使得对于所有的 j = 1,2,k 有 zj = xij。例如，序 列 Z = B,C,D,B是序列 X = A,B,C,B,D,A,B的子序列，相应的递增下标序列为2,3,5,7。 给定 2 个序列 X 和 Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。 问题表述：给定 2 个序列 X=x1,x2,xm和 Y = y1,y2,yn，找出 X 和 Y 的最长公共子序列。成 绩注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。 2. 命题教师和审题教师姓名应在试卷存档时填写。 共 2 页 第 1 页西北工业大学命题专用纸2、 最大整数最大整数设有 n 个正整数，将它们连接成一排，组成一个最大的多位整数。 例如：n=3 时，3 个整数 13，312，343，连成的最大整数为 34331213。 又如：n=4 时，4 个整数 7，13，4，246，连成的最大整数为 7424613。 输入：n N 个数 输出：连成的多位数教务处印制 共 2 页 第 2 页
