C++信奥赛能力阶段性测试（一）
试卷题目预览
环线
小A喜欢坐地铁。地铁环线有n个车站，依次以1~n标号。车站i(i
第一行，一个正整数n，表示车站的数量。 第二行，n个整数a_i，分别表示经过每个车站时获得的快乐值。
一行，一个整数，表示小A能获得的最大快乐值。
【样例输入1】 4 -1 2 3 0 【样例输出1】 5 对于所有测试点，保证1≤n≤2×10^5，-10^9≤a_i≤10^9。
学习小组
班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含k名同学，则该学习小组的讨论积极度为a_k。给定讨论积极度a_1~a_n，请你计算将这n名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
第一行，一个正整数n，表示班级人数。 第二行，n个非负整数a_1~a_n，表示不同人数学习小组的讨论积极度。
输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。
【样例输入1】 4 1 5 6 3 【样例输出1】 10 【样例输入2】 8 0 2 5 6 4 3 3 4 【样例输出2】 12 对于所有测试点，保证1≤n≤1000，0≤a_i≤10^9。
以下代码中，构造函数被调用的次数是1次。
下面的函数selectTopK()实现从n个学生中选出前k名成绩最好的学生颁发奖学金，则横线上应填写（ ）。
struct Student {
string name;
int score;
};
void selectTopK(Student students[], int n, int k) {
for (int i = 0; i < k; i++) {
int maxIdx = i;
for (____________________) { // 在此处填入代码
if (students[j].score > students[maxIdx].score) {
maxIdx = j;
}
}
if (maxIdx != i) {
Student temp = students[i];
students[i] = students[maxIdx];
students[maxIdx] = temp;
}
}
}
给定如下算法，其时间复杂度为（ ）。
bool f(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
sum += arr[j];
}
}
if (sum == target) return true;
}
return false;
}
执行下面C++代码，会输出( )。
int divide(int a, int b) {
if(b == 0) throw "Division by zero";
return a / b;
}
int main() {
int result = 0;
try {
result = divide(10, 0);
cout << "A";
}
catch(const char* msg) {
cout << "B";
result = -1;
}
cout << result;
return 0;
}
下面代码试图把数组按升序进行"插入排序"，横线处应填写（ ）。
void ins(int a[], int n) {
for(int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while(j >= 0 && __________) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
下面哪种方式不能实现将字符串Welcome to 2026!输出重定向到文件log.txt（ ）。
下面的程序中，如果输入10 0，会输出（ ）。
int main() {
int a, b;
cin >> a >> b;
try {
if (b == 0) {
throw "Division by zero condition!";
}
cout << a / b << endl;
} catch (const char* msg) {
cout << msg << endl;
}
return 0;
}
小杨和小刘是好朋友，她们在逛商场时发现新设置的大头贴自拍机，于是决定一起拍一组照片。一组照片包括4张，这4张照片没有顺序区分。拍每张照片时，可以选择有相框或无相框、两人可以分别选择有头饰或无头饰、 还可以从2种位置（小杨在左，或小刘在左）中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置 的组合。请问一组照片共有多少种不同的方案？（ ）。
下面程序的时间复杂度为（ ）。
int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
for (int n = 2; n <= MAXN; n++) {
if (!isPrime[n])
primes[num++] = n;
for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
isPrime[n * primes[i]] = true;
if (n % primes[i] == 0)
break;
}
}
}
下列Dijkstra算法，假设图graph中顶点数v、边数e，则程序的时间复杂度为（ ）。
typedef struct Edge {
int in, out;
int len;
struct Edge * next;
} Edge;
void dijkstra(int v, Edge * graph[], int start, int * dis) {
const int MAX_DIS = 0x7fffff;
for (int i = 0; i < v; i++)
dis[i] = MAX_DIS;
dis[start] = 0;
int * visited = new int[v];
for (int i = 0; i < v; i++)
visited[i] = 0;
visited[start] = 1;
for (int t = 0; ; t++) {
int min = MAX_DIS, minv = -1;
for (int i = 0; i < v; i++) {
if (visited[i] == 0 && min > dis[i]) {
min = dis[i];
minv = i;
}
}
if (minv < 0)
break;
visited[minv] = 1;
for (Edge * e = graph[minv]; e != NULL; e = e->next)
if (dis[e->out] > e->len)
dis[e->out] = e->len;
}
delete [] visited;
}
下面选择项中，与C++表达式not(x>5 or y<=10)等价的是（）。
下面的C++代码执行后其输出是（）。
int tnt = 0;
for (int i = 1; i < 5; i += 3) {
for (int j = 0; j < i; j++)
tnt += 1;
cout << tnt << "#";
}
cout << tnt;
下面的C++代码执行之后的输出是（）。
int i;
for (i = -2; i < 2; i++)
if (not i % 3 == 0)
cout << i << "#";
cout << i;
关于计算机中的二进制编码表示，下列说法错误的是（）。
下面关于埃氏筛法的说法正确的是（ ）。
下面代码在 main() 中有一行会导致编译错误，请找出来。
#include
using namespace std;
class Animal {
public:
virtual void speak() { cout << "Animal" << endl; } // ①
};
class Dog : public Animal {
public:
void speak() override { cout << "Dog" << endl; } // ②
};
int main() {
Animal* a = new Dog(); // ③
a->speak(); // ④
delete a;
return 0;
}
通过指向 Base 的指针删除 Derived 对象时，一定会先调用 Derived 的析构函数，再调用 Base 的析构函数。
在 C++ STL 中，stack 的 pop() 函数会返回栈顶元素并将其删除。
程序运行后会输出 2。
#include
#include
using namespace std;
int main() {
stacks;
s.push(1);
s.push(2);
s.push(3);
s.pop();
s.pop();
cout << s.top() << endl;
return 0;
}
下列函数试图将整数 x 插入到一棵二叉搜索树中。假设二叉搜索树满足如下性质：对于任意结点，左子树中所有结点的值均小于该结点的值，右子树中所有结点的值均大于或等于该结点的值。判断该函数是否能够在插入 后保持二叉搜索树性质。
void insert(TreeNode* root, int x) {
if (!root) { root = new TreeNode(x); return; }
if (x < root->val) insert(root->left, x);
else insert(root->right, x);
}
哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。
若用数组按层序存储完全二叉树，且根节点下标为 0，则下标为 i 的节点左孩子下标为 2 * i + 1，右孩子下标为 2 * i + 2。
以下代码可以正确地按层换行输出二叉树的节点值。
void printByLevel(TreeNode* root) {
if (!root) return;
queue q;
q.push(root);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
TreeNode* node = q.front(); q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << endl;
}
}