2023 云斗学院软件能力认证第一轮（YDSP-Junior）入门级 C++ 语言试题

ID: 306

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

admin

标签>

初赛

J组

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

CCF 的全称是（）。

Coin Collecting Federation
China Cheating Federation
China Computer Federation
Chinese Computer Foundation

集合 $[1,100]\cup[32,44]\cup[111,144]\cup[199,211]\cup[100,112]$ 中有（）个整数。

$(114)_7$ 和 $(514)_{16}$ 的最大公约数的十进制表示是（）。

2
4
6
1300

下列（）不是计算机的存储设备。

RAM
U 盘
硬盘
光盘驱动器

以序列 ABCDEFG，对一个初始为空的栈依次进行入栈、入栈、出栈、入栈、入栈、入栈、出栈、入栈、出栈、出栈、入栈的操作，最终栈中的元素从栈顶到栈底依次为（）。

ACDG
ACG
EFG
CDG

语句 freopen("input","r",stdin) 的含义解释正确的是（）。

从 input.txt 中读入文件
输出到 input.in
从 input 读入文件
输出到 input

对于两个布尔变量 $x,y$ ，前缀表达式 && || x y ! && x y 等价于中缀表达式（）。

x and y
x or y
x xor y
x == y

大浮点数加上小浮点数会产生很大的精度损失。在计算正浮点数总和时，为了减小精度误差，一种算法是每次取最小的两个，并用和替代这两个浮点数。这个过程接近于（）。

求图上两点间最短路径
求一定背包容量能装下物品价值和最大值
画一棵完全二叉树
求一堆数字的哈夫曼编码

前序遍历为 IHEABCDGF，后序遍历为 ABEGFDCHI 的二叉树，中序遍历不可能是（）。

AEBHGDCFI
AEBHCGDFI
IAEBHGDFC
IAEBHCGDF

如果 $a,b,c$ 均为 int 类型且绝对值不超过 $10^9$ ，那么 C++ 中下列一定成立的是（）。

max(a,b)+c==max(a,b+c)
max(a,b)*1ll*c==max(a*1ll*c,b*1ll*c)
max(a*2,b*2)+c==max(a*2+c,b*2+c)
2*min(a,b)==a+b-abs(a-b)

现有 24 个一样的苹果，要分给三个小朋友，且每个小朋友至少获得 2 个，方案数有（）种。

现有数列 $a$ ，规定 $S(l,r)=a_l+a_{l+1}+\cdots+a_r$ ，且 $S(1,12)=31$ ， $S(7,12)=17$ ， $S(10,20)=16$ ， $S(7,20)=24$ ，那么 $S(1,9)$ 为（）。

一款音乐游戏的计分方式是：假如某局游戏有 $n$ 个音符，那么每个音符的基础分 $m$ 为 $\dfrac{10^7}{n}$ ；对于每个音符，可能有 Max Pure、Pure、Far、Lost 四种判定，分别可以拿 $m+1,m,0.5m,0$ 分。

称一次游玩为“PM”，当且仅当所有音符都是 Max Pure 或 Pure，不难发现 PM 得分一定不小于 $10^7$ ；称一次游玩为“伪 PM”，当且仅当这次游玩分数不小于 $10^7$ ，且存在 Far 或 Lost。

这款游戏中有三首曲目名称以 T 开头的歌曲，分别有 2221、1540、1392 个音符。这三首歌曲中，有（）首可能产生伪 PM。

下列程序的输出是（）。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s="yUMmyadoRAbLE";
    for(int i=1;i<s.size();i++)
        if('A'<s[i] && s[i]<='Z')
            swap(s[i],s[s.size()-i]);
    cout<<s;
    return 0;
}

yUMmyadoRAbLE
yUMmyRdoaAbLE
yUMmARdoaybLE
EUMmRadoyAbLy

$G$ 有 6 个结点 $1,2,3,4,5,6$ 以及 7 条边 $(1,2),(1,3),(2,4),(3,4),(4,5),(4,6),(5,6)$ 。若以（）为起点，对这张图进行深度优先遍历，得到的遍历序可能性最多。

1
2 或 3
4
5 或 6

二、阅读程序（无特殊说明时，判断题每题 1.5 分，选择题每题 3 分，3 题共计 40 分）

判断题中，正确选“正确”，错误选“错误”。

