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

A. log10(x) B. sin(x) C. exp(x) D. pow(x,10)

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

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

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

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

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

A. 4 B. 6 C. 8 D. 12

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

A. 插入 B. 排序 C. 查找 D. 删除

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

A. 5 B. 6 C. 7 D. 8

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

A. x*x*sin(pi/3) B. x*x*sin(pi/3)/2 C. x*x*cos(pi/3) D. x*x*cos(pi/3)/2

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

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

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

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

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

A. for (int i = n; i >= 1; i--) for (int j = 1; j <= m; j++) B. for (int i = 1; i <= n; i++) for (int j = m; j >= 1; j--) C. for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++) D. for (int j = 1; j <= m; j++) for (int i = n; i >= 1; i--)

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

A. 5 B. 6 C. 7 D. 8

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

A. 1 4 3 2 B. 1 4 2 3 C. 1 3 2 4 D. 1 2 4 3

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

A. 77 B. 78 C. 79 D. 80

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

A. 3 B. 4 C. 5 D. 6

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

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

2

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

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

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×

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

A. 正确√ B. 错误×