排序算法
前綴/后綴表達式
二進制補碼、反碼
最短路
圖片/音頻/視頻文件格式

$?$ 以比較作為基本運算，在 N 個數中找最小數的最少運算次數為（ ）。
A. $N$
B. $N?1$
C. $N^2$
D. $logN$
正確答案： B

$?$ 設 A 和 B 是兩個長為 n 的有序數組，現在需要將 A 和 B 合并成一個排好序的 數組，請問任何以元素比較作為基本運算的歸并算法最壞情況下至少要做 （ ）次比較。
A. $n^2$
B. $nlogn$
C. $2n$
D. $2n?1$
正確答案：D

$?$ 某計算機的 CPU 和內存之間的地址總線寬度是 32 位（bit），這臺計算機最多可以使用( )的內存。
正確答案： 4GB
解析：
地址總線寬度為32位,一次可以發送的一個數據是32位的，則尋址的單元最大就是32位數據的最大值，就是2的32次方。
$2^{32}B=2^{22}KB=2^{12}MB=2^{2}GB=4GB$

$?$有 7 個一模一樣的蘋果，放到 3 個一樣的盤子中，一共有（ ）種放法。
正確答案：8

$?$ 將 7 個名額分給 4 個不同的班級，允許有的班級沒有名額，有（ ）種不 同的分配方案。
正確答案：120
解析：
排列組合 "N個球放入M個盒子"問題 總結
　　球，盒子都可以分成不能區分和能區分，還能分成是否能有空箱子，所以一共是8種情況。
1.球同，盒不同，無空箱
　　$C_{n?1}^{m?1}$,n>=m
　　0,n<m
　　使用插板法：n個球中間有n-1個間隙，現在要分成m個盒子，而且不能有空箱子，所以只要在n-1個間隙選出m-1個間隙即可

2.球同，盒不同，允許空箱
　　$C_{n+m?1}^{m?1}$
　　我們在第1類情況下繼續討論，我們可以先假設m個盒子里都放好了1個球，所以說白了就是，現在有m+n個相同的球，要放入m個不同的箱子，沒有空箱。也就是第1種情況

3.球不同，盒相同，無空箱
　　第二類斯特林數$dp[n][m]$
　　$dp[n][m]=m\times dp[n?1][m]+dp[n?1][m?1]$,1<=m<n
　　$dp[k][k]=1$,k>=0
　　$dp[k][0]=0$,k>=1
　　0,n<m
　　這種情況就是第二類斯特林數，我們來理解一下這個轉移方程。
　　對于第n個球，如果前面的n-1個球已經放在了m個箱子里，那么現在第n個球放在哪個箱子都是可以的，所以$m\times dp[n?1][m]$;
　　如果前n-1個球已經放在了m-1個箱子里，那么現在第n個球必須要新開一個箱子來存放，所以$dp[n?1][m?1]$
　　其他的都沒法轉移過來

4.球不同，盒相同，允許空箱
答案是${\sum }_{i=0}^{m}dp[n][i]$
　　$dp[n][m]$為情況3的第二類斯特林數
　　這種情況就是在第3種情況的前提下，去枚舉使用的箱子的個數

5.球不同，盒不同，無空箱
　　$dp[n][m]\times fac[m]$
　　dp[n][m]為情況3的第二類斯特林數,fac[m]為m的階乘
　　因為球是不同的，所以dp[n][m]得到的盒子相同的情況，只要再給盒子定義順序，就等于現在的答案了

6.球不同，盒不同，允許空箱
　　$m^n$
　　每個球都有m種選擇，所以就等于$m^n$

7.球同，盒同，允許空箱
　　$dp[n][m]=dp[n][m?1]+dp[n?m][m]$, n>=m
　　$dp[n][m]=dp[n][m?1]$, n<m
　　邊界$dp[k][1]=1,dp[1][k]=1,dp[0][k]=1$
　　
　　現在有n個球，和m個箱子，我可以選擇在所有箱子里面都放上1個球，也可以不選擇這個操作。
　　如果選擇了這個操作，那么就從$dp[n?m][m]$轉移過來
　　如果沒有選擇這個操作，那么就從$dp[n][m?1]$轉移過來

