一、選擇題
第 1 題
題目:C++ 中,bool 類型的變量占用字節數為( )。
A. 1
B. 2
C. 3
D. 4
答案:A
解析:
C++ 標準規定,bool
類型至少占用 1 字節(1 byte),用于存儲true
(非 0)或false
(0)。盡管邏輯上只需 1 位,但內存分配以字節為最小單位,因此選 A。
考點:C++ 基礎數據類型的內存占用。
重點:掌握bool
、char
、int
、double
等類型的字節數(如char
占 1 字節,int
通常占 4 字節)。
教學方案:通過對比表格講解數據類型,強調bool
的特殊性(1 字節而非 1 位),結合內存對齊原則理解。
第 2 題
題目:以下關于 C++ 結構體的說法,正確的是( )。
A. 結構體中只能包含成員變量,不能包含成員函數
B. 結構體不能從另一個結構體繼承
C. 結構體里面可以包含靜態成員變量
D. 結構體里面不能包含構造函數
答案:C
解析:
- A 錯誤:結構體可包含成員函數(與類的區別僅在于默認訪問權限為
public
)。 - B 錯誤:結構體支持繼承(語法與類相同,默認
public
繼承)。 - C 正確:結構體允許靜態成員變量(屬于類型本身,而非實例)。
- D 錯誤:結構體可定義構造函數,用于初始化成員。
考點:結構體與類的特性對比。
重點:理解結構體的成員類型(變量、函數、靜態成員、構造函數),區分結構體與類的默認訪問權限。
教學方案:編寫包含成員函數和構造函數的結構體示例,演示繼承語法,對比類與結構體的異同。
第 3 題
題目:設只含根結點的二叉樹高度為 1,共有 62 個結點的完全二叉樹的高度為( )。
A. 4
B. 5
C. 6
D. 7
答案:C
解析:
完全二叉樹高度h
滿足:
- 前
h-1
層是滿二叉樹,結點數為2^(h-1)-1
; - 第
h
層至少 1 個結點,最多2^(h-1)
個結點。
計算: - 當
h=5
時,前 4 層結點數為2^4-1=15
,總結點數最多15+8=23
(<62,不滿足); - 當
h=6
時,前 5 層結點數為2^5-1=31
,總結點數最多31+32=63
(≥62,滿足)。
故高度為 6,選 C。
考點:完全二叉樹的結點數與高度關系。
重點:掌握公式2^(h-1) ≤ 結點數 ≤ 2^h - 1
,通過不等式求解高度。
教學方案:畫圖演示滿二叉樹與完全二叉樹的結構,推導高度計算公式,通過例題強化計算。
第 4 題
題目:以下關于數組的說法,不正確的是( )。
A. 數組中所有元素的類型必須都相同
B. 數組中各元素在內存中是順序存放的
C. 數組最后一個元素的索引是數組的長度
D. 數組名的第一個字符可以是下劃線
答案:C
解析:
- A 正確:數組元素類型必須統一(如
int arr[5]
所有元素均為int
)。 - B 正確:數組在內存中連續存儲,元素地址遞增。
- C 錯誤:索引從 0 開始,最后一個元素索引為
長度-1
(如長度 5 的數組索引 0~4)。 - D 正確:數組名是標識符,允許以下劃線開頭(如
_arr
)。
考點:數組的基本特性。
重點:強調索引越界風險,區分數組長度與最大索引(長度 - 1)。
教學方案:通過代碼示例演示數組定義、訪問,故意寫出越界代碼(如arr[5]
對長度 5 的數組),觀察錯誤現象。
第 5 題
題目:執行以下代碼,輸出結果是( )。
cpp
#include <iostream>
using namespace std;
int f(int k) { if (k == 1) return 3; return 2 * f(k - 1) + 1;
}
int main() { int n = 6; cout << f(n); return 0;
}
A. 127
B. 97
C. 63
D. 126
答案:A
解析:
遞歸函數遞推關系:
- 基例:
f(1)=3
- 遞推:
f(k)=2*f(k-1)+1
展開計算: f(2)=2×3+1=7
f(3)=2×7+1=15
f(4)=2×15+1=31
f(5)=2×31+1=63
f(6)=2×63+1=127
考點:遞歸函數的遞推計算。
重點:理解遞歸終止條件與遞推公式,可轉化為等比數列(通項公式:f(k)=2^(k+1)-1
)。
教學方案:用遞歸展開法逐步計算,引入數學歸納法推導通項公式,避免深層遞歸導致棧溢出。
二、編程題
第 6 題:特殊運算符
題目描述:
定義運算符 “>>>N” 為提取 N 的前兩位數字(如 257→25,182→18),計算 N - (>>>N)。
輸入:三位數 N(100<N<1000)。
輸出:N 減去前兩位的結果。
樣例輸入:257 → 輸出 232(257-25=232)。
答案代碼:
cpp
#include <iostream>
using namespace std;
int main() { int n; cin >> n; int first_two = n / 10; // 提取前兩位(如257/10=25) cout << n - first_two << endl; return 0;
}
解析:
三位數的前兩位可通過整數除法n//10
得到(如 933//10=93),直接計算差值即可。
考點:數字處理(整數除法提取高位)。
重點:掌握//
和%
的用法,明確三位數的結構(百位 ×100 + 十位 ×10 + 個位)。
教學方案:通過分解數字的各位(百位、十位、個位)演示n//100
、n//10%10
、n%10
,強調整數除法的應用。
第 7 題:四葉玫瑰數
題目描述:
找出四位數中各位數字的四次方之和等于自身的數(如 1634=1?+6?+3?+4?),輸出 N~M 范圍內的數。
輸入:N 和 M(1≤N≤M≤1e6)。
輸出:按從小到大順序的四葉玫瑰數。
樣例輸入:1234 2345 → 輸出 1634。
答案思路:
- 僅枚舉四位數(1000≤num≤9999),減少計算量;
- 分解各位數字:千位
a=num/1000
,百位b=num/100%10
,十位c=num/10%10
,個位d=num%10
; - 計算四次方和,若等于原數則輸出。
代碼框架:
cpp
#include <iostream>
using namespace std;
bool is_rose(int num) { int a = num / 1000, b = num / 100 % 10, c = num / 10 % 10, d = num % 10; return a*a*a*a + b*b*b*b + c*c*c*c + d*d*d*d == num;
}
int main() { int n, m; cin >> n >> m; for (int i = max(n, 1000); i <= min(m, 9999); i++) { if (is_rose(i)) cout << i << " "; } return 0;
}
考點:枚舉算法與數字分解。
重點:限定枚舉范圍(僅四位數),優化循環條件,避免無效計算(如處理 N<1000 或 M>9999 的情況)。
教學方案:講解 “四葉玫瑰數” 的數學定義,演示數字分解方法,強調提前過濾非四位數以提高效率。
第 8 題:質因數的個數
題目描述:
統計 N~M 之間每個數的質因數個數(重復質因數算多個,如 8=2×2×2,個數為 3),求最大值。
輸入:N 和 M(1≤N≤M≤1e7)。
輸出:最大質因數個數。
樣例輸入:6 10 → 輸出 3(8 的質因數個數為 3)。
答案思路:
- 對每個數
num
進行質因數分解:從 2 到√num 試除,統計每個質因數的次數; - 若試除后
num>1
,說明剩余部分是質數,次數加 1; - 遍歷 N~M,記錄最大次數。
代碼核心:
cpp
int count_prime_factors(int num) { int count = 0; for (int i = 2; i * i <= num; i++) { while (num % i == 0) { // 統計i的次數 count++; num /= i; } } if (num > 1) count++; // 處理剩余質數(如7、13等) return count;
}
考點:質因數分解與貪心統計。
重點:試除法分解質因數,區分質因數的 “種類” 與 “個數”(本題統計個數,包括重復)。
教學方案:通過示例(如 12=22×31,個數 2+1=3)講解質因數個數的定義,演示試除過程,強調從小到大試除以確保質因數。
第 9 題:最大的矩形紙片
題目描述:
在直方圖中找最大矩形面積(高度數組 [3,2,1,4,5,2] 的最大面積為 8)。
輸入:N(列數)和高度數組。
輸出:最大矩形面積。
答案思路:
使用單調棧算法:
- 維護一個單調遞增棧,存儲索引,對應高度遞增;
- 遍歷每個高度,找到左右兩邊第一個比它小的位置,計算寬度
right - left - 1
,面積 = 高度 × 寬度; - 處理邊界條件(數組末尾加 0,確保棧中元素全部彈出)。
代碼框架:
cpp
#include <iostream>
#include <stack>
using namespace std;
long long max_area(int n, int* heights) { stack<int> st; long long res = 0; for (int i = 0; i <= n; i++) { // 末尾加0,處理所有元素 while (!st.empty() && (i == n || heights[st.top()] >= heights[i])) { int h = heights[st.top()]; st.pop(); int w = st.empty() ? i : i - st.top() - 1; res = max(res, (long long)h * w); } st.push(i); } return res;
}
考點:直方圖最大矩形面積(單調棧算法)。
重點:理解單調棧的作用(快速找到左右邊界),處理數據類型溢出(使用long long
)。
教學方案:通過直方圖畫圖演示單調棧的工作流程,解釋每個步驟的意義,對比暴力法與單調棧的時間復雜度(O (n) vs O (n2))。
第 10 題:數字游戲
題目描述:
交替調整最小數到第二小、最大數到第二大,直到不同數少于 3 個,輸出調整次數、最終最小和最大值。
輸入:數組。
輸出:次數、最終最小值、最大值。
樣例輸入:1 3 4 2 → 調整 2 次,結果 2 2 3。
答案思路:
- 每次操作后排序數組,統計不同數的數量;
- 第奇數次操作:將所有最小數改為第二小數;
- 第偶數次操作:將所有最大數改為第二大數;
- 直到不同數≤2 時終止。
代碼核心:
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() { int n; vector<int> nums; cin >> n >> nums; int count = 0; bool is_min_turn = true; // 第一次調整最小數 while (true) { sort(nums.begin(), nums.end()); // 統計不同數 int unique = 1; for (int i = 1; i < n; i++) { if (nums[i] != nums[i-1]) unique++; } if (unique < 3) break; if (is_min_turn) { int second_min = nums[1]; for (int i = 0; i < n; i++) { if (nums[i] == nums[0]) nums[i] = second_min; } } else { int second_max = nums[n-2]; for (int i = 0; i < n; i++) { if (nums[i] == nums[n-1]) nums[i] = second_max; } } count++; is_min_turn = !is_min_turn; } sort(nums.begin(), nums.end()); cout << count << " " << nums[0] << " " << nums.back() << endl; return 0;
}
考點:模擬算法與排序。
重點:每次操作后排序,正確識別第二小 / 第二大數,處理邊界情況(如所有數相同)。
教學方案:通過示例演示調整過程,強調排序的重要性,講解如何統計不同數的數量(遍歷或使用集合)。
第 11 題:活動人數
題目描述:
樹狀結構中,選某部門則不能選直接下級,求最大人數(樹形動態規劃)。
輸入:部門數 N,每個部門的上級 F、編號 S、人數 C。
輸出:最大人數。
樣例輸入:6 個部門,輸出 11(選部門 1、4、5、6,人數 2+3+2+4=11)。
答案思路:
每個節點有兩種狀態:
dp[u][1]
:選節點 u 時,最大人數(等于 u 的人數 + 所有子節點不選的最大值);dp[u][0]
:不選節點 u 時,最大人數(等于所有子節點選或不選的最大值之和)。
通過深度優先搜索(DFS)遞歸計算每個節點的狀態。
代碼框架:
cpp
#include <iostream>
#include <vector>
using namespace std;
struct Node { int c; vector<int> children;
};
Node nodes[100001];
int dp[100001][2]; // dp[u][1]選,dp[u][0]不選 void dfs(int u) { dp[u][1] = nodes[u].c; // 選當前節點,初始化為自身人數 for (int v : nodes[u].children) { dfs(v); dp[u][1] += dp[v][0]; // 子節點不能選 dp[u][0] += max(dp[v][0], dp[v][1]); // 子節點可選或不選 }
} int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int f, s, c; cin >> f >> s >> c; nodes[s].c = c; if (f != 0) nodes[f].children.push_back(s); // 構建樹結構 } // 找根節點(上級為0的節點) int root = 0; for (int i = 1; i <= n; i++) { if (nodes[i].children.size() > 0 && (root == 0 || ...)) { // 實際應遍歷找到f=0的s // 正確方法:記錄每個節點的父節點,找父節點為0的節點 } // 簡化:假設根節點是1(需根據輸入正確查找) root = 1; // 實際需遍歷所有節點,找到f=0對應的s } dfs(root); cout << max(dp[root][0], dp[root][1]) << endl; return 0;
}
考點:樹形動態規劃(樹上的選與不選問題)。
重點:樹的存儲(鄰接表),狀態轉移方程的推導,根節點的確定(上級為 0 的節點)。
教學方案:講解樹的基本概念,演示狀態轉移方程的推導過程,通過樣例分析選與不選的決策對結果的影響,強調遞歸 DFS 的實現。
詳細教學方案
一、選擇題模塊
-
數據類型與內存:
- 對比
bool
、char
、int
等類型的字節數,通過代碼sizeof(bool)
驗證。 - 講解內存對齊原則,解釋為何
bool
占 1 字節而非 1 位。
- 對比
-
結構體與類:
- 編寫包含成員函數、構造函數、靜態成員的結構體示例,演示繼承語法(
struct B : public A
)。 - 對比結構體與類的默認訪問權限(
public
?vs?private
)。
- 編寫包含成員函數、構造函數、靜態成員的結構體示例,演示繼承語法(
-
二叉樹性質:
- 畫圖演示滿二叉樹與完全二叉樹,推導高度計算公式
h = floor(log2(n)) + 1
。 - 通過練習題(如結點數 30、63 的高度)強化計算。
- 畫圖演示滿二叉樹與完全二叉樹,推導高度計算公式
-
數組基礎:
- 演示數組定義、初始化、越界訪問,用調試工具觀察內存布局。
- 強調索引從 0 開始,通過錯誤案例(如訪問
arr[len]
)加深印象。
-
遞歸函數:
- 用遞歸展開法計算第 5 題,引入數學歸納法推導通項公式
f(k)=2^(k+1)-1
。 - 講解遞歸與迭代的轉換,避免棧溢出(如限制遞歸深度)。
- 用遞歸展開法計算第 5 題,引入數學歸納法推導通項公式
二、編程題模塊
-
數字處理(第 6 題):
- 講解整數除法
//
和取余%
的用法,分解三位數的百位、十位、個位。 - 設計變式題:提取前兩位(三位數)、前三位(四位數),計算差值。
- 講解整數除法
-
枚舉算法(第 7 題):
- 限定枚舉范圍(四位數),避免無效循環(如 N=500 時從 1000 開始枚舉)。
- 優化數字分解:用數學公式快速獲取各位數字,減少計算量。
-
質因數分解(第 8 題):
- 演示試除法分解質因數,強調從小到大試除確保質因數(如先除 2,再除 3,直到√num)。
- 區分質因數的 “個數” 與 “種類”(本題統計個數,包含重復)。
-
單調棧算法(第 9 題):
- 通過直方圖動畫演示單調棧的工作流程,解釋每個元素的左右邊界如何確定。
- 對比暴力法(O (n2))與單調棧(O (n))的效率,強調算法優化的重要性。
-
模擬與排序(第 10 題):
- 通過示例表格記錄每次調整后的數組狀態,演示排序的作用(快速找到最小 / 最大值)。
- 處理邊界情況:如所有數相同(直接輸出 0 次),或只有兩種不同數(無需調整)。
-
樹形動態規劃(第 11 題):
- 講解樹的存儲方式(鄰接表),如何構建樹結構(根據輸入的上下級關系)。
- 推導狀態轉移方程:選當前節點則子節點不能選,不選則子節點可選或不選,取最大值。
- 通過樣例分析遞歸過程,強調根節點的正確查找(上級為 0 的節點)。
三、實戰訓練
- 選擇題:設計 10 道同類題目,涵蓋數據類型、結構體、二叉樹、數組、遞歸等考點,限時 5 分鐘完成。
- 編程題:
- 第 6 題變式:處理四位數,提取前三位,計算差值。
- 第 8 題優化:預處理質數表,加速質因數分解(適用于大數據范圍)。
- 第 11 題擴展:處理森林(多棵樹),求所有樹的最大人數之和。
- 調試技巧:
- 學會使用斷點調試,觀察遞歸過程或循環變量變化。
- 針對超時問題,分析算法時間復雜度,優化循環條件或選擇更高效的算法(如單調棧替代雙重循環)。
通過以上教學方案,學生可系統掌握 C++ 基礎、算法思維和編程技巧,提升解決競賽題目的能力。