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