8.球同，盒同，無空箱
　　$dp[n?m][m]$, $dp[][]$同第7種情況,n>=m
　　0, n<m
　　因為要求無空箱，我們先在每個箱子里面放1個球，然后還剩下n-m個球了,再根據情況7答案就出來了
　　
$?$ 由四個不同的點構成的簡單無向連通圖的個數是（ ）。
正確答案：38
解析：
最多可加$\frac{n?(n?1)}{2}$ 條邊,最少可加$n?1$條邊

個數即為：$C_6^3?4+C_6^4+C_6^5+C_6^6=38$

為什么減4呢？因為在6條邊中選3條邊會有4種不連通的情況，
即3條邊連了3個點構成一個環，剩下的一個點被孤立，顯然此種情況不能成立

$?$以下屬于無線通信技術的有（ ）。
A. 藍牙
B. WiFi
C. GPRS
D. 以太網
正確答案：ABC

$?$可以將單個計算機接入到計算機網絡中的網絡接入通訊設備有（ ）。
A. 網卡
B. 光驅
C. 鼠標
D. 顯卡
正確答案：A
解析：
網卡是一塊被設計用來允許計算機在計算機網絡上進行通訊的計算機硬件。
光驅是電腦用來讀寫光碟內容的機器。
顯卡：將電腦的數字信息轉成模擬信號讓顯示器顯示出來。

$?$一個 1×8 的方格圖形（不可旋轉）用黑、白兩種顏色填涂每個方格。如果每個方格只能填涂一種顏色，且不允許兩個黑格相鄰，共有_________種填涂方案。
正確答案：55
解析：
法一：
設DP狀態為$F[i][0/1]$ 分別表示取到第 i 個格，當前格是白/黑的方案數，
最后答案為$F[n][0]+F[n][1]$，
轉移 $F[i][0]=F[i?1][0]+F[i?1][1]，F[i][1]=F[i?1][0]$

法二：
設DP狀態為$F[i]$ 分別表示取到第 i 個格的方案數，
若當前格是白色的，前一格顏色任意，$F[n]=F[n?1]$；
若當前格是黑色的，前一格是白色的，$F[n]=F[n?2]$；
所以，$F[n]=F[n?1]+F[n?2]$。這是一個斐波那契數列。

$?$從（2020）年開始，NOIP 競賽將不再支持 Pascal 語言。
補充：
到2020年，除NOIP以外的賽事不再支持Pascal，c
到2022年，NOIP也不再支持Pascal，NOI賽事僅支持c++

$?$若 f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2，則隨著 i 的增大，f[i]將接近于( )。
A. 1/2
B. 2/3
C. (√5 ? 1)/2
D. 1
正確答案： B
解析：
$令g[n]=f[n]?f[n?1],n=1,2,...$
$f[n+1]\times 2=f[n]+f[n?1]$
$f[n+1]?f[n]=f[n?1]?f[n+1]$
$f[n+1]?f[n]=f[n?1]?(f[n]+f[n?1])/2$
$f[n+1]?f[n]=?(f[n]?f[n?1])/2$
$即g[n+1]=?g[n]/2$
$g[1]=1$
$故g[n]=(?2{)}^{1?n}$
$g[n]+g[n?1]+...+g[1]=f[n]?f[0]=(?2{)}^{1?n}+...+1=2/3\times (1?(?2{)}^{?n})$
$f[n]\to 2/3$

$?$小明要去南美洲旅游，一共乘坐三趟航班才能到達目的地，其中第 1 個航班 準點的概率是 0.9，第 2 個航班準點的概率為 0.8, 第 3 個航班準點的概率為 0.9。如果存在第 i 個（i=1,2）航班晚點，第 i+1 個航班準點，則小明將趕不 上第 i+1 個航班，旅行失敗；除了這種情況，其他情況下旅行都能成功。請 問小明此次旅行成功的概率是（ ）。
A. 0.5
B. 0.648
C. 0.72
D. 0.74
正確答案：D
解析：
第一班晚點第二班準點的概率為$0.1\times 0.8=0.08$，不必考慮第三班；第二班晚點第三班準點的概率為$0.2\times 0.9=0.18$，不必考慮第一班，加起來為不能成功的概率，即$0.08+0.18=0.26$，用1減去這個概率即為答案，即$1?0.26=0.74$

