2022CCF非專(zhuān)業(yè)級(jí)別軟件能力認(rèn)證第一輪（CSPJ1）入門(mén)級(jí)C++語(yǔ)言試題認(rèn)證時(shí)間：2022年9月18日09:30～11:30考生注意事項(xiàng)：試題紙共有12頁(yè)，答題紙共有1頁(yè)，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫(xiě)在試題紙上的一律無(wú)效。不得使用任何電子設(shè)備（如計(jì)算器、、電子詞典等）或查閱任何書(shū)籍資料。一、單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）1.以下哪種功能沒(méi)有涉及C++語(yǔ)言的面向?qū)ο筇匦灾С郑ǎ〢.C++中調(diào)用printf函數(shù)B.C++中調(diào)用用戶(hù)定義的類(lèi)成員函數(shù)C.C++中構(gòu)造一個(gè)class或structD.C++中構(gòu)造來(lái)源于同一基類(lèi)的多個(gè)派生類(lèi)2.有6個(gè)元素，按照6、5、4、3、2、1的順序進(jìn)入棧S，請(qǐng)問(wèn)下列哪個(gè)出棧序列是非法的（）A.543612 B.453126C.346521 D.2341563.運(yùn)行以下代碼片段的行為是（）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ù)組能存儲(chǔ)更多的信息C.數(shù)組大小固定，鏈表大小可動(dòng)態(tài)調(diào)整D.以上均正確5.對(duì)假設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空。存在e1～e6六個(gè)互不相同的數(shù)據(jù)，每個(gè)數(shù)據(jù)按照進(jìn)棧S、出棧S、進(jìn)隊(duì)列Q、出隊(duì)列Q的順序操作，不同數(shù)據(jù)間的操作可能會(huì)交錯(cuò)。已知棧S中依次有數(shù)據(jù)e1、e2、e3、e4、e5和e6進(jìn)棧，隊(duì)列Q依次有數(shù)據(jù)e2、e4、e3、e6、e5和e1出隊(duì)列。則棧S的容量至少是（）個(gè)數(shù)據(jù)。（）A.2 B.3 C.4 D.66.對(duì)表達(dá)式a+（bc）*d的前綴表達(dá)式為（），其中+、、*是運(yùn)算符。（）A.*+abcd B.+a*bcd C.abcd*+ D.abc+d7.假設(shè)字母表{a，b，c，d，e}在字符串出現(xiàn)的頻率分別為10%，15%，30%，16%，29%。若使用哈夫曼編碼方式對(duì)字母進(jìn)行不定長(zhǎng)的二進(jìn)制編碼，字母d的編碼長(zhǎng)度為（）位。（）A.1 B.2 C.2或3 D.38.一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)用數(shù)組進(jìn)行存儲(chǔ)與表示，已知根結(jié)點(diǎn)存儲(chǔ)在數(shù)組的第1個(gè)位置。若存儲(chǔ)在數(shù)組第9個(gè)位置的結(jié)點(diǎn)存在兄弟結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)，則它的兄弟結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置分別是（）A.8、18 B.10、18 C.8、19 D.10、199.考慮由N個(gè)頂點(diǎn)構(gòu)成的有向連通圖，采用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)表示時(shí)，該矩陣中至少存在（）個(gè)非零元素。（）A.N1 B.N C.N+1 D.N210.以下對(duì)數(shù)據(jù)結(jié)構(gòu)的表述不恰當(dāng)?shù)囊豁?xiàng)為（）A.圖的深度優(yōu)先遍歷算法常使用的數(shù)據(jù)結(jié)構(gòu)為棧B.棧的訪問(wèn)原則為后進(jìn)先出，隊(duì)列的訪問(wèn)原則是先進(jìn)先出C.隊(duì)列常常被用于廣度優(yōu)先搜索算法D.棧與隊(duì)列存在本質(zhì)不同，無(wú)法用棧實(shí)現(xiàn)隊(duì)列11.以下哪組操作能完成在雙向循環(huán)鏈表結(jié)點(diǎn)p之后插入結(jié)點(diǎn)s的效果（其中，next域?yàn)榻Y(jié)點(diǎn)的直接后繼，prev域?yàn)榻Y(jié)點(diǎn)的直接前驅(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.以下排序算法的常見(jiàn)實(shí)現(xiàn)中，哪個(gè)選項(xiàng)的說(shuō)法是錯(cuò)誤的（）A.冒泡排序算法是穩(wěn)定的 B.簡(jiǎn)單選擇排序是穩(wěn)定的C.簡(jiǎn)單插入排序是穩(wěn)定的 D.歸并排序算法是穩(wěn)定的13.八進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)是（）A. B. C. D.14.一個(gè)字符串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該字符串的子串，則字符串a(chǎn)bcab有（）個(gè)內(nèi)容互不相同的子串。（）A.12 B.13 C.14 D.1515.以下對(duì)遞歸方法的描述中，正確的是（）A.遞歸是允許使用多組參數(shù)調(diào)用函數(shù)編程技術(shù)B.遞歸是通過(guò)調(diào)用自身來(lái)求解問(wèn)題的編程技術(shù)C.遞歸是面向?qū)ο蠛蛿?shù)據(jù)而不是功能和邏輯的編程語(yǔ)言模型D.遞歸是將用某種高級(jí)語(yǔ)言轉(zhuǎn)換為機(jī)器代碼的編程技術(shù)二、閱讀程序（程序輸入不超過(guò)數(shù)組或字符串定義的范圍；判斷題正確填√，錯(cuò)誤填×；除特殊說(shuō)明外，判斷題分，選擇題3分，共計(jì)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均是不超過(guò)15的自然數(shù)，完成下面的判斷題和單選題：判斷題（1）刪去第7行與第13行的unsigned，程序行為不變。（）（2）將第7行與第13行的short均改為char，程序行為不變。（）（3）程序總是輸出一個(gè)整數(shù)“0”。（）（4）當(dāng)輸入為“22”時(shí)，輸出為“10”。（）（5）當(dāng)輸入為“22”時(shí)，輸出為“59”。（）單選題（6）當(dāng)輸入為“138”時(shí)，輸出為（）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均是不超過(guò)100的正整數(shù)，完成下面的判斷題和單選題：判斷題（1）當(dāng)輸入為“73”時(shí)，第19行用來(lái)取最小值的min函數(shù)執(zhí)行了449次。（）（2）輸出的兩行整數(shù)總是相同的。（）（3）當(dāng)m為1時(shí)，輸出的第一行總為n。（）單選題（4）算法g（n，m）最為準(zhǔn)確的時(shí)間復(fù)雜度分析結(jié)果為（）。A.0(n3/2m)B.0(nm)C.0(n2m)D.0(nm2)（5）當(dāng)輸入為“202”時(shí)，輸出的第一行為（）。A.“4”B.“5”C.“6”D.“20”（6）當(dāng)輸入為“100100”時(shí)，輸出的第一行為（）。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位有符號(hào)整數(shù)類(lèi)型，輸入的n是不超過(guò)47000的自然數(shù)、k是不超過(guò)int表示范圍的自然數(shù)，完成下面的判斷題和單選題：判斷題（1）該算法最準(zhǔn)確的時(shí)間復(fù)雜度分析結(jié)果為0(logn+k)。（）（2）當(dāng)輸入為“98011”時(shí)，輸出的第一個(gè)數(shù)為“99”。（）（3）對(duì)于任意輸入的n，隨著所輸入k的增大，輸出的第二個(gè)數(shù)會(huì)變成“1”。（）（4）該程序有存在缺陷。當(dāng)輸入的n過(guò)大時(shí)，第12行的乘法有可能溢出，因此應(yīng)當(dāng)將mid強(qiáng)制轉(zhuǎn)換為64位整數(shù)再計(jì)算。（）單選題（5）當(dāng)輸入為“21”時(shí)，輸出的第一個(gè)數(shù)最接近（）。（6）當(dāng)輸入為“310”時(shí)，輸出的第一個(gè)數(shù)最接近（）。（7）當(dāng)輸入為“25611”時(shí)，輸出的第一個(gè)數(shù)（）。A等于16B.接近但小于16C.接近但大于16D.前三種情況都有可能三、完善程序（單選題，每小題3分，共計(jì)30分）19.（枚舉因數(shù)）從小到大打印正整數(shù)n的所有正因數(shù)。試補(bǔ)全枚舉程序。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)有用字符標(biāo)記像素顏色的8x8圖像。顏色填充的操作描述如下：給定起始像素的位置和待填充的顏色，將起始像素和所有可達(dá)的像素（可達(dá)的定義：經(jīng)過(guò)一次或多次的向上、下、左、右四個(gè)方向移動(dòng)所能到達(dá)且終點(diǎn)和路徑上所有像素的顏色都與起始像素顏色相同），替換為給定的顏色。試補(bǔ)全程序。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