NOI大綱文字收藏版

長沙7喜 2021-09-01

展開全文

查看完整NOI大綱正式發(fā)布通知

NOI大綱正式發(fā)布

上期我們推送了全國青少年信息學(xué)奧林匹克系列競賽（NOI）大綱正式發(fā)布的通知，乖小助將會把大綱入門級、提高級和NOI級全部整理出來,，方便大家查閱與收藏，以下是官網(wǎng)發(fā)布的大綱詳情~

2.1 入門級

2.1.1計算機基礎(chǔ)與編程環(huán)境

1.【1】計算機的基本構(gòu)成（CPU,、內(nèi)存,、I/O設(shè) 備等）

2.【1】Windows、 Linux等操作系統(tǒng)的基本概念及其常見操作

3.【1】計算機網(wǎng)絡(luò)和Internet的基本概念

4.【1】計算機的歷史及其在現(xiàn)代社會中的常見應(yīng)用

5.【1】 NOI以及相關(guān)活動的歷史

6.【1】進制的基本概念與進制轉(zhuǎn)換,、字節(jié)與字

7.【1】程序設(shè)計語言以及程序編譯和運行的基本概念

8.【1】使用圖形界面新建,、復(fù)制、刪除,、移動文件或目錄

9.【1】使用Windows系統(tǒng)下的集成開發(fā)環(huán)境（例如 Dev C++等）

10.【1】使用Linux系統(tǒng)下的集成開發(fā)環(huán)境（例如 Code::Blocks等）

11.【1】g++,、gcc等常見編譯器的基本使用

【X】表示難度系數(shù)

2.1.2 C++程序設(shè)計1

1. 程序基本概念

·【1】標(biāo)識符、關(guān)鍵字,、常量,、變量、字符串,、表達式的概念

·【1】常量與變量的命名,、定義及作用

·【2】頭文件與名字空間的定義與理解
·【2】編輯、編譯,、解釋,、調(diào)試等概念理解

2. 基本數(shù)據(jù)類型

·【1】整數(shù)型：int, long long

·【1】實數(shù)型：float, double

·【1】字符型：char
·【1】布爾型：bool

3. 程序基本語句

·【2】cin 語句.scanf 語句，cout語句,，printf語句,，賦值語句，復(fù)合語句

·【2】if語句,，switch語句,，多層條件語句

·【2】for語句，while語句,，do while語句
·【3】多層循環(huán)語句

4. 基本運算

·【1】算數(shù)運算：加,、減、乘,、除,、整除,、求余

·【1】關(guān)系運算：大于，大于等于,，小于,，小于等于，等于,，不等于

·【1】邏輯運算：與（&&）,、或（||）、非（?。?/section>

·【1】變量自增與自減運算
·【1】三目運算
·【3】位運算：與（&）,、或（|）、非（~）,、異或（^）,、左移、右移

5. 數(shù)學(xué)庫常用函數(shù)

·【3】絕對值函數(shù),，四舍五入函數(shù),，取上整函數(shù)，取下整函數(shù),，常用三角函數(shù),，對數(shù)函數(shù)，指數(shù) 函數(shù),，平方根函數(shù)

6. 結(jié)構(gòu)化程序設(shè)計

·【1】順序結(jié)構(gòu),、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)

·【2】自頂向下、逐步求精的模塊化程序設(shè)計

·【2】流程圖的概念及流程圖描述

7. 數(shù)組

·【1】數(shù)組定義,，數(shù)組與數(shù)組下標(biāo)的含義

·【1】數(shù)組的讀入與輸出

·【2】純一維數(shù)組的綜合運用

·【3】純二維數(shù)組與多維數(shù)組的綜合應(yīng)用

8. 字符串的處理

·【2】字符數(shù)組與字符串的關(guān)系

·【2】字符數(shù)組的綜合應(yīng)用

·【2】string類定義,、相關(guān)函數(shù)引用

·【3】string類的綜合應(yīng)用

9. 函數(shù)與遞歸

·【2】函數(shù)定義與調(diào)用，形參與實參

·【3】傳值參數(shù)與傳引用參數(shù)

·【2】常量與變量的作用范圍

·【2】遞歸函數(shù)的概念,、定義與調(diào)用

10. 結(jié)構(gòu)體類型

·【3】結(jié)構(gòu)體的定義及應(yīng)用

11. 指針類型

·【4】指針的概念及調(diào)用

