noip競賽講解(參加noip競賽主要要學(xué)些什么)
1.參加noip競賽主要要學(xué)些什么
全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽競賽大綱一、初賽內(nèi)容與要求：（#表示普及組不涉及，以下同）計 基算 本機 常的 識* 誕生與發(fā)展 *特點 *在現(xiàn)代社會中的應(yīng)用* 計算機系統(tǒng)的基本組成* 計算機的工作原理# *計算機中的數(shù)的表示* 計算機信息安全基礎(chǔ)知識 *計算機網(wǎng)絡(luò)計 基算 本機 操的 作 * MS DOS與Windows的使用基礎(chǔ)* 常用輸入/輸出設(shè)備的種類、功能、使用* 漢字輸入/輸出方法* 常用計算機屏示信息程序設(shè)計基本知識 程序的表示 * 自然語言的描述* PASCAL或BASIC語言數(shù)據(jù)結(jié)構(gòu)的類型 * 簡單數(shù)據(jù)的類型* 構(gòu)造類型：數(shù)組、字符串* 了解基本數(shù)據(jù)結(jié)構(gòu)（線性表、隊列與棧）程序設(shè)計 * 結(jié)構(gòu)化程序的基本概念* 閱讀理解程序的基本能力* 具有完成下列過程的能力：現(xiàn)實世界（指知識范疇的問題）—>信息世界（表達解法）—>計算機世界（將解法用計算機能實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法描述出來）基本算法處理 * 簡單搜索 * 字串處理* 排序 * 查找* 統(tǒng)計 * 分類 * 合并* 簡單的回溯算法* 簡單的遞歸算法二、復(fù)賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容（2002年修改稿）：計算機軟 件 *操作系統(tǒng)的使用知識*編程語言的使用數(shù)據(jù)結(jié)構(gòu) *結(jié)構(gòu)類型中的記錄類型*指針類型*文件（提高組必須會使用文本文件輸入）*鏈表*樹*圖#程序設(shè)計 *程序設(shè)計能力*設(shè)計測試數(shù)據(jù)的能力*運行時間和占用空間的估算能力#算法處理*排列組合的應(yīng)用*進一步加深回溯算法、遞歸算法*分治法*搜索算法：寬度、深度優(yōu)先算法*表達式處理：計算、展開、化簡等#*動態(tài)規(guī)劃#三、初賽試題類型：注：試題語言兩者選一 （程序設(shè)計語言：基本BASIC或TURBO PASCAL） *判斷 *填空 *完善程序 *讀程序?qū)戇\行結(jié)果 *問答四、推薦讀物： *分區(qū)聯(lián)賽輔導(dǎo)叢書 *學(xué)生計算機世界報及少年電世界雜志。
2.參加noip競賽主要要學(xué)些什么
全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽競賽大綱 一、初賽內(nèi)容與要求：（#表示普及組不涉及，以下同） 計 基 算 本 機 常 的 識 * 誕生與發(fā)展 *特點 *在現(xiàn)代社會中的應(yīng)用 * 計算機系統(tǒng)的基本組成 * 計算機的工作原理# *計算機中的數(shù)的表示 * 計算機信息安全基礎(chǔ)知識 *計算機網(wǎng)絡(luò) 計 基 算 本 機 操 的 作 * MS DOS與Windows的使用基礎(chǔ) * 常用輸入/輸出設(shè)備的種類、功能、使用 * 漢字輸入/輸出方法 * 常用計算機屏示信息 程 序 設(shè) 計 基 本 知 識 程序的表示 * 自然語言的描述 * PASCAL或BASIC語言 數(shù)據(jù)結(jié)構(gòu)的類型 * 簡單數(shù)據(jù)的類型 * 構(gòu)造類型：數(shù)組、字符串 * 了解基本數(shù)據(jù)結(jié)構(gòu)（線性表、隊列與棧） 程序設(shè)計 * 結(jié)構(gòu)化程序的基本概念 * 閱讀理解程序的基本能力 * 具有完成下列過程的能力： 現(xiàn)實世界（指知識范疇的問題） —>信息世界（表達解法） —>計算機世界（將解法用計算機能實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法描述出來） 基本算法處理 * 簡單搜索 * 字串處理 * 排序 * 查找 * 統(tǒng)計 * 分類 * 合并 * 簡單的回溯算法 * 簡單的遞歸算法 二、復(fù)賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容（2002年修改稿）： 計算機 軟 件 *操作系統(tǒng)的使用知識 *編程語言的使用 數(shù) 據(jù) 結(jié) 構(gòu) *結(jié)構(gòu)類型中的記錄類型 *指針類型 *文件（提高組必須會使用文本文件輸入） *鏈表 *樹 *圖# 程 序 設(shè) 計 *程序設(shè)計能力 *設(shè)計測試數(shù)據(jù)的能力 *運行時間和占用空間的估算能力# 算 法 處 理 *排列組合的應(yīng)用 *進一步加深回溯算法、遞歸算法 *分治法 *搜索算法：寬度、深度優(yōu)先算法 *表達式處理：計算、展開、化簡等# *動態(tài)規(guī)劃# 三、初賽試題類型：注：試題語言兩者選一 （程序設(shè)計語言：基本BASIC或TURBO PASCAL） *判斷 *填空 *完善程序 *讀程序?qū)戇\行結(jié)果 *問答 四、推薦讀物： *分區(qū)聯(lián)賽輔導(dǎo)叢書 *學(xué)生計算機世界報及少年電世界雜志。
3.NOIP NOI IOI 要掌握什么知識點
你好，我也是一名中學(xué)生.也是走過OI這條路子的：）
我把算法分一下類大概是
基礎(chǔ)：
recursion （循環(huán)）
simulation （模擬）
enumeration （統(tǒng)計）
sorting （排序）
這些應(yīng)該不算算法吧.只能說是初學(xué)計算機或者初學(xué)程序設(shè)計的人所必需了解的東西.如果你學(xué)過OI，這些應(yīng)該聽過名字，而且能夠運用其中的至少2-3個.
初等：
string manipulation （字符串處理）
optimization （最優(yōu)化問題）
dynamic programming （動態(tài)規(guī)劃）
進入到這里應(yīng)該就算進入算法的殿堂了.動態(tài)規(guī)劃是需要深刻理解的東西.基本上任何考試都會考到.這些東西我沒什么好說的具體靠自己去學(xué).
對初學(xué)有一定難度：
searching （搜索）
graph search （圖論）
geometry （計算幾何）
這些東西使用起來看重的應(yīng)該是理解能力>>>；語言所帶來的影響.
特別是計算幾何.很bt的東西.如果沒有扎實的數(shù)學(xué)功底最好不要去碰.
如果你有時間，有精力，有能力，一個月之內(nèi)應(yīng)該可以把圖論中的最短路和最小生成樹弄懂.也只要把這兩個弄懂就可以了其他的圖論太難太深.
搜索的話.基礎(chǔ)的把.亂七八糟的什么A*疊代之類的就不要去弄了.
而你所說的知識點基本需要了解的就是以上這些.
如果你學(xué)習(xí)到一定深度，就自然知道接下來需要學(xué)習(xí)什么了.
競賽一般的題目都是1道基礎(chǔ)題+1動態(tài)規(guī)劃+1圖論+1綜合.
無論什么難度的競賽一般都是這樣.
任何知識點要考得難都能考的很難，要簡單也有簡單的方法.
說到底，還是靠做題 ：）
4.NOIP NOI IOI 要掌握什么知識點
你好，我也是一名中學(xué)生.也是走過OI這條路子的：）我把算法分一下類大概是 基礎(chǔ)： recursion （循環(huán)） simulation （模擬） enumeration （統(tǒng)計） sorting （排序） 這些應(yīng)該不算算法吧.只能說是初學(xué)計算機或者初學(xué)程序設(shè)計的人所必需了解的東西.如果你學(xué)過OI，這些應(yīng)該聽過名字，而且能夠運用其中的至少2-3個. 初等： string manipulation （字符串處理） optimization （最優(yōu)化問題） dynamic programming （動態(tài)規(guī)劃） 進入到這里應(yīng)該就算進入算法的殿堂了.動態(tài)規(guī)劃是需要深刻理解的東西.基本上任何考試都會考到.這些東西我沒什么好說的具體靠自己去學(xué). 對初學(xué)有一定難度： searching （搜索） graph search （圖論） geometry （計算幾何） 這些東西使用起來看重的應(yīng)該是理解能力>>>語言所帶來的影響. 特別是計算幾何.很bt的東西.如果沒有扎實的數(shù)學(xué)功底最好不要去碰. 如果你有時間，有精力，有能力，一個月之內(nèi)應(yīng)該可以把圖論中的最短路和最小生成樹弄懂.也只要把這兩個弄懂就可以了其他的圖論太難太深. 搜索的話.基礎(chǔ)的把.亂七八糟的什么A*疊代之類的就不要去弄了. 而你所說的知識點基本需要了解的就是以上這些.如果你學(xué)習(xí)到一定深度，就自然知道接下來需要學(xué)習(xí)什么了.競賽一般的題目都是1道基礎(chǔ)題+1動態(tài)規(guī)劃+1圖論+1綜合.無論什么難度的競賽一般都是這樣.任何知識點要考得難都能考的很難，要簡單也有簡單的方法.說到底，還是靠做題 ：）。
5.c語言各種算法詳細講解及NOIP提高組初賽的復(fù)習(xí)資料,要全,急
noip提高組的試題總體來說不是很難，
主要是好好熟悉基本概念，
基礎(chǔ)題的比重占了很大比例，難題很少。
離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)的知識可以看看屈婉玲寫的那一本《離散數(shù)學(xué)》，以及嚴蔚敏的《數(shù)據(jù)結(jié)構(gòu)》，不要看老外的書（雖然它們很好，但不適合noip考試），noip不會這么深入的考察。
不用太深入，只要熟悉常見的算法（比如圖和樹的常見遍歷算法以及最短距離算法），還有比較重要的是集合論，總之離散數(shù)學(xué)不要太過于糾纏細節(jié)，noip考試不是考博，不會出男的算法分析題。
計算機的基礎(chǔ)知識比較零散，各種常見硬件的原理可以在網(wǎng)上搜到。同樣，大概知道工作遠里就行，不要過分深入。
C語言編程部分，隨便找一本國人寫的入門書就行，主要是要知道各種基本數(shù)據(jù)結(jié)構(gòu)如何用C語言實現(xiàn)，以及會編寫簡單的算法就行（如查找排序遍歷）。
全是自己打的字，我08年參加noip的經(jīng)驗就這些，希望對你有用。
6.NOIP主要考哪些方面的內(nèi)容
試題的知識范圍 考試內(nèi)容主要包括：計算機發(fā)展史、計算機組成、計算機基本原理、計算機程序設(shè)計、計算機日常應(yīng)用等。
要求考生掌握至少一門高級程序設(shè)計語言（詳見競賽大綱）。為了保持競賽內(nèi)容的相對連續(xù)性，試題涵蓋的知識點和題型至少60%應(yīng)出現(xiàn)在普及類的參考書目中，其余內(nèi)容可能超出該范圍。
為了考核學(xué)生的基礎(chǔ)知識、綜合應(yīng)用能力，激發(fā)學(xué)生的求知欲和創(chuàng)新思維，體現(xiàn)“與時俱進”的特點，競賽題型在保持大綱相對穩(wěn)定、優(yōu)秀學(xué)生可能接受和理解的基礎(chǔ)上，按照下述趨勢適當(dāng)變化 1、增大與課內(nèi)知識結(jié)合的緊密度； 2、增大解題方法的多樣性和靈活程度； 3、增大開放性試題的比例。 試題的知識范圍具體如下： 一.初賽內(nèi)容與要求： A.計算機的基本常識： 1.計算機和信息社會（信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化） 2.信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式） 3.信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu)） 4.信息的存儲、組織與管理（存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理） 5.信息系統(tǒng)組成及互連網(wǎng)的基本知識（計算機構(gòu)成原理、槽和端口的部件間可擴展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP/IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點） 6.人機交互界面的基本概念（窗口系統(tǒng)、人和計算機交流信息的途徑（文本及交互操作）） 7.信息技術(shù)的新發(fā)展、新特點、新應(yīng)用等。
B.計算機的基本操作： 1. Windows和LINUX的基本操作知識 2. 互聯(lián)網(wǎng)的基本使用常識 （網(wǎng)上瀏覽、搜索和查詢等） 3. 常用的工具軟件使用（文字編輯、電子郵件收發(fā)等） C.數(shù)據(jù)結(jié)構(gòu)： 1.程序語言中基本數(shù)據(jù)類型（字符、整數(shù)、長整數(shù)、浮點） 2. 浮點運算中的精度和數(shù)值比較 3.一維數(shù)組（串）與線性表 4.記錄類型（PASCAL）/ 結(jié)構(gòu)類型（C） D.程序設(shè)計： 1.結(jié)構(gòu)化程序設(shè)計的基本概念 2.閱讀理解程序的基本能力 3.具有將簡單問題抽象成適合計算機解決的模型的基本能力 4.具有針對模型設(shè)計簡單算法的基本能力 5.程序流程描述（自然語言/偽碼/NS圖/其他） 6.程序設(shè)計語言（PASCAL/C/C++,2003仍允許BASIC） E.基本算法處理： 1.初等算法（計數(shù)、統(tǒng)計、數(shù)學(xué)運算等） 2.排序算法（冒泡法、插入排序、合并排序、快速排序） 3.查找（順序查找、二分法） 4.回溯算法 二、復(fù)賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容： A.數(shù)據(jù)結(jié)構(gòu)： 1.指針類型 2.多維數(shù)組 3.單鏈表及循環(huán)鏈表 4.二叉樹 5.文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中） B.程序設(shè)計 1.算法的實現(xiàn)能力 2.程序調(diào)試基本能力 3.設(shè)計測試數(shù)據(jù)的基本能力 4.程序的時間復(fù)雜度和空間復(fù)雜度的估計 C.算法處理 1.離散數(shù)學(xué)知識的應(yīng)用（如排列組合、簡單圖論、數(shù)理邏輯） 2.分治思想 3.模擬法 4.貪心法 5.簡單搜索算法（深度優(yōu)先 廣度優(yōu)先）搜索中的剪枝 6.動態(tài)規(guī)劃的思想及基本算法 評測環(huán)境 NOIP2010比賽環(huán)境規(guī)范依照使用Linux平臺、統(tǒng)一編譯器、提供多種集成開發(fā)環(huán)境選擇的原則制定。 NOIP2010的比賽環(huán)境中，操作系統(tǒng)平臺選擇Linux；在固定的操作系統(tǒng)平臺下，對應(yīng)不同的語言，使用統(tǒng)一的編譯器，消除編譯器不同給選手帶來的不利影響；對應(yīng)每種語言，提供了多種集成開發(fā)環(huán)境，選手可以根據(jù)自己的習(xí)慣選擇集成開發(fā)環(huán)境。
在全國評測時，評測環(huán)境保持與比賽環(huán)境的操作系統(tǒng)及編譯器一致。也就是說全國評測時，使用與選手比賽時一致的平臺對選手的程序進行評測，以消除平臺不一致帶來的不利影響。
以下是NOIP2010比賽環(huán)境要求的詳細描述： 使用Linux操作系統(tǒng)平臺： （1）Linux操作系統(tǒng)必須使用NOI linux，基于ubuntu開發(fā)； （2）Pascal語言，必須使用Free Pascal 2.0.4版本作為編譯器； （3）C語言，必須使用gcc 3.2.2作為編譯器； （4）C++語言，必須使用g++ 3.2.2作為編譯器。
7.參加noip需要哪些知識
初賽考的知識點，大綱如是說：計算機基本常識/基本操作和程序設(shè)計基本知識。
選擇題考查的是知識，而填空/問題解決題更加重視能力的考查。一般說來，選擇題是不需要單獨準備的 -- 也無從準備。
只要多用心積累就可以了。到是問題解決題目比較固定，大家應(yīng)當(dāng)做做以前的題目。
寫運行結(jié)果需要多做題目，培養(yǎng)良好的程序閱讀和分析能力，而完善程序最好總結(jié)一下以前題目常常要你填出來的語句類型。 1）選擇題 一般它們是比較容易得分的，一共30分，不可錯過！ 以前我建議大家找一本等級考試二級的書看，知識講的系統(tǒng)一些。
說選擇題一般不超過二級的知識點，現(xiàn)在顯然已經(jīng)不適用了。近幾年來，初賽的考查范圍有了很大的變化，越來越僅跟潮流了。
這是好事情，不過需要大家有比較廣泛的知識，包括計算機硬件，軟件，網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)（例如棧，隊列，排序算法），程序設(shè)計語言以及一些基本的數(shù)學(xué)知識和技巧（例如排列組合）。 2）填空/問題解決 這部分題目對數(shù)學(xué)要求要高一點，往往考查的是代數(shù)變形，數(shù)列（一般是考遞推），也考查 一些算法和數(shù)據(jù)結(jié)構(gòu)知識。
建議大家多花一點時間做，盡量做對。 例題： 1.數(shù)組A[30..100,20..100]以行優(yōu)先的方式存儲，每個元素占8個字節(jié)，且已知A[40 ,30] 的地址為2000，則A[60,90]的地址為：_________________ 如果以列優(yōu)先存儲，則為：_________________ 考查了數(shù)據(jù)結(jié)構(gòu)中數(shù)組存儲方式。
^^^^^^^^ ^^^^ 2.設(shè)棧S的初始狀態(tài)為空，現(xiàn)有6個元素組成的序列{1,3,5,7,9,11}，對該序列在S 棧上依 次進行如下操作（從序列中的1開始，出棧后不在進棧）：進棧，出棧，進棧，進棧， 進棧，進棧 ，出棧，進棧，問出棧的元素序列是：_________，棧頂指針的值為______ 棧頂元素為：___________________ 考查了數(shù)據(jù)結(jié)構(gòu)中的棧。 ^^^^^^^^ ^^ 3.把中綴表達式寫成后綴及前綴表達式 （1） (P+Q)*(A-B)/((C+D)/(E-F))-G 后：_________________ 前：_________________ （2） A-C*D+B/E*(D/A) 后：_________________ 前：_________________ 4.根據(jù)后綴表達式，寫出前綴及中綴表達式 ABC/DE+GH-/*+ 前：_________________ 中：_________________ 這兩題實際上考查了數(shù)據(jù)結(jié)構(gòu)中的表達式樹 ^^^^^^^^ ^^^^^^^^ 5.用一個字節(jié)來表示整數(shù)，最高位用作符號位（1為正，0為負），其他位表示數(shù)值， （1）這樣的表示法稱為原碼表示法，表示數(shù)的范圍為：_________________ （2）原碼表示法，將出現(xiàn)_________________有兩種表示 （3）實際上計算機中是用補碼表示數(shù)，其表示范圍為：_________________ 考查了數(shù)的原碼，補碼表示。
6.已知N*N個數(shù)據(jù)成方陣排列： A11 A12 A13 。 A1n A21 A22 A23 。
A2n 。 An1 An2 An3 。
Ann 已知Aij=Aji, (1)將A11,A21,A22,A31,A32,A33。 存儲到一維數(shù)組A(1),A(2),A(3)。
A(K) 給出i,j 寫出求K的表達式：_________________ （2）將A11,A12,。A1n,A22,A23,。
A2n,A33。 Ann存儲到一維數(shù)組A(1),A(2), A(3)。
A(K)， 給出i,j 寫出求K的表達式：_________________ 7.已知一個數(shù)列U1,U2,U3。Un。
往往可以找到一個最小的K值和K個數(shù)a1,a2,..,ak， 使得數(shù)列從某項開始都滿足：U(n+k)=a1*U(n+k-1)+a2*U(n+k-2)+。+akUn （式A） 例如數(shù)列 1,1,2,3,5。
可以發(fā)現(xiàn)：當(dāng)K=2,a1=1,a2=1時，從第3項起（N>=1）滿足： U(n+2)=U(n+1) + Un 試對數(shù)列1^3 ,2^3 ,3^3 ,。,N^3，。
求K和a1,a2,。ak，使得式A成立. 實質(zhì)是考數(shù)學(xué)。
8.給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA，畫出此二叉樹 9.給出二叉樹的前序遍歷與后序遍歷，能確定一棵二叉樹嗎，舉例說明. 10.下面是一個利用完全二叉樹特性，用順序表來存儲的一個二叉樹，結(jié)點數(shù)據(jù)為字符型（結(jié) 點層次從小到大，同一層從左到右順序存儲，#表示空結(jié)點，@表示存儲數(shù)據(jù)結(jié)束） 結(jié)點 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 數(shù)據(jù) A B C # # D E # # # # # G F @ 畫出對應(yīng)的二叉樹： 考查了數(shù)據(jù)結(jié)構(gòu)中的二叉樹 ^^^^^^^^ ^^^^^^ 10.用鄰接矩陣表示有向圖（圖略） 考查了數(shù)據(jù)結(jié)構(gòu)中的圖的表示 ^^^^^^^^ ^^ 11 根據(jù)Nocomachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)的和。 例如： 13=1 23=3+5 33=7+9+11 43=13+15+17+19 在這里，若將每一個式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請寫出X與n之間的關(guān)系表達式：___ 其實是考代數(shù) 12 某班有50名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫a,b,c三本書的書名，將讀過的書打“*”，結(jié)果統(tǒng)計數(shù)字如下： 只讀a者8人；只讀b者4人；只讀c者3人；全部讀過的有2人；讀過a,b兩本書的有4人；讀過a,c兩本書的有2人；讀過b,c兩本書的有3人。
（1）讀過a的人數(shù)是（ ）。 （2）一本書也沒讀過的人數(shù)是（ ）。
3）寫運行結(jié)果 幾乎是送分題，而且占的分數(shù)奇多，但得分率卻不見得高。大家一定不要錯過這個得分點?。?一般做這類題目的核心是找程序目的，即這個程序想干什么。
迄今為止考過的題目還沒有“亂寫”的，總有一點“寫作目的”的。抓住了它，不僅得出答案變得很容易了，而且對自己的結(jié)果也會比較有信心。
寫程序運。
