1、下列关于排序的说法 ，正确的是( )。

A. 冒泡排序是最快的排序算法之⼀。

B. 快速排序通常是不稳定的。

C. 最差情况 ，$N$个元素做归并排序的时间复杂度为$O(N)$

D. 以上均不正确。

【答案】B

【考纲知识点】排序算法

【解析】冒泡排序时间复杂度为$O(n^2)$,不是最快的排序算法，归并排序的时间复杂度为$O(nlogn)$,快速排序是不稳定的排序算法。

2、下⾯的程序属于哪种算法( )。

A. 贪⼼算法

B. 动态规划

C. 深度优先搜索

D. ⼴度优先搜索

【答案】C

【考纲知识点】搜索算法

【解析】代码采用递归的写法，每次从$queue(n)$转移到$queue(n+1)$，符合深度优先搜索的代码风格。

3、下⾯有关C++类的说法 ，错误的是（ ）。

A. C++类对象销毁时 ，会执⾏析构函数。

B. C++类可以通过定义构造函数实现⾃动类型转换。

C. C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。

D. C++类可以包含任意类型的成员变量。

【答案】D

【考纲知识点】类的创建

【解析】C++类不能包含自身，也不能包含定义在它下面的类。

4、⼀个连通的简单无向图 ，共有28条边 ，则该图⾄少有( )个顶点。

A. 6

B. 7

C. 8

D. 9

【答案】C

【考纲知识点】图

【解析】n个点的连通的简单无向图至多有$n*(n-1)/2$条边，当n=8时，$8*7/2=28$，故选C。

5、以下哪个⽅案不能合理解决或缓解哈希表冲突（ ）。

A. 在每个哈希表项处 ，使⽤单链表管理该表项的冲突元素。

B. 建⽴额外的单链表 ，⽤来管理所有发⽣冲突的元素。

C. 使⽤不同的哈希函数再建⽴⼀个哈希表 ，⽤来管理所有发⽣冲突的元素。

D. ⽤新元素覆盖发⽣冲突的哈希表项。

【答案】D

【考纲知识点】哈希表

【解析】不能使用新元素直接覆盖发生冲突的哈希表项，这样会造成之前的元素丢失。

6、 已知⼀颗⼆叉树的中序遍历序列为： {C F B A E D G} ，后序遍历序列为： {F C B E G D A} ，则下列说法中正确的是( )。

A. 该树是平衡⼆叉树。

B. 该树的⾼为4。

C. 该树有4个叶节点。

D. 以上说法都不对。

【答案】B

【考纲知识点】树的遍历

【解析】首先根据中序遍历和后序遍历将树构造出来：

选项A，C显然错误，选项B正确，树高为4。

7、以下关于⼆叉排序树的说法 ，正确的是（ ）。

A. ⼆叉排序树的中序遍历序列⼀定是有序的。

B. 在含 n 个节点的⼆叉排序树中查找元素 ，最差情况的时间复杂度为$O(log(n))$。

C. ⼆叉排序树⼀定是⼆叉平衡树。

D. 以上说法都不对。

【答案】A

【考纲知识点】二叉排序树

【解析】二叉排序树的左子树小于等于根，右子树大于等于根，而中序遍历按照左中右的顺序进行遍历，所以得到的序列一定是有序的，A正确。选项B错误，最差情况n个节点的每个右子树均为空，此时查找的时间复杂度为$O(n)$。选项C错误，比如第6题图中的树不是二叉平衡树，但可以按中序遍历由小到大填入数字形成二叉排序树。

8、已知 x 为 double 类型的变量 ，且值⼤于0 ，则下列表达式的值⼀定⼤于0的是( )。

A. $sin(x) / x$

B. $exp(x) - x$

C. $log(x) - x$

D. $x * x - x$

【答案】B

【考纲知识点】常用数学函数

【解析】$exp(x)$是$e^x$,而指数函数增长的速度非常快，当x>0时$e^x$一定大于x. 选项A当$\pi<x<2\pi$时，sin(x)<0,选项C，当x=e时，$log(x)-x=1-e<0$，选项D，当x=0.5时，$x*x-x=-0.25$。

9、一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。 ( )

A. 60

B. 70

C. 15

D. 20

【答案】A

【考纲知识点】图

【解析】10个点的有向完全图共有$10*9=90$条边，需要再增加60条边。

10、下列选项中 ，哪个可能是下图的深度优先遍历序列（ ）。

A. 8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9

B. 7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。

C. 8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7

D. 7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。

【答案】C

【考纲知识点】图的遍历

【解析】选项A 10后面不能接7，选项B 3后面不能接12，选项D 10后面不能接9。

11、下⾯ schedule 函数的时间复杂度为( )。

A. $O(n)$

B. $O(log(n))$

C. $O(n log(n))$

D. $O(n​^2​)$

【答案】C

【考纲知识点】时间复杂度分析

【解析】schedule函数由两部分组成，一个是sort排序，另一个是遍历p数组，sort复杂度为$O(n logn)$，遍历复杂度为$O(n)$,总复杂度为$O(n logn)$。

12、下⾯ search 函数的平均时间复杂度为( )。

A. $O(n)$

B. $O(log(n))$

C. $O(1)$

D. 可能⽆法返回

【答案】B

【考纲知识点】时间复杂度分析，二分查找

【解析】容易发现代码是在进行二分查找，每次查找区间减半，所以复杂度为$O(logn)$。

13、下⾯ count_triple 函数的时间复杂度为( )。

A. $O(N)$

B. $O(N​^2​)$

C. $O(N​^3​)$

D. $O(N​^4​)$

【答案】C

【考纲知识点】时间复杂度分析

【解析】三重for循环，每个循环的上界都是n，总复杂度为$O(N​^3)$。

14、下⾯程序的输出为（ ）。

A. 6

B. 13

C. 20

D. ⽆法正常结束。

【答案】A

【考纲知识点】递归，递推

【解析】使用递推的方式，从小到大依次计算出down(1~6),分别为1,0,1,2,3,6,故选A。

15、 下⾯的程序使⽤邻接矩阵表达的带权⽆向图 ，则从顶点0到顶点3的最短距离为（ ）。

A. 6

B. 7

C. 8

D. 9

【答案】B

【考纲知识点】最短路

【解析】可以从0->1->2->3,距离为2+1+4=7。选B。