·【4】指針與數(shù)組

·【4】字符指針與string類

·【4】指向結(jié)構(gòu)體的指針

12. 文件及基本讀寫

·【2】文件的基本概念,，文本文件的基本操作

·【2】文本文件類型與二進制文件類型

·【2】文件重定向、文件讀寫等操作

13. STL模板應(yīng)用

·【3】<algorithm> 中 sort 函數(shù)

·【4】棧（stack）,、隊列（queue）,、鏈表（list）、向量（vector）等容器

1 C++以外的其他高級程序設(shè)計語言可參照本部分內(nèi)容,。

2.1.3 數(shù)據(jù)結(jié)構(gòu)

1. 線性表

·【3】鏈表：單鏈表,、雙向鏈表、循環(huán)鏈表

·【3】棧

·【3】隊列

2. 簡單樹

·【3】樹的定義及其相關(guān)概念

·【4】樹的父親表示法

·【3】二叉樹的定義及其基本性質(zhì)
·【4】二叉樹的孩子表示法

·【4】二叉樹的遍歷：前序,、中序,、后序遍歷

3. 特殊樹

·【4】完全二叉樹的定義與基本性質(zhì)

·【4】完全二叉樹的數(shù)組表示法

·【4】哈夫曼樹的定義、構(gòu)造及其遍歷
·【4】二叉樹的定義,、構(gòu)造及其遍歷

4. 簡單圖

·【3】圖的定義及其相關(guān)概念

·【4】圖的鄰接矩陣存儲

·【4】圖的鄰接表存儲

2.1.4 算法

1. 算法概念與描述

·【1】算法概念

·【2】算法描述：自然語言描述,、流程圖描述,、偽代碼描述

2. 入門算法

·【1】枚舉法

·【1】模擬法

3. 基礎(chǔ)算法

·【3】貪心法

·【3】遞推法

·【4】遞歸法
·【4】二分法

·【4】倍增法

4. 數(shù)值處理算法

·【4】高精度的加法

·【4】高精度的減法

·【4】高精度的乘法

·【4】求高精度整數(shù)除以單精度整數(shù)的商和余數(shù)

5. 排序算法

·【3】排序的基本概念（穩(wěn)定性等）

·【3】冒泡排序

·【3】簡單選擇排序

·【3】簡單插入排序

6. 圖論算法

·【4】圖的深度優(yōu)先遍歷算法

·【4】圖的寬度優(yōu)先遍歷算法

·【5】洪水填充算法（floodfill）

7. 動態(tài)規(guī)則

·【4】動態(tài)規(guī)劃的基本思路

·【4】簡單一維動態(tài)規(guī)劃

·【5】簡單背包類型動態(tài)規(guī)劃

·【5】簡單區(qū)間類型動態(tài)規(guī)劃

2.1.5 數(shù)學(xué)

1. 數(shù)及其運算

·【1】數(shù)的概念，算術(shù)運算（加,、減,、乘、除,、求余）

·【1】數(shù)的進制：二進制,、八進制、十六進制和十進制及其轉(zhuǎn)換

·【2】編碼：ASCII碼,，哈夫曼編碼,，格雷碼

2. 初中數(shù)學(xué)

·【1】初中代數(shù)

·【1】初中平面幾何

3. 初等數(shù)論

·【3】整除、因數(shù),、倍數(shù),、指數(shù),、質(zhì)數(shù),、合數(shù)、同余等概念

·【3】唯一分解定理

·【3】歐幾里得算法（輾轉(zhuǎn)相除法）
·【4】埃氏篩法和線性篩法求素數(shù)

4. 組合數(shù)學(xué)

·【2】加法原理

·【2】乘法原理

·【4】排列及計算公式

·【4】組合及計算公式

·【4】楊輝三角公式

2.2 提高級

2.2.1 計算機基礎(chǔ)與編程環(huán)境

1.【5】在Linux系統(tǒng)終端中使用mkdir,、cp,、rm、mv等命令新建,、復(fù)制,、刪除、移動文件或目錄

2.【5】在Linux系統(tǒng)終端中使用cd,、pwd,、ls等命令更改、顯示目錄路徑和查看目錄中的文件

3.【5】在Linux系統(tǒng)下使用Gedit,、Vim或Emacs等文本編輯工具編寫代碼

4.【5】熟悉g++,、gcc等編譯器以及優(yōu)化、數(shù)學(xué)庫等常見編譯選項

