CSP-J 2023 初赛模拟试题二

CSP-J2023初赛模拟试题二基本信息：[矩阵文本题]*姓名：________________________班级：________________________当前是第几次作答：________________________1、将二进制数10101011与00110010进行按位与操作，得到的结果是（）。[单选题]*A.10101011B.00110010C.00100010(正确答案)D.101000112、浏览网页时，有些网址以http://开头，另一些则以https://开头。这里的h指的是（）的缩写。[单选题]*A.HighspeedB.HighC.HyperspeedD.Hyper(正确答案)3、下列网络设备中，主要用作连接不同局域网的是（）。[单选题]*A.路由器(正确答案)B.集线器C.网卡D.中继器4、将四个数字-1，-2，2，3经过四则运算（即只使用加、减、乘、除和括号）后，可能得到的最大结果是（）。[单选题]*A.12B.16(正确答案)C.8D.205、下述排序方法中在任何情况下时间复杂度都是O(nlogn)的是（）。[单选题]*A.插入排序B.选择排序C.快速排序D.归并排序(正确答案)6、计算机病毒是可以造成电脑故障的一种（）。[单选题]*A.计算机设备B.计算机芯片C.计算机部件D.计算机程序(正确答案)7、对于拓扑排序，若要求所有节点都入队一次，以下描述正确的是（）。[单选题]*A.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面。B.考虑一个有向无环图，如果在图中存在从节点u到节点v的有向边，那么在拓扑排序后的拓扑序中u一定在v的前面。(正确答案)C.拓扑排序可以用于有环图。D.拓扑排序的结果是唯一的，不受图的表示方式的影响。8、下列结构中为非线性结构的是（）。[单选题]*A.树(正确答案)B.数组C.链表D.高维矩阵9、逻辑变量A=true，B=false，C=true，D=false，以下逻辑运算表达式的值为真的有（）。[单选题]*A.(B∨C∨D)∧DB.((-A∧B)∨C)∧-B(正确答案)C.(A∧B)∨(C∧D∨-A)D.A∧(D∨-C)∧B10、一位魔术师要将名为雪球、芝麻和星宝的三只兔子藏进A,B,C,D四个帽子里。每个帽子最多放置两只兔子，那么一共有多少种不同的藏法（）。[单选题]*A.64B.81C.48D.60(正确答案)11、在一个单链表中，O(n)时间复杂度的操作是（）。[单选题]*A.在链表头部插入一个新节点B.在链表尾部插入一个新节点C.删除链表中的一个节点，已知该节点的指针。D.查找链表中的最大值节点(正确答案)12、若3个顶点的无权图G的邻接矩阵用数组存储为{{0,1,1},{1,0,1},{0,1,0}}，假定在具体存储中顶点依次为：1,2,3。关于该图，下面说法错误的是（）。[单选题]*A.该图是有向图B.该图是强连通的C.该图所有顶点的入度之和减所有顶点的出度之和等于1(正确答案)D.从1号点开始的深度优先遍历所经过的顶点序列与广度优先遍历经过的顶点序列是相同的（优先级相同时字典序小的顶点优先遍历）13、一位老师想用40米的栅栏靠着一面墙围出一个四边形。已知墙的长度足够长，问这个四边形的面积最大可能是（）平方米。[单选题]*A.180B.225C.1600/9D.200(正确答案)14、IPv4中，以下IP地址不合法的是（）[单选题]*A.55B.0C.0(正确答案)D.15、下面哪位科学家被世人尊称为人工智能之父。（）[单选题]*A.冯若依曼B.理查德·斯托曼C.香农D.图灵(正确答案)二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，

错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）(1)

01#include<bits/stdc++.h>

02usingnamespacestd;

03priority_queue<int,vector<int>,greater<int>>que;

04intmain()

05{

06intn,ans,val=0;

07cin>>n;

08for(inti=1;i<=n;i++){

09cin>>val;

10que.push(val);

11}

12while(que.size()>1){

13intx=que.top();

14que.pop();

15inty=que.top();

16que.pop();

17ans+=x+y;

18que.push(x+y);

19}

20cout<<ans<<endl;

21return0;

22}

