【第一部分 選擇題】1.以下不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語言的是 。A. CB. PythonC. JavaD. C【解析】D。C語言是一種面向過程的結(jié)構(gòu)化程序設(shè)計(jì)語言。2.以下獎項(xiàng)與計(jì)算機(jī)領(lǐng)域最相關(guān)的是 。A. 奧斯卡獎B. 圖靈獎C. 諾貝爾獎D. 普利策獎【解析】B。3.目前主流的計(jì)算機(jī)儲存數(shù)據(jù)最終都是轉(zhuǎn)換成 數(shù)據(jù)進(jìn)行儲存。A. 二進(jìn)制B. 十進(jìn)制C. 八進(jìn)制D. 十六進(jìn)制【解析】A。B選項(xiàng)十進(jìn)制 是人類習(xí)慣使用的計(jì)數(shù)方式。C和D選項(xiàng)八進(jìn)制 和 十六進(jìn)制 主要是為了方便人類閱讀和書寫二進(jìn)制代碼而引入的縮寫形式例如在編程中常用來表示顏色或內(nèi)存地址但它們在計(jì)算機(jī)硬件底層依然是以二進(jìn)制的形式存在的。4.以比較作為基本運(yùn)算在 N 個數(shù)中找出最大數(shù)最壞情況下所需要的最少的比較次數(shù)為 。A.N2N^{2}N2B. NC. N?1D. N1【解析】C。讓第1個數(shù)作為默認(rèn)最大數(shù)與后面的N-1個數(shù)進(jìn)行N-1次比較。5.對于入棧順序?yàn)?a,b,c,d,e 的序列下列 不是合法的出棧序列。A. a,b,c,d,eB. e,d,c,b,aC. b,a,c,d,eD. c,d,a,e,b【解析】D。d出棧后不可能是a出棧。6.對于有 n 個頂點(diǎn)、m 條邊的無向連通圖 (mn)需要刪掉 條邊才能使其成為一棵樹。A. n?1B. m?nC. m?n?1D. m?n1【解析】D。樹核心特點(diǎn)1沒有環(huán)無回路樹中的結(jié)點(diǎn)之間不能形成閉環(huán)。2連通樹中任意兩個結(jié)點(diǎn)之間都有且僅有一條路徑相連。3邊與結(jié)點(diǎn)的關(guān)系 n 個結(jié)點(diǎn)的樹有且僅有 n?1 條邊。4層次結(jié)構(gòu)樹具有明顯的層級關(guān)系包含根結(jié)點(diǎn)、雙親結(jié)點(diǎn)等。所以要成為一個棵樹需要保留n-1條邊刪掉m-(n-1)m-n1。7. 二進(jìn)制數(shù) 101.11 對應(yīng)的十進(jìn)制數(shù)是 。A. 6.5B. 5.5C. 5.75D. 5.25【解析】C。整數(shù)部分和小數(shù)部分按位權(quán)展開求和。101.112 1*222^{2}220*212^{1}211*202^{0}201*2?12^{-1}2?11*2?22^{-2}2?24010.50.255.75。8.如果一棵二叉樹只有根結(jié)點(diǎn)那么這棵二叉樹高度為 1。請問高度為 5 的完全二叉樹有 種不同的形態(tài)A. 16B. 15C. 17D. 32【解析】A。第1層有1個結(jié)點(diǎn)第2層有2個結(jié)點(diǎn)第3層有4個結(jié)點(diǎn)第4層有8個結(jié)點(diǎn)第5層最多有16個結(jié)點(diǎn)最少保證有1個結(jié)點(diǎn)第5層從左右依次不間斷的情況下增加結(jié)點(diǎn)構(gòu)成不同的完全二叉樹。9.表達(dá)式 a*(bc)*d 的后綴表達(dá)式為( )其中 * 和 是運(yùn)算符。A. **abcdB. abc*d*C. abcd**D. *a*bcd【解析】B。按照運(yùn)算優(yōu)先級依次加上括號:((a*(bc))*d),然后按照運(yùn)算優(yōu)先級依次將對應(yīng)括號中的運(yùn)算符挪到對應(yīng)括號后面((a(bc))*d)*去掉括號得到后綴表達(dá)式abc*d*。10.6 個人兩個人組一隊(duì)總共組成三隊(duì)不區(qū)分隊(duì)伍的編號。不同的組隊(duì)情況有 種。A. 10B. 15C. 30D. 20【解析】B。區(qū)分隊(duì)伍的編號即隊(duì)伍的先后順序第1支隊(duì)伍C(6,2)第2支隊(duì)伍C(4,2),第3支隊(duì)伍就是剩余2人所以共有C(6,2)* C(4,2)*1 90。如果6個人依次是16考慮隊(duì)伍編號的情況以下6種情況屬于一種組隊(duì)方式。[12 34 56]、[12 56 34]、[34 12 56]、[34 56 12]、[56 12 34]、[56 34 12]所以考慮隊(duì)伍編號的情況下總共的組隊(duì)方式是90/A(3,3) 90/6 15。11. 在數(shù)據(jù)壓縮編碼中的哈夫曼編碼方法在本質(zhì)上是一種 的策略。A. 枚舉B. 貪心C. 遞歸D. 動態(tài)規(guī)劃【解析】B。哈夫曼樹構(gòu)造規(guī)則每次選兩個頻率最小的結(jié)點(diǎn)合并新結(jié)點(diǎn)頻率為兩結(jié)點(diǎn)之和根據(jù)構(gòu)造出的哈夫曼樹進(jìn)行哈夫曼編碼是一種貪心的策略。12.由 1,1,2,2,3 這五個數(shù)字組成不同的三位數(shù)有 種。A. 18B. 15C. 12D. 24【解析】A。假設(shè)三位數(shù)為abc分情況討論三個數(shù)位都不相同從{1,2,3}中構(gòu)成有A(3,3) 6種。有兩個數(shù)位相同1有兩個數(shù)位是相同的1{ab,ac,bc}剩下一位可以是{2,3}共有3*2 6種。2有兩個數(shù)位是相同的2{ab,ac,bc}剩下一位可以是{1,3}共有3*2 6種。共有18種。13.考慮如下遞歸算法則調(diào)用 solve(7) 得到的返回結(jié)果為 。A. 105B. 840C. 210D. 420【解析】C。1*2*3*5*7 210。14.以 a 為起點(diǎn)對下邊的無向圖進(jìn)行深度優(yōu)先遍歷則 b,c,d,e 四個點(diǎn)中有可能作為最后一個遍歷到的點(diǎn)的個數(shù)為 。A. 1B. 2C. 3D. 4【解析】B。起點(diǎn)固定為a的情況下深搜過程可能是abdce、acedb、acdbe最后一個遍歷的點(diǎn)可能是e或b兩種情況。15.有四個人要從 A 點(diǎn)坐一條船過河到 B 點(diǎn)船一開始在 A 點(diǎn)。該船一次最多可坐兩個人。 已知這四個人中每個人獨(dú)自坐船的過河時間分別為 1,2,4,8且兩個人坐船的過河時間為兩人獨(dú)自過河時間的較大者。則最短 時間可以讓四個人都過河到 B 點(diǎn)包括從 B 點(diǎn)把船開回 A 點(diǎn)的時間。A. 14B. 15C. 16D. 17【解析】B。1先讓1和2一起過河到B然后1自己開回A點(diǎn)共耗時213。2再讓4和8一起過河到B然后2自己開回A點(diǎn)共耗時8210。3最后讓1和2一起過河到B耗時2。最少耗時15。核心點(diǎn)是第2步讓大的和大的一起否則可能會出現(xiàn)84的情況?！镜诙糠?閱讀程序題】閱讀程序程序輸入不超過數(shù)組或字符串定義的范圍1輸入的 n 等于 1001 時程序不會發(fā)生下標(biāo)越界。A.對B.錯【解析】B。數(shù)組a長度為1000最大下標(biāo)999n為1001第22行會用到下標(biāo)1000會發(fā)生下標(biāo)越界。2輸入的 a[i] 必須全為正整數(shù)否則程序?qū)⑾萑胨姥h(huán)。A.對B.錯【解析】B。可以參考3的解析f函數(shù)和g函數(shù)是對x的二進(jìn)制進(jìn)行的操作x是負(fù)數(shù)情況下不受影響。3當(dāng)輸入為 5 2 11 9 16 10 時輸出為 3 4 3 17 5。A.對B.錯【解析】B。n為5依次2、11、9、16、10這五個數(shù)的二進(jìn)制形式進(jìn)行操作輸出的為3 4 3 17 4。4當(dāng)輸入為 1 511998 時輸出為 18。A.對B.錯【解析】A。將511998轉(zhuǎn)換為二進(jìn)制111 1100 1111 1111 1110共16個1f函數(shù)返回16g函數(shù)取最低位有效1返回2程序輸出18。5將源代碼中 g 函數(shù)的定義14～17 行移到 main 函數(shù)的后面程序可以正常編譯運(yùn)行。A.對B.錯【解析】B。g函數(shù)沒有在main函數(shù)之前聲明會報(bào)編譯錯誤。6當(dāng)輸入為 2 -65536 2147483647 時輸出為 。A. 65532 33B. 65552 32C. 65535 34D. 65554 33【解析】B。2147483647 0111 1111 1111 1111 1111 1111 1111 1111共31個1f返回31g函數(shù)返回1。選B。-65536涉及負(fù)數(shù)的補(bǔ)碼可以理解為f函數(shù)和g函數(shù)的二進(jìn)制表示都是補(bǔ)碼形式正數(shù)的原碼和補(bǔ)碼相同所以不用可以刻意轉(zhuǎn)換。在32位系統(tǒng)中-65536的原碼是0000 0000 0000 0001 0000 0000 0000 0000取反1111 1111 1111 1110 1111 1111 1111 1111加11111 1111 1111 1111 0000 0000 0000 000所以f函數(shù)返回16g函數(shù)返回2^16 65536輸出65552。【閱讀程序-2】base64編碼是通過算法將任意的字節(jié)數(shù)組數(shù)據(jù)對照編碼表生成只有大小寫英文字母、數(shù)字字符、、-的字符串形式。原理base64編碼是把3個字節(jié)原數(shù)據(jù)變成4個字符編碼后的數(shù)據(jù)。編碼過程原數(shù)據(jù)3字節(jié)24位編碼成4字節(jié)具體過程如圖所示解碼過程對照編碼過程取出原3字節(jié)對應(yīng)的二進(jìn)制位還原回來。分析程序init函數(shù)初始化編碼表base和映射表table假設(shè)編碼后的字符‘F’通過table[‘F’]就能快速得到‘F’在base數(shù)組中的下標(biāo)5所以table數(shù)組是用來提高查表速度的。table的有效下標(biāo)是‘A’‘Z’、‘a(chǎn)’‘z’、‘0’‘9’、‘’、‘-’、‘’。decode函數(shù)每次取4字節(jié)還原為3字節(jié)可以參考下圖從下往上理解。1輸出的第二行一定是由小寫字母、大寫字母、數(shù)字和 、 /、 構(gòu)成的字符串。A.對B.錯【答案】B。decode函數(shù)是解碼還原的過程原先的字符串可能是任意值例如第6題結(jié)果中就有空格。base64編碼過程會將原先的字符串聚焦到小寫字母、大寫字母、數(shù)字和 、 /、構(gòu)成的字符串。2可能存在輸入不同但輸出的第二行相同的情形。A.對B.錯【解析】A。3輸出的第一行為 -1。A.對B.錯【解析】A。base編碼數(shù)組元素沒有0注意字符‘0’不是數(shù)值0table[0]就是0xffchar是有符號類型值對應(yīng)-1。4設(shè)輸入字符串長度為 ndecode 函數(shù)的時間復(fù)雜度為 。A. O(√n)B. O(n)C. O(nlogn)D. O(n2n^{2}n2)【解析】A。decode函數(shù)中只有一層for循環(huán)時間負(fù)責(zé)度為O(n)。5當(dāng)輸入為 Y3Nx 時輸出的第二行為。A. cspB. csqC. CSPD. Csp【解析】B。‘Y’- 24 – 00 011000‘3’- 55 - 00 110111‘N’- 13 – 00 001101‘x’- 49 – 00 110001還原后第1個字節(jié)011000 11 – 99 – ‘c’第2個字節(jié)0111 0011 – 115 – ‘s’第3個字節(jié)01110001 – 113 – ‘p’6當(dāng)輸入為 Y2NmIDIwMjE 時輸出的第二行為 。A. ccf2021B. ccf2022C. ccf 2021D. ccf 2022【解析】C。每4個字符為一組解碼后對應(yīng)3個字符。但是最后一組有一個‘’所以最后一組解碼后對應(yīng)2個字符所以會輸出8個字符排除A和B選項(xiàng)C和D選項(xiàng)只在最有一個分組不同解碼最后一個分組。第1組Y2Nm第2組IDIw第3組MjE最后一個分組參考第5題的過程需要超耐心的位運(yùn)算與進(jìn)制轉(zhuǎn)換計(jì)算儲備。【閱讀程序-3】假設(shè)輸入的 x 是不超過 1000 的自然數(shù)完成下面的判斷題和單選題題目是在經(jīng)典歐拉篩的基礎(chǔ)上增加了一些操作。從第15和第16行可以猜出a數(shù)組標(biāo)記是否是質(zhì)數(shù)b數(shù)組是存儲質(zhì)數(shù)。篩選幾次理解不同數(shù)組含義f[i]表示i的約數(shù)個數(shù)g[i]表示i的所有約數(shù)之和。1若輸入不為 1把第 13 行刪去不會影響輸出的結(jié)果。A.對B.錯【解析】A。除了第13行對f[1]和g[1]進(jìn)行初始化后面沒有用到f[1]和g[1]刪掉不影響輸出結(jié)果。2第 25 行的 f[i] / c[i * k]可能存在無法整除而向下取整的情況。A.對B.錯【解析】B。第24行i*k是合數(shù)k是i*k的最小質(zhì)因數(shù)每次c[i]1表示i*k的最小質(zhì)因數(shù)的個數(shù)。例如9 32c[9] 2。結(jié)合約數(shù)個數(shù)定理假設(shè)i的質(zhì)因數(shù)分解為(p1)a1(p1)^{a1}(p1)a1*(p2)a2(p2)^{a2}(p2)a2*…f[i] (p1 1)*p21*…所以f[i]是包含c[i]1的f[i] / c[i * k]不可能存在無法整除而向下取整的情況。3在執(zhí)行完 init() 后f 數(shù)組不是單調(diào)遞增的但 g 數(shù)組是單調(diào)遞增的。A.對B.錯【解析】B。f數(shù)組表示約數(shù)個數(shù)g數(shù)組表示約數(shù)之和都不是單調(diào)遞增的。4init 函數(shù)的時間復(fù)雜度為 。A. O(n)B. O(nlogn)C. O(n√n)D. O(n2n^{2}n2)【解析】A。歐拉篩也稱為線性篩應(yīng)為每個合數(shù)僅會被篩掉一次。5在執(zhí)行完 init() 后f[1],f[2],f[3]…f[100] 中有個等于 2。A. 23B. 24C. 25D. 26【解析】C。f數(shù)組存儲約數(shù)個數(shù)只有質(zhì)數(shù)的約數(shù)個數(shù)是2個1100之間的質(zhì)數(shù)有25個。6當(dāng)輸入為 1000 時輸出為。A. 15 1340B. 15 2340C. 16 2340D. 16 1340【解析】C。1000的約數(shù)有16個分別是1、2、4、5、8、10、20、25、40、50、100、125、200、250、500、1000約數(shù)之和2340?！镜谌糠?完善程序題】【完善程序-1】Josephus 問題有 n 個人圍成一個圈依次標(biāo)號 0 至 n1。從 0 號開始依次 0,1,0,1,… 交替報(bào)數(shù)報(bào)到 1 的人會離開直至圈中只剩下一個人。求最后剩下人的編號。做題順序先2、3、4、5再11①處應(yīng)填 A.i nB.c nC.i n- 1D.c n-1【解析】D。環(huán)上離開n-1個人剩余1個人就不需要循環(huán)c是記錄離開的人數(shù)排除A和C選項(xiàng)分析B選項(xiàng)當(dāng)c是n-1時c n成立仍進(jìn)行標(biāo)記可能把最后一個人也標(biāo)記掉不符合題意所以此處應(yīng)該c n-1。2②處應(yīng)填 A.i % 2 0B.i % 2 1C.pD.!p【解析】C。p用來實(shí)現(xiàn)0、1、0、1、...交替報(bào)數(shù)p初始值為0當(dāng)p為1時i離開圈。3③處應(yīng)填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】C。F[i]1表示i編號的人離開c記錄離開的人數(shù)此處c。4④處應(yīng)填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】D。p用來實(shí)現(xiàn)0、1、0、1、...交替報(bào)數(shù)p ^ 1異或運(yùn)算能夠?qū)崿F(xiàn)0、1交替例如當(dāng)p為0時p ^ 1p變?yōu)?當(dāng)p為1時p ^ 1p變?yōu)?。5⑤處應(yīng)填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】B。因?yàn)榈?3行會判斷當(dāng)前i是否被標(biāo)記所以此處就是下一個環(huán)上的編號不管這個編號是否被標(biāo)記因?yàn)槭窃诃h(huán)上環(huán)的大小是n此處要取余i (i 1) % n?！就晟瞥绦?2】矩形計(jì)數(shù)平面上有 n 個關(guān)鍵點(diǎn)求有多少個四條邊都和 x 軸或者 y 軸平行的矩形滿足四個頂點(diǎn)都是關(guān)鍵點(diǎn)。給出的關(guān)鍵點(diǎn)可能有重復(fù)但完全重合的矩形只計(jì)一次。試補(bǔ)全枚舉算法。1①處應(yīng)填 A. a.x ! b.x ? a.x b.x : a.id b.idB. a.x ! b.x ? a.x b.x : a.y b.yC. equals(a, b) ? a.id b.id : a.x b.xD. equals(a, b) ? a.id b.id : (a.x ! b.x ? a.x b.x : a.y b.y)【解析】B。第61行和62行是先排序再去重去重函數(shù)中unique中只要保證x和y都相同的關(guān)鍵點(diǎn)連續(xù)在一起不關(guān)心id的順序。2②處應(yīng)填 A. i 0 || cmp(A[i], A[i - 1])B. t 0 || equals(A[i], A[t - 1])C. i 0 || !cmp(A[i], A[i - 1])D. t 0 || !equals(A[i], A[t - 1])【解析】D。t用來記錄去重后關(guān)鍵點(diǎn)的個數(shù)當(dāng)!equals(A[i], A[t - 1])成立時記錄。3③處應(yīng)填 A. b - (b - a) / 2 1B. (a b 1) 1C. (a b) 1D. a (b - a 1) / 2【解析】C。取中間點(diǎn)。4④處應(yīng)填 A. !cmp(A[mid], p)B. cmp(A[mid], p)C. cmp(p, A[mid])D. !cmp(p, A[mid])【解析】B。4和5結(jié)合結(jié)合起來理解相當(dāng)于構(gòu)造了兩個新的點(diǎn)p1i點(diǎn)的x和j點(diǎn)的y構(gòu)成一個新的點(diǎn)p利用二分查找與p相同的點(diǎn)2i點(diǎn)的y和j點(diǎn)的x構(gòu)成一個新的點(diǎn)p利用二分查找與p相同的點(diǎn)。如果能找到就找到了如圖所示的矩形。因?yàn)殛P(guān)鍵點(diǎn)都按照x、y從小到大排序所以mid點(diǎn)小于p點(diǎn)時往右收斂。5⑤處應(yīng)填 A. A[i].x A[j].xB. A[i].id A[j].idC. A[i].x A[j].x A[i].id A[j].idD. A[i].x A[j].x A[i].y A[j].y【解析】D。枚舉i和j時所有情況都包含如果不保證i和j一個在左邊一個在右邊會有重復(fù)枚舉的情況。參考4解析的圖。