中国科学院自动化研究所20082008年招收攻读博士学位研究生入学考试题
考试科目：算法设计与分析
（共两页，6个大题，满分100分，时间为3个小时）1完成下列各题本题满分40分，每小题8分：（1）请写出算法，实现如下功能：对于输入的任意一个非负10进制整数N，打印出与其等值的8进制数。（2）请写出实现以双向线索链表为存储结构时，对二叉树进行遍历的算法。（3）请设计一个算法，删除字符串S中从第i个位置开始连续的
个字符，估计算法的执行时间。（4）请用图示说明用直接插入排序对以下序列：263335291857266进行排序的过程，包括每次的比较和交换次数。（5）对于给定序列：813172644568897
如果用二分法（折半查找法）检索88，请问：分几步可以找到88？请给出每一步中范围指针low（低位）和high（高位）及其中间位置指针mid的取值。2给定含有
个节点的带权有向图G，请写出求每一对顶点之间最短路径的算法，并说明算法的时间复杂度。（本题满分10分）3请写出迷宫求解算法，即设计算法求迷宫中从入口到出口的所有路径。（本题满分10分）4若M是m1×
1矩阵，N是m2×
2矩阵，
1m2，矩阵QM×N。写出下列两种情况下矩阵相乘的算法：（1）M和N为非稀疏矩阵并用二维数组存储；（2）M和N为稀疏矩阵并用三元组表存储非零值。（本题满分12分）
1
f5
假设集合S有
个元素，m个形如xy（xy∈S）的等价偶对确定了等价关系R，请设计算法求S的划分，即求S的所有等价类。（本题满分13分）
6
设有
种不同面值的硬币，各硬币的面值存储在数组T1
中。现要用这些面值的硬币来找零钱。可以使用的各种面值的硬币个数不限。（1）当只用前i种硬币面值T1T2LTi时（1≤i≤
），可找出钱数j的最少硬币个数记为Cij。若只用前i种硬币面值找不出钱数j时，记Cij∞。请给出计算Cij的递归表达式及其初始条件。（2）请设计一个动态规划算法，对1≤j≤L计算出所有的C
j。算法中只允许使用一个长度为L的数组。（本题满分15分）
2
fr