假设输入的n、val均是不超过50000的自然数，完成下面的判断题：

判断题

16.第3行priority_queue替换成queue，不会影响程序运行效率。（）[判断题]*对错(正确答案)17.本程序有缺陷，当输入的n和val都过大时，结果有可能溢出。（）[判断题]*对(正确答案)错18.程序最后输出的结果一定比输入的任何数都要大。（[判断题]*对(正确答案)错19.当输入为“3345”时，输出为“20”。（）[判断题]*对错(正确答案)20.该算法总的时间复杂度为O(nlogn)。（）[判断题]*对(正确答案)错21.当输入为“1012362641367031169043”时，输出为（）[单选题]*A.“160”B.“90”C.“1262”(正确答案)D.“22”(2)

01#include<iostream>

02#include<vector>

03usingnamespacestd;

04constintINF=(int)1e9;

05vector<vector<int>>zdl(constvector<vector<int>>&graph,intn){

06vector<vector<int>>dist(graph);

07for(intk=1;k<=n;k++){

08for(inti=1;i<=n;i++){

09for(intj=1;j<=n;j++){

10if(dist[i][k]!=INF&&dist[k][j]!=INF&&dist[i][k]+dist[k][j]<dist[i][j]){

11dist[i][j]=dist[i][k]+dist[k][j];

12}

13}

14}

15}

16returndist;

17}

18intmain(){

19intn,m,x;

20cin>>n>>m>>x;

21vector<vector<int>>graph(n+1,vector<int>(n+1,INF));

22for(inti=1;i<=n;i++)graph[i][i]=0;

23for(inti=0;i<m;i++){

24intu,v,w;

25cin>>u>>v>>w;

26graph[u][v]=w;

27}

28vector<vector<int>>dist=zdl(graph,n);

29for(inti=1;i<=n;i++){

30intround_trip_time=dist[i][x]+dist[x][i];

31if(round_trip_time>=INF)cout<<"impossible"<<endl;

32elsecout<<round_trip_time<<endl;

33}

34return0;

35}

假设输入的n、m、w都是不超过10000的自然数，完成下面的判断题和选

择题：

判断题

22.第5～17行计算最短路径使用的是Floyd算法。（[判断题]*对(正确答案)错23.第21～27行构建的图是有向图。（）[单选题]*A、正确(正确答案)B、错误24.该程序返回的是图中各顶点到x点的最短距离。（）[单选题]*A、正确B、错误(正确答案)25.该算法的时间复杂度是（）。[单选题]*A、O(n^3)(正确答案)B、O(n^2)C、O(nm)D、O(uv)26.当输入为“331122231313”时，输出分别为（）。[单选题]*A、“306”B、“330”C、“066”(正确答案)D、“336”27.当输入为“5551572543444565410”时，输出分别为（）。[单选题]*A、“0”、“16”、“10”、“6”、“7”B、“10”、“22”、“impossible”、“6”、“7”C、“impossible”、“impossible”、“impossible”、“impossible”和“0”D、“impossible”、“impossible”、“impossible”、16和“0”(正确答案)(3)

01#include<iostream>

02#include<vector>

03#include<queue>

04usingnamespacestd;

05typedefpair<int,int>pii;

06intmst(constvector<vector<pii>>&graph){

07intn=graph.size();

08vector<bool>visited(n,false);

09vector<int>distances(n,(int)1e9);

10priority_queue<pii,vector<pii>,greater<pii>>pq;

11distances[0]=0;

12pq.push({0,0});

13while(!pq.empty()){

14intu=pq.top().second;

15pq.pop();

16if(visited[u])continue;

17visited[u]=true;

18for(constauto&neighbor:graph[u]){

19intv=neighbor.first,weight=neighbor.second;

20if(!visited[v]&&distances[v]>weight){

21distances[v]=weight;

22pq.push({distances[v],v});

23}

24}

25}

26inttotalWeight=0;

27for(inti=0;i<n;++i)totalWeight+=distances[i];

28returntotalWeight;

29}

