CSP-J模拟卷9

ID: 2510

客观题

尝试: 17

已通过: 1

难度: 10

上传者:

yhxx

标签>

CSP-J

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

（2分）以下哪个不属于计算机的基本硬件组成部分？（）。{{ select(1) }}

中央处理器（CPU）
内存
操作系统
输入输出设备

（2分）以下代码段的时间复杂度为（）。

int n = 1000;
int ans = 0;
for(int i = 1; i <= n; i *= 2) {
    for(int j = 1; j <= i; j++) {
        a++;
    }
}

O(n)
O(n log n)
O(log² n)
O(2^log n)

（2分）以下C++代码片段执行后，变量result的值是多少？（）

signed char a = 0x80;
int b = a;
unsigned int result = b;

0x00000080
0x0000007F
0xFFFFFF7F
0xFFFFFF80

（2分）十进制数42转换为二进制数是多少？（）。{{ select(4) }}

101010
110010
101100
101001

（2分）投掷两枚均匀的骰子，出现点数之和为7的概率是（）。{{ select(5) }}

1/6
1/36
7/36
5/36

（2分）以下哪种数据结构常用于实现队列？（）。{{ select(6) }}

数组
链表
栈
以上都可以

（2分）快速排序在最坏情况下的时间复杂度是（）。{{ select(7) }}

$O(n)$
$O(n\log n)$
$O(n^2)$
$O(\log n)$

（2分）对于以下C++代码，输出结果是什么？

int a = 10;
int b = 20;
int c = a++ * 2;
int d = --b * 2;

c和d的值分别是（）。{{ select(8) }}

20和38
20和40
22和38
22和40

（2分）以下哪种网络协议负责将域名转换为IP地址？（）。{{ select(9) }}

HTTP
DNS
TCP
IP

（2分）以下C++语句中，哪一个是条件判断语句？（）。{{ select(10) }}

for
switch
while
if

（2分）若整型变量x的值为15，y的值为7，则表达式x & y的结果是（）。{{ select(11) }}

（2分）以下哪个逻辑表达式与表达式 A && B || C 等价？（）。{{ select(12) }}

(A && B) || C
A && (B || C)
(A || C) && (B || C)
A || B && C

（2分）一棵高度为h的完全二叉树，至少有多少个节点？（）。{{ select(13) }}

$2^h - 1$
$2^{h-1}$
$2^h$
$2^{h+1} - 1$

（2分）将4个不同的球放入3个不同的盒子中，允许有空盒子，共有多少种不同的放法？（）。{{ select(14) }}

3^4
4^3
C(4,3)
P(4,3)

（2分）无向图G有n个顶点和m条边，要保证G是连通的，m至少需要是多少？（）。{{ select(15) }}

n-1
n
n+1
n(n-1)/2

二、阅读程序（程序输入不超过数组或字符串定义的范围；每题有且仅有一个正确选项，除特殊说明外，每题 3 分，共计 40 分）

（一）

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 20;
long long dp[MAXN][MAXN];

long long comb(int n, int k) {
    if(k == 0 || k == n) return 1;
    if(k > n - k) k = n - k; 
    if(dp[n][k] != 0) return dp[n][k];  
    return dp[n][k] = comb(n-1, k-1) + comb(n-1, k);
}

int main() {
    int n, k;
    memset(dp, 0, sizeof(dp));
    cin >> n >> k;
    cout << comb(n, k) << endl;
    return 0;
}

（1.5分）该程序的时间复杂度是 $O(n^2)$ 。（）{{ select(16) }}

正确
错误

（1.5分）该程序的空间复杂度是 $O(n^2)$ 。（）{{ select(17) }}

正确
错误

（1.5分）当输入为(5,2)时，程序输出为10。（）{{ select(18) }}

正确
错误

（1.5分）如果去掉第10行的剪枝条件（k > n - k），程序的运行时间会增加。（）{{ select(19) }}

正确
错误

（3分）当输入为(10,5)时，程序的递归调用（不包含重复计算）次数大约是（）。{{ select(20) }}

10次
30次
55次
100次

（3分）以下哪种说法是错误的？（）{{ select(21) }}

该程序使用了动态规划的思想
该程序利用了组合数的对称性
该程序的dp数组存储了所有已计算的组合数结果
去掉memset初始化，程序仍能正确运行

（二）

#include<bits/stdc++.h>
using namespace std;