（1）阅读程序，完成第 16～21 题（共 12 分）

#include <bits/stdc++.h>
using namespace std;
union yun{
    int a[3];
    long long b;
}u,v;
int main(){
#define S(x) x*x
    cout<<S(3<<1)<<'\n';
    u.a[0]=1;
    u.a[1]=2;
    u.a[2]=0;
    cout<<sizeof sizeof v<<endl;
    cin>>v.b;
    switch(v.b){
    case 1:
        putchar((0110 ^ 101)-35);
    case 2:
        cout<<u.a[v.b[u.a][u.a]];
        return 0;
    case0:
        cout<<v.b+5;
    default:
        memset(&v,v.b,sizeof v);
        int i=2;
        while(i --> 0)
            cout<<hex<<max(v.a[i],1);
    }
    return 0;
}

输出的第二行是 8。（）

正确
错误

如果输入 400，那么程序会出错。（）

正确
错误

在第 13 行执行后，输出 u.b 是未定义行为。（）

正确
错误

第 27 行换成 cout<<hex<<(v.a[i]>100?v.a[i]:1);，效果不变。（）

正确
错误

输出的第一行是（）。

36
48
192
前三个选项都不正确

在输出的第三行中过滤非数字字符后，可能得到下列哪个数字？

1
511
20202022020202
前三个选项都不正确

（2）阅读程序，完成第 22～28 题（共 15 分）

#include <cstdio>

#define base 2
#define Y 1799
using namespace std;
int d_y[3010],d_m[13];
int sum_y[3010],sum_m[13];
int check(int i){
    return !(i%400) || i%100 && !(i%4);
}
void init(){
    for(int i=Y+1;i<=3000;i++){
        d_y[i]=365+check(i);
        sum_y[i]=sum_y[i-1]+d_y[i];
    }
    for(int i=1;i<=12;i++){
        if((i<8 && i&1) || (i>7 && !(i&1))) d_m[i]=31;
        else if(i==2) d_m[i]=28;
        else d_m[i]=30;
        sum_m[i]=sum_m[i-1]+d_m[i];
    }
}
int main(){
    init();
    int y,m,d,ans;
    scanf("%d%d%d ",&y,&m,&d);
    ans=sum_y[y-1]+sum_m[m]-d_m[m]+d+base;
    if(check(y) && m>2 || (m==2 && d==29)) ans++;
    printf("%d\n",ans%7);
    return 0;
}

程序满足输入 $y\ge 1800$ ， $m,d$ 均合法。

第 28 行中的判断 (m == 2 && d == 29) 多余。（）

正确
错误

当 $y=4\times 10^3$ 时，程序仍能输出正确结果。（）

正确
错误

将第 17 行的所有不等号后添加 = 号，对答案没有影响。（）

正确
错误

应将 sum_y 数组的 int 类型改为 long long 类型。（）

正确
错误

将 Y 与 base 分别替换为（）时，对程序输出没有影响。

1798, 3
1798, 1
1799, 2 * (int)cos(0)
1800, 3

输入为 2019 3 1 时，程序输出为（）。

下列做法中，对程序结果有影响的是（）（除了该做法外不进行任何其他操作）。

对于数组 d_m，不使用数组而仅用一个变量对数组 sum_m 进行累加。
将 sum_y 数组中所有数初始化为 365 ^ 1。
在第 24 行不调用 init()，而在第 26 行后调用 init()。
交换第 27、28 两行。

（3）阅读程序，完成第 29～34 题（共 13 分）

#include <bits/stdc++.h>
using namespace std;
int f(int &n,int m)
{
    if(n==m) return n;
    int A=0;
    if(n>m) A=f(n-=m,m);
    else A=f(n,m-=n);
    return A+n;
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<f(n,m);
    return 0;
}

若无其他限制，本题默认输入的 $n,m$ 是 $[1,10^9]$ 内的整数。

将第 8 行的 m-=n 改为 m-n，程序可以编译且运行结果不变。（）

正确
错误

程序的执行过程中可能会出现有符号整数溢出。（）

正确
错误

将第 15 行改为 cin>>m>>n，程序运行结果不变。（）

正确
错误

如果输入中 $n=0$ 或 $m=0$ ，程序可能会进入无限循环。（）

正确
错误

程序的最坏时间复杂度为（）。