$?$歡樂噴球：兒童游樂場有個游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一 個圓形軌道，軌道上有一列小火車在勻速運動，火車有六節車廂。

假設乒乓球等概率落到正方形場地的每個地點，包括火車車廂。小朋友玩這個游戲時，只能坐在同一個火車車廂里，可以在自己的車廂里撿落在該車廂內的所有乒乓球，每個人每次游戲有三分鐘時間，則一個小朋友獨自玩一次游戲期望可以得到（ ）個乒乓球。假設乒乓球噴出的速度為 2 個/秒，每節車廂的面積是整個場地面積的 1/20。
A. 60
B. 108
C. 18
D. 20
正確答案：C
解析：
一共有2 * 60 * 3=360個球
360 / 20=18（個）

$?$以下是面向對象的高級語言的有（ ）。
A. 匯編語言
B. C++
C. Fortran
D. Java
正確答案：BD

$?$下列屬于解釋執行的程序設計語言是
A. C
B. C++
C. Pascal
D. Python
正確答案：D

$?$以下和計算機領域密切相關的獎項有（ ）。
A. 奧斯卡獎
B. 圖靈獎
C. 諾貝爾獎
D. 王選獎
正確答案：BD

$?$中國計算機學會于（ ）年創辦全國青少年計算機程序設計競賽。
A. 1983
B. 1984
C. 1985
D. 1986
正確答案： B

$?$如右圖所示，共有 13 個格子。對任何一個格子進行一 次操作，會使得它自己以及與它上下左右相鄰的格子中 的數字改變（由 1 變 0，或由 0 變 1）。現在要使得所 有的格子中的數字都變為 0，至少需要_________次操作。

正確答案：3

$?$如下圖所示，A 到 B 是連通的。假設刪除一條細的邊的代價是 1，刪除一條粗的邊的代價是 2，要讓 A、B 不連通，最小代價是(________)（2 分），最小代價的不同方案數是(_______)（3 分）。（只要有一條刪除的邊不同，就 是不同的方案）

正確答案：4 9

$?$在一條長度為 1 的線段上隨機取兩個點，則以這兩個點為端點的線段的期望長度是（ ）。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5
正確答案： B
解析：
我們先考慮固定一個端點的情況，如果左端點固定在了最左邊那么答案為1/2，既然左端點更大，那么肯定答案會小于1/2，因此只能是B

正解：
法一：
從0～L任選一點x,0到x的線段長度期望為
$\frac{{\int }_0^{L}x}{L}=(\frac{1}{2}{L}^2?\frac{1}{2}{0}^2)/L=\frac{1}{2}L$
于是從0～1任選一點x，然后再選一點y與x的構成線段的期望長度為
$[{\int }_0^1(\frac{1?x}{1}\times \frac{1?x}{2}+\frac{x}{1}\times \frac{x}{2})]/1$
$={\int }_0^1(x^2?x+\frac{1}{2})$
$=(\frac{1}{3}\times 1^3?\frac{1}{2}\times 1^2+\frac{1}{2}\times 1)?(0)$
$=\frac{1}{3}$

法二
（ps.這篇博客是有點問題的，ans=（ans/2+ans/2+1/2+1/2）/2應該是除以4）

$?$關于Catalan 數 Cn = (2n)! / (n + 1)! / n！，下列說法中錯誤的是（ ）。
A. Cn 表示有n + 1 個結點的不同形態的二叉樹的個數。
B. Cn 表示含n 對括號的合法括號序列的個數。
C. Cn 表示長度為n 的入棧序列對應的合法出棧序列個數。
D. Cn 表示通過連接頂點而將n + 2 邊的凸多邊形分成三角形的方法個數。
正確答案： A
解析：卡特蘭數詳解