5.【5】在Linux系統(tǒng)終端中運行程序,，并使用time命令查看程序用時（區(qū)分real time,、sys time和user time）

6.【5】了解調(diào)式工具gdb及其break、display,、continue,、step等命令

2.2.1 C++程序設(shè)計2

1. 類（class）

·【6】類的概念及簡單應(yīng)用

·【6】成員函數(shù)和運算符重載

2. STL模板

·【5】集合（set）

·【5】列表（list），雙端隊列（deque）,，優(yōu)先隊列（priority_queue）

·【5】多重集合（multiset）
·【5】映射（map）,，多重映射（multimap）

·【5】對（pair），元組（tuple）

2 C++以外的其他高級程序設(shè)計語言可參照本部分內(nèi)容,。

2.2.2 數(shù)據(jù)結(jié)構(gòu)

1. 線性結(jié)構(gòu)

·【5】雙端棧

·【5】雙端隊列

·【5】有序隊列
·【6】優(yōu)先隊列

·【6】倍增表（ST表）

2. 集合與森林

·【6】等價類

·【6】并查集

·【6】樹與二叉樹的轉(zhuǎn)化——孩子兄弟表示法

3. 特殊樹

·【6】線段樹與樹狀數(shù)組

·【6】字典樹（trie樹）

·【7】笛卡爾樹
·【8】二叉平衡樹AVL,、treap,、splay等

·【8】基環(huán)樹

4. 常見圖

·【5】稀疏圖

·【6】偶圖（二分圖）

·【6】歐拉圖

·【6】有向無環(huán)圖
·【7】連通圖與強連通圖
·【7】重連通圖

5. 哈希表

·【5】數(shù)值哈希函數(shù)構(gòu)造

·【6】排列哈希函數(shù)構(gòu)造

·【6】字符串哈希函數(shù)構(gòu)造

·【6】哈希函數(shù)沖突的常見解決方法

2.2.3 算法

1. 復(fù)雜度分析

·【6】空間復(fù)雜度分析

·【6】時間復(fù)雜度分析

2. 基礎(chǔ)算法

·【6】分治算法

3. 排序算法

·【5】歸并排序

·【5】快速排序

·【6】堆排序
·【6】樹形選擇排序（錦標(biāo)賽排序）

·【5】桶排序

·【6】基數(shù)排序

4. 字符串相關(guān)算法

·【5】字符串匹配算法——KMP

5. 搜索算法

·【6】搜索的剪枝優(yōu)化

·【6】記憶化搜索

·【7】啟發(fā)式搜索

·【7】雙向?qū)挾葍?yōu)先搜索

·【7】迭代加深搜索

·【8】搜索對象的壓縮存儲

6. 圖論算法

·【6】Prim和kruskal等求最小生成樹算法

·【7】求次小生成樹算法

·【6】Dijkstra、bellman_ford,、SPFA等求單源最短路算法

·【7】求單源次短路徑算法

·【6】Floyd-Warshall算法求任意兩點間的最短路和傳遞閉包

·【6】有向無環(huán)圖的拓撲排序算法

·【6】求歐拉道路和歐拉回路算法

·【6】二分圖的構(gòu)造及其判定算法

·【6】最近公共祖先

·【7】求強聯(lián)通分量算法

·【7】強連通分量的縮點算法

·【7】求割點,、割邊算法

7. 動態(tài)規(guī)則

·【6】樹型動態(tài)規(guī)劃

·【7】狀態(tài)壓縮動態(tài)規(guī)劃

·【8】動態(tài)規(guī)劃的常用優(yōu)化

2.2.4 數(shù)學(xué)

1. 高中數(shù)學(xué)

·【5】代數(shù)

·【6】解析幾何

·【6】立體幾何

2. 初等數(shù)論

·【5】同余式

·【7】歐拉定理和歐拉函數(shù)

·【7】費馬小定理

·【7】威爾遜定理

·【7】裴蜀定理

·【7】逆元

·【7】擴展歐幾里得算法

·【7】孫子定理（即中國剩余定理）

3. 組合數(shù)學(xué)

·【6】可重集排列

·【6】可重集組合

·【6】錯排列、圓排列
·【6】鴿巢原理

·【6】二項式定理

·【7】容斥原理
·【7】卡特蘭數(shù)

4. 線性代數(shù)

·【5】矩陣概念

·【6】特殊矩陣：稀疏矩陣,，三角矩陣,，對稱矩陣

