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

《2008《算法设计与分析》考博试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国科学院自动化研究所2008年招收攻读博士学位研究生入学考试题考试科目：算法设计与分析（共两页，6个大题，满分100分，时间为3个小时）1.完成下列各题[本题满分40分，每小题8分]：（1）请写出算法，实现如下功能：对于输入的任意一个非负10进制整数N，打印出与其等值的8进制数。（2）请写出实现以双向线索链表为存储结构时，对二叉树进行遍历的算法。（3）请设计一个算法，删除字符串S中从第i个位置开始连续的n个字符，估计算法的执行时间。（4）请用图示说明用直接插入排序对以下序列：263335291857266进行排序的过程，包括每次的比较和交换次数。（5）对于给定序列：813172644

2、568897如果用二分法（折半查找法）检索88，请问：分几步可以找到88？请给出每一步中范围指针low（低位）和high（高位）及其中间位置指针mid的取值。2.给定含有n个节点的带权有向图G，请写出求每一对顶点之间最短路径的算法，并说明算法的时间复杂度。（本题满分10分）3.请写出迷宫求解算法，即设计算法求迷宫中从入口到出口的所有路径。（本题满分10分）4.若M是矩阵，N是矩阵，，矩阵。写出下列两种情况下矩阵相乘的算法：（1）M和N为非稀疏矩阵并用二维数组存储；（2）M和N为稀疏矩阵并用三元组表存储非零值。（本题满分12分）1.假设集合S有n个元素，m个形如（）的等价偶对确定了等价关

3、系R，请设计算法求S的划分，即求S的所有等价类。（本题满分13分）2.设有n种不同面值的硬币，各硬币的面值存储在数组中。现要用这些面值的硬币来找零钱。可以使用的各种面值的硬币个数不限。（1）当只用前i种硬币面值时（），可找出钱数j的最少硬币个数记为。若只用前i种硬币面值找不出钱数j时，记。请给出计算的递归表达式及其初始条件。（2）请设计一个动态规划算法，对计算出所有的。算法中只允许使用一个长度为L的数组。（本题满分15分）