一、选择题

1. 下列算法中，没有运用分治思想的一项是( )

{{ select(1) }}

• 归并排序算法
• 求二叉树的前序遍历
• 快速排序算法
• 求二叉树的层次遍历

2. 下列算法中，( )是稳定的排序算法。 {{ select(2) }}

• 快速排序
• 堆排序
• 希尔排序
• 插入排序

3. 排序算法稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的( )

{{ select(3) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

4. 以下( )哪种排序算法的时间复杂度是 $O(n^2 )$ ？ {{ select(4) }}

• 计数排序
• 插入排序
• 希尔排序
• 归并排序

5. 以比较作为基本运算，在 $N$ 个数中找出最大数，最坏情况下所需要的最少的比较次数为( )。 {{ select(5) }}

• $N^2$
• $N$
• $N-1$
• $N+1$

6. 将数组 {8, 23, 4, 16, 77, −5, 53, 100} 中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换( )次。 {{ select(6) }}

• $4$
• $5$
• $7$
• $6$

7. 对有序数组 {5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100} 进行二分查找，成功查找元素 $19$ 的查找长度（比较次数）是( )。 {{ select(7) }}

• $1$
• $2$
• $3$
• $4$

8. 冒泡排序算法的伪代码如下：

   

   对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次?( )。

   {{ select(8) }}

• $n^2$
• $n-2$
• $n-1$
• $n$

9. 设有 $1 00$ 个已排好序的数据元素，采用折半查找时，最大比较次数为( ) {{ select(9) }}

• 7
• 10
• 6
• 8

10.设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做( )次比较。 {{ select(10) }}

• $n^2$。
• $n\log n$
• $2n$
• $2n-1$

11. 考虑如下递归算法

int solve(int n)
{
    if (n <= 1) return 1;  
    else if (n >= 5) return n * solve(n - 2);
    else return n * solve(n - 1);
}

则调用 $solve(7)$ 得到的返回结果为( )。 {{ select(11) }}

• 105
• 840
• 210
• 420

12. 快速排序最坏情况下的算法时间复杂度为： {{ select(12) }}

• $O(\log_2n)$
• $O(n)$
• $O(n\log_2n)$
• $O(n^2)$

13. 下列算法中运用分治思想的是（ ）。

{{ select(13) }}

• 快速排序
• 插入排序
• 冒泡排序
• 计数排序

14. 以下排序算法在最坏情况下时间复杂度最优的是（ ）。

{{ select(14) }}

• 冒泡排序
• 快速排序
• 归并排序
• 插入排序