2025年9月GESP編程能力認(rèn)證C++等級考試八級真題(含答案和解析)一、單選題（每題2分，共30分）。1.小楊想點一杯奶茶外賣，但還差5元起送。于是，小楊決定點一些小料?？蛇x的小料包括：珍珠1元、椰果2元、奶凍3元、奶蓋4元。每種小料最多點1份。請問共有多少種滿足起送條件的點小料方案？（）。A.16B.10C.9D.7答案：C。解析：求解>=5的組合共9種。如下：1+2+3=6；1+2+3+4=10；1+2+4=7；1+3+4=8；1+4=5；2+3=5；2+3+4=9；2+4=6；3+4=7。2.小楊和小劉是好朋友，她們在逛商場時發(fā)現(xiàn)新設(shè)置的大頭貼自拍機，于是決定一起拍一組照片。一組照片包括4張，這4張照片沒有順序區(qū)分。拍每張照片時，可以選擇有相框或無相框、兩人可以分別選擇有頭飾或無頭飾、還可以從2種位置（小楊在左，或小劉在左）中選出一種。她們不希望一組照片中出現(xiàn)完全相同的相框、頭飾、位置的組合。請問一組照片共有多少種不同的方案？（）。A.1820B.70C.24D.16答案：A。解析：從16個不同的元素中選出4個的組合數(shù)C(16,4)=1820。3.下列關(guān)于C++類的說法，錯誤的是（）。A.派生類對象占用的內(nèi)存總是不小于基類對象。B.派生類可以不實現(xiàn)基類的虛函數(shù)。C.如果一個類包含純虛函數(shù)，則它不能包含成員變量。D.如果一個類包含純虛函數(shù)，則不能用它定義對象。答案：C。解析：一個包含純虛函數(shù)的類（抽象類）完全可以包含成員變量。純虛函數(shù)僅要求派生類必須實現(xiàn)該函數(shù)，但并不限制抽象類本身定義成員變量。4.下列關(guān)于樹和圖的說法，錯誤的是（）。A.每個連通圖都存在生成樹。B.每個存在生成樹的有向圖，都一定是強連通的。C.保留樹的所有節(jié)點，并把樹的每個節(jié)點指向其父節(jié)點，則可以將樹轉(zhuǎn)換為一個有向弱連通圖。D.保留樹的所有節(jié)點，并把樹的每個節(jié)點指向其子節(jié)點，則可以將樹轉(zhuǎn)換為一個有向無環(huán)圖。答案：B。解析：存在生成樹的有向圖不一定是強連通的。生成樹僅保證圖中存在一個包含所有頂點的連通子圖，但強連通要求任意兩頂點間存在雙向路徑。例如，有向樹（根節(jié)點指向子節(jié)點）存在生成樹，但子節(jié)點無法反向指向根節(jié)點，因此不滿足強連通性。5.一對夫妻生男生女的概率相同。這對夫妻希望兒女雙全。請問這對夫妻生下三個孩子時，實現(xiàn)兒女雙全的概率是多少？（）。A.1/4B.1/2C.3/4D.7/8答案：C。解析：可以用總概率減去全男和全女的概率，答案為1-(1/8)-(1/8)=(3/4)。6.二項式(x+y)6的展開式中x2y4項的系數(shù)是（）。A.720B.120C.20D.15答案：D。解析：x2y4對應(yīng)C(6,2)=15。7.對一個包含V個頂點、E條邊的圖，執(zhí)行廣度優(yōu)先搜索，其最優(yōu)時間復(fù)雜度是（）。A.O(V)B.O(V+E)C.O(V2)D.O(E)答案：B。解析：鄰接表存儲下,BFS每個點只遍歷一次，每個邊只走一次，復(fù)雜度O(V+E)。8.以下關(guān)于貪心法和動態(tài)規(guī)劃的說法中，錯誤的是（）。A.動態(tài)規(guī)劃能解決大部分多階段決策問題。B.對特定的問題，貪心法不一定適用。C.當(dāng)特定的問題適用貪心法時，通常比動態(tài)規(guī)劃的時間復(fù)雜度更低。D.對很多問題，遞推實現(xiàn)和遞歸實現(xiàn)動態(tài)規(guī)劃方法的時間復(fù)雜度相當(dāng)。答案：A。解析：適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。也就是說，使用動態(tài)規(guī)劃求解的多階段決策問題是有前提的。而且不是大部分多階段決策問題都能使用動態(tài)規(guī)劃。9.下面程序的輸出為（）。#include<iostream>usingnamespacestd;intmain(){intN=15,cnt=0;for(intx=1;x+x+x<=N;x++)for(inty=x;x+y+y<=N;y++)for(intz=y;x+y+z<=N;z++)cnt++;cout<<cnt<<endl;return0;}A.45B.102C.174D.3375答案：B。解析：將z進(jìn)行上下界統(tǒng)計,當(dāng)x和y固定時,z有N-x-2*y+1=16-x-2*y種方案，通過枚舉發(fā)現(xiàn)規(guī)律，如下表。10.下面程序的時間復(fù)雜度為（）。intprimes[MAXP],num=0;boolisPrime[MAXN]={false};voidsieve(){for(intn=2;n<=MAXN;n++){if(!isPrime[n])primes[num++]=n;for(inti=0;i<num&&n*primes[i]<=MAXN;i++){isPrime[n*primes[i]]=true;if(n%primes[i]==0)break;}}}A.O(nlogn)B.O(nloglogn)C.O(n)D.O(logn)答案：C。解析：歐拉線性篩，復(fù)雜度O(n)。11.下列Dijkstra算法，假設(shè)圖graph中頂點數(shù)v、邊數(shù)e，則程序的時間復(fù)雜度為（）。typedefstructEdge{intin,out;//從下標(biāo)in頂點到下標(biāo)out頂點的邊。intlen;//邊長度。structEdge*next;}Edge;//v頂點個數(shù)，graph出邊鄰接表，start起點下標(biāo)，dis輸出每個頂點的最短距離。voiddijkstra(intv,Edge*graph[],intstart,int*dis){constintMAX_DIS=0x7fffff;for(inti=0;i<v;i++)dis[i]=MAX_DIS;dis[start]=0;int*visited=newint[v];for(inti=0;i<v;i++)visited[i]=0;visited[start]=1;for(intt=0;;t++){intmin=MAX_DIS,minv=-1;for(inti=0;i<v;i++){if(visited[i]==0&&min>dis[i]){min=dis[i];minv=i;}}if(minv<0)break;visited[minv]=1;for(Edge*e=graph[minv];e!=NULL;e=e->next)if(dis[e->out]>e->len)dis[e->out]=e->len;}delete[]visited;}A.O(v2)B.O(vlogv+e)C.O((v+e)logv)D.O(v+e)答案：A。解析：dijkstra在矩陣存圖的情況下復(fù)雜度為O(V2)。12.下面count_triple函數(shù)的時間復(fù)雜度為（）。intgcd(intm,intn){if(m==0)returnn;returngcd(n%m,m);}intcount_triple(intn){intcnt=0;for(intv=1;v*v*4<=n;v++)for(intu=v+1;u*(u+v)*2<=n;u+=2)if(gcd(u,v)==1){inta=u*u-v*v;intb=u*v*2;intc=u*u+v*v;cnt+=n/(a+b+c);}returncnt;}A.O(n2)B.O(n2logn)C.O(n)D.O(nlogn)答案：D。解析：最外層v的復(fù)雜度為O(sqrt(n))，對內(nèi)層u，此時v看作常數(shù),復(fù)雜度為sqrt(n)級別,gcd的復(fù)雜度為log(n)級別，總體復(fù)雜度O(nlogn)。13.下面merge_sort函數(shù)試圖實現(xiàn)歸并排序算法，橫線處應(yīng)該填入的是（）。#include<vector>usingnamespacestd;voidmerge_sort(vector<int>&arr,intleft,intright){if(right-left<=1)return;intmid=(left+right)/2;merge_sort(________);//在此處填入選項。merge_sort(________);//在此處填入選項。vector<int>temp(right-left);inti=left,j=mid,k=0;while(i<mid&&j<right)if(arr[i]<=arr[j])temp[k++]=arr[i++];elsetemp[k++]=arr[j++];while(i<mid)temp[k++]=arr[i++];while(j<right)temp[k++]=arr[j++];for(i=left,k=0;i<right;++i,++k)arr[i]=temp[k];}A.arr,left,midarr,mid,rightB.arr,left,mid+1arr,mid+1,rightC.arr,left,midarr,mid+1,rightD.arr,left,mid+1arr,mid+1,right+1答案：A。解析：根據(jù)題目，在分治的分階段，填寫左右子區(qū)間的端點，程序中right是個開區(qū)間,所以兩個子區(qū)間原本是[Left,mid-1],[mid,right-1]，由于右端點為開區(qū)間，因此程序中的形參區(qū)間為[Left,mid）,[mid,right）。14.下面Prim算法程序中，橫線處應(yīng)該填入的是（）。#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intprim(vector<vector<int>>&graph,intn){vector<int>key(n,INT_MAX);vector<int>parent(n,-1);key[0]=0;for(inti=0;i<n;i++){intu=min_element(key.begin(),key.end())-key.begin();if(key[u]==INT_MAX)break;for(intv=0;v<n;v++){if(__________){//在此處填入選項。key[v]=graph[u][v];parent[v]=u;}}}intsum=0;for(inti=0;i<n;i++){if(parent[i]!=-1){cout<<"Edge:"<<parent[i]<<"-"<<i<<"Weight:"<<key[i]<<endl;sum+=key[i];}}returnsum;}intmain(){intn,m;cin>>n>>m;vector<vector<int>>graph(n,vector<int>(n,0));for(inti=0;i<m;i++){intu,v,w;cin>>u>>v>>w;graph[u][v]=w;graph[v][u]=w;}intresult=prim(graph,n);cout<<"Totalweightoftheminimumspanningtree:"<<result<<endl;return0;}A.graph[u][v]>=0&&key[v]>graph[u][v]B.graph[u][v]<=0&&key[v]>graph[u][v]C.graph[u][v]==0&&key[v]>graph[u][v]D.graph[u][v]!=0&&key[v]>graph[u][v]答案：D。解析：prim算法,該程序中用graph[x][y]是否為0表示x和y之間是否存在邊權(quán),程序的位置為更新最小生成樹的圈外的點v到圈的距離能否通過u更新,即graph[u][v]<key[v],則更新key[v]。15.下面的程序使用出邊鄰接表表達(dá)的帶權(quán)無向圖，則從頂點0到頂點3的最短距離為（）。#include<vector>usingnamespacestd;classEdge{public:intdest;intweight;Edge(intd,intw):dest(d),weight(w){}};classGraph{private:intnum_vertex;vector<vector<Edge>>vve;public:Graph(intv):num_vertex(v),vve(v){}voidaddEdge(ints,intd,intw){vve[s].emplace_back(d,w);vve[d].emplace_back(s,w)}};intmain(){Graphg(4);g.addEdge(0,1,8);g.addEdge(0,2,5);g.addEdge(1,2,1);g.addEdge(1,3,3);g.addEdge(2,3,7);return0;}A.12B.11C.10D.9答案：D。解析：根據(jù)題目要求畫圖，得到0-2-1-3為最短路徑，邊權(quán)和為9。二、判斷題（每題2分，共20分）。16.題C++語言中，表達(dá)式'9'^3的結(jié)果值為'999'。（）。答案：錯誤。解析：字符9的ASCII碼為57和3異或，結(jié)果為58,且‘999’的寫法錯誤。17.下列C++語言代碼，能夠安全地輸出arr[5]的值。（）。intn=5;intarr[n]={1,2,3};std::cout<<arr[5];答案：錯誤。解析：arr[5]的下標(biāo)為0~4，并不包括5,輸出arr[5]會導(dǎo)致數(shù)組越界訪問。18.對n個元素的數(shù)組進(jìn)行排序，最差情況的時間復(fù)雜度為O(n2)。（）。答案：錯誤。解析：每個排序算法都有自己的最差情況的時間復(fù)雜度。盡管常見的算法中，最差情況的時間復(fù)雜度為O(n^2)（例如選擇排序、插入排序等），但仍存在比O(n^2)慢得多的排序算法（例如猴子排序、臭皮匠排序等）。19.有4個紅球、3個藍(lán)球和2個綠球排成一排（相同色球視為完全相同），則不同的排列方案數(shù)為1260種。（）。答案：正確。解析：由排列組合公式，答案為9!/(2!*3!*4!)=1260種。20.使用math.h或cmath頭文件中的函數(shù)，對于int類型的變量x，表達(dá)式fabs(x)和sqrt(x*x)的結(jié)果總是近似相等的。（）。答案：錯誤。解析：fabs(x)是求解浮點數(shù)x的絕對值,sqrt(x*x)是將x開平方后再開根號;但是先開平方會容易溢出,當(dāng)x>=46341時,x*x就會溢出int出現(xiàn)負(fù)數(shù)，這個時候會導(dǎo)致sqrt()返回值異常。21.運算符重載是C++語言靜態(tài)多態(tài)的一種典型體現(xiàn)，而使用C語言則無法實現(xiàn)運算符重載。（）。答案：正確。解析：而C語言作為面向過程的編程語言，其設(shè)計不支持函數(shù)重載和運算符重載。C語言要求同一作用域中不能存在相同的標(biāo)識符，因此無法實現(xiàn)運算符重載功能。22.存在一個簡單無向圖滿足：頂點數(shù)為6，邊數(shù)為8，6個頂點的度數(shù)分別為3、3、3、3、2、2。（）。答案：正確。解析：根據(jù)題意，存在這樣的簡單無向圖。23.已知兩個double類型的變量r和theta分別表示一個扇形的圓半徑及圓心角（弧度），則扇形的周長可以通過表達(dá)式(2+theta)*r求得。（）。答案：正確。解析：弧長公式為L=r*theta直徑為2*r總周長為(2+theta)*r。24.題Dijkstra算法的時間復(fù)雜度為O(V2)，其中V為圖中頂點的數(shù)量。（）。答案：錯誤。解析：如果使用鄰接表存儲+堆優(yōu)化，則復(fù)雜度為O((V+W)logV)。25.從32名學(xué)生中選出2人分別擔(dān)任男生班長和女生班長（男生班長必須是男生，女生班長必須是女生），則共有C(32,2)/2種不同的選法。（）。答案：錯誤。解析：題目并沒有說明有多少男生多少女生,因此無法計算。三、編程題（每題25分，共50分）。26.試題名稱：最短距離。時間限制：1.0s。內(nèi)存限制：512.0MB。題目描述：給定正整數(shù)p,q以及常數(shù)N=1018。現(xiàn)在構(gòu)建一張包含N個結(jié)點的帶權(quán)無向圖，結(jié)點依次以1,2……N編號。對于任意滿足1≤u<v≤N的u,v，向圖中加入一條連接結(jié)點u與結(jié)點v的無向邊，邊權(quán)取決于u,v是否互質(zhì)。（1）若u,v互質(zhì)（即u,v的最大公因數(shù)為1），則連接結(jié)點u與結(jié)v的無向邊長度為p。（2）否則連接結(jié)點u與結(jié)點v的無向邊長度為q?，F(xiàn)在給定n組詢問，第i（1≤i≤n）組詢問給定兩個正整數(shù)ai,bi，你需要回答結(jié)點ai與結(jié)點bi之間的最短距離。輸入格式：第一行n,p,q，三個正整數(shù)，分別表示詢問數(shù)量，結(jié)點編號互質(zhì)時的邊權(quán)，以及結(jié)點編號不互質(zhì)時的邊權(quán)。接下來n行，每行兩個正整數(shù)ai,bi，表示一組詢問。輸出格式：輸出共n行，每行一個整數(shù)，表示結(jié)點ai與結(jié)點bi之間的最短距離。數(shù)據(jù)范圍：對于30%的測試點，保證1≤n≤10，1≤ai,bi≤50。對于另外30%的測試點，保證1≤ai,bi≤250。對于所有測試點，保證1≤n≤104，1≤ai,bi≤109，1≤p,q≤109。參考程序。#include<algorithm>#include<cstdio>usingnamespacestd;constintN=1e5+5;intn,p,q;inta,b;intans;intgcd(inta,intb){if(!a||!b)returna+b;returngcd(b,a%b);}intmain(){scanf("%d%d%d",&n,&p,&q);while(n--){scanf("%d%d",&a,&b);if(a==b)ans=0;elseif(a==1||b==1)ans=p;else{ans=min(p+p,q+q);if(gcd(a,b)==1)ans=min(ans,p);elseans=min(ans,q);}printf("%d\n",ans);}return0;}解析：①若x==y則答案為0。②如果gcd(x,y)==1，可以直接變換,代價為p，也可以選擇x≠1且y≠1時將x變?yōu)閘cm(x,y)*m再變?yōu)閥，代價為2*q，但是需要滿足1<=m,且lcm(x,y)*m<=1e18。③若gcd(x,y)!=1。則可以將x變?yōu)閙再變?yōu)閥，代價為2*p，但是需要滿足gcd(x,m)==1且gcd(y,m)==1。27.試題名稱：最小生成樹。時間限制：1.0s。內(nèi)存限制：512.0MB。題目描述：給定一張包含n個結(jié)點m條邊的帶權(quán)連通無向圖，結(jié)點依次以1,2……n編號，第i條邊（1≤i≤m）連接結(jié)點ui與結(jié)點vi，邊權(quán)為wi。對于每條邊，請你求出從圖中移除該條邊后，圖的最小生成樹中所有邊的邊權(quán)和。特別地，若移除某條邊后圖的最小生成樹不存在，則輸出-1。輸入格式：第一行，兩個正整數(shù)n,m，分別表示圖的結(jié)點數(shù)與邊數(shù)。接下來m行中的第i行（1≤i≤m）包含三個正整數(shù)ui,vi,wi，表示圖中連接結(jié)點ui與結(jié)點vi的邊，邊權(quán)為wi。輸出格式：輸出共m行，第i行（1≤i≤m）包含一個整數(shù)，表示移除第i條邊后，圖的最小生成樹中所有邊的邊權(quán)和。若移除第i條邊后圖的最小生成樹不存在，則輸出-1。數(shù)據(jù)范圍。對于所有測試點，保證1≤n≤105，1≤m≤105，1≤ui,vi≤n，1≤wi≤109。參考程序。#include<cstdio>#include<algorithm>usingnamespacestd;constintN=1e5+5;constintM=2e5+5;constlonglongoo=1e18;intn,m;intu[M],v[M],w[M],p[M];inth[N],id[M],nx[M],et;intf[N],mark[M];longlongs,ans[M];intdep[N],pid[N];boolcmp(intx,inty){returnw[x]<w[y];}intgetf(intu){returnf[u]?f[u]=getf(f[u]):u;}voidlink(intx,intp){id[++et]=p;nx[et]=h[x];h[x]=et;}voiddfs(intx,intf=0,intp=0){dep[x]=dep[f]+1;pid[x]=p;for(inti=h[x];i;i=nx[i]){intto=u[id[i]]^v[id[i]]^x;if(to!=f)dfs(to,x,id[i]);}}intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=m;i++){scanf("%d%d%d",&u[i