內容簡介
“中國計算機學會信息學奧林匹克系列叢書”由中國計算機學會信息學奧林匹克科學委員會主編，由全國著名專家學者精心編著而成。
本書是本套叢書普及本中培訓教程的第二冊，它在第一冊的基礎上，針對聯賽考核的知識點，講解了程式測試、效率分析和程式設計中數據結構和算法等內容，並提供了提高算法效率的具體策略，不僅能幫助剛剛邁進信息學奧林匹克競賽大門的參賽選手掌握程式設計的基本知識，更從啟迪思維的角度引導他們如何分析問題和解決問題。本書帶提供了大量的例題及解題算法，以幫助讀者更深刻的理解和掌握解題思路，並在實戰中靈活運用。
本書深入淺出、思路清晰，既可作為全國信息學奧林匹克聯賽的培訓教材、聯賽輔導教師的參考用書、參賽選手的自學用書，也可作為大中專院校相關專業以及電腦愛好者的參考書。
圖書目錄
第一篇程式的測試和效率分析
第1章測試程式 3
1.1系統的測試工具 3
1.1.1調試初始化 6
1.1.2單步跟蹤 7
1.1.3執行到游標所在行 7
1.1.4斷點 7
1.1.5求值和修改 7
1.1.6路標 8
1.1.7準備編譯運行調試後的程式 8
1.2測試用例的選取方法 8
1.2.1白箱法 8
1.2.2黑箱法 11
1.2.3綜合策略 13
習題 15
第2章程式的效率分析 17
2.1程式工作量的度量方法 17
2.1.1基本運算 17
2.1.2輸入尺寸 18
2.1.3輸入情況 18
2.1.4複雜度的階 20
2.2最佳化時間效率的方法 21
2.2.1常數計算 22
2.2.2儘可能在編譯時賦值 23
2.2.3算術運算 23
2.2.4避免重複計算 24
2.2.5應有利於編譯最佳化 25
2.2.6關於循環結構 25
2.2.7關於選擇語句 28
2.2.8關於邏輯表達式 30
2.2.9關於下標變數 30
2.2.10儘量利用庫模組 32
2.3程式的最優性 32
2.4程式的空間複雜度 35
2.4.1壓縮存儲技術 36
2.4.2原地工作 37
習題 37
第二篇數據結構
第3章順序存儲結構的線性表 41
3.1線性表的定義 41
3.1.1順序存儲結構 42
3.1.2鏈式存儲結構 43
3.2棧 44
3.2.1棧的定義 44
3.2.2棧的基本運算 45
3.2.3棧的重要套用——計算表達式值 46
3.3佇列 50
3.3.1佇列的定義 50
3.3.2佇列的基本運算 51
3.3.3循環佇列 52
3.3.4佇列的套用——計算廣義線性表 54
3.4串 58
3.4.1串的基本概念 58
3.4.2串運算的庫函式 60
3.4.3串運算的套用——子串模式匹配 61
習題 66
第4章非線性結構——樹和圖 69
4.1樹 69
4.1.1樹的概念 70
4.1.2樹的表示方法和存儲結構 72
4.1.3二叉樹的概念 74
4.1.4樹或森林轉換成二叉樹 76
4.1.5二叉樹的存儲結構 78
4.1.6樹或森林的遍歷 79
4.1.7由二叉樹的兩種遍歷順序確定樹結構 87
4.1.8二叉樹的重要套用 90
4.2圖 97
4.2.1圖的基本概念 97
4.2.2圖的存儲結構 99
4.2.3圖的遍歷和圖的生成樹 102
4.2.4圖的套用 106
習題 124
第三篇算法設計
第5章高精度運算 129
5.1高精度的十進制運算 129
5.1.1數據類型 129
5.1.2基本運算 130
5.2改善高精度運算的效率 132
5.2.1擴大進制數 132
5.2.2建立因子表 134
習題 135
第6章構造法 141
6.1對應策略 142
6.1.1對應經典問題 142
6.1.2對應簡單問題 147
6.1.3對應數學問題 151
6.2分治策略 159
6.2.1遞推的分治策略 160
6.2.2遞歸的分治策略 162
6.3歸納策略 166
6.3.1遞推法 166
6.3.2遞歸法 174
6.3.3制定目標 177
6.3.4貪心法 178
6.4模擬策略 185
6.4.1直敘式模擬 186
6.4.2篩選法模擬 188
6.4.3構造法模擬 189
習題 194
第7章搜尋法 203
7.1枚舉法 203
7.1.1“直譯”的枚舉算法 204
7.1.2枚舉算法的最佳化 207
7.2回溯法 213
7.2.1回溯法的基本思路 213
7.2.2回溯法的套用實例 219
7.2.3回溯法的最佳化 225
7.3廣度優先搜尋 229
7.3.1廣度優先搜尋的基本思路 229
7.3.2求初始狀態所能到達的所有狀態 230
7.3.3計算初始狀態到目標狀態的最短路徑 235
習題 239
第8章動態程式設計方法 243
8.1問題的引出 243
8.2動態程式設計方法的基本概念 246
8.2.1階段和狀態 246
8.2.2決策和策略 247
8.2.3最最佳化原理與無後效性 248
8.2.4最優指標函式和狀態轉移方程 248
8.3動態程式設計方法的基本思維方式 249
8.4動態程式設計方法的套用實例 254
8.4.1計算所有方案 254
8.4.2計算一些階段性明顯、但不具備最優子
結構特徵的問題 256
8.4.3雙重動態程式設計 257
8.4.4多進程的最最佳化決策問題 263
習題 266
