普及組CSP-J2024初賽模擬卷4

普及組CSP-J2024初賽模擬卷4[復(fù)制]您的姓名：[填空題]*_________________________________一、單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分；每題有且僅有一個正確選項(xiàng)）1.正整數(shù)2024與1840的最大公約數(shù)是（）。[單選題]A.46B.92C.44D.184(正確答案)2.十進(jìn)制數(shù)28與二進(jìn)制數(shù)10000001110000求和的結(jié)果是（）。[單選題]A.十進(jìn)制數(shù)8332(正確答案)B.十六進(jìn)制數(shù)208AC.二進(jìn)制數(shù)100000000110D.八進(jìn)制數(shù)202123.C++程序中,(25|6)^5的值是（）。[單選題]A.25B.26(正確答案)C.27D.284.在數(shù)組A[x]中，若存在(i<j)且(A[i]>A[j]),則稱(A[i],A[j])為數(shù)組A[x]的一個逆序?qū)?。對于序?7,4,1,9,3,6,8,5)，在不改變順序的情況下，去掉（）會使逆序?qū)Φ膫€數(shù)減少4。[單選題]B.3C.6D.5(正確答案)A.15.如果字符串s在字符串A中出現(xiàn)了，則字符串s被稱作字符串A的子串。設(shè)字符串A="players"，A的非空子串的數(shù)目是（）。[單選題]D.30A.27B.29C.28(正確答案)6.以下哪種算法的主要框架不是非比較排序？（）[單選題]A.計(jì)數(shù)排序B.堆排序(正確答案)C.基數(shù)排序D.桶排序7.采用了倍增法的程序運(yùn)行的時間復(fù)雜度是（）。[單選題]A.O(logn)(正確答案)B.O(n)C.O(n^2)D.O(nlogn)8.將數(shù)組{9,33,5,18,71,3,52,85}中的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換（）次。[單選題]A.4B.5(正確答案)C.6D.79.關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)，下面的說法中哪個是正確的？（）[單選題]A.計(jì)算機(jī)網(wǎng)絡(luò)是一個管理信息系統(tǒng)B.計(jì)算機(jī)網(wǎng)絡(luò)是一個管理數(shù)據(jù)系統(tǒng)C.計(jì)算機(jī)網(wǎng)絡(luò)是一個在協(xié)議控制下的多機(jī)互聯(lián)系統(tǒng)(正確答案)D.計(jì)算機(jī)網(wǎng)絡(luò)是一個獨(dú)立的操作系統(tǒng)10.下列哪款軟件不是操作系統(tǒng)軟件的名字？（）[單選題]A.安卓B.Windows11C.華為鴻蒙D.ChatGPT(正確答案)11.下述選項(xiàng)中哪個不是算法描述的通用方法？（）[單選題]A.自然語言B.流程圖C.人工智能(正確答案)D.偽代碼12.若A=True，B=False，C=True，D=False，以下邏輯運(yùn)算表達(dá)式的運(yùn)算結(jié)果為真的是（）。[單選題]A.(AΛB)V(CΛDV﹁A)B.((ΑΛB)ΛC)Λ﹁BC.(BVCVD)VDΛA(正確答案)D.(AΛ(DV﹁C)ΛB13.一棵二叉樹的高度為h(假設(shè)根高度=1)，所有結(jié)點(diǎn)的度數(shù)都為0或2，則此樹最少有（）個結(jié)點(diǎn)。[單選題]A.2^h-1B.2h-1(正確答案)C.2h+1D.h+114.從12個人中選出5個人，其中甲、乙、丙必選的方法共有（）種。[單選題]A.60B.36(正確答案)C.72D.12015.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。[單選題]A.1/2B.2C.1(正確答案)D.4二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填A(yù)，錯誤填B：除特殊說明外，判斷題每題1.5分，選擇題每題3分，共計(jì)40分）（1）01#include<bits/stdc++.h>

02usingnamespacestd;

03charchange(charstr)

04{

05

if(str>='a'&&str<='z')

06

str-=32;

07

returnstr;

08}

09intmain()

10{

11

12

strings1,s2;

13

cin>>s1>>s2;

14

intcnt=0;

15

for(inti=0;i<s1.size();i++)

16

{

17

for(intj=0;j<s2.size();j++)

18

if(change(s1[i])==change(s2[j]))

19

cnt++;

20

}

21

cout<<cnt;

22

return0;

23}判斷題16.將第1行頭文件改為＃include<iostream>，程序的運(yùn)行結(jié)果不會改變。（）[單選題]對(正確答案)錯答案解析：注意：C++11版本之后，iostream已經(jīng)包含了string頭文件17.將第5行中的＇a＇替換為97，程序的運(yùn)行結(jié)果不會改變。（）[單選題]對(正確答案)錯18.將第6行中的32替換為＇＇，程序的運(yùn)行結(jié)果不會改變。（）[單選題]對(正確答案)錯19.將第14行代碼中=0去掉，程序的運(yùn)行結(jié)果不會改變。（）[單選題]對錯(正確答案)選擇題20.若輸入數(shù)據(jù)為ABCDE

AbCdE，則輸出為（）。[單選題]A.3B.5(正確答案)C.2D.021.若輸入數(shù)據(jù)為WorldYiwuAsiaShanghai

ChinaHangzhouZhejiangJinhua，則輸出為（）。[單選題]A.36B.40C.42D.44(正確答案)（2）01#include<iostream>

02usingnamespacestd;

03intsolve(intn,intm)

04{

05

inti,sum;

06

if(m==1)

07

return1;

08

sum=0;

09

for(i=1;i<n;i++)

10

sum+=solve(i,m-1);

11

returnsum;

12}

13intmain()

14{

15

intn,m;

16

cin>>n>>m;

17

cout<<solve(n,m)<<endl;

18

return0;

19}判斷題22.如果n輸入一個負(fù)整數(shù)，程序的運(yùn)行會出錯。（）[單選題]對錯(正確答案)23.如果n輸入一個正整數(shù)，m輸入一個負(fù)整數(shù)，那么程序會進(jìn)入死循環(huán)，不會輸出任何結(jié)果。（）[單選題]對錯(正確答案)24.若輸入44，則程序的運(yùn)行結(jié)果為1。（）[單選題]對(正確答案)錯25.若輸入4-1，則程序的運(yùn)行結(jié)果為0。（）[單選題]對(正確答案)錯選擇題26.若輸入為74，則輸出為（）。[單選題]A.20(正確答案)B.10C.15D.527.若輸出為10，則輸入可能為（）。[單選題]A.53B.54C.64(正確答案)D.65（3）01#include<bits/stdc++.h>

02usingnamespacestd;

03constintMAXN=2e5+5;

04intnums[MAXN];

05intleft_bound(intn,inttarget){

06

intleft=0,right=n-1;

07

while(left<=right){

08

intmid=(left+right)/2;

09

if(nums[mid]<target)

10

left=mid+1;

11

else

12

right=mid-1;

13

}

14

if(left<n&&nums[left]==target)

15

returnleft;

16

return-1;

17}

18intright_bound(intn,inttarget){

19

intleft=0,right=n-1;

20

while(left<=right){

21

intmid=(left+right)/2;

22

if(nums[mid]<=target)

23

left=mid+1;

24

else

25

right=mid-1;

26

}

27

if(right>=0&&nums[right]==target)

28

returnright;

29

return-1;

30}

31intmain()

32{

33

intn,c;

34

cin>>n>>c;

35

for(inti=0;i<n;++i)

36

cin>>nums[i];

37

sort(nums,nums+n);

38

longlongans=0;

39

for(inti=0;i<n;++i){

40

intleft=left_bound(n,nums[i]+c);

41

intright=right_bound(n,nums[i]+c);

42

if(left!=-1)

43

ans+=right-left+1;

44

}

45

cout<<ans<<endl;

46

return0;

47}判斷題28.本段程序的算法用到了二分算法的思想。（）[單選題]對(正確答案)錯29.將第3行中的const去掉，程序的運(yùn)行結(jié)果不變。（）[單選題]對(正確答案)錯30.將第14行中的left<n去掉，程序的運(yùn)行結(jié)果不變。（）[單選題]對錯(正確答案)31.將第38行中的longlong替換為int，程序的運(yùn)行結(jié)果不變。（）[單選題]對錯(正確答案)選擇題32.第8行的寫法在某些時候會導(dǎo)致程序運(yùn)行有問題，最好換成寫法（）。[單選題]A.mid=(left+right)＜＜1B.mid=left+(right－left)/2(正確答案)C.mid=left+(right－left)＞＞1D.mid=(left+right)％2答案解析：B：當(dāng)left和right都比較大時，這種寫法可以防止超過int；C：用>>1這種寫法的目的是left和right出現(xiàn)負(fù)數(shù)時，仍然可以實(shí)現(xiàn)下取整；but這兒寫法有問題，因?yàn)?運(yùn)算優(yōu)先級更高33.本程序的時間復(fù)雜度為（）。[單選題]A.O(logn)B.O(n)C.O(n^2)D.O(nlogn)(正確答案)34.（4分）當(dāng)輸入

