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

算法期末考试复习题

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、利用计算出的信息构造一个最优解

 

 

 

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