1. 在下列关于计算机算法的说法中，不正确的是（ ）。 {{ select(1) }}

• 一个正确的算法至少要有一个输入
• 算法的改进，在很大程度上推动了计算机科学与技术的进步
• 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
• 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法

2. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（ ）。 {{ select(2) }}

• 选择排序
• 冒泡排序
• 插入排序
• 基数排序

3. 将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（ ）次比较，完成从小到大的排序。

{{ select(3) }}

• 6
• 7
• 8
• 9

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

• 4
• 5
• 6
• 7

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

• 1
• 2
• 3
• 4

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

• O(log2n)
• O(n)
• O(nlog2n)
• $O(n^2)$

7. 有一个由 4000 个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素： {{ select(7) }}

• 11 次
• 12 次
• 13 次
• 14 次

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

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

9. 以下排序算法中，不需要进行关键字比较操作的算法是（ ）。 {{ select(9) }}

• 基数排序
• 冒泡排序
• 堆排序
• 直接插入排序

10. 给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要N - 1 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（ ）次比较操作。（⌈ ⌉表示向上取整，⌊ ⌋表示向下取整） {{ select(10) }}

• ⌈3N / 2⌉ - 2
• ⌊3N / 2⌋ - 2
• 2N - 2
• 2N - 4

11. 下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’” {{ select(11) }}

• 枚举
• 递归
• 贪心
• 分治

12. 对于给定的序列{ak}，我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么序列1, 7, 2, 3, 5, 4的逆序对数为()个。

{{ select(12) }}

• 4
• 5
• 6
• 7

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

{{ select(13) }}

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

14. 某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n (n为正整数)及 T(0)=1，则该算法的时间复杂度为( )。 {{ select(14) }}

• O(logn)
• O(nlogn)
• O(n)
• $O(n^2 )$

15．基于比较的排序时间复杂度的下限是（ ），其中 n 表示待排序的元素个数。 {{ select(15) }}

• Θ（n）
• Θ（n log n）
• θ（log n）
• $Θ（n^2）$

16．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。 {{ select(16) }}

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

17．广度优先搜索时，需要用到的数据结构是（ ）。 {{ select(17) }}

• 链表
• 队列
• 栈
• 散列表

18．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。 {{ select(18) }}

• 程序运行时理论上所占的内存空间
• 程序运行时理论上所占的数组空间
• 程序运行时理论上所占的硬盘空间
• 程序源文件理论上所占的硬盘空间

19．在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最快情况下运行的时间复杂度是（ ）。 {{ select(19) }}

• O(1 )
• O( log n )
• O( n )
• O( n log n )

20．（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。： {{ select(20) }}

• 回溯法
• 枚举法
• 动态规划
• 贪心

21． 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 1 个逆序对，因此序列 5，4，3，2，1 需要执行（ ）次交换操作，才能完成冒泡排序。 {{ select(21) }}

• 0
• 5
• 10
• 15

22．（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 {{ select(22) }}

• 动态规划
• 贪心
• 分治
• 搜索

23. 设有 100 个数据元素，采用折半搜索时，最大比较次数为( )。 {{ select(23) }}

• 6
• 7
• 8
• 10

24. 下面的故事与（ ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‚从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’‛ {{ select(24) }}

• 枚举
• 递归
• 贪心
• 分治

25. （ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。 {{ select(25) }}

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