2008《算法设计与分析》考博试题.doc

中国科学院自动化研究所2008年招收攻读博士学位研究生入学考试题考试科目： 算法设计与分析 （共两页，6个大题，满分100分，时间为3个小时）1. 完成下列各题 [本题满分40分，每小题8分]：（1） 请写出算法，实现如下功能：对于输入的任意一个非负10进制整数N，打印出与其等值的8进制数2） 请写出实现以双向线索链表为存储结构时，对二叉树进行遍历的算法3） 请设计一个算法，删除字符串S中从第i个位置开始连续的n个字符，估计算法的执行时间4） 请用图示说明用直接插入排序对以下序列：26 33 35 29 18 57 2 66进行排序的过程，包括每次的比较和交换次数5） 对于给定序列：8 13 17 26 44 56 88 97 如果用二分法（折半查找法）检索88，请问：分几步可以找到88？请给出每一步中范围指针low（低位）和high（高位）及其中间位置指针mid的取值2. 给定含有n个节点的带权有向图G，请写出求每一对顶点之间最短路径的算法，并说明算法的时间复杂度本题满分10分）3. 请写出迷宫求解算法，即设计算法求迷宫中从入口到出口的所有路径。

本题满分10分）4. 若M是矩阵，N是矩阵，，矩阵写出下列两种情况下矩阵相乘的算法：（1） M和N为非稀疏矩阵并用二维数组存储；（2） M和N为稀疏矩阵并用三元组表存储非零值本题满分12分）5. 假设集合S有n个元素，m个形如（）的等价偶对确定了等价关系R，请设计算法求S的划分，即求S的所有等价类本题满分13分）6. 设有n种不同面值的硬币，各硬币的面值存储在数组中现要用这些面值的硬币来找零钱可以使用的各种面值的硬币个数不限1） 当只用前i种硬币面值时（），可找出钱数j的最少硬币个数记为若只用前i种硬币面值找不出钱数j时，记请给出计算的递归表达式及其初始条件2） 请设计一个动态规划算法，对计算出所有的算法中只允许使用一个长度为L的数组本题满分15分）。