#ACSP1009. cspj-模拟题9

cspj-模拟题9

普及组CSP-J2024初赛模拟卷9

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

  1. 已知数组A中，每个元素A[i][j]在存储时要占3字节，设i从1变化到8，j从1变化到10，分配内存时是从地址 SA 开始连续按行存储分配的。试问：A[4][7]的起始地址是什么？（{{ select(1) }}）
  • SA+108
  • SA+141
  • SA+111
  • SA+126
  1. 以下关于算法的描述正确的是（{{ select(2) }}）。
  • 算法可以没有输出
  • 算法至少有一个输入
  • 算法必须在计算机上用某种语言实现
  • 算法的改进在很大程度上推动了计算机科学与技术的进步
  1. 执行下述C++代码，输出的结果是（{{ select(3) }}）。
    #include< bits/ stdc++. h>
using namespace std;
int main() {
    int pos=2;
    string s=(" noip");
    cout<<s[++ pos]<< endl;
    return 0;
}
  • 0
  • i
  • p
  • 空格

4.（{{ select(4) }}）表示只读存储器。

  • HDD
  • SSD
  • ROM
  • RAM

5.有关下面C++代码的说法，正确的是（{{ select(5) }}）。

  • fun函数可以求出a和b的最大公共质因子
  • fun函数可能会死循环
  • 如果a小于9，那么 cnt 的值不会超过20
  • fun函数能够求出a和b的最小公倍数
    int cnt;
int fun(int a, int b) {
    int tmp;
    if(0==b) tmp=a;
    else {
        tmp = fun(b,a%b);
        cnt++;
    }
    return tmp;
}

6.以下哪个不属于与STL有关的函数？（{{ select(6) }}）

  • swap
  • sort
  • max
  • freopen

7.在顺序表(1,3,7,10,14,15,19,26,38,47,85)中,用二分法查找13, 所需的关键码比较的次数为（{{ select(7) }}）。

  • 2
  • 3
  • 4
  • 5

8.在下列各种排序算法中，关键字比较的次数与记录的初始排列次序无关的是（{{ select(8) }}）。

  • 插入排序
  • 快速排序
  • 选择排序
  • 冒泡排序

9.下列说法中正确的是。() {{ select(9) }}

  • 计算机网络按照地理范围分为局域网、城域网和广域网
  • 互联网的基础TCP/IP 是七层协议
  • 每台计算机配置的都是 C类IP 地址
  • 中国的计算机 IP 地址已经全部升级到了 IPv6地址

10.在U盘中发现计算机病毒后，较为彻底的清除方法是（{{ select(10) }}）。

  • 删除U盘文件
  • 格式化U盘
  • 用消毒水喷洒在U盘上
  • 用杀毒软件处理

11.下列关于十进制数101的说法中错误的是（{{ select(11) }}）。 注: 这里B 表示二进制 Binary, H 表示十六进制 Hexadecimal。

  • 该数原码为01100101B
  • 该数反码为65H
  • 该数真值为01100011B
  • 该数补码为65H

12.动态规划将一个问题分解为一系列子问题来求解。下面关于子问题的描述中正确的是（{{ select(12) }}）。

  • 具有重叠子问题的性质
  • 和分治法的子问题类似
  • 不具有最优子结构的性质
  • 问题的最优解可以由部分子问题的非最优解推导出来

13.在下面的有向图中，有多少个强连通分量？（{{ select(13) }}）

  • 3
  • 4
  • 5
  • 6

14.从4台甲型电视机和5台乙型电视机中任意取出3台，其中至少要甲型电视机与乙型电视机各一台，则不同的取法共有（{{ select(14) }}）种。

  • 140
  • 70
  • 80
  • 35

15.在32位计算机中，用补码表示的C++的整型变量int能够表示的数据范围是（{{ select(15) }}）。

  • 0∼231−10\sim 2^{31}-1
  • 0∼2320\sim 2^{32}
  • −231∼231−1-2^{31}\sim 2^{31}-1
  • −231+1∼231-2^{31}+1\sim 2^{31}

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

(1)

#include < bits/ stdc++. h>
using namespace std;
priority   queue < int, vector< int>, greater< int> > q;
int main() {
    int n,x, ans=0,t1=0,t2=0,t3=0;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin>>x;
        q. push(x);
    }
    for(int i=n; i>1; i--) {
        t1= q. top();
        q. pop();
        t2 = q. top();
        q. pop();
        t3 = t1+t2;
        ans += t3;
        q. push(t3);
    }
    cout<< ans<< endl;
    return 0;
}

