全國青少年信息學奧林匹克聯(lián)賽大綱

全國青少年信息學奧林匹克聯(lián)賽大綱(節(jié)選)NOIP大綱一、總則由中國計算機學會負責組織的全國青少年信息學奧林匹克聯(lián)賽(NOIP)是全國信息學奧林匹克競賽(NOI)整個系列中的一個重要組成部分，旨在向中學生普及計算機基礎知識,培養(yǎng)計算機科學和工程領域的后備人才。普及的重點是根據(jù)中學生的特點,培養(yǎng)學生學習計算機的興趣,使得他們對信息技術的一些核心內(nèi)容有更多的了解,提高他們創(chuàng)造性地運用程序設計知識解決實際問題的能力。對學生的能力培養(yǎng)將注重以下的幾個方面:?想象力與創(chuàng)造力;?對問題的理解和分析能力;?數(shù)學能力和邏輯思維能力;?對客觀問題和主觀思維的口頭和書面表達能力;?人文精神:包括與人的溝通能力,團隊精神與合作能力,恒心和毅力,審美能力等。二、命題程序和組織機構命題是選拔過程的重要一環(huán),同時對計算機的普及內(nèi)容起著導向性的作用。命題應注重趣味性、新穎性、知識性、應用性和中學生的心智特點,不直接從大學專業(yè)教材中選題。在命題和審題工作中,堅持開放和規(guī)范的原則。在NOI科學委員會主持下成立的聯(lián)賽命題委員會負責命題工作,命題委員會成員主要來自參加聯(lián)賽的省(包括直轄市、自治區(qū)、下同。每個省最多派一名委員）,也可來自社會計算機界。聯(lián)賽命題委員會的主要職責是提供聯(lián)賽的備選題目,并承擔對所提供的題目保密的責任。聯(lián)賽命題委員會委員應具備如下資格:?從事一線計算機教學或信息學奧賽輔導工作兩年（含）以上;?有精力和時間從事該項工作;?對此項工作有興趣并愿意作為志愿者從事NOIP命題及其相關工作。聯(lián)賽命題委員會委員的產(chǎn)生過程:?本人提出申請（填寫表格）;?中學教師需所在單位同意或省奧賽主管部門同意;?科學委員會批準,由中國計算機學會頒發(fā)聘書（每一聘期為兩年）。聯(lián)賽命題委員會委員的職責:每年為NOIP提供備選題題目若干，在9月1日之前提交科學委員會；?備選試題的保密期為2年,在該段時間內(nèi)不得泄密或另作他用;?搜集本省信息學奧賽的有關信息并向科學委員會通報;題目一經(jīng)提交,即表明同意授權中國計算機學會科學委員會全權處理,包括使用、修改和出版。無論是委員提交的題目還是科學委員會直接提交的題目,試題版權均歸中國計算機學會所有,試題原型一旦被正式采用,中國計算機學會將出具試題錄用證明。科學委員會確定當年的聯(lián)賽試題,這些試題可能從備選題庫中選取并做適當修改后成型,也可能直接命題。三、競賽形式和成績評定聯(lián)賽分兩個等級組:普及組和提高組。每組競賽分兩輪;初試和復試。?初試形式為筆試,測重考察學生的計算機基礎知識和編程的基本能力,并對知識面的廣度進行測試。初試為資格測試,各省初試成績在本賽區(qū)前15%的學生進入復賽。?復試形式為上機,著重考察學生對問題的分析理解能力,數(shù)學抽象能力,編程語言的能力和編程技巧、想象力和創(chuàng)造性等。各省聯(lián)賽的等第獎在復試的優(yōu)勝者中產(chǎn)生。比賽中使用的程序設計語言是:2003年：初賽:BASIC、PASCAL或C/C++;復賽:BASIC、PASCAL或C/C++。2004年：初賽:BASIC、PASCAL或C/C++;復賽:PASCAL或C/C++。2005年及之后：初賽：PASCAL或C/C++;復賽:PASCAL或C/C++。每年復賽結束后,各省必須在指定時間內(nèi)將本省一等獎候選人的有關情況、源程序和可執(zhí)行程序報送科學委員會。經(jīng)復審確認后,由中國計算機學會報送中國科協(xié)和教育部備案。中國計算機學會對各省獲NOIP二等獎和三等獎的分數(shù)線或比例提出指導性意見,各省可按照成績確定獲獎名單。四、試題形式每次聯(lián)賽的試題分四組:普及組初賽題A1、普級組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中,A1和B1類型相同,A2和B2類型相同，但題目不完全相同,提高組難度高于普及組。?初賽:初賽全部為筆試,滿分100分。試題由四部分組成:選擇題:共20題,每題1.5分,共計30分。每題有5個備選答案,前10個題為單選題（即每題有且只有一個正確答案,選對得分）,后10題為不定項選擇題（即每題有1至5個正確答案,只有全部選對才得分）。問題求解題:共2題,每題5分,共計10分。試題給出一個敘述較為簡單的問題,要求學生對問題進行分析,找到一個合適的算法,并推算出問題的解?？忌o出的答案與標準答案相同,則得分;否則不得分。程序閱讀理解題:共4題,每題8分,共計32分。題目給出一段程序（不一定有關于程序功能的說明）,考生通過閱讀理解該段程序給出程序的輸出。輸出與標準答案一致,則得分;否則不得分。程序完善題:共2題,每題14分,共計28分。題目給出一段關于程序功能的文字說明,然后給出一段程序代碼,在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格,要求考生根據(jù)程序的功能說明和代碼的上下文,填出被略去的語句。填對則得分;否則不得分。?復賽:復賽的題型和考試形與NOI類似,全部為上機編程題，但難度比NOI低。題目包括4道題,每題100分,共計400分。每一試題包括:題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時,測試程序為每道題提供了5-10組測試數(shù)據(jù),考生程序每答對一組得10-20分,累計分即為該道題的得分。五、試題的知識范圍（一）初賽內(nèi)容與要求:計算機基本常的識計算機和信息社會（信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡的主要特征、數(shù)字化）信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式）信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲結構、指令、程序,和存儲程序原理、程序的三種基本控制結構）信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、數(shù)據(jù)庫管理）信息系統(tǒng)組成及互連網(wǎng)的基本知識（計算機構成原理、槽和端口的部件間可擴展互連方式、層次式的互連結構、互聯(lián)網(wǎng)絡、TCP/IP協(xié)議、HTTP協(xié)議、WEB應用的主要方式和特點）人機交互界面的基本概念（窗口系統(tǒng)、人和計算機交流信息的途徑（文件及交互操作））信息技術的新發(fā)展、新特點、新應用等。計算機的基本操作WINDOWS和LINUX的基本操作知識互聯(lián)網(wǎng)的基本使用常識（網(wǎng)上的瀏覽、搜索和查詢等）常用的工具軟件使用（文字編輯、電子郵件收發(fā)等）程序設計的基本知識數(shù)據(jù)結構程序語言中基本數(shù)據(jù)類型（字符、整數(shù)、長整數(shù)、浮點）浮點運算中的精度和數(shù)值比較一維數(shù)組（串）與線性表記錄類型（PASCAL）/結構類型（C）程序設計結構化程序設計的基本概念閱讀理解程序的基本能力具有將簡單問題抽象成適合計算機解決的模型的基本能力具有針對模型設計簡單算法的基本能力程序流程描述（自然語言/偽碼/NS圖/其他）程序設計語言（PASCAL/C/C++,2003仍允許BASIC）基本算法處理初等算法（計數(shù)、統(tǒng)計、數(shù)學運算等）排序算法（冒泡法、插入排序、合并排序、快速排序）查找（順序查找、二分法）回溯算法（二）復賽內(nèi)容與要求:在初賽的內(nèi)容個增加以下內(nèi)容:數(shù)據(jù)結構指針類型多維數(shù)組單鏈表及循環(huán)鏈表二叉樹文件操作（從文本文件中讀入數(shù)據(jù),并輸出到文本文件中）程序設計算法的實現(xiàn)能力程序調(diào)試基本能力設計測試數(shù)據(jù)的基本能力程序的時間復雜度和空