PDF《中国科学院自动化研究所 2018 年招收攻读博士学位研究生入...》

1 中国科学院自动化研究所

2018 年招收攻读博士学位研究生入学考试题 考试科目: 算法设计与分析 (共2页,6 个大题,满分

100 分,时间为

3 个小时) 1.

完成下列各题 (本大题满分

30 分) : (1) 设n为正整数.请确定下面的程序段中前置以记号@的语句的执行频度: x = 91;

y = 100;

while ( y >

0 ) { @ if ( x > 100) { x - = 10;

y --;

} else x++;

} (本小题满分

5 分) (2) 请画出图

1 所示的树对应的二叉树: (本小题满分

5 分) 图1(3) 请将下面的递归过程改写为非递归过程: void test(int &sum) { int x;

scanf(x);

if (x ==0 ) sum = 0;

else {test(sum);

sum += x;

} printf(sum);

} (本小题满分

7 分) (4) 写出如下算法:在带头结点的双链循环线性表 L 中第 i 个位置之前插入元 素e,i 的合法值为:1 ? i ? 表长+1. (本小题满分

6 分) (5) 图2为有向图,请给出该图所有 可能的拓扑有序序列. (本小题满分

7 分) 图2BACDEFGHIJK12356422. 请设计一个算法,将按行优先原则顺序存储的二维数组 Ann 转置(aij 与aji 交换) .要求转置结果仍占用原来的存储空间. (本题满分

10 分) 3. 下面的两个邻接矩阵 G1.arcs 和G2.arcs 分别对应图 G1 和图 G2.请完成下 列问题: (1) G1 和G2 分别是有向图还是无向图?分别画出 G1 和G2. (2) 请写出有向图中顶点 v1 的出度和入度、无向图中顶点 v1 的度. (3) 请写出构造一个具有 n 个顶点和 e 条边的无向图的算法,并写出时间复 杂度. (本题满分

15 分) 4. 已知线性表 A 和B中的元素按值非递减有序排列,如:A=(3, 5, 8, 11),B=(2, 6, 8, 9, 11, 15, 20).请设计算法完成如下操作:将A和B归并为一个新的线 性表 C, C 中的数据元素仍按值非递减有序排列, 且不存在值相等的多余元 素.如在题中的例子,C=(2, 3, 5, 6, 8, 9, 11, 15, 20). (本题满分

15 分) 5. 已知长度为

12 的表:( Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec). (1) 若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表 进行折半查找成功的平均查找长度. (2) 按表中元素顺序构造一棵平衡二叉排序树,并求在等概率的情况下查找 成功的平均查找长度. (本题满分

15 分) 6. 一个给定序列的子序列是该序列中删除若干元素后得到的序列.给定两个序 列X和Y,若序列 Z 既是 X 的子序列,又是 Y 的子序列,则称 Z 是序列 X 和序列 Y 的公共子序列(Common sub-sequence) .如:X={A, B, C, B, D, A, B},Y={B, D, C, A, B, A},那么,其最长公共子序列 Z={B, C, B, A}.请设 计动态规划算法找出任意序列 X 和Y的一个最长公共子序列. (本题满分

15 分)