41

1123

時，程序的輸出結(jié)果為（）。[單選題]A.1B.2C.3(正確答案)D.4三、完善程序（單選題，每小題3分，共計(jì)30分）（1）給定一棵樹，輸出樹的根root、孩子結(jié)點(diǎn)最多的結(jié)點(diǎn)max以及它的孩子結(jié)點(diǎn)。輸入格式：

第1行輸入n（結(jié)點(diǎn)數(shù)≤100）和m（邊數(shù)≤200）。以下m行輸入每行兩個結(jié)點(diǎn)x和y，表示y是x的孩子結(jié)點(diǎn)（x，y≤1000）。輸出格式：

第1行是樹根root。第2行是孩子結(jié)點(diǎn)最多的結(jié)點(diǎn)max。第3行是max的孩子結(jié)點(diǎn)。輸入樣例：

87

41

42

13

15

26

27

28輸出樣例:

4

2

678

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

02usingnamespacestd;

03intn,m,tree[105]={0};

04intmain()

05{

06

inti,x,y,root,maxroot,sum=0,j,Max=0;

07

cin>>n>>m;

08

for(i=1;i<=m;i++)

09

{

10

cin>>x>>y;

11

①;

12

}

13

for(i=1;i<=n;i++)//找出樹的根

14

if(②)

15

{

16

root=i;

17

③;

18

}

19

for(i=1;i<=n;i++)//找孩子結(jié)點(diǎn)最多的結(jié)點(diǎn)

20

{

21

sum=0;

22

for(j=1;j<=n;j++)

23

if(tree[j]==i)

24

sum++;

25

if(④)

26

{

27

Max=sum;

28

maxroot=i;

29

}

30

}

31

cout<<root<<endl<<maxroot<<endl;

32

for(i=1;i<=n;i++)

33

if(⑤)

34

cout<<i<<"";

35

return0;

36}35.①處應(yīng)填（）。[單選題]A.tree[y]=x(正確答案)B.tree[x]=yC.tree[y]=iD.tree[x]=i36.②處應(yīng)填（）。[單選題]A.tree[i]==1B.tree[i]==0(正確答案)C.tree[i]==2D.tree[i]!=037.③處應(yīng)填（）。[單選題]A.break(正確答案)B.continueC.return0D.exit38.④處應(yīng)填（）。[單選題]A.sum==MaxB.sum＜=MaxC.sum>Max(正確答案)D.sum＜Max39.⑤處應(yīng)填（）。[單選題]A.tree[i]!=maxrootB.tree[i]＜=maxrootC.tree[i]>=maxrootD.tree[i]==maxroot(正確答案)（2）快速排序是一種高效的排序算法，我們常用的STL函數(shù)sort就是采用快速排序思想實(shí)現(xiàn)的。如下代碼是一個經(jīng)典的快速排序過程，輸入一個整數(shù)n，然后輸入n個整數(shù)，程序會按照從小到大的順序?qū)⑺姓麛?shù)進(jìn)行排序并輸出。請將程序補(bǔ)充完整。01#include<bits/stdc++.h>

02usingnamespacestd;

03inta[1005];

04voidquickSort(inta[],intbegin,intend)

05{

06

inti,j,temp;

07

if(begin>=end)

08

return;

09

①;

10

i=begin;

11

j=end;

12

while(i<j)

13

{

14

while(a[j]>tmp)

15

j--;

16

while(②)

17

i++;

18

if(i!=j)

19

swap(a[i],a[j]);

20

}

21