装订线－－－－班－级 ： 姓名： 学号： 2011-2012学年第二学期

天津商业大学信息工程学院《算法分析与设计》(课程)试卷

试卷来源：自拟 送卷人: 杨亮 打印：杨亮 田菊花 校对：杨亮

题 目 一 二 三 四 五 总 分 得 分 阅 卷

考试说明：本试卷适用于2011-2012学年度第二学期，软件工程专业，《算法分析与设计》 课程期末考试。考试试卷共5题，前四题是必答题，第五题为选答题，请在给出的四道 小题中选择一道作答,并用“О”勾选。考试时间110分钟，满分100分。要求其中的程 序要写清注释。祝大家好运。

本题得分 阅卷签字 一、分治策略相关问题（20分）

意大利数学家列昂纳多·斐波那契在《珠算原理》中记述了如下的问题：某人把一对兔子 放入一个四面被高墙围住的地方。假设每对兔子每月能生下一对小兔，而每对新生小兔 从第二个月开始又具备生育能力，请问：一年后应有多少对兔子。

每月的兔子对数形成了一个数列，由于此数列具有一些非常优美的性质，人们将这个数 列成为斐波那契数列。

1、请写出斐波那契数列的递推公式；（5分）

2、试用分治策略求解斐波那契数列的某一特定项，写出求解过程；（7分） 3、别分用树展开和主定理计算上面问题的时间复杂度。（8分）

1

本题得分 阅卷签字 二、动态规划相关问题（24分）

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列，公共子序列中长度最长的称为最长公共子序列。给定两个序列X={x1,x2,?,xm}和Y={y1,y2,?,yn}，找出X和Y的最长公共子序列（LCS）。 1、推到如何计算两个序列的最长公共子序列（写明推到过程）。（8分）

2、令X={ABAADEC}，Y={CAACEDC}，手动计算X与Y的最长公共子序列，并用矩阵的形式记录计算的过程及中间结果。（8分）

3、编写程序实现上面的计算过程（无需考虑输入输出，只需列出核心代码，并写明程序注释）（8分）

2

三、贪心策略相关问题（16分） 本题得分 阅卷签字

单元最短路径问题是指在一个带权有向图中，给定一个顶点，称为源，计算从源到其他各个顶点的最短路径长度。

1、简述Dijkstra算法的基本思想和步骤；（8分） 2、手动计算下图中以A为源，到各点的最短路径。（8分）

3

四、解空间搜索相关问题（20分） 本题得分 阅卷签字

八皇后问题是指要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有满足条件的解。 1、画图描述此问题的解空间的结构；（6分） 2、简述可用那些策略优化求解过程；（6分） 3、编程实现用解空间搜索方法求解八皇后问题。（8分）

4

本题得分 阅卷签字 五、选做题（20分）

1、有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。请描述算法的基本思想、步骤并用程序实现

2、给定一个整数组X={x1,x2,?,xm}和一个整数值M，希望可以在数组中找出所有满足p+q=M的数对（p，q），设计算法实现以上功能，描述算法的基本思想并用程序实现。 3、给定一个英文词典，任意给定一篇英文文章，请设计算法用尽量短的时间查找词典中的单词一共在这篇文章中出现了多少次（如果一个单词出现了多次，按照实际出现的次数计算），并用程序实现。

4、假设有一个各种字母组成的字符串，假设还有另外一个字符串，而且这个字符串

里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？并用程序实现算法。 比如，如果是下面两个字符串： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPOM

答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPOZ

答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

5