判断题

16.priority queue是STL 中的优先队列。（{{ select(16) }}）

  • 正确
  • 错误

17.将第3行中的 greater去掉，不管输入如何，程序的运行结果都不变。（{{ select(17) }}）

  • 正确
  • 错误

18.将第15行和第17行互换，不管输入如何，程序的运行结果都不变。（{{ select(18) }}）

  • 正确
  • 错误

19.将第21行去掉，不管输入如何，程序的运行结果都不变。（{{ select(19) }}）

  • 正确
  • 错误

选择题

20.若输入3 1 2 9, 则输出 ans为（{{ select(20) }}）。

  • 12
  • 22
  • 23
  • 15

21.若输入4 5 4 3 6, 则输出 ans为（{{ select(21) }}）。

  • 30
  • 36
  • 37
  • 38

(2)

#include < bits/ stdc++.h>
using namespace std;
typedef long long LL;
LL fun(int a, int b, LL &x, LL &y) {
    if(0==b) {
        x=1;
        y=0;
        return a;
    }
    LL d = fun(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}
int main() {
    LL a,b,x=0,y=0;
    cin >> a >> b;
    cout << fun(a, b, x, y) << endl;
    cout << x << " " << y << endl;
    return 0;
}

判断题

22.将第3行中的 typedef long long LL 改为# define long long LL, 程序的运行结果不会改变。（{{ select(22) }}）

  • 正确
  • 错误

23.将第4行中的两个&去掉，程序的运行结果不会改变。（{{ select(23) }}）

  • 正确
  • 错误

24.若输入b=0，则输出结果是 a 0 1。（{{ select(24) }}）

  • 正确
  • 错误

25.若输入两个为素数的正整数，则输出结果中，x和y一定有负数。（{{ select(25) }}）

  • 正确
  • 错误

选择题

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

  • 2024
  • 2024
  • 0
  • 0

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

  • 144
  • 144
  • 12
  • 12

(3)

#include < bits/ stdc++. h>
using namespace std;
int a[101][3], b[101];
void dfs(int k, int w) {
    if(1==w)
        cout<<k<<" ";
    if(a[k][1]!=0)
        dfs(a[k][1],w);
    if(2==w)
        cout<<k<<" ";
    if(a[k][2]!=0)
        dfs(a[k][2],w);
    if(3==w)
        cout<<k<<" ";
}
int main() {
    int n, m, t, root;
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>t;
        cin>>a[t][1]>>a[t][2];
        b[a[t][1]]=1;
        b[a[t][2]]=1;
    }
    for (int i=1; i<=n; i++)
        if(b[i]==0) {
            root=i;
            break;
        }
    dfs(root,1);
    cout<< endl;
    return 0;
}

判断题

28.dfs函数是处理二叉树的前、中、后序遍历的。（{{ select(28) }}）

  • 正确
  • 错误

29.若将第24行 cin>>a[t][1]>>a[t][2]更改为 cin>>a[1][t]>>a[2][t],程序的运行结果不会改变。（{{ select(29) }}）

  • 正确
  • 错误

30.若将第29行去掉，程序的运行结果不会改变。（{{ select(30) }}）

  • 正确
  • 错误

31.若将第34行 dfs(root,1)更换为 dfs(root,4), 程序的运行结果不会改变。（{{ select(31) }}）

  • 正确
  • 错误

选择题

32.若输入如下数据，则输出是（{{ select(32) }}）。

  • 3 12 4 8 5 6 7
  • 2 1 8 4 3 6 7 5
  • 2 8 4 1 7 6 5 3
  • 3 2 1 8 4 5 7 6
    8
1 2 4
20 0
4 8 0
3 15
5 6 0
7 0 0

33.若输入和第32题一样, 将第34行 dfs(root,1)更换为 dfs(root,2), 则输出是（{{ select(33) }}）。

  • 3 12 4 8 5 6 7
  • 2 1 8 4 3 6 7 5
  • 2 8 4 1 7 6 5 3
  • 3 2 1 8 4 5 7 6

34.若输入和第32题一样, 将第34行 dfs(root,1)更换为 dfs(root,3), 则输出是（{{ select(34) }}）。

  • 3 1 24 8 5 6 7
  • 2 1 8 4 3 6 7 5
  • 2 8 4 1 7 6 5 3
  • 3 2 1 8 4 5 7 6

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

