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

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