int f(int x, int y) {
    if(x == 0 || y == 0) return 1;
    return f(x-1, y) + f(x, y-1);
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << f(n, m) << endl;
    return 0;
}

（1.5分）当输入为0 0时，程序输出为1。（）{{ select(22) }}

正确
错误

（1.5分）当输入为2 3时，程序的输出结果与输入为3 2时的输出结果相同。（）{{ select(23) }}

正确
错误

（1.5分）该程序计算的是从(0,0)到(n,m)的路径数目，其中只能向右或向上移动。（）{{ select(24) }}

正确
错误

（3分）当输入为3 4时，程序的输出是（）。{{ select(25) }}

（3分）该程序的时间复杂度是（）。{{ select(26) }}

$O(n+m)$
$O(nm)$
$O(2^{n+m})$
$O(n^m)$

（3分）若n和m都较大时，程序可能会出现什么问题？（）{{ select(27) }}

运行时间过长
栈溢出
整数溢出
以上都有可能

（三）

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int a[MAXN];
int dp[MAXN];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        dp[i] = 1;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

（1.5分）该程序计算的是最长递增子序列的长度。（）{{ select(28) }}

正确
错误

（1.5分）该程序的时间复杂度是 $O(n^2)$ 。（）{{ select(29) }}

正确
错误

（1.5分）数组dp的初始化是正确的。（）{{ select(30) }}

正确
错误

（3分）当输入为5和数组[3,1,4,2,5]时，程序的输出是（）。{{ select(31) }}

（3分）当输入为7和数组[7,6,5,4,3,2,1]时，程序的输出是（）。{{ select(32) }}

（4分）若要计算最长不下降子序列，应该如何修改程序？（）{{ select(33) }}

将第15行的<改为<=
将第15行的<改为>
将第15行的<改为>=
将第15行的<改为!=

三、完善程序（单选题，每小题 3 分，共计 30 分）

（一）

以下程序实现了单调队列优化的滑动窗口最大值问题。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    deque<int> dq;  
    vector<int> res;
    
    for(int i = 0; i < n; i++) {
       
        while(!dq.empty() && dq.front() < ①) {
            dq.pop_front();
        }
        
        while(!dq.empty() && a[dq.back()] ② a[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if(i >= ③) {
            ⑤;
        }
    }

    for(int i = 0; i < res.size(); i++) {
        cout << ④ << " ";
    }
    cout << endl;
    
    return 0;
}

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

i - k + 1
i - k
i - k - 1
i + k

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

'<='
'<'
'>='
'>'

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

k - 1
k
k + 1
0

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

res[i]
dq[i]
a[i]
i

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

res.push_back(a[dq.front()])
res.push_back(a[i])
res.push_back(dq.back())
res.push_back(i)

（二）

以下程序实现了图的深度优先搜索（DFS）遍历算法，用于计算图中的连通分量数目。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN]; 
bool visited[MAXN];   


void dfs(int u) {
    visited[u] = ①;
    
    for(int v : ②) {
        if(③) {
            dfs(v);
        }
    }
}

int main() {
    int n, m; 
    cin >> n >> m;
    

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        ④;
    }
    

    memset(visited, 0, sizeof(visited));
    
    int component = 0; 
    for(int i = 1; i <= ⑤; i++) {
        if(!visited[i]) {
            component++;
            dfs(i);
        }
    }
    
    cout << "连通分量数目: " << component << endl;
    return 0;
}

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

true
false
1
0

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

adj[u]
adj[v]
visited
u

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

!visited[v]
visited[v]
u != v
v > u

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

adj[v].push_back(u)
adj[u].push_back(u)
adj[v].push_back(v)
adj[u].push_back(v)

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

n
m
MAXN
component

在下列比赛中:

cspj初赛模拟赛1

#2510. CSP-J模拟卷9

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；每题有且仅有一个正确选项，除特殊说明外，每题 3 分，共计 40 分）

（一）

（二）

（三）

三、完善程序（单选题，每小题 3 分，共计 30 分）

（一）

（二）

相关

状态

开发

支持

关于

#2510. CSP-J模拟卷9

CSP-J模拟卷9

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

二、阅读程序（程序输入不超过数组或字符串定义的范围；每题有且仅有一个正确选项，除特殊说明外，每题 3 分，共计 40 分）

（一）

（二）

（三）

三、完善程序（单选题，每小题 3 分，共计 30 分）

（一）

（二）

相关

状态

开发

支持

关于

还没有账户？

登录