PDF文檔公眾號回復關鍵字:20240629
2022 CSP-J 選擇題
單項選擇題（共15題，每題2分，共計30分：每題有且僅有一個正確選項）
5.對于入棧順序為a,b,c,d,e的序列，下列( )不合法的出棧序列
A. a，b，c，d，e
B. e，d，c，b，a
C. b，a，c，d，e
D. c，d，a，e，b
8.如果一顆二叉樹只有根節點，那么這棵二叉樹高度為1。請問高度為5的完全二叉樹有( )種不同的形態
A. 16
B. 15
C. 17
D. 32
9.表達式a* (b+c)* d的后綴表達式為( ),其中 *和 +是運算符
A. * * a + b c d
B. a b c + * d *
C. a b c + d * *
D. * a * + b c d
11.在數據壓縮編碼中的哈夫曼編碼方法，在本質上是一種( ) 策略
A. 枚舉
B. 貪心
C. 遞歸
D. 動態規劃
15.有四個人要從A點坐一條船過河到B點，船一開始在A點。該船一次最多可坐兩個人。已知這四個人中每個人獨自坐船的過河時間分別為1、2、4、8，且兩個人坐船的過河時間為兩人獨自過河時間的較大者。則最短( )時間可以讓四個人都過河到B點(包括從B點把船開回A點的時間)
A. 14
B. 15
C. 16
D. 17
2 相關知識點
棧
棧又名堆棧，是一種限定僅在表尾進行插入和刪除操作的線性表，這一端稱為棧頂，另一端稱為棧底
棧中的數據元素遵守后進先出的原則
二叉樹
每個結點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒，例如下面是一棵二叉樹
滿二叉樹
滿二叉樹又叫完美二叉樹，除了葉子結點之外的每一個結點都有兩個孩子，樹的葉子節點均在最后一層（也就是形成了一個完美的三角形）
完全二叉樹
除了最下層，其他每層都飽滿，去除最后一層是一棵滿二叉樹，最下層的結點都集中在該層最左邊的若干位置上
前綴表達式
前綴表達式，也稱為波蘭表達式,是一種算術表達式表示方法，其中運算符位于操作數之前.
//示例1 中綴表達式a+b對應的前綴表達式
+a bC++
//示例2 中綴表達式3+4*2對應的前綴表達式
+ 3 * 4 2
中綴表達式
是一種常見的算術表達式表示方法，其中運算符位于操作數之間
//示例1
3 + 4 * 2
//示例2
(1 + 2) * (3 - 4)C++
后綴表達式
后綴表達式，也稱為逆波蘭表達式，是一種算術表達式表示方法，其中運算符位于操作數之后
//示例1 中綴表達式a+b對應的后綴表達式C++
a b+
//示例2 中綴表達式3+4*2對應的前綴表達式3 4 2 * +
中綴表達式轉后綴表達式
確定優先級，按優先級逐一處理操作符(把操作符從操作數中間移到操作數后邊)
例如如下中綴表達式轉為后綴表達式
1 + ( 2 + 3)* 4 ) – 5
// 按優先級對表達式數字加括號
((1 + (( 2 + 3)* 4 )) – 5 )
//從最里面的一層括號開始運算，轉換成后綴表達式
//轉換方法，去除括號，數字在前，順序不變，操作符移到最后
1. ( 2 + 3) => 2 3 +
// ( 2 + 3)可以看作一個整體x
2. (( 2 + 3)* 4 ) => (x+4) => x 4 + => 2 3 + 4 *
//(( 2 + 3)* 4 )看作一個整體x
3. (1 + (( 2 + 3)* 4 ))=> (1+x)=>1 x + = 1 2 3 + 4 * +
// (1 + (( 2 + 3)* 4 )) 看作一個整體x
4. ((1 + (( 2 + 3)* 4 )) – 5 ) =>(x-5)=>x 5 - => 1 2 3 + 4 * + 5 -
所以轉換后的后綴表達式為 1 2 3 + 4 * + 5 -
哈夫曼樹
1 選剩下的兩棵根權值最小的樹合并成一棵新樹
2 新樹的根權值等于兩棵合并前樹的根權值和
3 重復1和2
哈夫曼編碼
哈夫曼樹的左右孩子進行編碼稱為哈夫曼編碼，通常左邊為0，右邊為1
只對葉子節點進行編碼/解碼，編碼唯一
哈夫曼編碼是前綴編碼，任何一個字符的編碼都不是另一個字符編碼的前綴(只有葉子節點編碼)
哈夫曼編碼左邊為0，右邊為1是通常規定，也可以左邊為1右邊為0，但確定后編碼是唯一的
如果下圖為字母a,b,c,d,e的編碼，字母旁邊對應數字為其出現的頻率
貪心算法
所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇 。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的 局部最優解
哈夫曼編碼總是把出現頻率少的編碼相對較長，從而保證全局總的編碼最短
哈夫曼編碼使用的是貪心算法進行編碼
3 思路分析
5.對于入棧順序為a,b,c,d,e的序列，下列( D )不合法的出棧序列
A. a，b，c，d，e
B. e，d，c，b，a
C. b，a，c，d，e
D. c，d，a，e，b
分析
根據入棧出棧性質模擬，棧為后進先出
A a 進 a 出 b 進 b 出 c 進 c 出 d 進 d 出 e 進 e 出 出棧順序合法
B a 進 b 進 c 進 d 進 e 進 e 出 d 出 c 出 b 出 a 出 出棧順序合法
C a 進 b 進 b 出 a 出 c 進 c 出 d 進 d 出 e 進 e 出 出棧順序合法
D a 進 b 進 c 進 c 出 d 進 d 出 此時b在棧頂，a無法出棧
所以選 D
8.如果一顆二叉樹只有根節點，那么這棵二叉樹高度為1。請問高度為5的完全二叉樹有( A )種不同的形態
A. 16
B. 15
C. 17
D. 32
分析
完全二叉樹，除最后一層，其他層都是滿的
高度為5有4層是滿的，后面1層節點是前面節點的2倍(1個父節點都有2個子節點)
前4層是滿的，形態不會變化，只有第5層形態可能變化，第5層節點只要保證從左到右排即可
具體如下
滿二叉樹
高度為1 1個節點 2^1-1=1
高度為2 1+2 個節點 2^2-1=3
高度為3 1+2+4個節點 2^3-1=7
高度為4 1+2+4+8 個節點2^4-1=15
高度為5 1+2+4+8+16 個節點 2^5-1=31
由于是完全二叉樹，說明第5層必有節點,第5層的節點最多可以31-15=16個
當第5層節點為16個時，此時是5層的滿二叉樹，是特殊的完全二叉樹
因此有16種不同的形態
9.表達式a* (b+c)* d的后綴表達式為( B ),其中 *和 +是運算符
A. * * a + b c d
B. a b c + * d *
C. a b c + d * *
D. * a * + b c d
分析
確定優先級，按優先級逐一處理操作符(把操作符從操作數中間移到操作數后邊)
a * (b+c)* d -- ((a * (b+c))* d)((a * (b+c))* d)
1 (b+c) => b c+
// (b+c) 可以看作一個整體x
(a * (b+c)) => (a * x) => a x * => a b c + *
//(a * (b+c)) 可以看作一個整體x((a * (b+c))* d) => (x * d) => x d * => a b c + * d *
11.在數據壓縮編碼中的哈夫曼編碼方法，在本質上是一種( B ) 策略
A. 枚舉
B. 貪心
C. 遞歸
D. 動態規劃
分析
哈夫曼編碼總是把出現頻率少的編碼相對較長，從而保證全局總的編碼最短
哈夫曼編碼使用的是貪心算法進行編碼
15.有四個人要從A點坐一條船過河到B點，船一開始在A點。該船一次最多可坐兩個人。已知這四個人中每個人獨自坐船的過河時間分別為1、2、4、8，且兩個人坐船的過河時間為兩人獨自過河時間的較大者。則最短( B )時間可以讓四個人都過河到B點(包括從B點把船開回A點的時間)
A. 14
B. 15
C. 16
D. 17
分析
貪心算法解決此問題，貪心策略
1從剩余的人中選擇用時最小的2人過河
2 用時最小的人返回去接剩余的人
1 初始 1 2 4 8 在河的A邊
2從剩余的 1 2 4 8 找用時最少的2人(1 和 2)過河到B ,用時為2
3 在B端選擇用時間最少的去接，1去接，用時1
4 從剩余的 4 8 找用時最少的2人(4 和 8)過河到B ,用時為8
5 在B端選擇用時間最少的去接，2去接，用時2
6 從剩余的 1 2 過河 用時為2
上述過河時間累加 2+1+8+2+2=15
——RemoteAttestation)