$?$假設一臺抽獎機中有紅、藍兩色的球，任意時刻按下抽獎按鈕，都會等概率獲得紅球或藍球之一。有足夠多的人每人都用這臺抽獎機抽獎，假如他們的策略均為：抽中藍球則繼續抽球，抽中紅球則停止。最后每個人都把自己獲得的所有球放到一個大箱子里，最終大箱子里的紅球與藍球的比例接近于（ ）。
A. 1 : 2
B. 2 : 1
C. 1 : 3
D. 1 : 1
正確答案： D
解析：
紅球每個人都會抽一個。
藍球設每個人抽S個：
n趨于正無窮。
$S=\frac{0}{2^1}+\frac{1}{2^2}+\frac{2}{2^3}+...+\frac{n?1}{2^n}$
$\frac{S}{2}=\frac{0}{2^2}+\frac{1}{2^3}+\frac{2}{2^4}+...+\frac{n?2}{2^n}+\frac{n?1}{2^{n+1}}$
相減得到：
$\frac{S}{2}=\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+...+\frac{1}{2^n}?\frac{n?1}{2^{n+1}}$
$S=1$
所以比例是1:1。

$?$為了統計一個非負整數的二進制形式中 1 的個數，代碼如下：

int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
___________;
}
return ret;
}
則空格內要填入的語句是（ ）。
A. x >>= 1
B. x &= x - 1
C. x |= x >> 1
D. x <<= 1
正確答案： B
解析：
每執行一次x = x&(x-1)，會將x用二進制表示時最右邊的一個1變為0

$?$NOIP 初賽中，選手可以帶入考場的有（ ）。
A. 筆
B. 橡皮
C. 手機（關機）
D. 草稿紙
正確答案： AB

$?$ 2-3 樹是一種特殊的樹，它滿足兩個條件：

每個內部結點有兩個或三個子結點；
所有的葉結點到根的路徑長度相同。
如果一棵2-3 樹有10 個葉結點，那么它可能有（ ）個非葉結點。
A. 5
B. 6
C. 7
D. 8
正確答案： CD
解析：
把10個葉結點分成幾堆，每堆有2或3個點，同一個堆的點有相同的父親
10=2+2+2+2+2=2+2+3+3
對應5+2+1=8或4+2+1=7個非葉結點

$?$下列關于圖靈獎的說法中，正確的有（ ）。
A. 圖靈獎是由電氣和電子工程師協會（IEEE）設立的。
B. 目前獲得該獎項的華人學者只有姚期智教授一人。
C. 其名稱取自計算機科學的先驅、英國科學家艾倫·麥席森·圖靈。
D. 它是計算機界最負盛名、最崇高的一個獎項，有“計算機界的諾貝爾獎”之稱。
正確答案： BCD

$?$方程 a*b = (a or b) * (a and b)，在 a, b 都取 [0, 31] 中的整數時，共有_____組解。（*表示乘法；or 表示按位或運算；and 表示按位與運算）
正確答案： 454
解析：
蒙一下：當 (a or b)=max(a,b) ，(a and b)=min(a,b) 時，等式成立，此時二進制下一個數是另一個數的子集
$ans=2\times ({\sum }_{i=0}^5{C}_5^i\times 2^{5?i})?2^5=454$
即枚舉小的數有多少個1，算出方案，再減去重復的即兩個數相同的情況。

$?$設變量x為float型且已賦值，則以下語句中能將x中的數值保留到小數點后兩位，并將第三位四舍五入的是（）
A. x= (x * 100+0. 5)/100. 0;
B. x=(int) (x * 100+0. 5)/100. 0;
C. x=(x/100+0. 5）* 100. 0;
D. x=x*100+0. 5/100. 0;
正確答案： B
解析：運算符優先級

$?$若某算法的計算時間表示為遞推關系式：
T(N) = 2T(N / 2) + N log N
T(1) = 1
則該算法的時間復雜度為（ ）。
A. $O(N)$
B. $O(N\log N)$
C. $O(N{\log }^{2}N)$
D. $O(N^2)$
正確答案： C
解析：$T(N)=2T(N/2)+NlogN$
$\frac{T(N)}{N}=\frac{T(N/2)}{N/2}+logN$
時間復雜度為$O(Nlo{g}^{2}N)$

總結

以上是生活随笔為你收集整理的csp初赛复习（往年真题+解析）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。