第 1 题 如果下面代码输入整数为10，输出是1，则横线处填写？（ ）

{{ select(1) }}

• log10(x)
• sin(x)
• exp(x)
• pow(x,10)

第 2 题 下面定义的函数用来求斐波那契数列的F(n)，其中，描述正确的是（ ）。

{{ select(2) }}

• f[0]和f[1]是递归终止条件
• 数组f保存算法执行过程的状态
• 使用倍增法来求解
• 算法不能正常结束

第 3 题 下列关于C++语言中函数的叙述，正确的是（ ）。

{{ select(3) }}

• 函数定义前必须声明
• 函数调用前必须定义
• 函数调用时必须提供足够的实际参数
• 函数声明只能写在函数调用前

第 4 题 4个结点的简单有向图，最多可以有多少条边（ ）。

{{ select(4) }}

• 4
• 6
• 8
• 12

第 5 题 哈希表上可以执行的操作不包括（ ）

{{ select(5) }}

• 插入
• 排序
• 查找
• 删除

第 6 题 将关键码集合{100，300，500，700，800，900}逐一保存在一个长度为100的哈希表中，选取哈希函数为Hash(key)=key/100，则800保存在表中的位置应该是（ ）。

{{ select(6) }}

• 5
• 6
• 7
• 8

第 7 题 定义double型常量pi=3.14和变量x，x代表等边三角形边长，则该三角形的面积是（ ）。

{{ select(7) }}

• x*x*sin(pi/3)
• x*x*sin(pi/3)/2
• x*x*cos(pi/3)
• x*x*cos(pi/3)/2

第 8 题 动态规划将一个问题分解为一系列子问题后来求解。下面关于子问题的描述正确的是（ ）。

{{ select(8) }}

• 具有重叠子问题的性质
• 和分治法的子问题类似
• 不具有最优子结构的性质
• 问题的最优解可以由部分子问题的非最优解推导出来

第 9 题 阅读以下代码，visited起到的作用是（ ）。

{{ select(9) }}

• 实现遍历过程
• 以广度优先的方式记录图中的顶点
• 存储深搜时节点的访问顺序
• 能够记录最短路径

第 10 题 下面函数尝试使用动态规划方法求出如下递推公式的函数，则横线处填写下列哪段代码可以完成预期功能?（ ）

{{ select(10) }}

• for (int i = n; i >= 1; i--) for (int j = 1; j <= m; j++)
• for (int i = 1; i <= n; i++) for (int j = m; j >= 1; j--)
• for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++)
• for (int j = 1; j <= m; j++) for (int i = n; i >= 1; i--)

第 11 题 深度为4的完全二叉树，结点总数最少有多少个？（ ）

{{ select(11) }}

• 5
• 6
• 7
• 8

第 12 题 下面有向图中的数字表示顶点序号，则从1号顶点出发的BFS遍历的输出顶点序列可能是（ ）。

{{ select(12) }}

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

第 13 题 一个简单有向图有20个结点，假设图中已经存在300条边，请问增加多少条边可以成为完全图。（ ）

{{ select(13) }}

• 77
• 78
• 79
• 80

第 14 题 在下面的有向图中，强连通分量有多少个？（ ）

{{ select(14) }}

• 3
• 4
• 5
• 6

第 15 题 下⾯有关格雷码的说法，错误的是（ ）。

{{ select(15) }}

• 在格雷码中，任意两个相邻的代码只有一位二进制数不同
• 格雷码是一种唯一性编码
• 在格雷码中，最大数和最小数只有一位二进制数不同
• 格雷码是一种可靠性编码

2

判断题（每题 2 分，共 20 分）

第 1 题 定义变量double x=exp(-1)，则x<0为真。( ) {{ select(16) }}

• 正确√
• 错误× 第 2 题 假设x和y都是double型正数，如果说x比y大一个数量级，log(x/y)等于10。( )

{{ select(17) }}

• 正确√
• 错误×

第 3 题 如果double型变量x代表锐角对应的弧度角，则可以编程来确定sin(x)>cos(x)的近似区间。( )

{{ select(18) }}

• 正确√
• 错误×

第 4 题 pow(1,2)返回的结果是浮点数。( )

{{ select(19) }}

• 正确√
• 错误×

第 5 题 如果哈希表足够大，哈希函数确定后，不会产生冲突。( )

{{ select(20) }}

• 正确√
• 错误×

第 6 题 动态规划最终要推导出状态转移方程才能求解。( )

{{ select(21) }}

• 正确√
• 错误×

第 7 题 简单有向图的深搜结果和广搜结果一样。( )

{{ select(22) }}

• 正确√
• 错误×

第 8 题 判断图是否连通可以用深搜实现。( )

{{ select(23) }}

• 正确√
• 错误×

第 9 题 在C++中，可以使⽤二分法查找链表中的元素。( )

{{ select(24) }}

• 正确√
• 错误×

第 10 题 有些算法或数据结构在C/C++语⾔中使⽤指针实现，⼀个典型的例⼦就是链表。因此，链表这⼀数据结构在C/C++语⾔中只能使⽤指针来实现。( ) {{ select(25) }}

• 正确√
• 错误×