（CSP-J1）入門級-C++語言試題

語言試題第10頁，共12頁2022CCF非專業(yè)級別軟件能力認證第一輪（CSP-J1）C++語言試題認證時間：202291809:30~11:30考生注意事項：100分。請在答題紙上作答，寫在試題紙上的一律無效。不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共15題，每題2分，共計30分；每題有且僅有一個正確選項）以下哪種功能沒有涉及C++語言的面向對象特性支持（ C++printf函數(shù)C++中調用用戶定義的類成員函數(shù)C++classstructC++中構造來源于同一基類的多個派生類66、5、4、3、2、1S，請問下列哪個出棧序列是非法的（ ）。A.543612B.453126C.346521D.234156運行以下代碼片段的行為是（ ）。intx=101;intx=101;inty=201;int*p=&x;int*q=&y;p=q;x201y101qx的地址py的地址鏈表和數(shù)組的區(qū)別包括（ ）。數(shù)組不能排序，鏈表可以鏈表比數(shù)組能存儲更多的信息數(shù)組大小固定，鏈表大小可動態(tài)調整以上均正確SQe1~e6六個互不相同的數(shù)據(jù)，每個數(shù)據(jù)按照的順序操作，不同數(shù)據(jù)間的操作可能會交錯。已知Se1、e2、e3、e4、e5e6Qe2、e4、e3、e6、e5e1S的容量至少是（）個數(shù)據(jù)。2346對表達式a+(b-c)*d的前綴表達式為（ ），其中+、-、*是運算符。*+a-bcd+a*-bcdabc-d*+abc-+d{a,b,c,d,e}在字符串出現(xiàn)的頻率分別為10%,15%,30%,16%,29%d的編碼長度為（ ）位。122331個位置。若存儲在數(shù)組第9個位置的結點存在兄弟結點和兩個子結點，則它的兄弟結點和右子結點的位置分別是（）。8、18B.10、18C.8、19D.10、19考慮由N個頂點構成的有向連通圖，采用鄰接矩陣的數(shù)據(jù)結構表示時，該矩陣中至少存在（ ）個非零元素。N-1NN+1N2以下對數(shù)據(jù)結構的表述不恰當?shù)囊豁棡椋海?）。圖的深度優(yōu)先遍歷算法常使用的數(shù)據(jù)結構為棧。棧的訪問原則為后進先出，隊列的訪問原則是先進先出。隊列常常被用于廣度優(yōu)先搜索算法。棧與隊列存在本質不同，無法用棧實現(xiàn)隊列。以下哪組操作能完成在雙向循環(huán)鏈表結點p之后插入結點s的效果（其中，next域為結點的直接后繼，prev域為結點的直接前驅）：（）。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;以下排序算法的常見實現(xiàn)中，哪個選項的說法是錯誤的：（ ）。冒泡排序算法是穩(wěn)定的簡單選擇排序是穩(wěn)定的簡單插入排序是穩(wěn)定的歸并排序算法是穩(wěn)定的八進制數(shù)32.1對應的十進制數(shù)是（ ）。A.24.125B.24.250C.26.125D.26.250一個字符串中任意個連續(xù)的字符組成的子序列稱為該字符串的子串，則字符串abcab有（ ）個內容互不相同的子串。12131415以下對遞歸方法的描述中，正確的是：（ ）遞歸是允許使用多組參數(shù)調用函數(shù)的編程技術遞歸是通過調用自身來求解問題的編程技術遞歸是面向對象和數(shù)據(jù)而不是功能和邏輯的編程語言模型遞歸是將用某種高級語言轉換為機器代碼的編程技術二、閱讀程序（程序輸入不超過數(shù)組或字符串定義的范圍；判斷題正確填√，錯誤填×；除特1.5340分）(1)01#include<iostream>0203usingnamespacestd;0405intmain()06{07unsignedshortx,y;08cin>>x>>y;09 x=(x|x<<2)&0x33;10 x=(x|x<<1)&0x55;11 y=(y|y<<2)&0x33;12 y=(y|y<<1)&0x55;unsignedshortz=x|y<<1;cout<<z<<endl;return0;16}x、y15的自然數(shù)，完成下面的判斷題和單選題：判斷題刪去第7行與第13行的unsigned，程序行為不變。（ ）將第7行與第13行的short均改為char，程序行為不變。（ ）程序總是輸出一個整數(shù)“0”。（ ）19.當輸入為“22”時，輸出為“10”。（ ）20.當輸入為“22”時，輸出為“59”。（ ）單選題當輸入為“138”時，輸出為（）。A.“0”B.“209”C.“197”D.“226”（2）#include<algorithm>#include<iostream>#include<limits>0405usingnamespacestd;06constintMAXN=105;constintMAXK=105;0910inth[MAXN][MAXK];1112intf(intn,intm)13{if(m==1)returnn;if(n==0)return0;16intret=numeric_limits<int>::max();for(inti=1;i<=n;i++)19 ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);20 returnret;21}2223intg(intn,intm)24{25 for(inti=1;i<=n;i++)26 h[i][1]=i;27 for(intj=1;j<=m;j++)28 h[0][j]=0;2930 for(inti=1;i<=n;i++){31 for(intj=2;j<=m;j++){h[i][j]=numeric_limits<int>::max();for(intk=1;k<=i;k++)h[i][j]=min(35 h[i][j],36 max(h[i-k][j],h[k-1][j-1])+1);37 }38 }3940 returnh[n][m];41}4243intmain()44{intn,m;cin>>n>>m;cout<<f(n,m)<<endl<<g(n,m)<<endl;return0;49}n、m100的正整數(shù)，完成下面的判斷題和單選題：判斷題當輸入為“73”時，第19行用來取最小值的min函數(shù)執(zhí)行了449次。（ ）輸出的兩行整數(shù)總是相同的。（ ）當m為1時，輸出的第一行總為n。（ ）單選題算法g(n,m)最為準確的時間復雜度分析結果為（ ）。A.????(????/2????)B.????(????????)C.????(????2????)D.????(????????2)當輸入為“202”時，輸出的第一行為（）。A.“4”B.“5”C.“6”D.“20”27.（4分）當輸入為“100100”時，輸出的第一行為（ ）。A.“6”B.“7”C.“8”D.“9”（3）01#include<iostream>0203usingnamespacestd;0405intn,k;0607intsolve1()08{09 intl=0,r=n;while(l<=r){intmid=(l+r)/2;if(mid*mid<=n)l=mid+1;elser=mid-1;14 }15 returnl-1;16}1718doublesolve2(doublex)19{if(x==0)returnx;for(inti=0;i<k;i++)22 x=(x+n/x)/2;23 returnx;24}2526intmain()27{28cin>>n>>k;29doubleans=solve2(solve1());30cout<<ans<<''<<(ans*ans==n)<<endl;31return0;32}int32n47000的自然數(shù)、kint表示范圍的自然數(shù)，完成下面的判斷題和單選題：判斷題該算法最準確的時間復雜度分析結果為????(log????+????)。（ ）當輸入為“98011”時，輸出的第一個數(shù)為“99”。（ ）對于任意輸入的n，隨著所輸入k的增大，輸出的第二個數(shù)會變成“1”。（ ）該程序有存在缺陷。當輸入的n過大時，第12行的乘法有可能溢出，因此應當將mid強制轉換為64位整數(shù)再計算。（ ）單選題當輸入為“21”時，輸出的第一個數(shù)最接近（ ）。A.1B.1.414C.1.5D.2當輸入為“310”時，輸出的第一個數(shù)最接近（ ）。A.1.7B.1.732C.1.75D.2當輸入為“25611”時，輸出的第一個數(shù)（ ）。A.16B.16C.16D.前三種情況都有可能三、完善程序（單選題，每小題3分，共計30分）（1）（枚舉因數(shù)）從小到大打印正整數(shù)n的所有正因數(shù)。試補全枚舉程序。01#include<bits/stdc++.h>02usingnamespacestd;0304intmain(){05 intn;06 cin>>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}24 for(intk=fac.size()-1;k>=0;--k){25 cout<<⑤<<"";26 }27}①處應填（）A.n%i==0B.n%i==1C.n%(i-1)==0D.n%(i-1)==1②處應填（ ）A.n/fac[k]B.fac[k]C.fac[k]-1D.n/(fac[k]-1)③處應填（ ）A.(i-1)*(i-1)==nB.(i-1)*i==nC.i*i==nD.i*(i-1)==n④處應填（ ）A.n-iB.n-i+1C.i-1D.I⑤處應填（ ）A.n/fac[k]B.fac[k]C.fac[k]-1D.n/(fac[k]-1)（2）（洪水填充）現(xiàn)有用字符標記像素顏色的8x8圖像。顏色填充的操作描述如下：給定起始像素的位置和待填充的顏色，將起始像素和所有可達的像素（可達的定義：經過都與起始像素顏色相同，替換為給定的顏色。試補全程序。01#include<bits/stdc++.h>02usingnamespacestd;03constintROWS=8;constintCOLS=8;0607structPoint{08 intr,c;09 Point(intr,intc):r(r),c(c){}10};11boolis_valid(charimage[ROWS][COLS],Pointpt,intprev_color,intnew_color){intr=pt.r;intc=pt.c;return(0<=r&&r<ROWS&&0<=c&&c<COLS&&①&&image[r][c]!=new_color);18}19voidflood_fill(charimage[ROWS][COLS],Pointcur,intnew_color){queue<Point>queue;2324 intprev_color=image[cur.r][cur.c];25 26while(!queue.empty()){Pointpt=queue.front();30Pointpoints[4]={③,Point(pt.r-1,pt.c),Point(pt.r,pt.c+1),Point(pt.r,pt.c-1)};for(autop:points){if(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'}};51Pointcur(4,4);charnew_color='y';5455 flood_fill(image,cur,new_color);56for(intr=0;r<ROWS;r++){for(intc=0;c<COLS;c++){cout<<image[r][c]<<"";60 }61 cout