(1) 米老鼠上次在唐老鸭的迷宫城堡里玩了很久，现在她也想设计一个迷宫让唐老鸭来走。

但是她设计迷宫的思路不一样，她认为所有的通道都应该是双向连通的，也就是说，如果有一个通道连通了房间A 和房间B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A。

为了提高难度，米老鼠希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。米老鼠现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。

比如下面的例子，前两个是符合条件的，但是最后一个有两种方法从5到达8。

输入格式：

输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。整个输入以两个-1结尾。

输出格式：

对于输入的每一组数据，输出仅包括一行。如果该迷宫符合米老鼠的思路，那么输出 YES,否则输出NO。

输入样例：

6 8 5 3 5 2 6 4 5 6 0 0
8 1 7 3 6 2 8  9 7 5 7 4 7 8 7 6 0 0
3 8 6 8 6 4 5 3 5 6 5 2 0 0
-1-1

输出样例：

YES
YES
NO

#include< iostream>
using namespace std;
#define MAXN 100005
int fa[MAXN];
int visit[MAXN];
int path, node;
void init(int n){
    for(int i=1;i<=n;++i) {
        fa[i] = i;
        visit[i] = 0;
    }
    path = 0;
    node = 0;
}
int get(int x){
    if(x == fa[x])
        return x;
    else
        return ①;
}
int main(){
    int a,b;
    bool flag;
    cin>>a>>b;
    while(a!=-1 && b!=-1){
        init(MAXN);
        flag = true;
        if(0==a && 0==b)
            path--;
        while(②){
            path++;
            if(visit[a]==0){
                visit[a]=1;
                node++;
            }
            if(visit[b]==0){
                visit[b]=1;
                node++;
            }
            int root1= get(a);
            int root2= get(b);
            if(③)
                flag = false;
            else
                ④;
            cin>>a>>b;
        }
        if(⑤)
            cout<<"NO"<< endl;
        else
            cout<<"YES"<< endl;
        cin>>a>>b;
    }
    return 0;
}

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

  • fa[x]
  • x
  • fa[x] = get(fa[x])
  • 1

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

  • a!=0 || b!=0
  • a!=0 && b!=0
  • a!=0
  • b!=0

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

  • root1 == root2
  • root1 != root2
  • flag == true
  • visit[a] == visit[b]

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

  • fa[root1] = root1
  • fa[root2] = root2
  • fa[root1] = root2
  • flag = true

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

  • path != node && !flag
  • path != node || !flag
  • path != node-1 && !flag
  • path != node-1 || !flag

(2)

给定一个字符串，请计算至少添加几个字符，可以让其构成回文字符串。

输入样例：

5
acbcd

输出样例：

2

#include< bits/ stdc++. h>
using namespace std;
#define MAXN 5005
char str1[MAXN], str2[MAXN];
int maxlen[2][MAXN];
int main() {
    int n;
    while(cin>>n) {
        for(int i=1;i<=n;++i)
            cin>>str1[i];
        str1[n+1]='\0';
        for(int i=1; i<=n; ++i)
            ①;
        memset(maxlen,0, sizeof(maxlen));
        int x=0;
        for(int i=1; i<=n; ++i) {
            x = 1-x;
            for(int j=0; j<=n; ++j) {
                if(str1[i] == str2[j])
                    ②;
                else {
                    int len1 = ③;
                    int len2 = maxlen[1-x][j];
                    if(④)
                        maxlen[x][j] = len1;
                    else
                        maxlen[x][j] = len2;
                }
            }
        }
        cout<<⑤<< endl;
    }
    return 0;
}

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

  • str2[i] = str1[i]
  • str2[i] = str1[n-1-i]
  • str2[i] = str1[n-i]
  • str2[i] = str1[n+1-i]

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

  • maxlen[x][j] = maxlen[1-x][j-1] + 1
  • maxlen[x][j] = maxlen[x-1][j-1] + 1
  • maxlen[x][j] = maxlen[1-x][j] + 1
  • maxlen[x][j] = maxlen[x-1][j] + 1

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

  • maxlen[x][j]
  • maxlen[x][j+1]
  • maxlen[x][j-1]
  • maxlen[1-x][j-1]

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

  • len1 > len2 + 1
  • len1 > len2
  • len2 > len1
  • len2 > len1 + 1

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

  • maxlen[x][n]
  • n-maxlen[x][n]
  • maxlen[1-x][n]
  • n-maxlen[1-x][n]
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2022008388号-1
  3. Worker 0, 112ms
  4. Powered by Hydro v4.19.1 Community