30intmain(){

31intn,m;

32cin>>n>>m;

33vector<int>colors(n);

34for(inti=0;i<n;++i)cin>>colors[i];

35vector<vector<pii>>graph(n);

36for(inti=0;i<m;++i){

37intu,v;

38cin>>u>>v;

39u--;v--;

40intweight=(colors[u]==colors[v])?1:0;

41graph[u].push_back({v,weight});

42graph[v].push_back({u,weight});

43}

44intans=mst(graph);

45cout<<ans<<endl;

46return0;

47}

假设输入的n,m是不超过1000的自然数，完成下面的判断题和选择题：

判断题

28.程序中使用的是kruskal算法。（[判断题]*对错(正确答案)29.输入的n表示图的顶点数，m表示边数。()[单选题]*A.正确(正确答案)B.错误30：当visited[u]==true时，表示u这个点已经访问过了。()[单选题]*A.正确(正确答案)B.错误31：ans表示保持所有点连通，连接所有同色顶点的最少边数。()[单选题]*A.正确(正确答案)B.错误32：使用priority_queue的目的在于加速查找()[单选题]*A.与已选边相连的边中权值最小的(正确答案)B.所有边中权值最小的C.任意两点间的最短路径D.同色点间的最短路径33：由程序可知同色顶点间边的权值为1，异色顶点间边的权值为0，这是为了()[单选题]*A.同色点间的边优先选择B.异色点间的边优先选择(正确答案)C.同色和异色点间的边交替选择D.只选择同色点间的边34：

当输入为

44

1122

12

23

34

41

，输出是（）[单选题]*A.4B.3C.1D.2(正确答案)三、完善程序（单选题，每小题3分，共计30分）

（1）（进制转换）现给出两个转换后的3位数，请你算出原数转换时分别使

用的进制。

试补全枚举程序。

01#include<bits/stdc++.h>

02usingnamespacestd;

03inta1,a2,a3,s,b1,b2,b3,n,x,y,l,r,to,mid,ans;

04inter(intone,inttwo,intan)

05{

06l=10;r=15000;

07while(l+1<r)

08{

09mid=(l+r)/2;

10to=mid*one+mid*mid*two;

11if(to<an)l=mid;

12elseif(①)returnmid;

13elser=mid;

14}

15if(l*one+l*l*two==an)returnl;

16if(②)returnr;

17if(③)returnl+1;

18return0;

19}

20intmain()

21{

22scanf("%d%d",&x,&y);

23a1=x%10;a2=x/10%10;a3=x/100;

24b1=y%10;b2=y/10%10;b3=y/100;

25for(inti=10;i<=15000;i++)

26{

27s=a3*i*i+a2*i+④;

28ans=er(⑤);

29if(ans){printf("%d%d\n",i,ans),return;}

30}

31return0;

32}

35.①处应填（[单选题]*A.to>=anB.to!=aC.to==an(正确答案)D.to＜=an36.②处应填()[单选题]*A.(r1)*one+(r1)*(r1)*two==anB.r*r*one+r*two==anC.r*one+r*r*two>=anD.r*one+r*r*two==an(正确答案)37:③处应填()[单选题]*A.l*one+l*l*two==anB.(l+1)*one+(l+1)*(l+1)*two==an(正确答案)C.(l+1)*(l+1)*one+(l+1)*two==anD.l*one+(l+1)*(l+1)*two==an38:④处应填()[单选题]*A.a1B.a1-b1(正确答案)C.b1D.a1+b139.⑤处应填()[单选题]*A.b2,b3,s(正确答案)B.a2,a3,sC.a1,b1,sD.a2,b2,s（2）（教室安排）有两门课可选，每人只能选一门。N名同学排成一排，老师只

会把连续一段的同学分进同一间教室，教室里选两门课的人数相差不超过M。求

至少需要多少间教室。

试补全程序。

01#include<cstdio>

02#include<cstring>

03#include<algorithm>

04usingnamespacestd;

05intn,k,m,a[10010],l[10010],r[10010],f[10010];

06intmai