GESP C++ 七级样题

1 单选题（每题 2 分，共 30 分）

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

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main()
{
	int x;
	
	cin >> x;
	
	cout << __________ << endl;
	
	return 0;
}

{{ select(1) }}

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

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

int fab (int n)
{
	int f[n + 1];
	
	f[0] = 0, f[1] = 1;
	
	for (int i = 2; i <= n; i++)
		f[i] = f[i - 1] + f[i - 2];
		
	return 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起到的作用是（ ）。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int visited[100], k = 0;

void dfs (int graph[][100], int start, int vexnum)
{
	visited[start] = ++k;
	cout << start << " ";
	for (int i = 0; i < vexnum; i++) {
		if ((start != i) && !visited[i]) {
			dfs(graph, i, vexnum);
		}
	}
}

{{ select(9) }}

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

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

int rec_C[MAXN][MAXM];
int C (int n, int m) {
	for (int i = 0; i <= n; i++)
		rec_C[i][0] = 1;
	for (int j = 0; j <= m; j++)
		rec_C[0][j] = 1;
	__________ // 在此处填入代码
		rec_C[i][j] = rec_C[i - 1][j - 1] + rec_C[i - 1][j];
	return rec_C[n][m];
}

{{ 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++语⾔中使⽤指针实现，⼀个典型的例⼦就是链表。因此，链表这⼀数据结构在 {{ select(25) }}

• 对
• 错