中科院自动化研究所算法设计与分析2015年考博真题考博试题博士研究生入学考试试题
1/4 中国科学院自动化研究所 2015 年招收攻读博士学位研究生入学考试题 考试科目: 算法设计与分析 (共 4 页,6 个大题,满分 100 分,时间为 3 个小时) 说明:算法设计可以用类程序语言描述。 1. 完成下列各题 (本题包括 6 个小题,满分 40 分): (1) 希尔排序(Shell’s Sort)又称缩小增量排序。现有如下 10 个关键字: 49,38,65,97,76,13,27,49,55,4 请写出每一趟希尔排序的结果,并说明希尔排序算法的时间复杂度。 (本小题满分 7 分) (2) 有如下三元多项式: 请用表达式描述该多项式的广义表表示,并设计该多项式的广义表存储结构。 (本小题满分 7 分) (3) 图 1 是一个有向图。请分别画出从顶点 V1 出发其深度优先搜索和广度优 先搜索的生成森林。 (本小题满分 6 分) 图 1. 有向图 图 2. 一个二叉树 (4) 图 2 是一棵二叉树,请给出按后序周游该树的结点序列,并画出该二叉树 的中序穿线二叉树存储表示。 (本小题满分 7 分) A B C D G H I FE V1 V4 V8 V2 V5 V7 V3 V6
上一篇文章: 辽宁大学广告学理论与实务2014年考研真题考研试题 下一篇文章: 中科院自动化研究所数字信号处理2015年考博真题考博试题博士研究生入学考试试题 |