1/3 中国科学院自动化研究所 2014 年招收攻读博士学位研究生入学考试题 考试科目： 算法设计与分析 （共 3 页，6 个大题，满分 100 分，时间为 3 个小时） 说明：设计算法可以用类程序语言描述。 1. 完成下列各题 （本题包括 7 个小题，满分 40 分）： (1) 下面是一个包含 11 个元素的有序表（关键字即为数据元素的值）： （5，13，19，21，40，56，64，75，88，88，92） 若利用折半查找方法查找关键字为 21 的数据元素，请写出其查找过程， 并给出一般情况下折半查找的平均查找长度。（本小题满分 6 分） (2) 有如下数据元素： 49，38，65，97，76，13，27，49 若使用直接插入排序方法对其排序，请写出其排序过程，并给出直接插入 排序的时间复杂度。（本小题满分 6 分） (3) 已知某二叉树的前序序列为：A B C D E F G 其中序序列为： C B E D A F G 请画出整棵二叉树，并说明具有 n 个结点的不同形态的二叉树的数目。 （本小题满分 6 分） (4) 请写出“双亲表示法”存储树的数据结构。 有图 1 所示的树，请画出该树的双亲表示法 存储结构。 （本小题满分 6 分） 图 1 R A C D B E G H K F
您现在的位置： 
