2016年中国科学院自动化研究所考博试题算法设计与分析

1中国科学院自动化研究所2016年招收攻读博士学位研究生入学考试试题考试科目：算法设计与分析（共2页，7个大题，满分100分，时间为3个小时）说明：算法设计可以使用类程序语言（伪代码）描述。1.完成下列各题（本题包括6个小题，满分30分）：(1)下列算法求一个十进制正整数在二进制表示中的二进制数字的个数：Binary(n)/*n为十进制正整数*/count1whilen1docountcount+12/nnreturncount请问该算法的循环次数大约是多少？n1时，比较运算次数为多少？(2)阅读下面的算法，写出针对图1中的二叉树执行该算法的结果。Statusfunction(BiTeeT,Status(*Visit)(TElemTypee)){StatusPrintElement(TElemTypee){printf(e);returnOK;}if(T){if(Visit(T-data))if(function(T-lchild,Visit))if(function(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//function(3)请设计一个递归函数，计算二叉树的高度（只有一个根结点的二叉树的高度为1）。-+/acfe*b-d2(4)对于环状的链式队列，请写出计算队列元素个数的算法。(5)Fibonacci序列为0，1，1，2，3，5，8，13，21，……其中，每个元素是前两个元素之和。请设计一个计算该序列任意元素的递归算法。(6)设一有向图G的顶点集合为{v1,v2,v3,v4,v5}，边的集合为{v1,v2,v2,v4,v3,v5,v1,v3,v1,v5,v2,v3,v3,v4,v4,v5}。请写出入度最大的顶点和出度最大的顶点，并给出G的拓扑序列。2.一元n次多项式可以写成如下形式：1212()meeenmPxpxpxpx其中，ip是指数为ie的项的非零系数，且满足：120meeen。n和m均为正整数。假设A(x)和B(x)为满足上述形式的两个一元多项式。请设计算法用于计算：()()AxBx。（本题满分10分）3.请设计一个广度优先的非递归算法，打印出任意给定无向图的所有结点，给出算法的时间复杂度。（本题满分10分）4.请设计一个算法，实现如下功能：打开任意给定的文本文件，打印出某个字符串（可让用户输入）在该文件中出现的所有位置。（本题满分10分）5.设有如下关键字序列：4938659776132749(1)请写出快速排序的过程和结果；(2)写出递归形式的快速排序算法，并说明平均排序时间。（本题满分10分）6.给定n种物品和一个袋子，物品i的重量是wi，其价值为vi，袋子的容量为c。物品i装入袋子时可以选择物品i的一部分，而不一定全部装入袋子。请问：如何选择装入袋子的物品，使得装入袋子中物品的总价值最大？要求：（1）给出该问题的形式化描述；（2）给出算法描述；（3）给出算法的时间复杂度。（本题满分15分）7.一个长度为n的有序序列加入k个新元素（kn），假设这k个新元素随机地分布于整个序列中。请编写算法对插入新元素后的序列排序，并分析该算法的时间代价和空间代价。（本题满分15分）