CSP-J 2023 初賽模擬試題二

CSP-J2023初賽模擬試題二基本信息：[矩陣文本題]*姓名：________________________班級：________________________當(dāng)前是第幾次作答：________________________1、將二進(jìn)制數(shù)10101011與00110010進(jìn)行按位與操作，得到的結(jié)果是（）。[單選題]*A.10101011B.00110010C.00100010(正確答案)D.101000112、瀏覽網(wǎng)頁時，有些網(wǎng)址以http://開頭，另一些則以https://開頭。這里的h指的是（）的縮寫。[單選題]*A.HighspeedB.HighC.HyperspeedD.Hyper(正確答案)3、下列網(wǎng)絡(luò)設(shè)備中，主要用作連接不同局域網(wǎng)的是（）。[單選題]*A.路由器(正確答案)B.集線器C.網(wǎng)卡D.中繼器4、將四個數(shù)字-1，-2，2，3經(jīng)過四則運(yùn)算（即只使用加、減、乘、除和括號）后，可能得到的最大結(jié)果是（）。[單選題]*A.12B.16(正確答案)C.8D.205、下述排序方法中在任何情況下時間復(fù)雜度都是O(nlogn)的是（）。[單選題]*A.插入排序B.選擇排序C.快速排序D.歸并排序(正確答案)6、計算機(jī)病毒是可以造成電腦故障的一種（）。[單選題]*A.計算機(jī)設(shè)備B.計算機(jī)芯片C.計算機(jī)部件D.計算機(jī)程序(正確答案)7、對于拓?fù)渑判?，若要求所有?jié)點都入隊一次，以下描述正確的是（）。[單選題]*A.拓?fù)渑判蛑腥攵葹?的結(jié)點總會排在入度大于0的結(jié)點的前面。B.考慮一個有向無環(huán)圖，如果在圖中存在從節(jié)點u到節(jié)點v的有向邊，那么在拓?fù)渑判蚝蟮耐負(fù)湫蛑衭一定在v的前面。(正確答案)C.拓?fù)渑判蚩梢杂糜谟协h(huán)圖。D.拓?fù)渑判虻慕Y(jié)果是唯一的，不受圖的表示方式的影響。8、下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是（）。[單選題]*A.樹(正確答案)B.數(shù)組C.鏈表D.高維矩陣9、邏輯變量A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式的值為真的有（）。[單選題]*A.(B∨C∨D)∧DB.((-A∧B)∨C)∧-B(正確答案)C.(A∧B)∨(C∧D∨-A)D.A∧(D∨-C)∧B10、一位魔術(shù)師要將名為雪球、芝麻和星寶的三只兔子藏進(jìn)A,B,C,D四個帽子里。每個帽子最多放置兩只兔子，那么一共有多少種不同的藏法（）。[單選題]*A.64B.81C.48D.60(正確答案)11、在一個單鏈表中，O(n)時間復(fù)雜度的操作是（）。[單選題]*A.在鏈表頭部插入一個新節(jié)點B.在鏈表尾部插入一個新節(jié)點C.刪除鏈表中的一個節(jié)點，已知該節(jié)點的指針。D.查找鏈表中的最大值節(jié)點(正確答案)12、若3個頂點的無權(quán)圖G的鄰接矩陣用數(shù)組存儲為{{0,1,1},{1,0,1},{0,1,0}}，假定在具體存儲中頂點依次為：1,2,3。關(guān)于該圖，下面說法錯誤的是（）。[單選題]*A.該圖是有向圖B.該圖是強(qiáng)連通的C.該圖所有頂點的入度之和減所有頂點的出度之和等于1(正確答案)D.從1號點開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先遍歷經(jīng)過的頂點序列是相同的（優(yōu)先級相同時字典序小的頂點優(yōu)先遍歷）13、一位老師想用40米的柵欄靠著一面墻圍出一個四邊形。已知墻的長度足夠長，問這個四邊形的面積最大可能是（）平方米。[單選題]*A.180B.225C.1600/9D.200(正確答案)14、IPv4中，以下IP地址不合法的是（）[單選題]*A.55B.0C.0(正確答案)D.15、下面哪位科學(xué)家被世人尊稱為人工智能之父。（）[單選題]*A.馮若依曼B.理查德·斯托曼C.香農(nóng)D.圖靈(正確答案)二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填√，

