csp-s 2023
廣東2023csp-s第一輪晉級分?jǐn)?shù)線：46.5
1. 您的姓名：
2. 在Linux系統(tǒng)終端中，以下哪個命令用于創(chuàng)建一個新的目錄？（ ）
newdir
mkdir
create
mkfolder
3. 0，1，2，3，4中選取4個數(shù)字，能組成（ ）個不同四位數(shù)。（注：最小的四位數(shù)是1000， 最大的四位數(shù)是9999。）
96
18
120
84
4. 假設(shè)n是圖的頂點的個數(shù)，m是圖的邊的個數(shù)，為求解某一問題有下面四種不同時間復(fù)雜 度的算法。對于m=Θ(n)的稀疏圖而言，下面的四個選項，哪一項的漸近時間復(fù)雜度最小。
O(m (logn?loglogn)^0.5)
O(n^2 +m)
O(n^2 logm +mlogn)
O(m+nlogn)
5. 假設(shè)有n根柱子，需要按照以下規(guī)則依次放置編號為1、2、3、...的圓環(huán)：每根柱子的底 部固定，頂部可以放入圓環(huán)；每次從柱子頂部放入圓環(huán)時，需要保證任何兩個相鄰圓環(huán)的 ?港 編號之和是一個完全平方數(shù)。請計算當(dāng)有4根柱子時，最多可以放置（ ）個圓環(huán)。
7
9
11
5
6. 以下對數(shù)據(jù)結(jié)構(gòu)的表述不恰當(dāng)?shù)囊豁検牵海?）
隊列是一種先進先出（FIFO）的線性結(jié)構(gòu)
哈夫曼樹的構(gòu)造過程主要是為了實現(xiàn)圖的深度優(yōu)先搜索
散列表是一種通過散列函數(shù)將關(guān)鍵字映射到存儲位置的數(shù)據(jù)結(jié)構(gòu)
二叉樹是一種每個結(jié)點最多有兩個子結(jié)點的樹結(jié)構(gòu)
7. 以下連通無向圖中，（ ）一定可以用不超過兩種顏色進行染色
完全三叉樹
平面圖
邊雙連通圖
歐拉圖
8. 最長公共子序列長度常常用來衡量兩個序列的相似度。其定義如下：給定兩個序列X= {x1, x2,x3,?,xm}和 Y = {y1,y2,y3,?,yn}，最長公共子序列（LCS）問題的目標(biāo)是找到一個 最長的新序列Z={z1,z2,z3,?,zk}，使得序列Z既是序列X的子序列，又是序列Y的子序 ?港 列，且序列Z的長度k在滿足上述條件的序列里是最大的。（注：序列A是序列B的子序 列，當(dāng)且僅當(dāng)在保持序列B元素順序的情況下，從序列B中刪除若干個元素，可以使得剩余的元素構(gòu)成序列A。）則序列“ABCAAAABA”和“ABABCBABA”的最長公共子序列長度 為（ ）。
4
5
6
7
9. 一位玩家正在玩一個特殊的擲骰子的游戲，游戲要求連續(xù)擲兩次骰子，收益規(guī)則如下：玩 家第一次擲出x點，得到2x元；第二次擲出y點，當(dāng)y=x時玩家會失去之前得到的2x元， 而當(dāng)y≠x時玩家能保住第一次獲得的2x元。上述x,y∈{1,2,3,4,5,6}。例如：玩家第 一次擲出3點得到6元后，但第二次再次擲出3點，會失去之前得到的6元，玩家最終收益為0元；如果玩家第一次擲出3點、第二次擲出4點，則最終收益是6元。假設(shè)骰子擲 出任意一點的概率均為1/6，玩家連續(xù)擲兩次骰子后，所有可能情形下收益的平均值是多 少？（ ）
7元
35 / 6 元
16 / 3 元
19 / 3 元
10. 假設(shè)我們有以下的C++代碼：
int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c
請問，res的值是什么？（ ）
提示：在C++中，邏輯運算的優(yōu)先級從高到低依次為：邏輯非（!）、邏輯與（&&）、邏 輯或（||）。位運算的優(yōu)先級從高到低依次為：位非（~）、位與（&）、位異或（^）、位或 ?港 （|）。同時，雙目位運算的優(yōu)先級高于雙目邏輯運算；邏輯非和位非優(yōu)先級相同，且高于所 有雙目運算符。
true
false
1
0
11. 假設(shè)快速排序算法的輸入是一個長度為n的已排序數(shù)組，且該快速排序算法在分治過程總 是選擇第一個元素作為基準(zhǔn)元素。以下哪個選項描述的是在這種情況下的快速排序行為？ （ ）
快速排序?qū)τ诖祟愝斎氲谋憩F(xiàn)最好，因為數(shù)組已經(jīng)排序。
快速排序?qū)τ诖祟愝斎氲臅r間復(fù)雜度是O(nlogn)。
快速排序?qū)τ诖祟愝斎氲臅r間復(fù)雜度是O(n^2)。
快速排序無法對此類數(shù)組進行排序，因為數(shù)組已經(jīng)排序。
12. 以下哪個命令，能將一個名為“main.cpp”的C++源文件，編譯并生成一個名為“main” 的可執(zhí)行文件？（ ）
g++-o main main.cpp
g++-o main.cpp main
g++ main-o main.cpp
g++ main.cpp-o main.cpp
13. 在圖論中，樹的重心是樹上的一個結(jié)點，以該結(jié)點為根時，使得其所有的子樹中結(jié)點數(shù)最 多的子樹的結(jié)點數(shù)最少。一棵樹可能有多個重心。請問下面哪種樹一定只有一個重心？（ ）
4個結(jié)點的樹
6個結(jié)點的樹
7個結(jié)點的樹
8個結(jié)點的樹
14. 如圖是一張包含6個頂點的有向圖，但頂點間不存在拓?fù)湫?。如果要刪除其中一條邊，使 ?港 這6個頂點能進行拓?fù)渑判?，請問總共有多少條邊可以作為候選的被刪除邊？（ ）
1
2
3
4
15.
10
11
12
13
16.
O(n)
O(1)
O(logn)
O(nlogn)
17.
當(dāng)輸入非零時，輸出一定不為零。（）
對
錯
18. （2分）將f函數(shù)的輸入?yún)?shù)的類型改為unsignedint，程序的輸出不變。（）
對
錯
19. 當(dāng)輸入為“65535”時，輸出為“63”。（）
對
錯
20. 當(dāng)輸入為“1”時，輸出為“64”。（）
對
錯
21. 當(dāng)輸入為“512”時，輸出為（）
“33280”
“33410”
“33106”
“33346”
22. 當(dāng)輸入為“64”時，執(zhí)行完第5行后x的值為（）。
“8256”
“4130”
“4128”
“4160”
23.
將第15行刪去，輸出不變。（）
對
錯
24. 當(dāng)輸入為“10”時，輸出的第一行大于第二行。（）
對
錯
25. （2分）當(dāng)輸入為“1000”時，輸出的第一行與第二行相等。（）
對
錯
26. solve1(n)的時間復(fù)雜度為（）
n(logn)^2
n
nlogn
nloglogn
27. solve2(n)的時間復(fù)雜度為（）。
n^2
n
nlogn
n(n)^0.5
28. 輸入為“5”時，輸出的第二行為（）
20
21
22
23
29.
將第24行的“m”改為“m-1”，輸出有可能不變，而剩下情況為少1。（）
對
錯
30. 將第22行的“g +(h-g) /2”改為“(h+g)>>1”，輸出不變。（）
對
錯
31. 當(dāng)輸入為“57 2-4 51-3”，輸出為“5”。（）
對
錯
32. 設(shè)a數(shù)組中最大值減最小值加1為A，則f函數(shù)的時間復(fù)雜度為（）
nlogA
n^2logA
nlog(nA)
nlogn
33. 將第10行中的“>”替換為“>=”，那么原輸出與現(xiàn)輸出的大小關(guān)系為
一定小于
一定小于等于且不一定小于
一定大于等于且不一定大于
以上三種情況都不對
34. 當(dāng)輸入為“58 2-5 38-12”時，輸出為（）
13
14
8
15
35.
①處應(yīng)填（）
k ＞= f[u]
k ＜= f[u]
k ＞ f[u]
k ＜ f[u]
36. ②處應(yīng)填（）
deg[v] == 1
deg[v] == 0
deg[v] ＞ 1
deg[v] ＞ 0
37. ③處應(yīng)填（）
std::min(f[u] + f[v], LIM)
std::min(f[u] + f[v] + 1, LIM)
std::min(f[u] * f[v], LIM)
std::min(f[u]*(f[v]+1),LIM)
38. ④處應(yīng)填（）
u !=-1
!E[u].empty()
k ＞ 0
k ＞ 1
39. ⑤處應(yīng)填（）
k += f[u]
k-= f[u]
--k
++k
40.
①處應(yīng)填（）
pre[i] = std::max(pre[i-1], a[i-1])
pre[i + 1] = std::max(pre[i], pre[i + 1])
pre[i] = std::max(pre[i-1], a[i])
pre[i] = std::max(pre[i], pre[i-1])
41. ②處應(yīng)填（）
a[j] ＜ max
a[j] ＜ a[i]
pre[j-mid] ＜ max
pre[j-mid] ＞ max
42. ③處應(yīng)填（ ）
(long long)(j- mid) * max
(long long)(j- mid) * (i- l) * max
sum[j- mid]
sum[j- mid] * (i- l)
43. ④處應(yīng)填（ ）
(long long)(r- j) * max
(long long)(r- j) * (mid- i) * max
sum[r- mid]- sum[j- mid]
(sum[r- mid]- sum[j- mid]) * (mid- i)
44. ⑤處應(yīng)填（ ）
solve(0, n)
solve(0, n- 1)
solve(1, n)
solve(1, n- 1)
關(guān)閉
更多問卷
復(fù)制此問卷