2022CCF非專業(yè)級別軟件能力認(rèn)證第一輪(CSP-J1)入門級C++語言試題認(rèn)證時間：2022年9月18日09:30~11:30一、單項選擇題(每題2分，共計30分)【答案】A【解析】printf函數(shù)是C語言中的函數(shù)，C語言是面向過程的語言，因此選A?！敬鸢浮緾【解析】模擬入棧出棧，C選項中"65"不可能實現(xiàn)?！敬鸢浮緿【解析】初始時p指向x的地址，q指向y的地址，執(zhí)行第5行程序后，將p指向y的地址?！敬鸢浮緾【解析】A選項，數(shù)組可以排序；B選項，鏈表不能存儲比數(shù)組更多的信息；C選項正確?！敬鸢浮緽【解析】棧的特點是后進(jìn)先出，隊列的特點是先進(jìn)先出。依題意模擬過程，括號中表示棧中數(shù)據(jù)的個數(shù)：e1入棧(1)，e2入棧(2)，e2出棧(1)，e3入棧(2)，e4入棧(3)，e4出棧(2)，e3出棧(1)，e5入棧(2)，e6入棧(3)，e6出棧(2)，e5出棧(1)，e1出棧(0)。棧的容量至少為3?！敬鸢浮緽【解析】中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法：①將所有運算按照優(yōu)先級加上小括號，(a+((b-c)*d))②將運算符移到對應(yīng)小括號前，+(a*(-(bc)d)③去掉小括號，+a*-bcd【答案】B【解析】按照哈夫曼編碼規(guī)則畫出哈夫曼樹，如下圖結(jié)點d到根節(jié)點的邊數(shù)即編碼長度為2?！敬鸢浮緾【解析】9的父結(jié)點是4，兄弟結(jié)點是8，左兒子結(jié)點是18，右兒子結(jié)點是19【答案】B【解析】n個點有向連通圖，至少有n條邊，連成一圈，鄰接矩陣中非零元素即為邊數(shù)最少為n。【答案】D【解析】使用兩個棧，一個棧存放入隊的操作，另一個棧用來出隊，即可用棧實現(xiàn)隊列?！敬鸢浮緿【解析】畫圖模擬，選項D正確。【答案】B【解析】選擇排序是不穩(wěn)定排序?！敬鸢浮緾【解析】按權(quán)展開，3×8+2×1+1×1/8=26.125【答案】B【解析】所有子串共有16個，刨去重復(fù)的子串"a","b","ab"，余下13個不重復(fù)的子串。【答案】B【解析】遞歸是通過調(diào)用自身來求解問題的編程技術(shù)，B選項正確。二、閱讀程序題(除特殊說明外，判斷題每題1.5分，選擇題每題3分，共計40分)01程序（1）【解析】本程序考查位運算的知識點。unsignedshort表示無符號短整型，數(shù)據(jù)范圍為0~65535，占2個字節(jié)。|為按位或運算，&為按位與運算，<<為左移運算。需要注意的是<<運算優(yōu)先級高于|。0x33表示十六進(jìn)制的33，即十進(jìn)制的51;0x55表示十六機制的55，即十進(jìn)制的85?！敬鸢浮俊獭窘馕觥縮hort為16位，刪除unsigned，相當(dāng)于少了一位最高位。0x55=01010101B，少一位不影響運算結(jié)果?！敬鸢浮俊痢窘馕觥枯斎霝椴怀^15的自然數(shù)，改為char以后，當(dāng)輸入為兩位數(shù)時，x，y分別讀入的是第一個數(shù)的十位和個位，改變了程序的行為和結(jié)果?！敬鸢浮俊痢窘馕觥看?22"，輸出結(jié)果為"12"?！敬鸢浮俊痢窘馕觥看?22"，輸出結(jié)果為"12"?！敬鸢浮俊痢窘馕觥看?22"，輸出結(jié)果為"12"?！敬鸢浮緽【解析】代入"138"，輸出結(jié)果為"209"。02程序（2）【解析】本程序中f函數(shù)和g函數(shù)的計算結(jié)果是一樣的，f函數(shù)通過遞歸實現(xiàn)，g函數(shù)通過循環(huán)實現(xiàn)。因此，在計算結(jié)果時，可以代入任意函數(shù)列表進(jìn)行計算得到結(jié)果?！敬鸢浮俊痢窘馕觥看肽M計算，共執(zhí)行了448次。亦可通過遞推式根據(jù)奇偶性快速判斷?！敬鸢浮俊獭窘馕觥績蓚€函數(shù)的計算結(jié)果是一樣的?！敬鸢浮俊獭窘馕觥看雈函數(shù)，當(dāng)m==1時，計算結(jié)果為n?！敬鸢浮緾【解析】i=1時，內(nèi)層兩重循環(huán)重復(fù)(m-1)次;i=2時，內(nèi)層兩重循環(huán)重復(fù)2(m-1)次；……i=n時，內(nèi)層兩重循環(huán)重復(fù)n(m-1)次；累加求和，可得∑i(m-1)=n(n+1)(m+1)/2，時間復(fù)雜度為O()?！敬鸢浮緾【解析】代入模擬，可以發(fā)現(xiàn)m=2時，列舉出n為1~20的計算結(jié)果為1個1，2個2，3個3，4個4，5個5，5個6，因此結(jié)果為6。【答案】B【解析】代入模擬，先計算出m=1，m=2，m=3的情況，找出規(guī)律，可以發(fā)現(xiàn)當(dāng)m=100的時候，列舉出n從1~100的結(jié)果，為1個1，2個2，4個3，8個4，16個5，32個6，37個7，因此結(jié)果為7。032程序（3）【解析】本程序考查二分法及牛頓迭代法求算術(shù)平方根。solve1函數(shù)用二分法求出近似的算術(shù)平方根，然后用solve2函數(shù)進(jìn)行牛頓迭代法，求出n的算術(shù)平方根。k為迭代的次數(shù)?！敬鸢浮俊獭窘馕觥縮olve1函數(shù)是二分O(logn)，solve2函數(shù)是O(k)，都只執(zhí)行一次，是O(logn+k)?！敬鸢浮俊獭窘馕觥?801=99×99，算術(shù)平方根為99?！敬鸢浮俊痢窘馕觥咳绻阈g(shù)平方根是無理數(shù)，則第二個數(shù)輸出為0。【答案】×【解析】n<=47000,mid<=n/2<=23500,mid*mid<=552,250,000，不會溢出。【答案】C【解析】代入計算，solve1函數(shù)的計算結(jié)果為1，solve2函數(shù)的計算結(jié)果為1.5?！敬鸢浮緽【解析】√3=1.732…，k=10，迭代次數(shù)越多精度越高，因此接近B?！敬鸢浮緼【解析】256=16×16，輸出的第一個數(shù)等于16。三、完善程序(每題3分，共計30分)01程序（1）【解析】本程序先從小到大輸出小于算術(shù)平方根的因數(shù)，再特判算術(shù)平方根，最后輸出大于算術(shù)平方根的因數(shù)?！敬鸢浮緼【解析】判斷i是n的一個因數(shù)，則加入數(shù)組fac中，因此判斷條件為A?！敬鸢浮緽【解析】當(dāng)前數(shù)組fac存儲的是小于平方根的所有因數(shù)，按順序輸出即可。【答案】C【解析】特判，如果是完全平方數(shù)i*i==n，則輸出算術(shù)平方根i?！敬鸢浮緿【解析】如果是完全平方數(shù)i*i==n，則輸出算術(shù)平方根i。【答案】A【解析】從小到大輸出大于算術(shù)平方根的因數(shù)，因此需要倒序枚舉小于算術(shù)平方根的因數(shù)fac[k]，輸出對應(yīng)的另一個因數(shù)n/fac[k]。021程序（2）【解析】用bfs實現(xiàn)洪水填充算法。flood_fill函數(shù)的參數(shù)依次為圖像二維數(shù)組image，起始位置cur，給定的顏色new_color。【答案】A【解析】判斷image[r][c]為舊顏色prev_color時，需要更新顏色，因此選A?！敬鸢浮緽【解析】