A. CSP-J模拟卷14

A
    客观题

CSP-J模拟卷14

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

选择题

  1. （2分）以下关于计算机存储器的说法错误的是：{{ select(1) }}
  • 内存比硬盘访问速度快
  • RAM是易失性存储器
  • ROM中的数据断电后会丢失
  • 硬盘是非易失性存储器
  1. （2分）关于C++中的变量作用域，以下说法正确的是：{{ select(2) }}
  • 全局变量在程序结束时自动销毁
  • 局部变量可以在函数外部访问
  • 静态局部变量在函数调用结束后立即销毁
  • 函数参数属于全局变量
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int a = 2, b = 3;
    cout << (a++ * ++b) + (++a * b--) << endl;
    return 0;
}

{{ select(3) }}

  • 20
  • 22
  • 24
  • 26
  1. （2分）关于C++中的数组，以下说法错误的是：{{ select(4) }}
  • 数组下标从0开始
  • 数组名代表数组首元素的地址
  • 可以通过sizeof获得数组的字节数
  • 数组大小在运行时可以改变
  1. （2分）以下代码执行后x的值是：
int x = 1;
for (int i = 1; i <= 4; i++) {
    x = x * i + i;
}

{{ select(5) }}

  • 60
  • 76
  • 88
  • 92
  1. （2分）关于递归函数，以下说法正确的是：{{ select(6) }}
  • 递归函数一定比循环效率高
  • 每次递归调用都会创建新的局部变量
  • 递归函数不需要终止条件
  • 递归深度没有限制
  1. （2分）在不需要查找的情况下,在单链表中插入一个新节点的时间复杂度是：{{ select(7) }}
  • O(1)
  • O(logn)
  • O(n)
  • O(n²)
  1. （2分）关于二分查找，以下条件必须满足的是：{{ select(8) }}
  • 数组元素必须是整数
  • 数组必须是有序的
  • 数组长度必须是2的幂
  • 数组不能有重复元素
  1. （2分）一棵完全二叉树有31个节点，它的高度是：{{ select(9) }}
  • 4
  • 5
  • 6
  • 7
  1. （2分）关于图的存储方式，邻接矩阵的优点是：{{ select(10) }}
  • 节省存储空间
  • 便于添加删除顶点
  • 便于判断两顶点是否相邻
  • 适合稀疏图存储
  1. （2分）关于C++中的位运算优化，以下代码片段的输出结果是：
int x = 13;
int result = (x & -x) + ((x ^ (x - 1)) >> 1);
cout << result << endl;

{{ select(11) }}

  • 7
  • 5
  • 3
  • 1
  1. （2分）用8位二进制补码表示-5是：{{ select(12) }}
  • 10000101
  • 11111011
  • 11111010
  • 10000100
  1. （2分）关于C++中的内存对齐，以下结构体在64位系统下的大小是：
struct Node {
    char a;
    int b;
    char c;
    double d;
};

{{ select(13) }}

  • 16字节
  • 20字节
  • 24字节
  • 32字节
  1. （2分）关于C++中的引用和指针，以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int a = 10, b = 20;
    int &ref = a;
    int *ptr = &b;
    ref = *ptr;
    *ptr = 30;
    cout << a << " " << b << " " << ref << endl;
    return 0;
}

{{ select(14) }}

  • 10 30 10
  • 20 30 20
  • 30 30 30
  • 20 20 20
  1. （2分）关于STL容器的时间复杂度，以下说法错误的是：{{ select(15) }}
  • vector的push_back操作平均时间复杂度为O(1)
  • deque的首尾插入删除操作时间复杂度为O(1)
  • map的查找操作时间复杂度为O(1)
  • set的插入操作时间复杂度为O(log n)

阅读理解1（12分）

数据范围：1 ≤ n ≤ 8，1 ≤ m ≤ 8

#include <iostream>
#include <vector>
using namespace std;

int n, m, ans;
vector<vector<int>> board;
vector<bool> col, diag1, diag2;

void dfs(int row) {
    if (row == n) {
        ans++;
        return;
    }
    
    for (int c = 0; c < m; c++) {
        if (board[row][c] == 0) continue;
        
        if (col[c] || diag1[row + c] || diag2[row - c + m - 1]) {      // 第20题
            continue;// 第20题
        }// 第20题
        
        col[c] = diag1[row + c] = diag2[row - c + m - 1] = true;
        dfs(row + 1);
        col[c] = diag1[row + c] = diag2[row - c + m - 1] = false;
    }
}

int main() {
    cin >> n >> m;
    board.resize(n, vector<int>(m));
    col.resize(m, false);
    diag1.resize(n + m, false);
    diag2.resize(n + m, false);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    
    ans = 0;
    dfs(0);
    cout << ans << endl;
    return 0;
}

第16题（1.5分）

在该程序中，如果board[2][1] == 0，则dfs(2)函数不会在第1列放置任何元素。（ ）{{ select(16) }}

  • 正确
  • 错误

