1、祖冲之是南北朝时期杰出的数学家、天⽂学家 ，其主要贡献在数学、天⽂历法和机械制造三⽅⾯ 。他⾸次将 “ 圆周率”精算到⼩数第七位， 即在3. 1415926和3. 1415927之间。

【答案】正确

【考纲知识点】计算机历史

【解析】祖冲之发现了圆周率，并计算到了小数第七位。

2、C++语⾔中 ，表达式 2 ^ 3 的结果类型为 int 、值为 8 。( )

【答案】错误

【考纲知识点】位运算

【解析】2 ^ 3= $(10)_2$^ $(11)_2 = (01)_2 =1$

3、⼀棵有N个节点的完全⼆叉树 ，则树的深度为$\lfloor log​_2~​(N)\rfloor +1$ 。( )

【答案】正确

【考纲知识点】树

【解析】一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为$i（1≤i≤n）$的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。具有n个结点的完全二叉树的深度为$\lfloor log​_2~​(N)\rfloor +1$

4、能⽤动态规划解决的问题 ，⼀般也可以⽤贪⼼法解决 ，但动态规划的效率更⾼ 。( )

【答案】错误

【考纲知识点】动态规划，贪心

【解析】能用动态规划解决的问题 ，不一定可以⽤贪⼼法解决。

5、使⽤ math.h 或 cmath 头⽂件中的正弦函数 ，表达式 $sin(30)$ 的结果类型为 double 、值约为 0.5 。( )

【答案】错误

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

【解析】$sin()$函数的参数是弧度而不是角度。

6、要求出简单有向图中从顶点 A 到顶点 B 的最短路径 ，在深度优先搜索和⼴度优先搜索中选择 ，⼴度优先更适 合 。( )

【答案】正确

【考纲知识点】搜索

【解析】广度优先搜索第一次遍历到一个点时，经过的路径长度就是最短的，广度优先搜索更适合于查找最短路径。

7、某 N 个表项的哈希表 ，在发⽣哈希函数冲突时采⽤向后寻找空位的⽅法解决冲突 。其查找操作的平均时间复 杂度为$O(1)$ ， 即使当该哈希表的每个表项都有元素时 ，查找操作的平均时间复杂度仍为$O(1)$ 。( )

【答案】错误

【考纲知识点】哈希表

【解析】在哈希表中查找某个元素时，如果该元素的哈希值所在的位置不是该元素，则需要往后进行比较，查找复杂度会超过$O(1)$。特别的，当该哈希表的每个表项都有元素时，如果待查找元素不在该哈希表中，时间复杂度可以达到$O(n)$。

8、动态规划有递推实现和递归实现 ，有时两种实现的时间复杂度不同 。( )

【答案】正确

【考纲知识点】动态规划

【解析】动态规划的递推实现可能会导致重复计算，从而提高时间复杂度。动态规划的递归实现有时会由于自顶向下比自底向上更难（例如，自顶向下需要找到所有因数，自底向上只需要找到所有倍数），从而提高时间复杂度。

9、围棋游戏中 ，判断落下⼀枚棋⼦后是否会提掉对⽅的⼦ ，可以使⽤泛洪算法来实现 。( )

【答案】正确

【考纲知识点】搜索

【解析】假设落下的是白子，则可以从该子周围四个有黑子的位置分别开始进行泛洪算法，若某个区间全部是黑子、没有空位，则该区间需要被提掉。

10、类 B 继承了抽象类 A ，但未实现类 A 中的纯虚函数 f ，则类 B 不能直接实例化 。( )

【答案】正确

【考纲知识点】类的创建

【解析】因为类B没有实现类A中的纯虚函数f，若将B实例化，则B没有办法执行函数f。