中国科学院自动化研究所
2006年招收攻读博士学位研究生入学统一考试试题 科目名称：算法设计与分析
考生须知：
1．本试卷满分为100分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

（共两页，六个大题，满分100分）
1.完成下列各题[25分]：
（1） 下列算法求一个十进制正整数在二进制表示中的二进制数字的个数：
Binary(n) /* n为十进制正整数 */
count← 1
while n > 1 do
count←count +1
n←
⎣⎦2/n
return count
请问该算法的循环次数大约是多少？n>1时，比较运算次数为多少？
（2） 请写一个递归函数计算二叉树的高度（只有一个根结点的二叉树的高度为1）。

（3） 从空的二叉树开始，根据字典顺序（注意，“he”< “toss”, “tea”< “teach”），严格按照A VL树（或“称平衡的二叉检索树”，“平衡的二
叉排序树”）插入算法，依次插入he、tea、teach、twin、hot、toss这
6个关键码。

请画出插入所有结点后的A VL树。

（4） 对于环状的链式队列，写出计算队列元素个数的程序。

（5） Fibonacci序列为0，1，1，2，3，5，8，13，21，…其中，每个元素是前两个元素之和。

请设计一个计算该序列任意元素的递归过程。

2.一个n个节点的有向图的传递闭包可以定义为一个n阶布尔矩阵T，使得当
第i 个顶点到第j 个顶点的路径长度为正时，T [i , j ]=1；否则，T [i , j ]=0（n j i ≤≥,1）。

请设计一个算法来求该传递闭包，并分析你设计的算法的时间复杂度。

[10分]
3. 给定由n 个整数（可能为负整数）组成的序列n a a a ,,,21L ，给出动态规划算
法求该序列形如∑=j
i k k a 的子段和的最大值，并说明算法的时间代价和空间代
价。

当所有整数均为负整数时定义其最大子段和为0。

依此定义，所求的最优值为}max ,0max{1∑=≤≤≤j i k k n j i a 。

例如，当)
2,5,13,4,11,2().,.,,(654321
−−−−=a a a a a a 时，最大子段和为204
2=∑=k k a 。

[15分]
4. 给定n 种物品和一个袋子，物品i 的重量是w i ，其价值为v i ，袋子的容量为
c 。

物品i 装入袋子时可以选择物品i 的一部分，而不一定全部装入袋子。

请问：如何选择装入袋子的物品，使得装入袋子中物品的总价值最大？要求：（1）给出该问题的形式化描述；（2）给出算法描述；（3）给出算法的时间复杂度。

[15分]
5. 一个长度为n 的有序序列加入k 个新元素（k << n ）
，假设这k 个新元素随机地分布于整个序列中。

请编写算法对插入新元素后的序列排序，并分析该算法的时间代价和空间代价。

[15分]
6. 设A 和B 是两个字符串。

对于字符串可以执行如下操作：
（1） 删除一个字符；（2）插入一个字符；（3）将一个字符替换成另外一个
字符。

利用上面的三种操作可以将字符串A 转换成字符串B 。

这种转换所需要的最少的字符串操作次数称为字符串A 到B 的编辑距离，记为d(A, B)。

请设计一个算法，对任意给定的两个字符串A 和B ，计算出他们的编辑距离d(A, B)。

[20分]。