CSP-J模拟卷11

ID: 2511

客观题

尝试: 13

已通过: 0

难度: 10

上传者:

yhxx

标签>

CSP-J

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

（2分）以下关于C++中int类型变量的取值范围，正确的是（）。{{ select(1) }}

-2^31 ~ 2^31-1
-2^15 ~ 2^15-1
0 ~ 2^32-1
0 ~ 2^64-1

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

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

O(log n)
O(n)
O(n log n)
O(n²)

（2分）以下关于C++中指针的说法，错误的是？（）。{{ select(3) }}

指针可以指向任何数据类型
指针变量存储的是内存地址
空指针可以安全地访问数据
可以通过指针进行动态内存分配

（2分）十六进制数0xA7转换为二进制数是（）。{{ select(4) }}

10100111
10101111
10110111
10100110

（2分）在一个袋子中有5个红球和3个白球，随机取出一个球后放回，再取一个球，两次都是红球的概率是（）。{{ select(5) }}

25/64
15/64
5/8
3/8

（2分）以下哪种数据结构最适合实现优先队列？（）。{{ select(6) }}

二叉堆
栈
队列
链表

（2分）以下排序算法中，最坏情况下时间复杂度不是O(n²)的是（）。{{ select(7) }}

冒泡排序
快速排序
插入排序
归并排序

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

int a = 10, b = 3, c = 0;
int d = 2;
b = a++ - (--b) * d;
c = (a > b) ? (a % b) : (b % a);

（2分）以下关于计算机网络的说法，正确的是（）。{{ select(9) }}

TCP协议是无连接的协议
IP地址由32位组成，分为网络部分和主机部分
HTTP协议属于传输层协议
局域网的传输速率通常低于广域网

（2分）以下关于图的描述中，错误的是（）。{{ select(10) }}

在无向图中，边是没有方向的
图中的顶点可以没有边连接
邻接矩阵适合存储边数较多的稠密图
有向图中，顶点A到顶点B的边和顶点B到顶点A的边是同一条边

（2分）若整型变量x的值为5，y的值为3，则表达式x << 2 + y % 2的结果是（）。{{ select(11) }}

（2分）以下逻辑表达式与表达式 !(A || B) && (C || !D) 等价的是（）。{{ select(12) }}

(!A && !B) && (C || !D)
(!A && !B) || (C || !D)
(!A || !B) && (C || !D)
(!A && !B) && (C && !D)

（2分）一棵完全二叉树有100个节点，其中叶子节点的个数是（）。{{ select(13) }}

（2分）在10名学生中，选出3人参加数学竞赛，其中甲和乙两人中至少有一人参加，且丙不参加的选法有（）种。{{ select(14) }}

（2分）已知某二叉树的前序遍历序列为"ABDECF"，中序遍历序列为"DBEACF"，则其对应的后序遍历序列为（）。{{ select(15) }}

DEBFCA
DEBCFA
DBEACF
DBEFCA

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

（一）

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

const int MAXN = 1005;
int dp[MAXN][MAXN];
string s1, s2;

int lcs(int i, int j) {
    if(i == 0 || j == 0) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    if(s1[i-1] == s2[j-1]) {
        dp[i][j] = lcs(i-1, j-1) + 1;
    } else {
        dp[i][j] = max(lcs(i-1, j), lcs(i, j-1));
    }
    return dp[i][j];
}

int main() {
    cin >> s1 >> s2;
    int n = s1.length();
    int m = s2.length();
    memset(dp, -1, sizeof(dp));
    cout << lcs(n, m) << endl;
    return 0;
}

（1.5分）删除memset(dp, -1, sizeof(dp));不会影响程序的正确性？（）{{ select(16) }}

正确
错误

（1.5分）该程序使用了递归的方式实现，而不是动态规划。（）{{ select(17) }}

正确
错误

（1.5分）当输入为"ABCBDAB"和"BDCABA"时，程序输出为4。（）{{ select(18) }}

正确
错误

（1.5分）该程序的时间复杂度为O(nm)，其中n和m分别是两个字符串的长度。（）{{ select(19) }}

正确
错误

（3分）当输入为两个长度为100的随机字符串时，dp数组的使用大小是（）。{{ select(20) }}

100
200
10000
1000000

（3分）当输入为"ABCBAABCBAB"和"BCABCABCABC"时,程序输出为（）{{ select(21) }}

（二）

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

int n, k, m, Min = 0x7fffffff;
int f[501][501];

struct info
{
	int h, w;
}a[1001];

bool cmp(const info & x, const info & y)
{
	return x.h < y.h;
}

int main()
{
	cin >> n >> k;
	m = n - k;
	for(int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].h, &a[i].w);
	 
	sort(a+1, a+n+1, cmp);
	memset(f, 20, sizeof(f));
	 
	for(int i = 1; i <= n; i++)
		f[i][1] = 0;
	 
	for(int i = 2; i <= n; i++)        // 23题
		for(int j = 1; j <= i-1; j++)
			for(int l = 2; l <= min(i, m); l++)     // 24题
				f[i][l] = min(f[i][l], f[j][l-1] + abs(a[i].w - a[j].w));
	 
	for(int i = m; i <= n; i++)
		Min = min(Min, f[i][m]);
	 
	printf("%d\n", Min);
	return 0;
}

