学海网

中国科学院自动化研究所2008年招收攻读博士学位研究生入学《算法设计与分析》考试题
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分）
......