算法期末考试复习题

------------恢复内容开始------------

算法期末考试复习题

XD专用 

program 2

1、归并排序在最差最好平均情况下的时间复杂度分别是多少?

答案:nlgn nlgn

2、(判断) 归并排序的空间复杂度是O(1)? (判断)

答案:false 应该是 O(n)

3、优先队列提取最大元素的算法时间复杂度?(用O表示)

答案:O(lgn)

4、堆排序在最差最好平均情况下的时间复杂度分别是多少?

答案:答案有争论,都是O(nlgn),最好达到O(n)

5、(判断)堆排序的空间复杂度是O(1) ?

答案:true

6、请写出堆排序的适用情况是什么?写两个以上

答案: 1、n比较大 2、部分排序,前几个或后几个 3、实时应用

7、(填空) 确保一个堆是大顶堆的算法的时间复杂度是 O(lgn)

构建一个大顶堆算法的时间复杂度是 O(n)

8、快速排序在最差最好平均情况下的时间复杂度分别是多少?

答案:最好平均都是nlgn , 最坏O(n^2)

9、归并排序稳定性

答案:稳定

10、堆排序稳定性

答案:不稳定

11、快速排序稳定性

答案:不稳定

12、直接插入排序稳定性

答案:稳定

13、计数排序稳定性

答案:稳定

14、(填空)如果待排序的n个元素有相同的值,那么快速排序总共需要比较多少次?(算出一个具体的关于n的表达式)

答案:1+2+3+4+....... (n*(n-1))/2

15、快速排序出现的最坏情况的两种实例?

答案:1、元素相等 2、升序或降序

动态规划

1、矩阵链相乘

<3,5,7,1,10>

答案:

2、LCS (最长公共子序列)

3、LCS (最长公共子串)——>注意箭头指向

4、Max Sum (最大子序列和)

5、最短路径(从0到15)

算法期末考试复习题

补充题

1、矩阵链乘写出第一个上机题四个情况最终加括号的形式

2、写出矩阵链乘算法的递推表达式

 

3、(判断题)Ai Ai+1...Aj 被完全加括号的开销等于计算矩阵Ai...Ak与计算矩阵Ak+1...Aj的开销之和。

答案:false

4、矩阵链乘主算法的时间复杂度是多少?用O表示 O(n^3)

5、矩阵链乘的实现需要两个辅助数组m[],s[]。请写出m数组作用 答:数乘最小次数

6、请写出s数组的作用

答:s记录了最优解所需的信息

7、请写出LCS算法的递推式?

8、(填空题)若两个序列长度分别是m,n。则算法LCS(length)时间复杂度是多少? LCS问题的子问题的个数是多少? 答:时间复杂度为O(m*n)

9、output(LCS)的算法时间复杂度是多少?

10、Max Sum算法的递推式?

实验报告中所有递推式都要手写一边

 

描述动态规划的四个步骤:

1、刻画一个最优解的结构特征

2、递归的定义最优解的值

3、计算最优解的值,采用字底向下的方法

4、利用计算出的信息构造一个最优解

 

 

 

------------恢复内容结束------------

上一篇:最长公共子序列


下一篇:P4303 [AHOI2006]基因匹配