ID: 58

Type: Objective

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

jike1994

Tags>

满分之路

普及组CSP-J2024 初赛模拟卷

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

在C++语言中，以下哪种方式不能用于向函数传递参数？（{{ select(1) }}）

值传递
模板传递
引用传递
指针传递

以下关于算法的描述中正确的是（{{ select(2) }}）。

算法是为解决问题而编制的计算机程序
算法是为解决问题而采用的计算机程序设计语言
算法是为解决问题而采用的计算方法
算法是为解决问题而采取的方法与步骤

在关系数据库中，存放在数据库中的数据的逻辑结构以（{{ select(3) }}）为主。

二维表
二叉树
哈希表
邻接表

设某算法的时间复杂度函数的递推方程是 T(n)=T(n-1)+n(n为正整数)及 T(0)=1,则该算法的时间复杂度为（{{ select(4) }}）。

O(logn)
O(n)
O(n²)
O(nlogn)

在C++语言中，一般提到的“空间复杂度”中的“空间”是指（{{ select(5) }}）。

程序运行时所占的内存大小
程序运行时所占的数组大小
程序运行时所占的硬盘大小
程序源文件所占的硬盘大小

2017年9月30日是星期六, 1999年9月30 日是（{{ select(6) }}）。

星期三
星期六
星期五
星期四

设栈S的初始状态为空，元素1，2，3，4，5依次入栈，以下出栈序列中不可能出现的是（{{ select(7) }}）。

1,2,3,5,4
2,3,1,5,4
1,5,3,2,4
4,3,5,2,1

关于分治算法，下列说法中错误的是（{{ select(8) }}）。

分治算法的核心思想是分而治之，把问题转化为多个规模更小的子问题再求解
分治算法可以不使用递归实现
分治算法的时间复杂度是O(logn)，其中n表示问题的规模
二分法、快速排序等算法都是使用分治思想的典型算法

如下代码主要表示什么数据结构？（{{ select(9) }}）

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* prev;
    struct ListNode* next;
    LTDataType data;
} LTNode;

单向链表
双向链表
循环链表
优先队列

10.使用如下代码片段定义4个字符串（假设头文件已正确定义），以下说法中错误的是（{{ select(10) }}）。

对于4个字符串, 都可以使用std::cout输出其中的内容(例如, cout<<str3;)
str3只占用4字节内存，但str1要占用更多内存
由于 str2 由str1直接赋值得到，因此二者指向同一块内存，即修改 str1 的内容后 str2的内容也会随之改变
由于 str4 由str3直接赋值得到，因此二者指向同一块内存，即修改 str3的内容后 str4的内容也会随之改变
```
string str1 = "csp";
string str2 = str1;
char str3[] = "csp";
char * str4 = str3;
```

11.冯·诺依曼体系结构中组成计算机的五大部件是（{{ select(11) }}）。

总线、处理器、存储器、输入设备、输出设备
处理器、运算器、存储器、输入设备、输出设备
总线、控制器、存储器、输入设备、输出设备
控制器、运算器、存储器、输入设备、输出设备

12.如下代码对树的操作是（{{ select(12) }}）。

后序遍历
中序遍历
前序遍历

层次遍历

void postorder(tree bt) {
   if(bt) {
       postorder(bt->lchild);
       postorder(bt->rchild);
       cout << bt->data;
   }
}

13.有规格尺寸相同的5种颜色的手套（不分左右）各 15 只混装在箱子里，从中至少取出多少只，才能保证配出3副颜色相同的手套？（{{ select(13) }}）

14.由3个a、5个b和2个c构成的字符串中, 包含子串"abc"的共有（{{ select(14) }}）个。

39600
780
840
260

15.1 GB 代表的字节数量是（{{ select(15) }}）。

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填✔，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

#include<bits/stdc++. h>
using namespace std;
const int SIZE = 25;
int n,k,a[SIZE];
int cnt=0;
long long ans;
bool isPrime(int n) {
    cnt++;
    cout<<cnt<<endl;
    if(n<=1) return false;
    for(int i=2;i*i<=n;++i)
        if(0==n%i) return false;
    return true;
}
void dfs(int m, int sum, int x) {
    if(m==k) {
        if(isPrime(sum)) {
            ans++;
        }
        return;
    }
    for(int i=x;i<n;++i)
        dfs(m+1, sum+a[i],i+1);
    return;
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n;++i)
        cin >> a[i];
    dfs(0,0,0);
    cout << ans <<endl;
    return 0;
}

判断题

16.将第13行中的i*i<=n改为i<=sqrt(n), 程序的运行结果不会改变。（{{ select(16) }}）

正确
错误

17.将第14行中的if(0==n%i)改为if(n%i==0), 程序的运行结果不会改变。（{{ select(17) }}）

