【第一部分 選擇題】1.以下不屬于面向?qū)ο蟪绦蛟O(shè)計語言的是 。A. CB. PythonC. JavaD. C【解析】D。C語言是一種面向過程的結(jié)構(gòu)化程序設(shè)計語言。2.以下獎項與計算機領(lǐng)域最相關(guān)的是 。A. 奧斯卡獎B. 圖靈獎C. 諾貝爾獎D. 普利策獎【解析】B。3.目前主流的計算機儲存數(shù)據(jù)最終都是轉(zhuǎn)換成 數(shù)據(jù)進行儲存。A. 二進制B. 十進制C. 八進制D. 十六進制【解析】A。B選項十進制 是人類習慣使用的計數(shù)方式。C和D選項八進制 和 十六進制 主要是為了方便人類閱讀和書寫二進制代碼而引入的縮寫形式例如在編程中常用來表示顏色或內(nèi)存地址但它們在計算機硬件底層依然是以二進制的形式存在的。4.以比較作為基本運算在 N 個數(shù)中找出最大數(shù)最壞情況下所需要的最少的比較次數(shù)為 。A.N2N^{2}N2B. NC. N?1D. N1【解析】C。讓第1個數(shù)作為默認最大數(shù)與后面的N-1個數(shù)進行N-1次比較。5.對于入棧順序為 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 個頂點、m 條邊的無向連通圖 (mn)需要刪掉 條邊才能使其成為一棵樹。A. n?1B. m?nC. m?n?1D. m?n1【解析】D。樹核心特點1沒有環(huán)無回路樹中的結(jié)點之間不能形成閉環(huán)。2連通樹中任意兩個結(jié)點之間都有且僅有一條路徑相連。3邊與結(jié)點的關(guān)系 n 個結(jié)點的樹有且僅有 n?1 條邊。4層次結(jié)構(gòu)樹具有明顯的層級關(guān)系包含根結(jié)點、雙親結(jié)點等。所以要成為一個棵樹需要保留n-1條邊刪掉m-(n-1)m-n1。7. 二進制數(shù) 101.11 對應(yīng)的十進制數(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é)點那么這棵二叉樹高度為 1。請問高度為 5 的完全二叉樹有 種不同的形態(tài)A. 16B. 15C. 17D. 32【解析】A。第1層有1個結(jié)點第2層有2個結(jié)點第3層有4個結(jié)點第4層有8個結(jié)點第5層最多有16個結(jié)點最少保證有1個結(jié)點第5層從左右依次不間斷的情況下增加結(jié)點構(gòu)成不同的完全二叉樹。9.表達式 a*(bc)*d 的后綴表達式為( )其中 * 和 是運算符。A. **abcdB. abc*d*C. abcd**D. *a*bcd【解析】B。按照運算優(yōu)先級依次加上括號:((a*(bc))*d),然后按照運算優(yōu)先級依次將對應(yīng)括號中的運算符挪到對應(yīng)括號后面((a(bc))*d)*去掉括號得到后綴表達式abc*d*。10.6 個人兩個人組一隊總共組成三隊不區(qū)分隊伍的編號。不同的組隊情況有 種。A. 10B. 15C. 30D. 20【解析】B。區(qū)分隊伍的編號即隊伍的先后順序第1支隊伍C(6,2)第2支隊伍C(4,2),第3支隊伍就是剩余2人所以共有C(6,2)* C(4,2)*1 90。如果6個人依次是16考慮隊伍編號的情況以下6種情況屬于一種組隊方式。[12 34 56]、[12 56 34]、[34 12 56]、[34 56 12]、[56 12 34]、[56 34 12]所以考慮隊伍編號的情況下總共的組隊方式是90/A(3,3) 90/6 15。11. 在數(shù)據(jù)壓縮編碼中的哈夫曼編碼方法在本質(zhì)上是一種 的策略。A. 枚舉B. 貪心C. 遞歸D. 動態(tài)規(guī)劃【解析】B。哈夫曼樹構(gòu)造規(guī)則每次選兩個頻率最小的結(jié)點合并新結(jié)點頻率為兩結(jié)點之和根據(jù)構(gòu)造出的哈夫曼樹進行哈夫曼編碼是一種貪心的策略。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 為起點對下邊的無向圖進行深度優(yōu)先遍歷則 b,c,d,e 四個點中有可能作為最后一個遍歷到的點的個數(shù)為 。A. 1B. 2C. 3D. 4【解析】B。起點固定為a的情況下深搜過程可能是abdce、acedb、acdbe最后一個遍歷的點可能是e或b兩種情況。15.有四個人要從 A 點坐一條船過河到 B 點船一開始在 A 點。該船一次最多可坐兩個人。 已知這四個人中每個人獨自坐船的過河時間分別為 1,2,4,8且兩個人坐船的過河時間為兩人獨自過河時間的較大者。則最短 時間可以讓四個人都過河到 B 點包括從 B 點把船開回 A 點的時間。A. 14B. 15C. 16D. 17【解析】B。1先讓1和2一起過河到B然后1自己開回A點共耗時213。2再讓4和8一起過河到B然后2自己開回A點共耗時8210。3最后讓1和2一起過河到B耗時2。最少耗時15。核心點是第2步讓大的和大的一起否則可能會出現(xiàn)84的情況。【第二部分 閱讀程序題】閱讀程序程序輸入不超過數(shù)組或字符串定義的范圍1輸入的 n 等于 1001 時程序不會發(fā)生下標越界。A.對B.錯【解析】B。數(shù)組a長度為1000最大下標999n為1001第22行會用到下標1000會發(fā)生下標越界。2輸入的 a[i] 必須全為正整數(shù)否則程序?qū)⑾萑胨姥h(huán)。A.對B.錯【解析】B。可以參考3的解析f函數(shù)和g函數(shù)是對x的二進制進行的操作x是負數(shù)情況下不受影響。3當輸入為 5 2 11 9 16 10 時輸出為 3 4 3 17 5。A.對B.錯【解析】B。n為5依次2、11、9、16、10這五個數(shù)的二進制形式進行操作輸出的為3 4 3 17 4。4當輸入為 1 511998 時輸出為 18。A.對B.錯【解析】A。將511998轉(zhuǎn)換為二進制111 1100 1111 1111 1110共16個1f函數(shù)返回16g函數(shù)取最低位有效1返回2程序輸出18。5將源代碼中 g 函數(shù)的定義14～17 行移到 main 函數(shù)的后面程序可以正常編譯運行。A.對B.錯【解析】B。g函數(shù)沒有在main函數(shù)之前聲明會報編譯錯誤。6當輸入為 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涉及負數(shù)的補碼可以理解為f函數(shù)和g函數(shù)的二進制表示都是補碼形式正數(shù)的原碼和補碼相同所以不用可以刻意轉(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)的二進制位還原回來。分析程序init函數(shù)初始化編碼表base和映射表table假設(shè)編碼后的字符‘F’通過table[‘F’]就能快速得到‘F’在base數(shù)組中的下標5所以table數(shù)組是用來提高查表速度的。table的有效下標是‘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ù)的時間復雜度為 。A. O(√n)B. O(n)C. O(nlogn)D. O(n2n^{2}n2)【解析】A。decode函數(shù)中只有一層for循環(huán)時間負責度為O(n)。5當輸入為 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當輸入為 Y2NmIDIwMjE 時輸出的第二行為 。A. ccf2021B. ccf2022C. ccf 2021D. ccf 2022【解析】C。每4個字符為一組解碼后對應(yīng)3個字符。但是最后一組有一個‘’所以最后一組解碼后對應(yīng)2個字符所以會輸出8個字符排除A和B選項C和D選項只在最有一個分組不同解碼最后一個分組。第1組Y2Nm第2組IDIw第3組MjE最后一個分組參考第5題的過程需要超耐心的位運算與進制轉(zhuǎn)換計算儲備。【閱讀程序-3】假設(shè)輸入的 x 是不超過 1000 的自然數(shù)完成下面的判斷題和單選題題目是在經(jīng)典歐拉篩的基礎(chǔ)上增加了一些操作。從第15和第16行可以猜出a數(shù)組標記是否是質(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]進行初始化后面沒有用到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ù)的時間復雜度為 。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當輸入為 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 個人圍成一個圈依次標號 0 至 n1。從 0 號開始依次 0,1,0,1,… 交替報數(shù)報到 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選項分析B選項當c是n-1時c n成立仍進行標記可能把最后一個人也標記掉不符合題意所以此處應(yīng)該c n-1。2②處應(yīng)填 A.i % 2 0B.i % 2 1C.pD.!p【解析】C。p用來實現(xiàn)0、1、0、1、...交替報數(shù)p初始值為0當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用來實現(xiàn)0、1、0、1、...交替報數(shù)p ^ 1異或運算能夠?qū)崿F(xiàn)0、1交替例如當p為0時p ^ 1p變?yōu)?當p為1時p ^ 1p變?yōu)?。5⑤處應(yīng)填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】B。因為第13行會判斷當前i是否被標記所以此處就是下一個環(huán)上的編號不管這個編號是否被標記因為是在環(huán)上環(huán)的大小是n此處要取余i (i 1) % n。【完善程序-2】矩形計數(shù)平面上有 n 個關(guān)鍵點求有多少個四條邊都和 x 軸或者 y 軸平行的矩形滿足四個頂點都是關(guān)鍵點。給出的關(guān)鍵點可能有重復但完全重合的矩形只計一次。試補全枚舉算法。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)鍵點連續(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)鍵點的個數(shù)當!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。取中間點。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é)合起來理解相當于構(gòu)造了兩個新的點p1i點的x和j點的y構(gòu)成一個新的點p利用二分查找與p相同的點2i點的y和j點的x構(gòu)成一個新的點p利用二分查找與p相同的點。如果能找到就找到了如圖所示的矩形。因為關(guān)鍵點都按照x、y從小到大排序所以mid點小于p點時往右收斂。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一個在左邊一個在右邊會有重復枚舉的情況。參考4解析的圖。