第17题（1.5分）

在该程序中，如果系统在位置(2,1)放置了一个元素，则位置(3,0)和(1,2)都不能再放置元素。（ ）{{ select(17) }}

  • 正确
  • 错误

第18题（1.5分）

如果输入n=3，m=3，且board数组全部为1，则程序的输出结果为1。（ ）{{ select(18) }}

  • 正确
  • 错误

第19题（1.5分）

如果输入4 4然后输入16个1，输出为2。（ ）{{ select(19) }}

  • 正确
  • 错误

第20题（3分）

在该程序中，第20题所标代码删除，程序的行为会变为：{{ select(20) }}

  • 仍然正确计算方案数
  • 方案数会偏大但程序不会出错
  • 程序可能陷入死循环
  • 程序会立即崩溃

第21题（3分）

该算法的时间复杂度在最坏情况下是（ ）{{ select(21) }}

  • O(n!)
  • O(2^n)
  • O(n^n)
  • O(n^m)

阅读理解2（12分）

数据范围：1 ≤ 字符串长度 ≤ 12，字符串只包含小写字母

#include<bits/stdc++.h>
using namespace std;
string s;
int ans,n;
int c(int m,int n)//组合数计算 
{
	if(m==0)return 1;
	int mut=1;
	for(int i=n;i>n-m;i--)mut*=i;
	for(int i=m;i>1;i--)mut/=i;
	return mut;
}
int main()
{
	cin>>s,n=s.size();
	for(int i=1;i<n;i++)
		if(s[i]<=s[i-1])cout<<0,exit(0);
	for(int i=1;i<n;i++)ans+=c(i,26);
	for(int i=0;i<n;i++)
		for(char j=(i==0?'a':s[i-1]+1);j<s[i];j++)
			ans+=c(n-i-1,'z'-j);
	cout<<++ans;
	return 0;
}

第22题（1.5分）

该程序计算的是某个字符串在所有排列可能的字符串中的排名。（ ）{{ select(22) }}

  • 正确
  • 错误

第23题（1.5分）

如果输入字符串"aa"，程序的输出结果为27。（ ）{{ select(23) }}

  • 正确
  • 错误

第24题（1.5分）

在本题中c(int m,int n)函数存在整数溢出的可能。（ ）{{ select(24) }}

  • 正确
  • 错误

第25题（1.5分）

在第二个for循环中，j的起始值在第一位时为'a'，其他位时为s[i-1]+1。（ ）{{ select(25) }}

  • 正确
  • 错误

第26题（3分）

在第三个for循环中，ans+=c(n-i-1,'z'-j)这一语句的作用是：{{ select(26) }}

  • 计算剩余位置可以组成的字符串数量
  • 计算当前位置之前的所有可能组合
  • 计算字典序比当前字符串小的数量
  • 验证组合数计算的正确性

第27题（3分）

如果输入字符串"abc"，程序的输出结果为：{{ select(27) }}

  • 350
  • 351
  • 352
  • 354

阅读理解3（16分）

数据范围：1 ≤ n ≤ 2 × 10^6，1 ≤ m ≤ 10^9，1 ≤ a[i] ≤ 10^9

#include <cstdio>
#include <algorithm>
#define ll long long
#define inf 1023456789

using namespace std;

ll n, m, a[2000005], ans, tot;