正确
错误

18.若输入k值比n大，则程序会死循环，无输出。（{{ select(18) }}）

正确
错误

19.将第29行中的sum+a[i]改为 sum+=a[i], 程序的运行结果不会改变。（{{ select(19) }}）

正确
错误

选择题

20.若输入k的值为6，且输入 n>=k，a数组的元素均为相等的正整数，则输出为（{{ select(20) }}）。

21.若输入 12 8, 则isPrime被调用的次数为（{{ select(21) }}）。

(2)

#include <bits/stdc++. h>
using namespace std;
int CNT, p;
int check(int tmp, int n) {
    int res = 0;
    for(int i=tmp; i>0; i--) {
        res += n;
        int a=0, ans=res;
        while(ans%n == 0)
            a++, ans/=n;
        i -= a-1;
    }
    return res;
}
int main() {
    cin >> CNT;
    while(CNT--) {
        int ans=1;
        cin >> p;
        for(int i=2; i<=sqrt(p); i++) {
            int tmp=0;
            while(p%i == 0)
                tmp++, p/=i;
            if(tmp)
                ans = max(ans, check(tmp,i));
        }
        ans = max(ans,p);
        cout<<ans<<endl;
    }
    return 0;
}

判断题

22.若输入1 2，程序的输出会报错。（{{ select(22) }}）

正确
错误

23.若将第27行中的while 改为if, 程序的输出结果不变。（{{ select(23) }}）

正确
错误

24.若输入p是一个素数，则程序中的第30行不会被执行。（{{ select(24) }}）

正确
错误

25.若输入p是一个素数，则输出ans的值为p。（{{ select(25) }}）

正确
错误

选择题

26.若输入1 36, 则输出为（{{ select(26) }}）。

27.若tmp < n, 则返回的res结果为（{{ select(27) }}）。

n
tmp
tmp*n
tmp+n

(3)

#include<iostream>
#include<string>
#include<set>
using namespace std;
string a, s[105];
int cnt=0;
set<string>dict;
void trim(string &s) {
    if(!s.empty()) {
        s.erase(0,s.find_first_not_of(" "));
        s.erase(s.find_last_not_of(" ")+1);
    }
}
int main() {
    cin>>a;
    while(a!="#") {
        int length = a.length();
        for(int i=0;i<length;i++)
            if(isalpha(a[i]))
                a[i] = tolower(a[i]);
            else
                a[i] = ' ';
        trim(a);
        s[cnt]=a;
        dict.insert(a);
        cnt++;
        cin>>a;
    }
    for(set<string>::iterator it=dict.begin();it!=dict.end();++it)
        cout << *it << " ";
    return 0;
}

判断题

28.STL 中的set属于关联式容器。（{{ select(28) }}）

正确
错误

29.若将第6行中的int cnt=0替换为int cnt, 程序的运行结果不会改变。（{{ select(29) }}）

正确
错误

30.若将第21行中的a.length()替换为a.size(), 程序的运行结果不会改变。（{{ select(30) }}）

正确
错误

31.若输入34 12 56 #, 则程序输出12 34 56。（{{ select(31) }}）

正确
错误

选择题

32.若输入为A Dream Is To Build A Big Big World #, 则输出是（{{ select(32) }}）。

A Dream Is To Build A Big Big World
a dream is to build a big big world
a big build dream is to world
A Big Build Dream Is To World

33.若输入为 WorldYiwu AsiaShanghai ChinaHangzhou ZhejiangJinhua #, 则输出是（{{ select(33) }}）。

WorldYiwu AsiaShanghai ChinaHangzhou ZhejiangJinhua
worldyiwu asiashanghai chinahangzhou zhejiangjinhua
AsiaShanghai ChinaHangzhou WorldYiwu ZhejiangJinhua
asiashanghai chinahangzhou worldyiwu zhejiangjinhua

34.若输入为I am 12 years old. #, 则输出是（{{ select(34) }}）。

am i old years
am I old years
I am years old.
I am 12 years old.

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

(1)

假设有一个无向图，将这个无向图的某一条欧拉路或者欧拉回路用算法实现并打印出来。

无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度节点（度数为奇数的顶点）或者无奇度节点。

当G是仅有两个奇度节点的连通图时，G的欧拉通路必以此两个节点为端点

当G是无奇度节点的连通图时，G必有欧拉回路

为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度节点的连通图

提示：欧拉通路/回路的算法流程，选择一个正确的起始顶点，用DFS算法遍历所有的边（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。

输入格式：

第1行是n和m，表示有n个点和m条边，以下m行描述每条边连接的两点。

输入样例：

输出格式：

欧拉路或欧拉回路。

输出样例：

1 5 4 3 2 1