錯誤填×；除特殊說明外，判斷題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}

假設(shè)輸入的n、val均是不超過50000的自然數(shù)，完成下面的判斷題：

判斷題

16.第3行priority_queue替換成queue，不會影響程序運(yùn)行效率。（）[判斷題]*對錯(正確答案)17.本程序有缺陷，當(dāng)輸入的n和val都過大時，結(jié)果有可能溢出。（）[判斷題]*對(正確答案)錯18.程序最后輸出的結(jié)果一定比輸入的任何數(shù)都要大。（[判斷題]*對(正確答案)錯19.當(dāng)輸入為“3345”時，輸出為“20”。（）[判斷題]*對錯(正確答案)20.該算法總的時間復(fù)雜度為O(nlogn)。（）[判斷題]*對(正確答案)錯21.當(dāng)輸入為“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}

假設(shè)輸入的n、m、w都是不超過10000的自然數(shù)，完成下面的判斷題和選

擇題：

判斷題

22.第5～17行計算最短路徑使用的是Floyd算法。（[判斷題]*對(正確答案)錯23.第21～27行構(gòu)建的圖是有向圖。（）[單選題]*A、正確(正確答案)B、錯誤24.該程序返回的是圖中各頂點到x點的最短距離。（）[單選題]*A、正確B、錯誤(正確答案)25.該算法的時間復(fù)雜度是（）。[單選題]*A、O(n^3)(正確答案)B、O(n^2)C、O(nm)D、O(uv)26.當(dāng)輸入為“331122231313”時，輸出分別為（）。[單選題]*A、“306”B、“330”C、“066”(正確答案)D、“336”27.當(dāng)輸入為“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}

假設(shè)輸入的n,m是不超過1000的自然數(shù)，完成下面的判斷題和選擇題：

判斷題

28.程序中使用的是kruskal算法。（[判斷題]*對錯(正確答案)29.輸入的n表示圖的頂點數(shù)，m表示邊數(shù)。()[單選題]*A.正確(正確答案)B.錯誤30：當(dāng)visited[u]==true時，表示u這個點已經(jīng)訪問過了。()[單選題]*A.正確(正確答案)B.錯誤31：ans表示保持所有點連通，連接所有同色頂點的最少邊數(shù)。()[單選題]*A.正確(正確答案)B.錯誤32：使用priority_queue的目的在于加速查找()[單選題]*A.與已選邊相連的邊中權(quán)值最小的(正確答案)B.所有邊中權(quán)值最小的C.任意兩點間的最短路徑D.同色點間的最短路徑33：由程序可知同色頂點間邊的權(quán)值為1，異色頂點間邊的權(quán)值為0，這是為了()[單選題]*A.同色點間的邊優(yōu)先選擇B.異色點間的邊優(yōu)先選擇(正確答案)C.同色和異色點間的邊交替選擇D.只選擇同色點間的邊34：

當(dāng)輸入為

44

1122

12

23

34

41

，輸出是（）[單選題]*A.4B.3C.1D.2(正確答案)三、完善程序（單選題，每小題3分，共計30分）

（1）（進(jìn)制轉(zhuǎn)換）現(xiàn)給出兩個轉(zhuǎn)換后的3位數(shù)，請你算出原數(shù)轉(zhuǎn)換時分別使

用的進(jìn)制。

試補(bǔ)全枚舉程序。

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.①處應(yīng)填（[單選題]*A.to>=anB.to!=aC.to==an(正確答案)D.to＜=an36.②處應(yīng)填()[單選題]*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:③處應(yīng)填()[單選題]*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:④處應(yīng)填()[單選題]*A.a1B.a1-b1(正確答案)C.b1D.a1+b139.⑤處應(yīng)填()[單選題]*A.b2,b3,s(正確答案)B.a2,a3,sC.a1,b1,sD.a2,b2,s（2）（教室安排）有兩門課可選，每人只能選一門。N名同學(xué)排成一排，老師只

會把連續(xù)一段的同學(xué)分進(jìn)同一間教室，教室里選兩門課的人數(shù)相差不超過M。求

至少需要多少間教室。

試補(bǔ)全程序。

01#include<cstdio>

02#include<cstring>

03#include<algorithm>

04usingnamespacestd;

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

06intmai