2022年CCF非專業(yè)級別軟件能力認證CSP第一輪-普及組（初中組）試題（原卷版）

2022CCF非專業(yè)級別軟件能力認證第一輪（CSPJ1）入門級C++語言試題認證時間：2022年9月18日09:30～11:30考生注意事項：試題紙共有12頁，答題紙共有1頁，滿分100分。請在答題紙上作答，寫在試題紙上的一律無效。不得使用任何電子設(shè)備（如計算器、、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共15題，每題2分，共計30分；每題有且僅有一個正確選項）1.以下哪種功能沒有涉及C++語言的面向?qū)ο筇匦灾С郑ǎ〢.C++中調(diào)用printf函數(shù)B.C++中調(diào)用用戶定義的類成員函數(shù)C.C++中構(gòu)造一個class或structD.C++中構(gòu)造來源于同一基類的多個派生類2.有6個元素，按照6、5、4、3、2、1的順序進入棧S，請問下列哪個出棧序列是非法的（）A.543612 B.453126C.346521 D.2341563.運行以下代碼片段的行為是（）intx=10；inty=201；int*p=&x；int*q=&y；p=q；A.將x的值賦為201 B.將y的值賦為101C.將q指向x的地址 D.將p指向y的地址4.鏈表和數(shù)組的區(qū)別包括（）A.數(shù)組不能排序，鏈表可以B.鏈表比數(shù)組能存儲更多的信息C.數(shù)組大小固定，鏈表大小可動態(tài)調(diào)整D.以上均正確5.對假設(shè)棧S和隊列Q的初始狀態(tài)為空。存在e1～e6六個互不相同的數(shù)據(jù)，每個數(shù)據(jù)按照進棧S、出棧S、進隊列Q、出隊列Q的順序操作，不同數(shù)據(jù)間的操作可能會交錯。已知棧S中依次有數(shù)據(jù)e1、e2、e3、e4、e5和e6進棧，隊列Q依次有數(shù)據(jù)e2、e4、e3、e6、e5和e1出隊列。則棧S的容量至少是（）個數(shù)據(jù)。（）A.2 B.3 C.4 D.66.對表達式a+（bc）*d的前綴表達式為（），其中+、、*是運算符。（）A.*+abcd B.+a*bcd C.abcd*+ D.abc+d7.假設(shè)字母表{a，b，c，d，e}在字符串出現(xiàn)的頻率分別為10%，15%，30%，16%，29%。若使用哈夫曼編碼方式對字母進行不定長的二進制編碼，字母d的編碼長度為（）位。（）A.1 B.2 C.2或3 D.38.一棵有n個結(jié)點的完全二叉樹用數(shù)組進行存儲與表示，已知根結(jié)點存儲在數(shù)組的第1個位置。若存儲在數(shù)組第9個位置的結(jié)點存在兄弟結(jié)點和兩個子結(jié)點，則它的兄弟結(jié)點和右子結(jié)點的位置分別是（）A.8、18 B.10、18 C.8、19 D.10、199.考慮由N個頂點構(gòu)成的有向連通圖，采用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)表示時，該矩陣中至少存在（）個非零元素。（）A.N1 B.N C.N+1 D.N210.以下對數(shù)據(jù)結(jié)構(gòu)的表述不恰當?shù)囊豁棡椋ǎ〢.圖的深度優(yōu)先遍歷算法常使用的數(shù)據(jù)結(jié)構(gòu)為棧B.棧的訪問原則為后進先出，隊列的訪問原則是先進先出C.隊列常常被用于廣度優(yōu)先搜索算法D.棧與隊列存在本質(zhì)不同，無法用棧實現(xiàn)隊列11.以下哪組操作能完成在雙向循環(huán)鏈表結(jié)點p之后插入結(jié)點s的效果（其中，next域為結(jié)點的直接后繼，prev域為結(jié)點的直接前驅(qū)）（）A.p>next>prev=s；s>prev=p；p>next=s；s>next=p>next；B.p>next>prev=s；p>next=s；s>prev=p；s>next=p>next；C.s>prev=p；s>next=p>next；p>next=s；p>next>prev=s；D.s>next=p>next；p>next>prev=s；s>prev=p；p>next=s；12.以下排序算法的常見實現(xiàn)中，哪個選項的說法是錯誤的（）A.冒泡排序算法是穩(wěn)定的 B.簡單選擇排序是穩(wěn)定的C.簡單插入排序是穩(wěn)定的 D.歸并排序算法是穩(wěn)定的13.八進制數(shù)對應(yīng)的十進制數(shù)是（）A. B. C. D.14.一個字符串中任意個連續(xù)的字符組成的子序列稱為該字符串的子串，則字符串a(chǎn)bcab有（）個內(nèi)容互不相同的子串。（）A.12 B.13 C.14 D.1515.以下對遞歸方法的描述中，正確的是（）A.遞歸是允許使用多組參數(shù)調(diào)用函數(shù)編程技術(shù)B.遞歸是通過調(diào)用自身來求解問題的編程技術(shù)C.遞歸是面向?qū)ο蠛蛿?shù)據(jù)而不是功能和邏輯的編程語言模型D.遞歸是將用某種高級語言轉(zhuǎn)換為機器代碼的編程技術(shù)二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填√，錯誤填×；除特殊說明外，判斷題分，選擇題3分，共計40分）1601#include<iostream>0203usingnamespacestd;0405intmain()06{07unsignedshortx,y;08cin>>x>>y;09x=(x|x<<2)&0x33;10x=(x|x<<1)&0x55;11y=(y|y<<2)&0x33;12y=(y|y<<1)&0x55;13unsignedshortz=x|y<<1;14cout<<z<<endl;15return0;16}假設(shè)輸入的x、y均是不超過15的自然數(shù)，完成下面的判斷題和單選題：判斷題（1）刪去第7行與第13行的unsigned，程序行為不變。（）（2）將第7行與第13行的short均改為char，程序行為不變。（）（3）程序總是輸出一個整數(shù)“0”。（）（4）當輸入為“22”時，輸出為“10”。（）（5）當輸入為“22”時，輸出為“59”。（）單選題（6）當輸入為“138”時，輸出為（）A.“0”B.“209”C.“197”D.“226”17.01#include<algorithm>02#include<iostream>03#include<limits>0405usingnamespacestd;0607constintMAXN=105;08constintMAXK=105;0910inth[MAXN][MAXK];1112intf(intn,intm)13{14if(m==1)returnn;15if(n==0)return0;1617intret=numeric_limits<int>::max();18for(inti=1;i<=n;i++)19ret=min(ret,max(f(ni,m),f(i1,m1))+1);20returnret;21}2223intg(intn,intm)24{25for(inti=1;i<=n;i++)26h[i][1]=i;27for(intj=1;j<=m;j++)28h[0][j]=0;2930for(inti=1;i<=n;i++){31for(intj=2;j<=m;j++){32h[i][j]=numeric_limits<int>::max();33for(intk=1;k<=i;k++)34h[i][j]=min(35h[i][j],36max(h[ik][j],h[k1][j1])+1);37}38}3940returnh[n][m];41}4243intmain()44{45intn,m;46cin>>n>>m;47cout<<f(n,m)<<endl<<g(n,m)<<endl;48return0;49}假設(shè)輸入的n、m均是不超過100的正整數(shù)，完成下面的判斷題和單選題：判斷題（1）當輸入為“73”時，第19行用來取最小值的min函數(shù)執(zhí)行了449次。（）（2）輸出的兩行整數(shù)總是相同的。（）（3）當m為1時，輸出的第一行總為n。（）單選題（4）算法g（n，m）最為準確的時間復(fù)雜度分析結(jié)果為（）。A.0(n3/2m)B.0(nm)C.0(n2m)D.0(nm2)（5）當輸入為“202”時，輸出的第一行為（）。A.“4”B.“5”C.“6”D.“20”（6）當輸入為“100100”時，輸出的第一行為（）。A.“6”B.“7”C.“8”D.“9”18.01#include<iostream>0203usingnamespacestd;0405intn,k;0607intsolve1()08{09intl=0,r=n;10while(l<=r){11intmid=(l+r)/2;12if(mid*mid<=n)l=mid+1;13elser=mid1;14}15returnl1;16}1718doublesolve2(doublex)19{20if(x==0)returnx;21for(inti=0;i<k;i++)22x=(x+n/x)/2;23returnx;24}2526intmain()27{28cin>>n>>k;29doubleans=solve2(solve1());30cout<<ans<<''<<(ans*ans==n)<<endl;31return0;32}假設(shè)int為為32位有符號整數(shù)類型，輸入的n是不超過47000的自然數(shù)、k是不超過int表示范圍的自然數(shù)，完成下面的判斷題和單選題：判斷題（1）該算法最準確的時間復(fù)雜度分析結(jié)果為0(logn+k)。（）（2）當輸入為“98011”時，輸出的第一個數(shù)為“99”。（）（3）對于任意輸入的n，隨著所輸入k的增大，輸出的第二個數(shù)會變成“1”。（）（4）該程序有存在缺陷。當輸入的n過大時，第12行的乘法有可能溢出，因此應(yīng)當將mid強制轉(zhuǎn)換為64位整數(shù)再計算。（）單選題（5）當輸入為“21”時，輸出的第一個數(shù)最接近（）。（6）當輸入為“310”時，輸出的第一個數(shù)最接近（）。（7）當輸入為“25611”時，輸出的第一個數(shù)（）。A等于16B.接近但小于16C.接近但大于16D.前三種情況都有可能三、完善程序（單選題，每小題3分，共計30分）19.（枚舉因數(shù)）從小到大打印正整數(shù)n的所有正因數(shù)。試補全枚舉程序。01#include<bits/stdc++.h>02usingnamespacestd;0304intmain(){05intn;06cin>>n;0708vector<int>fac;09fac.reserve((int)ceil(sqrt(n)));1011inti;12for(i=1;i*i<n;++i){13if(①){14fac.push_back(i);15}16}1718for(intk=0;k<fac.size();++k){19cout<<②<<"";20}21if(③){22cout<<④<<"";23}24for(intk=fac.size()1;k>=0;k){25cout<<⑤<<"";26}27}（1）①處應(yīng)填（）A.n%i==0B.n%i==1C.n%（i1）==0D.n%（i1）==1（2）②處應(yīng)填（）A.n/fac[k]B.fac[k]C.fac[k]1（fac[k]1）（3）③處應(yīng)填（）A.（i1）*（i1）==nB.（i1）*i==nC.i*i==nD.i*（i1）==n（4）④處應(yīng)填（）B.ni+1（5）⑤處應(yīng)填（）A.n/fac[k]B.fac[k]C.fac[k]1（fac[k]1）20.（洪水填充）現(xiàn)有用字符標記像素顏色的8x8圖像。顏色填充的操作描述如下：給定起始像素的位置和待填充的顏色，將起始像素和所有可達的像素（可達的定義：經(jīng)過一次或多次的向上、下、左、右四個方向移動所能到達且終點和路徑上所有像素的顏色都與起始像素顏色相同），替換為給定的顏色。試補全程序。01#include<bits/stdc++.h>02usingnamespacestd;0304constintROWS=8;05constintCOLS=8;0607structPoint{08intr,c;09Point(intr,intc):r(r),c(c){}10};1112boolis_valid(charimage[ROWS][COLS],Pointpt,13intprev_color,intnew_color){14intr=pt.r;15intc=ptc;16return(0<=r&&r<ROWS&&0<=c&&c<COLS&&17①&&image[r][c]!=new_color);18}1920voidflood_fill(charimage[ROWS][COLS],Pointcur,intnew_color){21queue<Point>queue;22queue.push(cur);2324intprev_color=image[cur.r][cur.c];25②;2627while(!queue.empty()){28Pointpt=queue.front();29queue.pop();3031Pointpoints[4]={③,Point(pt.r1,pt.c),32Point(pt.r,pt.c+1),Point(pt.r,pt.c1)};33for(autop:points){34if(is_valid(image,p,prev_color,new_color)){35④;36⑤;37}38}39}40}4142intmain(){43charimage[ROWS][COLS]={{'g','g','g','g','g','g','g','g'},44{'g','g','g','g','g','g','r','r'},45{'g','r','r','g','g','r','g','g'},46{'g','b','b','b','b','r','g','r'},47{'g','g','g','b','b','r','g','r'},48{'g','g','g','b','b','b','b','r'},49{'g','g','g','g','g','b','g','g'},50{'g','g','g','g','g','b','b','g'}};5152Pointcur(4,4);53charnew_color='y';5455flood_fill(imagecur,new_color);5657for(intr=0;r<ROWS;r++){58for(intc=0;c<COLS;c++){59cout<<image[r][c]<<"";60}61cout<<endl;62}63//輸出：64//gggggggg65//gggg