·【6】矩陣的初等變換

·【6】矩陣的加減乘和轉(zhuǎn)置運算

·【7】線性方程組的高斯消元法

2.3 NOI級

2.3.1 C++程序設(shè)計3

1.【8】STL模板：容器（containers）、迭代器（iterators）,、空間配置器（allocators）,、配接器（adapters）、算法（algorithms）,、仿函數(shù)（functors）

2.【8】面向?qū)ο蟮某绦蛟O(shè)計思想（OOP）

3 C++以外的其他高級程序設(shè)計語言可參照本部分內(nèi)容,。

2.3.2 數(shù)據(jù)結(jié)構(gòu)

1. 線性結(jié)構(gòu)

·【8】分塊

·【8】塊狀鏈表

2. 序列

·【8】后綴數(shù)組

·【9】跳躍表

·【9】無根樹的Prüfer序列

3. 復(fù)雜樹

·【8】樹鏈剖分

·【8】主席樹

·【8】二位線段樹

·【9】后綴樹

·【9】樹套樹

·【9】k-d 樹

·【10】最小樹形圖

·【10】動態(tài)樹（LCT）

4. 可合并堆

·【8】左偏樹

·【10】二項堆

5.【9】可持久化數(shù)據(jù)結(jié)構(gòu)

2.3.3 算法

1. 算法策略

·【9】復(fù)雜分治思想

·【9】平衡規(guī)劃思想

·【9】構(gòu)造思想

2. 字符串算法

·【8】求最長回文串的Manacher算法

·【8】多模匹配算法——AC自動機

·【9】求字符串前綴和后綴算法——擴展KMP

·【9】確定性有窮自動機——DFA算法

·【10】非確定性有窮自動機——NFA算法

·【10】后綴自動機

3. 圖論算法

·【8】網(wǎng)絡(luò)流算法

·【10】圖的支配集、獨立集與覆蓋集

·【8】二分圖的最大匹配——匈牙利算法
·【9】二分圖的最佳匹配算法——KM算法

·【10】一般圖的匹配

4. 動態(tài)規(guī)劃

·【9】復(fù)雜動態(tài)規(guī)劃模型構(gòu)建

·【9】復(fù)雜動態(tài)規(guī)劃模型的優(yōu)化

2.2.4 數(shù)學(xué)

1. 信息論基礎(chǔ)

·【10】熵,、互信息,、條件熵、相對熵的基本概念

·【10】信息復(fù)雜度的基本概念

·【10】描述復(fù)雜度的基本概念

·【10】通訊復(fù)雜度的基本概念

2. 初等數(shù)論

·【8】原根和指數(shù)

·【8】大步小步（Baby Step Giant Step,，BSGS）算法

·【9】完全數(shù)

·【9】狄利克雷（Dirichlet）卷積

·【10】平方剩余

·【10】二次同余式

·【10】二次互反律

3. 離散數(shù)學(xué)

·【9】代數(shù)系統(tǒng)的基本概念

·【9】群的基本概念

·【9】置換群與循環(huán)群

4. 組合數(shù)學(xué)

·【9】母函數(shù)

·【9】莫比烏斯變換

·【9】Burnside引理與Pólya原理

·【9】斯特林?jǐn)?shù)

5. 高等數(shù)學(xué)

·【9】多項式函數(shù)微分

·【9】多項式函數(shù)積分

·【10】泰勒級數(shù)

·【10】快速傅里葉變換（Fast Fourier Transform,，F(xiàn)FT）

·【10】卷積

6. 線性代數(shù)

·【9】矩陣的逆運算

·【9】行列式及其運算

·【9】線性相關(guān)與矩陣的逆

7. 概率論

·【8】概率相關(guān)概念

·【9】求概率的乘法公式、全概率公式,、貝葉斯公式

8. 博弈論

·【9】零和博弈問題——Nim博弈等

·【9】Sprague-Garundy（SG）函數(shù)概念及應(yīng)用

9. 運籌學(xué)

·【10】線性規(guī)劃之單純形法

10. 計算幾何

·【7】矢量及其運算

·【8】點,、線、面之間的位置判斷

·【8】常見圖形的面積計算

·【8】二維凸包的求及其應(yīng)用

·【9】半平面交

— end —

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息,，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點擊一鍵舉報,。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻花（0） +1

來自：長沙7喜 > 《信息課》

舉報/認(rèn)領(lǐng)