$O(\log nm)$
$O(\log n\cdot\log m)$
$O(n+m)$
$O(nm)$

（本题 4 分）如果输入 10 12，输出为（）。

三、完善程序（2 题，共计 30 分）

（1）冒泡排序（第 35～39 题，每题 3 分，共 15 分）

将要排序的数全部放进双向链表，然后从小到大排序并输出。试补全程序。

#include <bits/stdc++.h>
using namespace std;
struct node{
    int val=0;
    node *prv=nullptr,*nxt=nullptr;
};
int main(){
    int n;
    scanf("%d",&n);
    node *head=new node,*tail=/* Blank 1 */;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        node *tmp=head;
        head=new node;
        head->val=x;
        head->nxt=tmp;
        tmp->prv=head;
    }
    tail->nxt=head;
    head->prv=tail;
    for(node *i=head;i!=tail;i=i->nxt)
        for(node *j=/* Blank 2 */){
            node *p=j->prv;
            if(p->val>j->val){
#define Symm j->prv->nxt=j; p->nxt->prv=p;
#define Swap j->prv=p->prv; p->nxt=j->nxt;
#define Reve j->nxt=p; p->prv=j;
                /* Blank 3 */
                j=p;
                if(p==i){
                    /* Blank 4 */
                }
            }
        }
    node *it=/* Blank 5 */;
    for(int i=1;i<=n;i++){
        it=it->nxt;
        printf("%d ",it->val);
    }
    return 0;
}

/* Blank 1 */ 空应该填（）。

nullptr
new node
head
&head

/* Blank 2 */ 空应该填（）。

i->nxt;j!=tail;j=j->nxt
tail;j!=i->prv;j=j->prv
tail;j!=i;j=j->prv
tail->prv;j!=i;j=j->prv

/* Blank 3 */ 空应该填（）。

Swap Symm Reve
Reve Symm Swap
Symm Reve Swap
Symm Swap Reve

/* Blank 4 */ 空应该填（）。

i=i->prv;break;
j=j->prv;
j=j->nxt;
i=p;break;

/* Blank 5 */ 空应该填（）。

head
head->prv
tail
tail->prv

（2）数独变换（第 40～46 题，第 42 题 3 分，其余每题 2 分，共 15 分）

初始给定一个有 $n\times n$ 个宫、每个宫中有 $n\times n$ 个元素，且早已全部正确填好的 $n$ 阶数独。之后，会将一些宫向左或者向右转 $90$ 度或 $180$ 度。例如，若一个宫初始为：

087
654
321

那么它向左旋转 $90$ 度后会变成：

741
852
063

现在你需要对数独进行恢复。在恢复数独时，也只能将一些宫向左转 $90$ 度，一次旋转算作一步。求把数独重新恢复成合法的数独，最少需要多少步。如果一开始给出的数独局面不可以通过任意次、任意位置的左旋得到，则输出 $-1$ 。

数据保证当存在解时，最优解方案唯一。 $2\le n\le4$ 。

提示：

$n$ 阶数独合法的条件：每一行、每一列、每一个粗线宫（ $n\times n$ ）内的数字均含 $0\sim n^2-1$ ，且不重复。
对于 4 阶数独， $>9$ 的数字采用十六进制表示法：A=10，B=11，C=12，D=13，E=14，F=15。
输出格式：第 1 行输出一个整数，表示最小步数 $s$ 。第 $2\sim s+1$ 行，每行输出两个整数 $x_i,y_i$ ，表示对行号、列号为 $x_i,y_i$ 的宫向左旋转了 $90$ 度。若不存在合法方案，请输出 $-1$ 。
解决思路为深度优先搜索，并进行两个优化：程序会定期检查当前行和全部列是否已经正确填写，否则不会继续；保证 dfs 运行到最后时的答案单调不升。

试补全程序。

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

const int N=110;
const int Inf=998244353;

int n;
int ans;

char a[N][N];

int buc[N];
int tmp[N][N];
int res[N][N];
int base[N][N];

