2025年9月GESP編程能力認(rèn)證C++等級考試五級真題(含答案和解析)一、單選題（每題2分，共30分）。1.以下哪種情況使用鏈表比數(shù)組更合適？A.數(shù)據(jù)量固定且讀多寫少B.需要頻繁在中間或開頭插入、刪除元素。C.需要高效隨機(jī)訪問元素D.存儲(chǔ)空間必須連續(xù)答案：B。解析：線性表特點(diǎn)——內(nèi)存連續(xù)，訪問速度快O(1)，插入刪除速度慢O(n)。鏈表特點(diǎn)：內(nèi)存不連續(xù)，插入/刪除速度快O(1)，訪問速度慢O(n)。2.函數(shù)removeElements刪除單鏈表中所有結(jié)點(diǎn)值等于val的結(jié)點(diǎn)，并返回新的頭結(jié)點(diǎn)，其中鏈表頭結(jié)點(diǎn)為head，則橫線處填寫（）。//結(jié)點(diǎn)結(jié)構(gòu)體。structNode{intval;Node*next;Node():val(0),next(nullptr){}Node(intx):val(x),next(nullptr){}Node(intx,Node*next):val(x),next(next){}};Node*removeElements(Node*head,intval){Nodedummy(0,head);//啞結(jié)點(diǎn)，統(tǒng)一處理頭結(jié)點(diǎn)。Node*cur=&dummy;while(cur->next){if(cur->next->val==val){_______________________//在此填入代碼。}else{cur=cur->next;}}returndummy.next;}A.Node*del=cur;cur=del->next;deletedel;B.Node*del=cur->next;cur->next=del;deletedel;C.Node*del=cur->next;cur->next=del->next;deletedel;D.Node*del=cur->next;deletedel;cur->next=del->next;答案：C。解析：需要先記錄要?jiǎng)h除的節(jié)點(diǎn)，然后繞過該節(jié)點(diǎn)，最后再釋放內(nèi)存。3.函數(shù)hasCycle采用Floyd快慢指針法判斷一個(gè)單鏈表中是否存在環(huán)，鏈表的頭節(jié)點(diǎn)為head，即用兩個(gè)指針在鏈表上前進(jìn)：slow每次走1步，fast每次走2步，若存在環(huán)，fast終會(huì)追上slow（相遇）；若無環(huán)，fast會(huì)先到達(dá)nullptr，則橫線上應(yīng)填寫（）。structNode{intval;Node*next;Node(intx):val(x),next(nullptr){}};boolhasCycle(Node*head){if(!head||!head->next)returnfalse;Node*slow=head;Node*fast=head->next;while(fast&&fast->next){if(slow==fast)returntrue;_______________________//在此填入代碼。}returnfalse;}A.slow=slow->next;fast=fast->next->next;B.slow=fast->next;fast=slow->next->next;C.slow=slow->next;fast=slow->next->next;D.slow=fast->next;fast=fast->next->next;答案：A。解析：根據(jù)題目文字提示，慢指針每次走1步，快指針每次走2步，所以選A。4.函數(shù)isPerfectNumber判斷一個(gè)正整數(shù)是否為完全數(shù)（該數(shù)是否即等于它的真因子之和），則橫線上應(yīng)填寫（）。一個(gè)正整數(shù)n的真因子包括所有小于n的正因子，如28的真因子為1,2,4,7,14。boolisPerfectNumber(intn){if(n<=1)returnfalse;intsum=1;for(inti=2;______;i++){if(n%i==0){sum+=i;if(i!=n/i)sum+=n/i;}}returnsum==n;}A.i<=nB.i*i<=nC.i<=n/2D.i<n答案：B。解析：因數(shù)都是成對出現(xiàn)的，比如28的因數(shù)對1和28，2和14，4和7，所以只需要遍歷到sqrt(n)就可以了。第7行判斷i!=n/i是為了避免重復(fù)加平方跟。5.以下代碼計(jì)算兩個(gè)正整數(shù)的最大公約數(shù)(GCD)，橫線上應(yīng)填寫（）。intgcd0(inta,intb){if(a<b){swap(a,b);}while(b!=0){inttemp=a%b;a=b;b=temp;}return______;}A.bB.aC.tempD.a*b答案：B。解析：歐幾里得算法的核心思想是——兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。當(dāng)余數(shù)為0的時(shí)候，除數(shù)就是兩個(gè)數(shù)的最大公約數(shù)。6.函數(shù)sieve實(shí)現(xiàn)埃拉托斯特尼篩法(埃氏篩)，橫線處應(yīng)填入（）。vector<bool>sieve(intn){vector<bool>is_prime(n+1,true);is_prime[0]=is_prime[1]=false;for(inti=2;i<=n;i++){if(is_prime[i]){for(intj=______;j<=n;j+=i){is_prime[j]=false;}}}returnis_prime;}A.iB.i+1C.i*2D.i*i答案：D。解析：埃篩的原理是從每個(gè)質(zhì)數(shù)的平方開始，標(biāo)記這個(gè)數(shù)字所有的倍數(shù)為合數(shù)。7.函數(shù)linearSieve實(shí)現(xiàn)線性篩法(歐拉篩)，橫線處應(yīng)填入（）。vector<int>linearSieve(intn){vector<bool>is_prime(n+1,true);vector<int>primes;for(inti=2;i<=n;i++){if(is_prime[i])primes.push_back(i);for(intp:primes){if(p*i>n)break;is_prime[p*i]=false;if(________)break;}}returnprimes;}A.i%p==0B.p%i==0C.i==pD.i*p==n答案：A。解析：線性篩的核心是每個(gè)合數(shù)都用自己的最小質(zhì)因子標(biāo)記，保證每個(gè)數(shù)字只會(huì)被標(biāo)記一次，從而達(dá)到O(n)的時(shí)間復(fù)雜度。當(dāng)i能被當(dāng)前質(zhì)數(shù)p整除時(shí)（i%p==0）說明i已經(jīng)包含了p作為最小質(zhì)因數(shù)，此時(shí)如果繼續(xù)用更大的質(zhì)數(shù)乘i進(jìn)行標(biāo)記，就會(huì)造成重復(fù)標(biāo)記。8.關(guān)于“埃氏篩”和“線性篩”的比較，下列說法錯(cuò)誤的是（）。A.埃氏篩可能會(huì)對同一個(gè)合數(shù)進(jìn)行多次標(biāo)記B.線性篩的理論時(shí)間復(fù)雜度更優(yōu)，所以線性篩的速度往往優(yōu)于埃氏篩。C.線性篩保證每個(gè)合數(shù)只被其最小質(zhì)因子篩到一次D.對于常見范圍（n≤107），埃氏篩因?qū)崿F(xiàn)簡單，常數(shù)較小，其速度往往優(yōu)于線性篩。答案：B。解析：線性篩的理論時(shí)間復(fù)雜度是O(n)優(yōu)于埃氏篩的O(nloglogn)，但在n≤107時(shí)，埃篩通常更快。9.唯一分解定理描述的是（）。A.每個(gè)整數(shù)都能表示為任意素?cái)?shù)的乘積B.每個(gè)大于1的整數(shù)能唯一分解為素?cái)?shù)冪乘積（忽略順序）C.合數(shù)不能分解為素?cái)?shù)乘積D.素?cái)?shù)只有兩個(gè)因子：1和自身。答案：B。解析：唯一分解定理就是把一個(gè)合數(shù)（1既不是質(zhì)數(shù)也不是合數(shù)）寫成很多個(gè)質(zhì)數(shù)相乘的形式，這種表示時(shí)唯一的。10.給定一個(gè)nxn的矩陣matrix，矩陣的每一行和每一列都按升序排列。函數(shù)countLE返回矩陣中第k小的元素，則兩處橫線上應(yīng)分別填寫（）。//統(tǒng)計(jì)矩陣中<=x的元素個(gè)數(shù)：從左下角開始。intcountLE(constvector<vector<int>>&matrix,intx){intn=(int)matrix.size();inti=n-1,j=0,cnt=0;while(i>=0&&j<n){if(matrix[i][j]<=x){cnt+=i+1;++j;}else{--i;}}returncnt;}intkthSmallest(vector<vector<int>>&matrix,intk){intn=(int)matrix.size();intlo=matrix[0][0];inthi=matrix[n-1][n-1];while(lo<hi){intmid=lo+(hi-lo)/2;if(countLE(matrix,mid)>=k){________________//在此處填入代碼。}else{________________//在此處填入代碼。}}returnlo;}A.hi=mid-1;lo=mid+1;B.hi=mid;lo=mid;C.hi=mid;lo=mid+1;D.hi=mid+1;lo=mid;答案：C。解析：countLE(matrix,mid)的作用時(shí)統(tǒng)計(jì)小于等于mid的元素個(gè)數(shù)，如果count>=k，說明第k小的元素<=mid，所以答案在[lo,mid]區(qū)間，如果count<k,說明第k小的元素>mid,所以答案在[mid+1,hi]區(qū)間。11.下述C++代碼實(shí)現(xiàn)了快速排序算法，下面說法錯(cuò)誤的是（）。intpartition(vector<int>&arr,intlow,inthigh){inti=low,j=high;intpivot=arr[low];//以首元素為基準(zhǔn)。while(i<j){while(i<j&&arr[j]>=pivot)j--;//從右往左查找。while(i<j&&arr[i]<=pivot)i++;//從左往右查找。if(i<j)swap(arr[i],arr[j]);}swap(arr[i],arr[low]);returni;}voidquickSort(vector<int>&arr,intlow,inthigh){if(low>=high)return;intp=partition(arr,low,high);quickSort(arr,low,p-1);quickSort(arr,p+1,high);}A.快速排序之所以叫“快速”，是因?yàn)樗谄骄闆r下運(yùn)行速度較快，常數(shù)小、就地排序，實(shí)踐中通常比歸并排序更高效。B.在平均情況下，劃分的遞歸層數(shù)為logn，每層中的總循環(huán)數(shù)為n，總時(shí)間為O(nlogn)。C.在最差情況下，每輪劃分操作都將長度為的數(shù)組劃分為長度為0和n-1的兩個(gè)子數(shù)組，此時(shí)遞歸層數(shù)達(dá)到n，每層中的循環(huán)數(shù)為n，總時(shí)間為O(n2)。D.劃分函數(shù)partition中“從右往左查找”與“從左往右查找”的順序可以交換。答案：D。解析：partition函數(shù)中，兩個(gè)while循環(huán)的順序（先從右往左查找，再從左往右查找）是關(guān)鍵設(shè)計(jì)，確保分區(qū)正確。如果交換順序，會(huì)導(dǎo)致分區(qū)錯(cuò)誤，即pivot不能正確放置，破壞算法正確性，所以，順序不可交換。12.下述C++代碼實(shí)現(xiàn)了歸并排序算法，則橫線上應(yīng)填寫（）。voidmerge(vector<int>&nums,intleft,intmid,intright){//左子數(shù)組區(qū)間為[left,mid],右子數(shù)組區(qū)間為[mid+1,right]。vector<int>tmp(right-left+1);inti=left,j=mid+1,k=0;while(i<=mid&&j<=right){if(nums[i]<=nums[j])tmp[k++]=nums[i++];elsetmp[k++]=nums[j++];}while(i<=mid){tmp[k++]=nums[i++];}while(________){//在此處填入代碼。tmp[k++]=nums[j++];}for(k=0;k<tmp.size();k++){nums[left+k]=tmp[k];}}voidmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return;intmid=(left+right)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);merge(nums,left,mid,right);}A.i<midB.j<rightC.i<=midD.j<=right答案：D。解析：根據(jù)歸并排序的合并邏輯，在將左右兩個(gè)有序子數(shù)組合并時(shí)，第三個(gè)while循環(huán)用于處理右子數(shù)組中剩余的元素。因此，填空的地方要確保右子數(shù)組索引j在有效范圍內(nèi)，也就是mid+1到right。13.假設(shè)你是一家電影院的排片經(jīng)理，只有一個(gè)放映廳。你有一個(gè)電影列表movies，其中movies[i]=[start_i,end_i]表示第i部電影的開始和結(jié)束時(shí)間。請你找出最多能安排多少部不重疊的電影，則橫線上應(yīng)分別填寫的代碼為（）。intmaxMovies(vector<vector<int>>&movies){if(movies.empty())return0;sort(movies.begin(),movies.end(),[](constvector<int>&a,constvector<int>&b){return______;//在此處填入代碼。});intcount=1;intlastEnd=movies[0][1];for(inti=1;i<movies.size();i++){if(movies[i][0]>=lastEnd){count++;______=movies[i][1];//在此處填入代碼。}}returncount;}A.a[0]<b[0]和lastEndB.a[1]<b[1]和lastEndC.a[0]<b[0]和movies[i][0]D.a[1]<b[1]和movies[i][0]答案：B。解析：第一空填寫排序，按照結(jié)束時(shí)間升序排序，如果下一個(gè)電影的開始時(shí)間大于等于上一個(gè)結(jié)束時(shí)間，可以選擇。14.給定一個(gè)整數(shù)數(shù)組nums，下面代碼找到一個(gè)具有最大和的連續(xù)子數(shù)組，并返回該最大和。則下面說法錯(cuò)誤的是（）。intcrossSum(vector<int>&nums,intleft,intmid,intright){intleftSum=INT_MIN,rightSum=INT_MIN;intsum=0;for(inti=mid;i>=left;i--){sum+=nums[i];leftSum=max(leftSum,sum);}sum=0;for(inti=mid+1;i<=right;i++){sum+=nums[i];rightSum=max(rightSum,sum);}returnleftSum+rightSum;}inthelper(vector<int>&nums,intleft,intright){if(left==right)returnnums[left];intmid=left+(right-left)/2;intleftMax=helper(nums,left,mid);intrightMax=helper(nums,mid+1,right);intcrossMax=crossSum(nums,left,mid,right);returnmax({leftMax,rightMax,crossMax});}intmaxSubArray(vector<int>&nums){returnhelper(nums,0,nums.size()-1);}A.上述代碼采用分治算法實(shí)現(xiàn)B.上述代碼采用貪心算法C.上述代碼時(shí)間復(fù)雜度為O(nlogn)D.上述代碼采用遞歸方式實(shí)現(xiàn)答案：B。解析：分治思想用到遞歸，執(zhí)行過程就是每次將問題分解為兩個(gè)子問題（規(guī)模減半）并執(zhí)行O(n)的合并操作，遞歸深度為logn，總時(shí)間復(fù)雜度為O(nlogn)，這個(gè)代碼未使用貪心思想。15.給定一個(gè)由非負(fù)整數(shù)組成的數(shù)組digits，表示一個(gè)非負(fù)整數(shù)的各位數(shù)字，其中最高位在數(shù)組首位，且digits不含前導(dǎo)0（除非是0本身）。下面代碼對該整數(shù)執(zhí)行+1操作，并返回結(jié)果數(shù)組，則橫線上應(yīng)填寫（）。vector<int>plusOne(vector<int>&digits){for(inti=(int)digits.size()-1;i>=0;--i){if(digits[i]<9){digits[i]+=1;returndigits;}________________//在此處填入代碼。}digits.insert(digits.begin(),1);returndigits;}A.digits[i]=0;B.digits[i]=9;C.digits[i]=1;D.digits[i]=10;答案：A。解析：循環(huán)從右往前處理數(shù)字，當(dāng)前位digits[i]=9時(shí)，加1后產(chǎn)生進(jìn)位(即變?yōu)?)，因此需要將當(dāng)前位設(shè)為0，并繼續(xù)處理前一位。如果所有位都是9，循環(huán)結(jié)束后在數(shù)組開頭插入1，設(shè)為0能正確實(shí)現(xiàn)進(jìn)位處理，其他選項(xiàng)不符合進(jìn)位邏輯。二、判斷題（每題2分，共20分）。16.基于下面定義的函數(shù)，通過判斷isDivisibleBy9(n)==isDigitSumDivisibleBy9(n)代碼可驗(yàn)算如果一個(gè)數(shù)能被9整除，則它的各位數(shù)字之和能被9整除。（）。boolisDivisibleBy9(intn){returnn%9==0;}boolisDigitSumDivisibleBy9(intn){intsum=0;stringnumStr=to_string(n);for(charc:numStr){sum+=(c-'0');}returnsum%9==0;}答案：正確。解析：第一個(gè)函數(shù)判斷n能否被9整除，第二個(gè)函數(shù)先將數(shù)字轉(zhuǎn)換為字符串，然后再遍歷每個(gè)字符，統(tǒng)計(jì)各個(gè)位數(shù)字之和，判斷是否能被9整除。17.假設(shè)函數(shù)gcd()能正確求兩個(gè)正整數(shù)的最大公約數(shù)，則下面的findMusicalPattern(4，6)函數(shù)返回2。（）。voidfindMusicalPattern(intrhythm1,intrhythm2){intcommonDivisor=gcd(rhythm1,rhythm2);intpatternLength=(rhythm1*rhythm2)/commonDivisor;returnpatternLength。}答案：錯(cuò)誤。解析：兩個(gè)數(shù)的最小公倍數(shù)等于兩個(gè)數(shù)的乘積除以兩個(gè)數(shù)的最小公約數(shù)。18.下面遞歸實(shí)現(xiàn)的斐波那契數(shù)列的時(shí)間復(fù)雜度為O(2n)。（）。longlongfib_memo(intn,longlongmemo[]){if(n<=1)returnn;if(memo[n]!=-1)returnmemo[n];memo[n]=fib_memo(n-1,memo)+fib_memo(n-2,memo);returnmemo[n];}intmain(){intn=40;longlongmemo[100];fill_n(memo,100,-1);longlongresult2=fib_memo(n,memo);return0;}答案：錯(cuò)誤。解析：本題代碼是通過記憶化搜索實(shí)現(xiàn)斐波那契數(shù)列，不是樸素遞歸。樸素遞歸的時(shí)間復(fù)雜度是O(2n)，本題通過memo數(shù)組存儲(chǔ)已經(jīng)計(jì)算過的結(jié)果，不會(huì)重復(fù)計(jì)算，時(shí)間復(fù)雜度是O(n)。19.鏈表通過更改指針實(shí)現(xiàn)高效的結(jié)點(diǎn)插入與刪除，但結(jié)點(diǎn)訪問效率低、占用內(nèi)存較多，且對緩存利用不友好。（）。答案：正確。解析：鏈表的插入刪除效率高O(1)，訪問效率低O(n)。占用的內(nèi)存較多，除了數(shù)據(jù)域，還要存儲(chǔ)指針。結(jié)點(diǎn)內(nèi)存不連續(xù)，對緩存利用不友好。20.二分查找依賴數(shù)據(jù)的有序性，通過循環(huán)逐步縮減一半搜索區(qū)間來進(jìn)行查找，且僅適用于數(shù)組或基于數(shù)組實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。（）。答案：正確。解析：二分查找需要待查找數(shù)據(jù)是有序的，且可以隨機(jī)訪問。21.線性篩關(guān)鍵是“每個(gè)合數(shù)只會(huì)被最小質(zhì)因子篩到一次”，因此為O(n)。（）。答案：正確。解析：線性篩法每個(gè)數(shù)字只會(huì)被標(biāo)記一次。22.快速排序和歸并排序都是穩(wěn)定的排序算法。（）。答案：錯(cuò)誤。解析：歸并排序是穩(wěn)定的排序算法，快速排序是不穩(wěn)定的排序算法。23.下面代碼采用分治算法求解標(biāo)準(zhǔn)3柱漢諾塔問題，時(shí)間復(fù)雜度為O(nlogn)。（）。voidmove(vector<int>&src,vector<int>&tar){intpan=src.back();src.pop_back();tar.push_back(pan);}voiddfs(intn,vector<int>&src,vector<int>&buf,vector<int>&tar){if(n==1){move(src,tar);return;}dfs(n-1,src,tar,buf);move(src,tar);dfs(n-1,buf,src,tar);}voidsolveHanota(vector<int>&A,vector<int>&B,vector<int>&C){intn=A.size();dfs(n,A,B,C);}答案：錯(cuò)誤。解析：漢諾塔的遞歸關(guān)系為T(n)=2T(n-1)+1，時(shí)間復(fù)雜度為O(2n)。24.所有遞歸算法都可以轉(zhuǎn)換為迭代算法。（）。答案：正確。解析：遞歸和迭代在計(jì)算能力上是等價(jià)的，任何遞歸算法都可以通過使用顯式的?；蜿?duì)列來模擬遞歸調(diào)用過程，從而轉(zhuǎn)換為迭代算法。25.貪心算法總能得到全局最優(yōu)解。（）。答案：錯(cuò)誤。解析：貪心算法只有在滿足貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)時(shí)才可以保證全局最優(yōu)。三、編程題（每題25分，共50分）。26.試題名稱：數(shù)字選取。時(shí)間限制：1.0s。內(nèi)存限制：512.0MB。題目描述：給定正整數(shù)n，現(xiàn)在有1,2……n共計(jì)n個(gè)整數(shù)。你需要從這n個(gè)整數(shù)中選取一些整數(shù)，使得所選取的整數(shù)中任意兩個(gè)不同的整數(shù)均互質(zhì)（也就是說，這兩個(gè)整數(shù)的最大公因數(shù)為1）。請你最大化所選取整數(shù)的數(shù)量。例如，當(dāng)n=9時(shí)，可以選擇1,5,7,8,9共計(jì)5個(gè)整數(shù)?？梢则?yàn)證不存在數(shù)量更多的選取整數(shù)的方案。輸入格式：一行，一個(gè)正整數(shù)n，表示給定的正整數(shù)。輸出格式：一行，一個(gè)正整數(shù)，表示所選取整數(shù)的最大數(shù)量。數(shù)據(jù)范圍：對于40%的測試點(diǎn)，保證1≤n≤1000。對于所有測試點(diǎn)，保證1≤n≤105。參考程序。#include<algorithm>#include<cstdio>usingnamespacestd;constintN=1e5+5;intn,p[N],cnt;boolnp[N];intmain(){scanf("%d",&n);for(inti=2;i<=n;i++){if(!np[i])p[++cnt]=i;for(intj=1;j<=cnt&&i*p[j]<=n;j++){np[i*p[j]]=1;if(i%p[j]==0