算法分析与设计章节测试课后答案2024秋

第二章单元测试

1. 直接或间接调用自身的算法称为递归算法。（ ）

A:对 B:错
答案:对

2. 递归算法的基本原则包括基准情形、不断推进、设计法则和合成效益法则。（ ）

A:错 B:对
答案:对

3. 使用分治法解决的一个问题时，需要将一个大的问题分解成若干个子问题，这些子问题可以和原问题相同，也可以不同。（ ）

A:对 B:错
答案:错

4. 适合于用分治法求解的问题，经分解得到的子问题可以不是互相独立的。（ ）

A:错 B:对
答案:错


5. 设当n＞1时，T（n）=2T（n/2）+O（n），则此分治法的时间复杂度为（ ）。


A:Θ（n）
B:Θ（nlogn）
C:Θ(n²) D:Θ（logn）

答案:Θ（nlogn）



6. 设当n＞1时，T（n）=27T（n/3）+O（n2），则此分治法的时间复杂度为（ ）。


A:Θ(n³) B:Θ（n²logn） C:Θ（n²） D:Θ（n）

答案:Θ(n³)


7. 二分查找有序表（2，8，13，24，33，41，52，58，63，100 ），若查找表中元素51，则其依次和表中元素（ ）进行比较，查找结果是失败。


A:33，56，41，52
B:56，52
C:56，41，52
D:33，9，41，52

答案:33，56，41，52


8. 对于棋盘覆盖问题的分治算法，使用主定理进行算法分析时，k、m、d的值分别为（ ）。

A:k=2，m=4，d=1
B:k=2，m=4，d=0
C:k=4，m=2，d=1
D:k=4，m=2，d=0

答案:k=4，m=2，d=0


9. 下列选项中，不可能是快速排序第2趟排序结果的是（ ）。

A:{2，7，5，6，4，3，9}
B:{4，3，2，5，7，6，9}
C:{3，2，5，4，7，6，9}
D:{2，3，5，4，6，7，9}

答案:{3，2，5，4，7，6，9}


10. 采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（ ）。

A:每次划分后，先处理较长的分区可以减少递归次数
B:递归次数与初始初始数据的排列次序无关
C:递归次数与每次划分后得到的分区处理顺序无关
D:每次划分后，先处理较短的分区可以减少递归次数

答案:递归次数与每次划分后得到的分区处理顺序无关


• «
• 1
• 2
• 3
• 4
• 5
• 6
• »