全國信息學奧林匹克聯(lián)賽培訓教程（二）

第一篇 程序的測試和效率分析
第1章 測試程序
1.1 系統(tǒng)的測試工具
1.1.1 調(diào)試初始化
1.1.2 單步跟蹤
1.1.3 執(zhí)行到光標所在行
1.1.4 斷點
1.1.5 求值和修改
1.1.6 路標
1.1.7 準備編譯運行調(diào)試后的程序
1.2 測試用例的選取方法
1.2.1 白箱法
1.2.2 黑箱法
1.2.3 綜合策略
習題
第2章 程序的效率分析
2.1 程序工作量的度量方法
2.1.1 基本運算
2.1.2 輸入尺寸
2.1.3 輸入情況
2.1.4 復雜度的階
2.2 優(yōu)化時間效率的方法
2.2.1 常數(shù)計算
2.2.2 盡可能在編譯時賦值
2.2.3 算術(shù)運算
2.2.4 避免重復計算
2.2.5 應有利于編譯優(yōu)化
2.2.6 關(guān)于循環(huán)結(jié)構(gòu)
2.2.7 關(guān)于選擇語句
2.2.8 關(guān)于邏輯表達式
2.2.9 關(guān)于下標變量
2.2.10 盡量利用庫模塊
2.3 程序的最優(yōu)性
2.4 程序的空間復雜度
2.4.1 壓縮存儲技術(shù)
2.4.2 原地工作
習題
第二篇 數(shù)據(jù)結(jié)構(gòu)
第3章 順序存儲結(jié)構(gòu)的線性表
3.1 線性表的定義
3.1.1 順序存儲結(jié)構(gòu)
3.1.2 鏈式存儲結(jié)構(gòu)
3.2 棧
3.2.1 棧的定義
3.2.2 棧的基本運算
3.2.3 棧的重要應用——計算表達式值
3.3 隊列
3.3.1 隊列的定義
3.3.2 隊列的基本運算
3.3.3 循環(huán)隊列
3.3.4 隊列的應用——教育處廣義線性表
3.4 串
3.4.1 串的基本概念
3.4.2 串運算的庫函數(shù)
3.4.3 串運算的應用——子串模式匹配
習題
第4章 非線性結(jié)構(gòu)——樹和圖
4.1 樹
4.1.1 樹的概念
4.1.2 樹的表示方法和存儲結(jié)構(gòu)
4.1.3 二叉樹的概念
4.1.4 樹或森林轉(zhuǎn)換成二叉樹
4.1.5 二叉樹的存儲結(jié)構(gòu)
4.1.6 樹或森林的遍歷
4.1.7 由二叉樹的兩種遍歷順序確定樹結(jié)構(gòu)
4.1.8 二叉樹的重要應用
4.2 圖
4.2.1 圖的基本概念
4.2.2 圖的存儲結(jié)構(gòu)
4.2.3 圖的遍歷和圖的生成樹
4.2.4 圖的應用
習題
第三篇 算法設(shè)計
第5章 高精度運算
5.1 高精度的十進制運算
5.1.1 數(shù)據(jù)類型
5.1.2 基本運算
5.2 改善高精度運算的效率
5.2.1 擴大進制數(shù)
5.2.2 建立因子表
習題
第6章 構(gòu)造法
6.1 對應策略
6.1.1 對應經(jīng)典問題
6.1.2 對應簡單問題
6.1.3 對應數(shù)學問題
6.2 分治策略
6.2.1 遞推的分治策略
6.2.2 遞歸的分治策略
6.3 歸納策略
6.3.1 遞推法
6.3.2 遞歸法
6.3.3 制定目標
6.3.4 貪心法
6.4 模擬策略
6.4.1 直敘式模擬
6.4.2 篩選法模擬
6.4.3 構(gòu)造法模擬
習題
第7章 搜索法
7.1 枚舉法
7.1.1 “直譯”的枚舉算法
7.1.2 枚舉算法的優(yōu)化
7.2 回溯法
7.2.1 回溯法的基本思路
7.2.2 回溯法的應用實例
7.2.3 回溯法的優(yōu)化
7.3 廣度優(yōu)先搜索
7.3.1 廣度優(yōu)先搜索的基本思路
7.3.2 求初始狀態(tài)所能到達的所有狀態(tài)
7.3.3 計算初始狀態(tài)到目標狀態(tài)的最短路徑
習題
第8章 動態(tài)程序設(shè)計方法
8.1 問題的引出
8.2 動態(tài)程序設(shè)計方法的基本概念
8.2.1 階段和狀態(tài)
8.2.2 決策和策略
8.2.3 最優(yōu)化原理與無后效性
8.2.4 最優(yōu)指標函數(shù)和狀態(tài)轉(zhuǎn)移方程
8.3 動態(tài)程序設(shè)計方法的基本思維方式
8.4 動態(tài)程序設(shè)計方法的應用實例
8.4.1 計算所有方案
8.4.2 計算一些階段性明顯、但不具備最優(yōu)子結(jié)構(gòu)特征的問題
8.4.3 雙重動態(tài)程序設(shè)計
8.4.4 多進程的最優(yōu)化決策問題
習題