#1709. 八级(2506)
八级(2506)
C++ ⼋级
2025 年 06 ⽉
1 单选题(每题 2 分,共 30 分)
第 1 题 ⼀间的机房要安排6名同学进⾏上机考试,座位共2⾏3列。考虑到在座位上很容易看到同⼀⾏的左右两侧的屏幕,安排中间⼀列的同学做A卷,左右两列的同学做B卷。请问共有多少种排座位的⽅案?( )。
{{ select(1) }}
- 720
- 90
- 48
- 15
第 2 题 ⼜到了毕业季,学长学姐们都在开⼼地拍毕业照。现在有3位学长、3位学姐希望排成⼀排拍照,要求男⽣不相邻、⼥⽣不相邻。请问共有多少种拍照⽅案?( )。
{{ select(2) }}
- 720
- 72
- 36
- 2
第 3 题 下列关于C++类和对象的说法,错误的是( )。
{{ select(3) }}
- 通过语句
const int x = 5;
定义了⼀个对象x
。 - 通过语句
std::string t = "12345";
定义了⼀个对象t
。 - 通过语句
void (*fp)() = NULL;
定义了⼀个对象fp
。 - 通过语句
class MyClass;
定义了⼀个类MyClass
。
第 4 题 关于⽣成树的说法,错误的是( )。
{{ select(4) }}
- ⼀个⽆向连通图,⼀定有⽣成树。
- n个顶点的⽆向图,其⽣成树要么不存在,要么⼀定包含 条边。
- n个顶点、 n-1条边的⽆向图,不可能有多颗⽣成树。
- n个顶点、 n-1条边的⽆向图,它本⾝就是⾃⼰的⽣成树。
第 5 题 ⼀对夫妻⽣男⽣⼥的概率相同。这对夫妻希望⼉⼥双全。请问这对夫妻⽣下两个孩⼦时,实现⼉⼥双全的概率是多少?( )。
{{ select(5) }}
- 2/3
- 1/3
- 1/2
- 1/4
第 6 题 已定义变量 double a, b;
,下列哪个表达式可以⽤来判断⼀元⼆次⽅程 是否有实根?( )。
{{ select(6) }}
4 * b - a * a < 0
4 * b <= a * a
a * a - 4 * b
b * 4 - a * a
第 7 题 n 个结点的⼆叉树,执⾏⼴度优先搜索的平均时间复杂度是( )。
{{ select(7) }}
第 8 题 以下关于动态规划的说法中,错误的是( )。
{{ select(8) }}
- 动态规划⽅法通常能够列出递推公式。
- 动态规划⽅法的时间复杂度通常为状态的个数。
- 动态规划⽅法有递推和递归两种实现形式。
- 对很多问题,递推实现和递归实现动态规划⽅法的时间复杂度相当。
第 9 题 下⾯的 sum_digit
函数试图求出从 1 到 n (包含 1 和 n )的数中,包含数字 d 的个数。该函数的时间复杂度为( )。
#include <string>
int count_digit(int n, char d) {
int cnt = 0;
std::string s = std::to_string(n);
for (int i = 0; i < s.length(); i++)
if (s[i] == d)
cnt++;
return cnt;
}
int sum_digit(int n, char d) {
int sum = 0;
for (int i = 1; i <= n; i++)
sum += count_digit(i, d);
return sum;
}
{{ select(9) }}
第 10 题 下⾯程序的输出为( )。
#include <iostream>
const int N = 10;
int ch[N][N][N];
int main() {
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
for (int z = 0; z < N; z++)
if (x == 0 && y == 0 && z == 0)
ch[x][y][z] = 1;
else {
if (x > 0)
ch[x][y][z] += ch[x - 1][y][z];
if (y > 0)
ch[x][y][z] += ch[x][y - 1][z];
if (z > 0)
ch[x][y][z] += ch[x][y][z - 1];
}
std::cout << ch[1][2][3] << std::endl;
return 0;
}
{{ select(10) }}
- 60
- 20
- 15
- 10
第 11 题 下⾯ count_triple
函数的时间复杂度为( )。
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int count_triple(int n) {
int cnt = 0;
for (int v = 1; v * v * 4 <= n; v++)
for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
if (gcd(u, v) == 1) {
int a = u * u - v * v;
int b = u * v * 2;
int c = u * u + v * v;
cnt += n / (a + b + c);
}
return cnt;
}
{{ select(11) }}
第 12 题 下⾯ quick_sort
函数试图实现快速排序算法,两处横线处分别应该填⼊的是( )。
void swap(int & a, int & b) {
int temp = a; a = b; b = temp;
}
int partition(int a[], int l, int r) {
int pivot = a[l], i = l + 1, j = r;
while (i <= j) {
while (i <= j && a[j] >= pivot)
j--;
while (i <= j && a[i] <= pivot)
i++;
if (i < j)
swap(a[i], a[j]);
}
________; // 在此处填入选项
return ________; // 在此处填入选项
}
void quick_sort(int a[], int l, int r) {
if (l < r) {
int pivot = partition(a, l, r);
quick_sort(a, l, pivot - 1);
quick_sort(a, pivot + 1, r);
}
}
//A:
swap(a[l], a[i])
i
//B:
swap(a[l], a[j])
i
//C:
swap(a[l], a[i])
j
//D:
swap(a[l], a[j])
j
{{ select(12) }}
- A
- B
- C
- D
第 13 题 下⾯ LIS
函数试图求出最长上升⼦序列的长度,横线处应该填⼊的是( )。
int max(int a, int b) {
return (a > b) ? a : b;
}
int LIS(vector<int> & nums) {
int n = nums.size();
if (n == 0)
return 0;
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
________; // 在此处填入选项
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
//A:
dp[j] = max(dp[j] + 1, dp[i])
//B:
dp[j] = max(dp[j], dp[i] + 1)
//C:
dp[i] = max(dp[i] + 1, dp[j])
//D:
dp[i] = max(dp[i], dp[j] + 1)
{{ select(13) }}
- A
- B
- C
- D
第 14 题 下⾯ LIS
函数试图求出最长上升⼦序列的长度,其时间复杂度为( )。
#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
int n = nums.size();
vector<int> tail;
tail.push_back(INT_MIN);
for (int i = 0; i < n; i++) {
int x = nums[i], l = 0, r = tail.size();
while (l < r) {
int mid = (l + r) / 2;
if (tail[mid] < x)
l = mid + 1;
else
r = mid;
}
if (r == tail.size())
tail.push_back(x);
else
tail[r] = x;
}
return tail.size() - 1;
}
{{ select(14) }}
第 15 题 下⾯的程序使⽤邻接矩阵表达的带权⽆向图,则从顶点0到顶点3的最短距离为( )。
int weight[4][4] = {
{ 0, 5, 8, 10},
{ 5, 0, 1, 7},
{ 8, 1, 0, 3},
{10, 7, 3, 0}};
{{ select(15) }}
- 9
- 10
- 11
- 12
2 判断题(每题 2 分,共 20 分)
第 1 题 C++语⾔中,表达式 9 | 12
的结果类型为 int
、值为 13
。
{{ select(16) }}
- 对
- 错
第 2 题 C++语⾔中,访问数据发⽣下标越界时,总是会产⽣运⾏时错误,从⽽使程序异常退出。
{{ select(17) }}
- 对
- 错
第 3 题 对 n 个元素的数组进⾏归并排序,最差情况的时间复杂度为 。
{{ select(18) }}
- 对
- 错
第 4 题 5个相同的红球和4个相同的蓝球排成⼀排,要求每个蓝球的两侧都必须⾄少有⼀个红球,则⼀共有15种排列⽅案。
{{ select(19) }}
- 对
- 错
第 5 题 使⽤ math.h
或 cmath`` 头⽂件中的函数,表达式
log(8)的结果类型为
double、值约为
3` 。
{{ select(20) }}
- 对
- 错
第 6 题 C++是⼀种⾯向对象编程语⾔,C则不是。继承是⾯向对象三⼤特性之⼀,因此,使⽤C语⾔⽆法实现继承。
{{ select(21) }}
- 对
- 错
第 7 题 n 个顶点的⽆向完全图,有 棵⽣成树。
{{ select(22) }}
- 对
- 错
第 8 题 已知三个 double
类型的变量 a
、 b
和 theta
分别表⽰⼀个三角形的两条边长及⼆者的夹角(弧度),则三角形的周长可以通过表达式 sqrt(a * a + b * b - 2 * a * b * cos(theta))
求得。
{{ select(23) }}
- 对
- 错
第 9 题 有 V 个顶点、 E 条边的图的深度优先搜索遍历时间复杂度为 。
{{ select(24) }}
- 对
- 错
第 10 题 从32名学⽣中选出4⼈分别担任班长、副班长、学习委员和组织委员,⽼师要求班级综合成绩排名最后的4名学⽣不得参选班长或学习委员(仍可以参选副班长和组织委员),则共有 种不同的选法。
{{ select(25) }}
- 对
- 错