（1.5分）删除memset(f, 20, sizeof(f))不影响结果（）{{ select(22) }}

正确
错误

（1.5分）'// 23'那行,i从1开始,不影响结果（）{{ select(23) }}

正确
错误

（1.5分）'// 24题'那行,l从1开始,不影响结果。（）{{ select(24) }}

正确
错误

（3分）程序中使用的算法是（）。{{ select(25) }}

动态规划
深度优先搜索
广度优先搜索
贪心算法

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

O(n^2)
O(n^2m)
O(nm)
O(n^3)

（3分）若输入[6 1 2 6 3 5 2 1 3 5 1 2 3 6],则输出（）{{ select(27) }}

（三）

#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1005;
char s[MAXN];
int freq[26];
char res[MAXN];

int main() {
    scanf("%s", s);
    int len = strlen(s);
    
    for(int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    int idx = 0;
    for(int i = 0; i < 26; i++) {
        if(freq[i] % 2 == 1) {
            res[idx++] = 'a' + i;
            freq[i]--;
            break;
        }
    }
    
    for(int i = 0; i < 26; i++) {
        while(freq[i] > 0) {
            res[idx++] = 'a' + i;
            res[idx++] = 'a' + i;
            freq[i] -= 2;
        }
    }
    
    for(int i = 0; i < idx; i++) {
        printf("%c", res[i]);
    }
    printf("\n");
    
    return 0;
}

（1.5分）该程序的主要功能是统计字符串中每个字符的出现次数。（）{{ select(28) }}

正确
错误

（1.5分）该程序只能处理小写字母的字符串。（）{{ select(29) }}

正确
错误

（1.5分）当输入字符串为"aabbcc"时，程序输出的结果是"aabbcc"。（）{{ select(30) }}

正确
错误

（3分）当输入字符串为"abcde"时，程序输出的结果是（）。{{ select(31) }}

abcde
abbccddee
aabccee
无法确定

（3分）改程序的时间复杂度为（）。{{ select(32) }}

O(n)
O(n^2)
O(nlogn)
O(1)

（4分）若将程序中的第19行break语句删除，程序的功能会发生什么变化？（）{{ select(33) }}

程序可能会少输出字符
程序可能奔溃
程序正确运行
程序运行时间会缩短

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

（一）

以下程序实现了并查集（Union-Find）数据结构，用于解决连通性问题。

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

const int MAXN = 1005;
int parent[MAXN];
int rank_[MAXN];

void init(int n) {
    for(int i = 0; i <= n; i++) {
        parent[i] = ①;
        rank_[i] = 0;
    }
}

int find(int x) {
    if(parent[x] != x) {
        parent[x] = ②;
    }
    return parent[x];
}

void unite(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if(root_x == root_y) return;
    
    if(rank_[root_x] < rank_[root_y]) {
        ③;
    } else {
        parent[root_y] = root_x;
        if(rank_[root_x] == rank_[root_y]) {
            ④;
        }
    }
}

bool isConnected(int x, int y) {
    return ⑤ == find(y);
}

int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        unite(u, v);
    }
    
    int query;
    cin >> query;
    while(query--) {
        int a, b;
        cin >> a >> b;
        if(isConnected(a, b)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

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

i
0
-1
n

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

find(parent[x])
find(x)
find(parent[parent[x]])
x

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

parent[root_x] = root_y
parent[root_y] = root_x
rank_[root_x]++
rank_[root_y]++

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

rank_[root_x]++
rank_[root_y]++
parent[root_x] = root_y
parent[root_y] = root_x

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

find(x)
parent[x]
x
parent[y]

（二）

以下程序实现了二分查找算法，用于在有序数组中查找目标值的插入位置。

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

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = ①;
    
    while(left <= right) {
        int mid = left + (right - left) / 2;
        
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] > target) {
            right = ②;
        } else {
            left = ③;
        }
    }

    return ④;
}

int lower_bound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int ans = nums.size();
    
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] >= target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return ans;
}

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    int insert_pos = ⑤;
    cout << "插入位置: " << insert_pos << endl;

    int lb_pos = lower_bound(nums, target);
    cout << "lower_bound位置: " << lb_pos << endl;
    
    return 0;
}

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

nums.size() - 1
nums.size()
0
1

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

mid - 1
mid + 1
left
right

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

mid + 1
mid - 1
left
right

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

left
right
mid
0

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

searchInsert(nums, target)
lower_bound(nums, target)
searchInsert(target, nums)
lower_bound(target, nums)

在下列比赛中:

cspj初赛模拟赛2

#2511. CSP-J模拟卷11

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

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

（一）

（二）

（三）

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

（一）

（二）

相关

状态

开发

支持

关于

#2511. CSP-J模拟卷11

CSP-J模拟卷11

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

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

（一）

（二）

（三）

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

（一）

（二）

相关

状态

开发

支持

关于

还没有账户？

登录