#include<bits/stdc++. h>
using namespace std;
#define MAXN 105
int g[MAXN][MAXN];
int du[MAXN];
int circuit[MAXN];
int n,e, circuitpos,x,y, start;
void find_circuit(int i) {
    for (int j = 1; j <= n; j++)
        if (①) {
            g[j][i] = 0;
            g[i][j] = 0;
            find_circuit(j);
        }
    ②;
}
int main() {
    memset(g,0, sizeof(g));
    cin >> n >> e;
    for (int i = 1; i <= e; i++) {
        cin >> x >> y;
        g[y][x] = 1;
        ③;
        du[x]++;
        du[y]++;
    }
    start = 1;
    for (int i = 1; i <= n; i++)
        if (④)
            start = i;
    circuitpos = 0;
    ⑤;
    for (int i = 1; i <= circuitpos; i++)
        cout << circuit[i] << ' ';
    cout << endl;
    return 0;
}

35.①处应填（{{ select(35) }}）。

g[i][j] == 0
g[i][j] == 1
du[i] == 1
du[j] == 1

36.②处应填（{{ select(36) }}）。

circuit[++circuitpos] = i
circuit[circuitpos] = i
circuit[j] = i
circuit[i] = j

37.③处应填（{{ select(37) }}）。

start=1
start=0
g[x][y]=1
g[x][y]=0

38.④处应填（{{ select(38) }}）。

g[i][j] % 2 == 0
g[i][j] % 2 == 1
du[i] % 2 == 0
du[i] % 2 == 1

39.⑤处应填（{{ select(39) }}）。

find_circuit(0)
find_circuit(start)
find_circuit(1)
find_circuit(n)

(2)

设一棵n结点的二叉树tree 的中序遍历为(1,2,3,…,n), 其中数字1,2,3,…,n为结点编号。每个结点都有一个分数（均为正整数），记第 i个结点的分数为 d₁，tree 及它的每棵子树都有一个加分，任意一棵子树subtree（也包含 tree 本身）的加分计算方法如下：

subtree 的左子树的加分×subtree 的右子树的加分+subtree的根的分数

若某棵子树为空，规定其加分为1。叶子的加分就是叶子结点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为(1，2，3，…，n)且加分最高的二叉树 tree。

要求输出：(1) tree的最高加分；(2) tree 的前序遍历。

输入格式：

第1行是一个整数n，为结点个数。第2行是 n个用空格隔开的整数，为每个结点的分数（0<分数<100）。

输出格式：

第1行是一个整数，为最高加分（结果不会超过int范围）。

第2行是n个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围：n<30。

输入样例：

5
5 7 1 2 10

输出样例：

145
3 1 2 4 5

#include<bits/stdc++. h>
using namespace std;
const int N=30;
int n, w[N], f[N][N], rt[N][N];
void print(int l, int r) {
    if(l > r) return;
    ①;
    printf("%d ", root);
    ②;
    print(root+1, r);
}
int main() {
    memset(f,0, sizeof(f));
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%d", &w[i]);
        ③;
        rt[i][i] = i;
    }
    for (int l=n; l>=1; l--)
        for(int r=l+1; r<=n; r++)
            for(int root=l; root<=r; root++) {
                int lw=f[l][root-1];
                ④;
                if(lw == 0) lw = 1;
                if(rw == 0) rw = 1;
                if( ⑤ ) {
                    f[1][r] = lw*rw+w[root];
                    rt[l][r] = root;
                }
            }
    printf("%d\n", f[1][n]);
    print(1, n);
    printf("\n");
    return 0;
}

40.①处应填（{{ select(40) }}）。

int root = 0
int root = 1
int root = rt[l][r]
int root = rt[1][n]

41.②处应填（{{ select(41) }}）。

print(1, root-1)
print(l, root-1)
print(1, root)
print(l, root)

42.③处应填（{{ select(42) }}）。

f[i][i] = 0
f[i][i] = 1
f[i][i] = i
f[i][i] = w[i]

43.④处应填（{{ select(43) }}）。

int rw=f[root][r]
int rw=f[root+1][r]
int rw=f[root][n]
int rw=f[root+1][n]

44.⑤处应填（{{ select(44) }}）。

lw*rw+w[root] > f[l][r]
lw*rw+w[root] < f[l][r]
lw*rw+w[root] > f[1][n]
lw*rw+w[root] < f[1][n]

#ACSP1008. cspj-模拟题8

cspj-模拟题8

普及组CSP-J2024 初赛模拟卷

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填✔，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

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

Status

Development

Support

#ACSP1008. cspj-模拟题8

cspj-模拟题8

普及组CSP-J2024 初赛模拟卷

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填✔，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

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

Status

Development

Support

SIGN IN