bool chkRow(int x){
    x=/* Blank 2 */;
    for(int i=x;i<x+n;++i){
        memset(buc,0,sizeof(buc));
        for(int j=1;j<=n*n;++j){
            if(/* Blank 3(1) */) return 0;
            /* Blank 3(2) */
        }
    }
    return 1;
}
bool chkColumn(){
    for(int i=1;i<=n*n;++i){
        memset(buc,0,sizeof(buc));
        for(int j=1;j<=n*n;++j){
            if(buc[base[j][i]]) return 0;
            buc[base[j][i]]=1;
        }
    }
    return 1;
}
void rot(int x,int y){
    ++tmp[x][y];
    x=n*(x-1)+1;
    y=n*(y-1)+1;
    if(/* Blank 1 */){
        swap(base[x+1][y],base[x][y+1]);
        swap(base[x+2][y],base[x][y+2]);
        swap(base[x+3][y],base[x][y+3]);
        swap(base[x+2][y+1],base[x+1][y+2]);
        swap(base[x+3][y+1],base[x+1][y+3]);
        swap(base[x+3][y+2],base[x+2][y+3]);

        swap(base[x+1][y],base[x+2][y]);
        swap(base[x+1][y+1],base[x+2][y+1]);
        swap(base[x+1][y+2],base[x+2][y+2]);
        swap(base[x+1][y+3],base[x+2][y+3]);
        swap(base[x][y],base[x+3][y]);
        swap(base[x][y+1],base[x+3][y+1]);
        swap(base[x][y+2],base[x+3][y+2]);
        swap(base[x][y+3],base[x+3][y+3]);
    }
    else{
        swap(base[x+1][y],base[x][y+1]);
        swap(base[x+2][y],base[x][y+2]);
        swap(base[x+2][y+1],base[x+1][y+2]);

        swap(base[x][y],base[x+2][y]);
        swap(base[x][y+1],base[x+2][y+1]);
        swap(base[x][y+2],base[x+2][y+2]);
    }
}
int cnt;
void dfs(int c,int r,int s){
    ++cnt;
    if(s>ans) return;
    if(c==n+1){
        if(/* Blank 4 */) return;
        if(/* Blank 5 */){
            if(ans>s){
                ans=s;
                for(int i=1;i<=n;++i)
                    for(int j=1;j<=n;++j)
                        res[i][j]=tmp[i][j];
            }
            return;
        }
        if(r==n) return;
        return dfs(1,r+1,s);
    }
    dfs(c+1,r,s);
    rot(r,c);
    dfs(c+1,r,s+1);
    rot(r,c);
    dfs(c+1,r,s+2);
    rot(r,c);
    dfs(c+1,r,s+3);
    rot(r,c);
    /* Blank 6 */
}
int main(){
    cin>>n; ans=Inf;
    memset(res,0,sizeof(res));
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n*n;++i)
        for(int j=1;j<=n*n;++j){
            cin>>a[i][j];
            if(isdigit(a[i][j]))
                base[i][j]=a[i][j]-'0';
            else base[i][j]=a[i][j]-'A'+10;
        }
    dfs(1,1,0);
    cout<<(ans==Inf ? -1 : ans)<<endl;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int o=1;o<=/* Blank 7 */;++o)
                printf("%d %d\n",i,j);
    return 0;
}

/* Blank 1 */ 空应该填（）。

n == 3
n == 4
n >= 3
n <= 3

/* Blank 2 */ 空应该填（）。

n * x - n + 1
n * x
n * x - n
n * x - n - 1

（本题 3 分）/* Blank 3(1) */ 和 /* Blank 3(2) */ 分别应该填（）。

(1) buc[base[j][i]]；(2) buc[base[j][i]]++;
(1) buc[base[i][j]]；(2) buc[base[i][j]]++;
(1) buc[base[i][j]] > 1；(2) buc[base[i][j]]++;
(1) buc[base[j][i]] > 1；(2) buc[base[j][i]]++;

/* Blank 4 */ 空应该填（）。

chkColumn()
!chkColumn()
chkRow(n)
!chkRow(n)

/* Blank 5 */ 空应该填（）。

chkRow(n) and r == n
chkColumn() and r == n
r == n
chkRow(1) and r == n

/* Blank 6 */ 空应该填（）。

tmp[r][c]--;
res[r][c]=0;
tmp[r][c]-=4;
c--;

/* Blank 7 */ 空应该填（）。

res[i][j]
base[i][j]
tmp[i][j]
res[i][j] * tmp[i][j]

#YDSPJ2023. 2023 云斗学院软件能力认证第一轮（YDSP-Junior）入门级 C++ 语言试题