int main(){
	scanf("%lld%lld",&n,&m);
	for(int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	sort(a + 1, a + n + 1);
	if(a[1] != 1) {
		printf("No answer!!!\n");
		return 0;
	}
	a[n + 1] = m;
	for(int i = 1; i <= n; i++){
		if(tot < a[i + 1] - 1){
			ll k = (a[i + 1] - 2 - tot) / a[i] + 1;
			tot += a[i] * k;
			ans += k;
			if(tot >= m){
				printf("%lld\n",ans);
				return 0;
			}
		}
	}
	printf("%lld\n",ans + 1);
	return 0;
}

第28题（1.5分）

如果没有#include 这句,不影响编译（ ）{{ select(28) }}

  • 正确
  • 错误

第29题（1.5分）

如果输入的数据a[1] != 1时，程序会输出"No answer!!!"并退出。（ ）{{ select(29) }}

  • 正确
  • 错误

第30题（3分）

该算法的时间复杂度是：{{ select(30) }}

  • O(n)
  • O(n log n)
  • O(n^2)
  • O(n * m)

第31题（3分）

本题使用了什么算法：{{ select(31) }}

  • 动态规划
  • 贪心算法
  • 分治算法
  • 回溯算法

第32题（3分）

如果输入n=4, m=20, 数组a为[1, 2,5,6]程序的输出结果为：{{ select(32) }}

  • 4
  • 5
  • 6
  • 7

第33题（4分）

如果不管限制,输入n=1e9, m=1e9, 数组a为[1-1e9]，程序的输出结果为：{{ select(33) }}

  • 27
  • 28
  • 29
  • 30

编程填空1（15分）

（放棋子问题）给你一个N×N的矩阵，每行有一个障碍，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求放置N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。 数据范围：1 ≤ N ≤ 200

样例1： 输入： 3 输出：2 解释：当N=3时，有2种不同的放置方案

样例2： 输入： 4 输出：9 解释：当N=4时，有9种不同的放置方案

#include<bits/stdc++.h>
using namespace std;
int n; 
struct high
{
	int a[500], len;
}f[205];
high add(high a, high b)
{
	for(int i = 1; i <= b.len; ++ i) a.a[i] += b.a[i];
	for(int i = 1; i <= ①; ++ i)
		if(a.a[i] > 9){
            a.a[i] -= 10;
            a.a[i + 1] ++;
        } 
	if(a.a[a.len + 1] != 0) {
        ②;
    }
	return a;
}
high mul(high a, int b)
{
	for(int i = 1; i <= a.len; ++ i){
        a.a[i] *= b;
    } 
	a.len += 4;
	for(int i = 1; i <= a.len; ++ i)
	{
		if(a.a[i] > 9) {
            ③;
            a.a[i] %= 10;
        }
	}
	④;
	return a;
}
void write(high a)
{
	for(int i = a.len; i >= 1; -- i) {
        putchar(a.a[i] + '0');
    }
	putchar('\n');
}
int main()
{
	scanf("%d", &n);
	if(n == 1) { printf("1\n"); return 0; }
	if(n == 2) { printf("2\n"); return 0; }
	f[1].a[1] = 1; f[1].len = 1;
	f[2].a[1] = 2; f[2].len = 1;
	for(int i = 3; i <= n; ++ i)
		f[i] = mul(add(f[i - 1], f[i - 2]), ⑤);
	write(f[n]);
	return 0;
}

第34题（3分）①处应填（ ）{{ select(34) }}

  • n
  • b.len
  • a.len
  • min(a.len, b.len)

第35题（3分）②处应填（ ）{{ select(35) }}

  • a.len--
  • a.len++
  • b.len--
  • b.len++

第36题（3分）③处应填（ ）{{ select(36) }}

  • a.a[i] += 1
  • a.a[i] += a.a[i] / 10
  • a.a[i + 1] += 1
  • a.a[i + 1] += a.a[i] / 10

第37题（3分）④处应填（ ）{{ select(37) }}

  • if(a.a[a.len] == 0) a.len--
  • if(b.a[b.len] == 0) b.len--
  • while(a.a[a.len] == 0) a.len--
  • while(b.a[b.len] == 0) b.len--

第38题（3分）⑤处应填（ ）{{ select(38) }}

  • i
  • i - 1
  • i + 1
  • 2

编程填空2. （15分）

（单调栈求最大矩形面积）给定一个直方图，求其中能构成的最大矩形面积。 数据范围：1 ≤ n ≤ 10^5，0 ≤ height[i] ≤ 10^4

样例1： 输入： 6 2 1 5 6 2 3 输出：10 解释：最大矩形面积为10（高度为5，宽度为2）

样例2： 输入： 4 2 4 3 2 输出：8 解释：最大矩形面积为8（高度为2，宽度为4）

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int height[n + 2];
    height[0] = ①;
    for (int i = 1; i <= n; i++) {
        cin >> height[i];
    }
    height[n + 1] = ②;
    
    stack<int> st;
    int maxArea = 0;
    
    for (int i = 0; i <= n + 1; i++) {
        while (!st.empty() && height[st.top()] > height[i]) {
            int h = height[③];
            st.pop();
            int w = i - ④ - 1;
            maxArea = max(maxArea, h * w);
        }
        st.push(⑤);
    }
    
    cout << maxArea << endl;
    return 0;
}

第39题（3分）①处应填（ ）{{ select(39) }}

  • 1
  • 0
  • -1
  • height[1]

第40题（3分）②处应填（ ）{{ select(40) }}

  • 1
  • height[n]
  • 0
  • -1

第41题（3分）③处应填（ ）{{ select(41) }}

  • i
  • st.top()
  • st.size()
  • st.empty()

第42题（3分）④处应填（ ）{{ select(42) }}

  • i
  • st.size() - 1
  • st.top()
  • height[i]

第43题（3分）⑤处应填（ ）{{ select(43) }}

  • height[i]
  • st.size()
  • i
  • maxArea

cspj初赛模拟赛4

未参加
状态
已结束
规则
IOI
题目
1
开始于
2025-9-5 19:00
结束于
2025-9-5 21:00
持续时间
2 小时
主持人
参赛人数
11
  1. Language
  2. 兼容模式
  3. 主题
  2. 浙ICP备2025154918号
  3. Worker 0, 87ms
  4. Powered by Hydro v5.0.0-beta.8 Community