2010-2011学年度第一学期08级

武汉大学计算机学院

2010-2011学年度第一学期08级

《算法设计与分析》期末考试试题（A卷）

姓名： 学号：

1.（12分）考虑如下排序算法BUBBLESORT:

（1）（2分）执行该算法，元素比较的最少次数是多少？什么时候达到最小值？

（2）（2分）执行该算法，元素比较的最多次数是多少？什么时候达到最大值？

（3）（2分）执行该算法，元素赋值的最少次数是多少？什么时候达到最小值？

（4）（2分）执行该算法，元素赋值的最多次数是多少？什么时候达到最大值？

（5）（2分）用O符号和 表示算法BUBBLESORT的运行时间。

（6）（2分）可以用 符号来表示算法的运行时间吗？为什么？

2.（13分）已知数组A[1 8]={4,5,2,9,8,7,1,3},

（1）（8分）请用HEAPSORT（堆排序）算法将其按升序排列，详细给出每一个具体步骤。

（2）（5分）元素比较的总次数是多少？详细给出求解过程。

3．（10分）令{1}，{2}，{3} {8}是n个单元素的集合，每个集合由一棵仅有一个节点的树表示。用带有按秩合并和路径压缩措施的UNION-FIND算法来画出每一步的树表示并写出每一步得到的树中每个节点的秩。它们从以下每一个合并和寻找导出：

UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),UNION(1,3),UNION(5,7),FIND(1),UNION(1,5),FIND(1)。

4．（15分）设当元素个数小于6个时，直接求解。用算法SELECT在如下数组A[1 26]中找出第19小的元素，要求写出详细的过程:

{8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,10}

5．（15分）最长公共子序列问题：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1， ，xm-1”，序列Y=“y0，y1， ，yk-1”是X的子序列，存在X的一个严

格递增下标序列<i0，i1， ，ik-1>，使得对所有的j=0，1， ，k-1，有xij=yj。例如，

X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。最长公共子序列问题就是给定两个字符序列，设A=“a0，a1， ，am-1”，B=“b0，b1， ，bn-1”，求二者长度最长的公共子序列。

最长公共子序列问题一般采用动态规划的方法进行求解，试回答下述问题：

（1）（3分）试写出动态规划算法的递推式子，并分析你所得到递推方程的依据；

（2）（2分）动态规划算法所求解问题具有最优子结构的性质，分析第（1）问中得到的递推式子，指出两个长度是n和m的字符串所包含的子问题的个数，并说明动态规划方法求解该问题为什么有效的原因；

（3）（5分）给定两个字符串A={xyxxzxyzxy}和B={zxzyyzxxyxxz}，写出动态规划方法求解这两个字符串最长公共子序列的长度的过程；

（4）（5分）用伪语言写出你的动态规划算法的流程，并要求你的算法不仅能找到最长公共子序列的长度，并且能够输出任意一个最长公共子序列。

6．（10分）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这棵树叫最小生成树。给定下述带权无向连通图，详细写出利用Kruskal算法求解该实例的过程。

7.（10分）什么是P类问题？什么是NP类问题？什么是NP完全（简记为NPC）问题？什么是NP难（简记为NPH）问题？这四类问题之间的关系是什么？

8.（15分）给定一个无向连通图，一个哈密顿回路是指一条沿着图中的边环形的路径，它访问图中每个顶点一次并且返回到它开始的位置。设计一个回溯算法求解给定无向连通图中的一条哈密顿回路。

武汉大学计算机学院

2010-2011学年度第一学期08级

《算法设计与分析》期末考试试题（B卷）

姓名： 学号：

1. （10分）考虑算法COUNT，它的输入是正整数n.

(1) （2分）当n为2的幂时，第5步执行的最大次数是多少？为什么？

(2) （2分）当n为3的幂时，第5步执行的最大次数是多少？为什么？

(3) （2分）用O符号表示的算法的时间复杂性是怎样的？

(4) （2分）用 符号表示的算法的时间复杂性是怎样的？

(5) （2分）O和 哪个符号更适合用来表示算法的时间复杂性？

2．（15分）设A[1 19] 是一个有19个整数的数组，假设对这一数组用算法MAKEHEAP。 (a) 调用几次SIFT-DOWN过程？请解释。

(b) 这种情况下元素交换的最大次数是多少？为什么？

(c) 给出一个19个元素的数组，它们需要如上所说的元素交换最大次数。

3．（10分）写出一个算法，将两个同样大小的最大堆合并成一个，并分析算法的时间复杂性。

4.（15分）用图示的方法详细说明算法MAJORITY对下列数组的运算的具体过程。

（1）{5,7,5,4,5}；（2）{5,7,5,4,8}；（3）{2,4,1,4,4,4,6,4}

5．（15分）矩阵链相乘问题：给定n个矩阵构成的一个链<A[1], A[2], ... , A[n]>，其

中i = 1, 2, ... , n，矩阵A[i]的维数为p[i-1]× p[i]，对乘积A[1]A[2]...A[n]以一种最小化标量乘法次数的方式进行运算的矩阵乘的顺序。矩阵链相乘问题一般采用动态规划的方法进行求解，试回答下述问题：

（1） （3分）试写出动态规划算法的递推式子，并分析你所得到递推方程的依据；

（2） （2分）动态规划算法所求解问题具有最优子结构的性质，分析第（1）问中得到

的递推式子，指出长度为n的矩阵链相乘所包含的子问题的个数，并说明动态规划方法求解该问题为什么有效的原因；

（3） （5分）给定5个矩阵：A1：5 × 10，A2：10 × 4，A3：4 × 6，A4：6 × 10，

A5：10 × 2，写出动态规划方法求解这5个矩阵链相乘最优标量乘法次数的过程；

（4） （5分）用伪语言写出你的动态规划算法的流程，并要求你的算法不仅能找到矩阵

链相乘最优标量乘法次数，并且能够输出矩阵乘的顺序。

6．（10分）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树。Kruskal算法的思路是：将图中边按其权值由小到大的次序顺序选取，若选边后不形成回路，则保留作为一条边，若形成回路则除去。依次选够(n-1)条边，即得最小生成树(n为顶点数)。请证明在带权无向图连通图中，Kruskal算法能正确找到最小生成树。

7．（10分）图的顶点k（k>2）着色问题是指使用k种颜色，对图上的顶点进行着色，使得无向图中任意两个相邻顶点都分配不同的颜色的着色方案问题。试证明图的k（k>2）着色问题是NP类问题。

8．（15分）设计一个回溯算法求解马周游问题：规定马走“日”字。在n×n个格点的棋盘的某一个位置放置一个中国象棋马，马走日字，求一条周游棋盘的路径，使得马能够从起始位置沿着该路径的每一个格点恰好走一次最后回到出发位置。

本文来源：https://www.bwwdw.com/article/3qt4.html