《信息學奧賽一本通關》是2023年清華大學出版社出版的圖書，作者是蔡榮嘯。
基本介紹
- 中文名：信息學奧賽一本通關
- 作者：蔡榮嘯
- 出版時間：2023年1月1日
- 出版社：清華大學出版社
- ISBN：9787302607281
- 定價：128 元
內容簡介,圖書目錄,
內容簡介
《信息學奧賽一本通關》共30 章分7 部分。其中前6 部分內容分別為編程平台介紹、計算機基礎知識、從圖形化編程到C++ 入門、數學知識基礎、數據結構和算法補充與歸納。第七部分給出2019—2022年CSP-J/S 真題及參考答案。本書基於圖形化編程學習，詳細介紹由圖形化編程向C++ 代碼編程過渡的系統知識，最終幫助讀者提高參與信息學奧賽的水平。
圖書目錄
第一部分
編程平台介紹
第1 章 圖形化編程模組簡介 2
1.1 變數 2
1.2 運算符 4
1.3 順序語句 6
1.4 分支語句 6
1.5 循環語句 8
1.6 函式運算 9
第2 章 Dev-C++ 簡介 10
2.1 Dev-C++ 界面 10
2.2 快捷鍵 11
2.3 調試配置 11
2.4 設定斷點並查看 12
2.5 編譯器與編譯日誌 13
第二部分
計算機基礎知識
第3 章 信息學奧賽簡介 16
3.1 NOIP 16
3.2 CSP-J/S 16
3.3 NOI 17
3.4 APIO 和IOI 17
第4 章 計算機硬體基礎 18
4.1 計算機發展史 18
4.2 計算機硬體 19
4.2.1 運算器 20
4.2.2 控制器 20
4.2.3 存儲器 21
4.2.4 輸入設備 21
4.2.5 輸出設備 22
4.3 數制與編碼 22
4.3.1 二進制與十進制 24
4.3.2 二進制與八進制 25
4.3.3 二進制與十六進制 26
4.3.4 ASCII 編碼 27
4.3.5 漢字編碼 27
4.3.6 原碼、反碼、補碼 27
4.3.7 位運算 28
4.3.8 多媒體檔案的數位化 30
第5 章 作業系統與套用軟體 32
5.1 DOS 作業系統 32
5.2 Windows 作業系統及軟體 34
5.3 Linux 作業系統 34
第6 章 計算機網路基礎 35
6.1 計算機網路組成 35
6.2 計算機網路類型 37
6.3 IP 地址 38
6.4 網路安全 39
第三部分
從圖形化編程到C++ 入門
第7 章 C++ 基礎 42
7.1 數據類型 42
7.2 語法 46
7.2.1 程式入口 46
7.2.2 注釋 47
7.2.3 變數定義及使用 47
7.2.4 語句結束符 48
7.2.5 語句塊與縮進 48
7.2.6 作用域 48
7.2.7 常量與轉義字元 49
7.3 運算符 51
7.3.1 算術運算符 51
7.3.2 關係運算符 53
7.3.3 邏輯運算符 53
7.3.4 賦值運算符 53
7.3.5 三目運算符 54
7.4 輸入、輸出 54
7.4.1 輸入、輸出流 55
7.4.2 格式化輸入、輸出 55
7.4.3 檔案輸入、輸出 57
第8 章 程式三大基本結構 60
8.1 順序結構 60
8.2 分支結構 64
8.2.1 if-else 結構 65
8.2.2 switch-case 結構 69
8.3 循環結構 72
8.3.1 for 循環 73
8.3.2 while 循環 76
8.3.3 do-while 循環 79
第9 章 數組 81
9.1 一維數組 81
9.2 二維數組 88
第10 章 自定義函式與指針 95
10.1 自定義函式 95
10.2 內聯函式 96
10.3 指針 96
10.4 函式的參數傳遞 97
10.4.1 按值傳遞 97
10.4.2 地址傳遞 99
10.4.3 指針傳遞 100
10.5 遞歸 101
10.6 數組傳遞參數 105
10.6.1 一維數組傳遞參數 105
10.6.2 二維數組傳遞參數 107
第11 章 結構體 110
11.1 結構體的定義與初始化 110
11.2 結構體的調用 111
11.3 運算符重載 113
第四部分
數學知識基礎
第12 章 數論 118
12.1 整除理論（CSP-J） 118
12.1.1 定義及性質 118
12.1.2 奇數與偶數 119
12.2 同餘理論（CSP-S） 120
12.3 素數（CSP-J/S） 122
12.4 最大公約數（CSP-S） 128
12.4.1 輾轉相除法 128
12.4.2 二進制算法 130
12.5 最低公倍數（CSP-S） 131
12.6 擴展歐幾里得法（CSP-S） 133
12.7 快速冪算法（CSP-J/S） 135
12.8 逆元（CSP-S） 136
12.8.1 擴展歐幾里得法求逆元 137
12.8.2 費馬小定理求逆元 138
12.8.3 線性算法/ 遞歸求逆元 140
12.9 中國剩餘定理（CSP-S） 142
12.10 斐波那契數列（CSP-S） 144
12.11 卡特蘭數（CSP-S） 147
第13 章 組合數學 151
13.1 排列（CSP-J/S） 151
13.1.1 選排列 151
13.1.2 全排列 154
13.1.3 錯位排列 154
13.1.4 循環排列 157
13.2 組合（CSP-J/S） 157
13.2.1 重複組合 158
13.2.2 不相鄰組合 159
13.3 計數原理（CSP-J） 161
13.3.1 加法原理（分類加法計數原理） 161
13.3.2 乘法原理（分步乘法計數原理） 162
13.4 抽屜原理/ 鴿巢原理（CSP-J） 163
13.5 容斥原理（CSP-J） 165
13.6 母函式（CSP-S） 166
13.6.1 普通型母函式 167
13.6.2 指數型母函式 172
第14 章 機率論（CSP-S） 176
14.1 基礎知識 176
14.1.1 樣本空間與隨機事件 176
14.1.2 事件的機率 179
14.2 隨機變數 180
14.3 期望 182
第15 章 計算幾何（CSP-S） 185
15.1 基礎知識 185
15.1.1 平面直角坐標系 185
15.1.2 點、直線、線段 186
15.1.3 圓與多邊形 186
15.1.4 矢量 188
15.2 計算幾何C++ 模型 190
15.2.1 計算點、點關係 190
15.2.2 計算點、線關係 193
15.2.3 計算線、線（矢量）關係 198
15.2.4 圓與多邊形 202
15.3 平面凸包 211
15.3.1 判斷凸多邊形 211
15.3.2 凸多邊形重心 213
15.3.3 尋找凸包—Graham算法 216
15.4 旋轉卡殼 220
15.4.1 基礎概念 220
15.4.2 凸多邊形直徑 221
15.4.3 凸多邊形寬度 226
15.4.4 凸多邊形間最大距離 227
15.4.5 凸多邊形間最小距離 232
15.4.6 凸多邊形外接矩形最小面積 238
15.4.7 凸多邊形外接矩形最小周長 244
第16 章 線性代數（CSP-J/S） 245
16.1 行列式 245
16.2 矩陣 246
16.2.1 矩陣的加法 248
16.2.2 數與矩陣的乘法 248
16.2.3 矩陣與矩陣的乘法 249
16.2.4 逆矩陣 249
16.2.5 分塊矩陣 250
16.3 矩陣的初等變換 252
16.4 求解線性方程組 253
16.4.1 高斯消元法 253
16.4.2 LU 分解法 259
第17 章 函式（CSP-J/S） 267
17.1 定義 267
17.2 基本性質 267
17.2.1 有界性 267
17.2.2 單調性 267
17.2.3 奇偶性 268
17.2.4 周期性 268
17.3 初等函式 268
第五部分
數據結構
第18 章 時間、空間複雜度 274
18.1 時間複雜度 274
18.1.1 常數階O(1) 274
18.1.2 線性階O(n) 275
18.1.3 對數階O(log2n) 275
18.1.4 線性對數階O(n log2n) 276
18.1.5 冪指數階O(na) 276
18.1.6 時間複雜度曲線對比 276
18.2 空間複雜度 277
第19 章 STL 簡介 278
19.1 疊代器 278
19.2 容器 279
19.2.1 序列容器 279
19.2.2 關聯容器 287
19.3 容器適配器 292
19.3.1 queue 適配器 292
19.3.2 stack 適配器 294
19.3.3 priority_queue適配器 295
19.4 算法 297
19.4.1 非可變序列算法 298
19.4.2 可變序列算法 300
19.4.3 排序及相關算法 303
19.4.4 數值算法 307
第20 章 線性數據結構 310
20.1 順序存儲線性表 310
20.2 鍊表 312
20.2.1 單鍊表 312
20.2.2 靜態鍊表 318
20.2.3 循環鍊表 318
20.2.4 雙鍊表 319
20.3 佇列 322
20.4 棧 329
第21 章 樹 333
21.1 樹的一般概念 333
21.1.1 結點關係 333
21.1.2 度與深度 334
21.1.3 樹的遍歷 335
21.2 二叉樹 339
21.2.1 二叉樹性質 340
21.2.2 二叉樹結構與操作 340
21.2.3 遍歷二叉樹 345
21.2.4 二叉排序樹 350
21.2.5 平衡二叉樹 357
21.3 樹狀數組 363
21.3.1 前綴和 363
21.3.2 樹狀數組思想 364
21.3.3 lowbit 算法 365
21.3.4 單點更新 366
21.3.5 區間求和 366
21.4 線段樹 369
21.4.1 線段樹基本結構 369
21.4.2 建立線段樹 371
21.4.3 單點更新 372
21.4.4 區間查詢與修改 373
21.5 並查集 382
21.5.1 基本操作 382
21.5.2 算法最佳化 383
21.6 哈夫曼樹 387
21.6.1 構建哈夫曼樹 387
21.6.2 哈夫曼樹的實現 388
21.6.3 哈夫曼編碼 391
第22 章 圖論 392
22.1 圖的重要概念 392
22.2 歐拉路與歐拉迴路 393
22.3 連通圖 401
22.3.1 廣度優先算法 402
22.3.2 強連通圖 406
22.3.3 割點與橋 411
22.4 哈密爾頓圖 415
22.5 最短路徑 420
22.5.1 Floyed 算法 422
22.5.2 Dijkstra 算法 426
22.5.3 Bellman-Ford 算法 431
22.5.4 SPFA 算法 433
22.6 最小生成樹 437
22.6.1 Prim 算法 437
22.6.2 Kruskal 算法 445
22.7 關鍵路徑 449
22.7.1 相關概念 450
22.7.2 拓撲排序 451
22.7.3 關鍵路徑的套用 455
第六部分
算法補充與歸納
第23 章 數學公式補充 464
23.1 蔡勒公式 464
23.2 歸一問題 465
23.3 等差數列 465
23.4 等比數列 467
第24 章 高精度四則運算 468
24.1 數字存儲 468
24.2 高精度加法計算 469
24.3 高精度減法計算 472
24.4 高精度乘法計算 476
24.5 高精度除法計算 478
第25 章 字元串算法 484
25.1 哈希算法 484
25.2 KMP 算法 488
25.3 Trie 樹 494
25.4 Manacher 算法 498
25.5 AC 自動機 502
第26 章 排序算法 508
26.1 冒泡排序算法 508
26.2 插入排序算法 510
26.3 選擇排序算法 512
26.4 快速排序算法 513
26.5 歸併排序算法 516
26.6 桶排序算法 519
26.7 堆排序算法 521
第27 章 搜尋算法 522
27.1 A* 算法 522
27.2 回溯算法 531
27.2.1 解空間樹 531
27.2.2 回溯算法框架 540
第28 章 貪心算法 543
28.1 區間問題 543
28.1.1 最多不相交區間問題 543
28.1.2 選點問題 546
28.1.3 區間覆蓋問題 548
28.2 部分背包問題 551
28.3 種樹問題 553
第29 章 分治算法 558
29.1 漢諾塔問題 558
29.2 二分查找算法 561
29.3 主定理 563
29.4 Strassen 算法 567
29.5 循環賽日程表問題 570
第30 章 動態規划算法 574
30.1 資源分配問題 575
30.2 最長遞增/ 遞減子序列問題 579
30.3 項鍊問題 582
30.4 雙線動態規劃問題 585
第七部分
2019—2022 年CSP-JS 真題及參考答案
2019 CCF 非專業級別軟體能力認證
第一輪（CSP-J） 590
2019 CCF 非專業級別軟體能力認證第一輪
（CSP-J）參考答案 600
2019 CCF 非專業級別軟體能力認證
第一輪（CSP-S） 601
2019 CCF 非專業級別軟體能力認證
第一輪（CSP-S）參考答案 613
2020 CCF 非專業級別軟體能力認證
第一輪（CSP-J） 614
2020 CCF 非專業級別軟體能力認證
第一輪（CSP-J）參考答案 625
2020 CCF 非專業級別軟體能力認證
第一輪（CSP-S） 626
2020 CCF 非專業級別軟體能力認證
第一輪（CSP-S）參考答案 640
2021 CCF 非專業級別軟體能力認證
第一輪（CSP-J） 641
2021 CCF 非專業級別軟體能力認證
第一輪（CSP-J）參考答案 653
2021 CCF 非專業級別軟體能力認證
第一輪（CSP-S） 654
2021 CCF 非專業級別軟體能力認證
第一輪（CSP-S）參考答案 670
2022 CCF 非專業級別軟體能力認證
第一輪（CSP-J） 671
2022 CCF 非專業級別軟體能力認證
第一輪（CSP-J）參考答案 683
2022 CCF 非專業級別軟體能力認證
第一輪（CSP-S） 684
2022 CCF 非專業級別軟體能力認證
第一輪（CSP-S）參考答案 697
