第一篇：信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)感言張春霞

信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)感言

張春霞

一、引言

信息學(xué)奧林匹克聯(lián)賽是一項(xiàng)旨在向中學(xué)生普及計(jì)算機(jī)基礎(chǔ)知識(shí)，培養(yǎng)計(jì)算機(jī)科學(xué)和工程領(lǐng)域的后備人才，其重點(diǎn)是根據(jù)中學(xué)生的特點(diǎn)，培養(yǎng)學(xué)生學(xué)習(xí)計(jì)算機(jī)的興趣，使得他們對(duì)信息技術(shù)的一些核心內(nèi)容有更多的了解，提高他們創(chuàng)造性地運(yùn)用程序設(shè)計(jì)知識(shí)解決實(shí)際問題的能力。對(duì)學(xué)生的能力培養(yǎng)注重以下的幾個(gè)方面：

· 想象力與創(chuàng)造力； · 對(duì)問題的理解和分析能力； · 數(shù)學(xué)能力和邏輯思維能力；

· 對(duì)客觀問題和主觀思維的口頭和書面表達(dá)能力；

· 人文精神：包括與人的溝通能力，團(tuán)隊(duì)精神與合作能力，恒心和毅力，審美能力等。

現(xiàn)從我自己從事聯(lián)賽輔導(dǎo)工作兩年來的一些收獲，談?wù)勎业囊恍w會(huì)。信息學(xué)奧林匹克聯(lián)賽是一項(xiàng)旨在推動(dòng)計(jì)算機(jī)普及的學(xué)科競(jìng)賽活動(dòng)，重在培養(yǎng)學(xué)生能力，使得有潛質(zhì)有才華的學(xué)生在競(jìng)賽活動(dòng)中鍛煉和發(fā)展，提高他們創(chuàng)造性地運(yùn)用程序設(shè)計(jì)知識(shí)解決實(shí)際問題的能力。

我是從2006年開始從事信息學(xué)奧林匹克聯(lián)賽的輔導(dǎo)工作，目前信息學(xué)奧林匹克聯(lián)賽在我們學(xué)校正廣泛開展，學(xué)生也表現(xiàn)出非常高的熱情。但實(shí)際情況是比較嚴(yán)峻的，幾年來我校一直沒有取得較好成績(jī)，只在今年的聯(lián)賽中取得了3個(gè)二等獎(jiǎng)和1個(gè)三等獎(jiǎng)，作為一名信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)老師，我根據(jù)兩年來自己的教學(xué)實(shí)踐經(jīng)驗(yàn)和教學(xué)工作收獲談?wù)勛约旱捏w會(huì)。

二、發(fā)展教師自身素質(zhì)

學(xué)生所學(xué)習(xí)的內(nèi)容是程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)，要求我們教師不僅懂一種程序設(shè)計(jì)語言而且還要精通。2006年我開始從事信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)工作的時(shí)候發(fā)現(xiàn)，大學(xué)所學(xué)的程序設(shè)計(jì)所編的程序難度根本沒有奧林匹克競(jìng)賽所編的程序難度高。給學(xué)生一杯水，要求教師有一桶水。所以我就買了許多關(guān)于信息學(xué)奧林匹克聯(lián)賽的書，努力鉆研，提高自身的專業(yè)素質(zhì)。給學(xué)生的題目，無論簡(jiǎn)單的還是難的，每一道題都力求在給學(xué)生上課前親自做一遍。同一道題目有不同的解法，作為教師要好好比較。如果沒有過硬的專業(yè)知識(shí)，輔導(dǎo)學(xué)生，那就會(huì)誤人子弟了。

同時(shí)信息學(xué)和其他學(xué)科相比有其特殊性，因?yàn)樾畔W(xué)的知識(shí)會(huì)“過期”，所以信息學(xué)的學(xué)習(xí)不得不“與時(shí)俱進(jìn)”。因此作為一名信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)教師，只有具備終身學(xué)習(xí)的態(tài)度和能力，才能跟得上信息學(xué)的發(fā)展。

三、循序漸進(jìn)，教學(xué)相長(zhǎng)

信息學(xué)奧賽的內(nèi)容主要是程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)，這些全部都是大學(xué)計(jì)算機(jī)本科專業(yè)的重點(diǎn)課程。這是學(xué)生們從沒接觸過的東西，也與平時(shí)課上的內(nèi)容相脫節(jié)，學(xué)生學(xué)習(xí)有一定的難度。所以我們教師要采用有效的教學(xué)方法，讓學(xué)生輕松的獲取知識(shí)。

1．最大限度地激發(fā)學(xué)生的興趣

興趣是學(xué)生最好的老師。C程序設(shè)計(jì)語言的編程界面非常的單調(diào)，而且輔導(dǎo)時(shí)間相對(duì)集中，持續(xù)時(shí)間又長(zhǎng)，學(xué)生學(xué)習(xí)起來就比較枯燥。所以在教學(xué)過程中要調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，讓學(xué)生充分感知。初學(xué)程序的時(shí)候，學(xué)生經(jīng)常會(huì)問我，老師，我們學(xué)的程序設(shè)計(jì)能編游戲嗎？我回答他們能的。在講解分支語句時(shí)，我就采用編程編游戲的方法，要求學(xué)生編一個(gè)人機(jī)對(duì)戰(zhàn)“石頭、剪刀和布”的游戲。學(xué)生非常的感興趣，都做得非常的好，并且提出了新問題，對(duì)分支語句有了較全面的認(rèn)識(shí)。

2．夯實(shí)基礎(chǔ)，拾級(jí)而上

信息學(xué)聯(lián)賽的題目是有一定難度的，但再難的題也有一定的梯度。在學(xué)習(xí)過程中，要求學(xué)生切忌好高務(wù)遠(yuǎn)，要將每一個(gè)細(xì)小的環(huán)節(jié)都了然于胸。教學(xué)時(shí)將題目難度分解，按教學(xué)進(jìn)度逐步提高題目的難度，讓學(xué)生在學(xué)習(xí)中一步一個(gè)腳印。這樣學(xué)生學(xué)習(xí)起來比較輕松，也容易掌握知識(shí)。

3．目標(biāo)恰當(dāng)，舉一反三

合理使用“最近發(fā)展區(qū)”思想，教學(xué)中將每一次練習(xí)的目標(biāo)都設(shè)置的恰到好處，不要讓學(xué)生覺得太簡(jiǎn)單而不屑，也不能讓學(xué)生覺得太難而退縮，讓學(xué)生在已有知識(shí)的基礎(chǔ)上，只要跳一跳就能夠得著。但又不能面面俱到，要給學(xué)生的思考和嘗試的余地。對(duì)于一個(gè)簡(jiǎn)單的題目，在課上不要一一例舉，而讓學(xué)生自己去編寫程序。鼓勵(lì)學(xué)生養(yǎng)成“發(fā)現(xiàn)問題”、“思考問題”、“想辦法解決問題”良好思維習(xí)慣，不要一遇到問題就找老師，鍛煉獨(dú)立解決問題和小組協(xié)作解決問題的能力。

舉一反三是學(xué)習(xí)的普遍現(xiàn)象，也就是要讓學(xué)生學(xué)會(huì)遷移。程序設(shè)計(jì)的題目太多，我們不可能將每一題都做過。要讓學(xué)生學(xué)會(huì)對(duì)比，從典型例題中找出相同點(diǎn)和不同點(diǎn)，把新舊知識(shí)結(jié)合起來。

4．因材施教，各得其所

“學(xué)生水平差異較大，課難上”是目前開展信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)的難題。而有效解決的方法是分層次教學(xué)。教師可以進(jìn)行調(diào)查或者小測(cè)試的方法。根據(jù)測(cè)試的結(jié)果對(duì)學(xué)生分層次。讓水平高的學(xué)生做些難的題目，讓水平低的學(xué)生做些基礎(chǔ)題，也可以讓水平高的學(xué)生給掌握較慢的學(xué)生當(dāng)小老師，既縮小了學(xué)生層次的差異，又培養(yǎng)了學(xué)生的協(xié)作精神。

四、輔導(dǎo)時(shí)的無奈

信息學(xué)奧賽的內(nèi)容主要是程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)，這些全部都是大學(xué)計(jì)算機(jī)本科專業(yè)的重點(diǎn)課程。這是學(xué)生們毫無接觸過的東西，也與平時(shí)課上的內(nèi)容相脫節(jié)。學(xué)生平時(shí)在高考科目上時(shí)間花得很多，如果學(xué)生參加信息學(xué)奧賽輔導(dǎo)，那時(shí)間就更緊了。我們只能用非教學(xué)時(shí)間進(jìn)行輔導(dǎo)，如晚上或周末，這樣上完初賽的內(nèi)容，大概就得一個(gè)學(xué)期。程序設(shè)計(jì)不用就會(huì)生疏，所以比賽前都得安排集訓(xùn)。而集訓(xùn)時(shí)又不能耽誤學(xué)生上課，所以只得犧牲節(jié)假日，利用暑假、國慶來強(qiáng)化。

開始進(jìn)行信息學(xué)奧賽輔導(dǎo)的時(shí)候，一點(diǎn)經(jīng)驗(yàn)都沒有。在學(xué)生的選擇上也只是選擇幾個(gè)計(jì)算機(jī)能力比較好的學(xué)生進(jìn)行培訓(xùn)。到后來學(xué)習(xí)的時(shí)候發(fā)現(xiàn)僅有計(jì)算機(jī)知識(shí)是不夠的。很多時(shí)候用到數(shù)學(xué)和物理的知識(shí)，特別是數(shù)學(xué)。數(shù)學(xué)學(xué)得不好，信息學(xué)奧賽就很難出成績(jī)。這是我們后來選擇學(xué)生時(shí)極力注意的，盡量選擇數(shù)學(xué)學(xué)得好且自律能力強(qiáng)的學(xué)生。但是這些學(xué)生的時(shí)間縮減之后，其他科任教師尤其是班主任老師經(jīng)常會(huì)對(duì)他們“特別關(guān)注”，若成績(jī)稍有下滑就會(huì)勸學(xué)生放棄，真是無奈。

以上是我在信息學(xué)奧林匹克聯(lián)賽輔導(dǎo)時(shí)的一點(diǎn)心得體會(huì)，我們市其他學(xué)?；旧隙疾桓?，我們也是在摸索中，但我們會(huì)盡力，也希望以后能取得更好的成績(jī)。

第二篇：全國青少年信息學(xué)奧林匹克聯(lián)賽

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

目錄

高考加分和保送 聯(lián)賽命題宗旨 普及的內(nèi)容

競(jìng)賽形式和成績(jī)?cè)u(píng)定 試題的知識(shí)范圍

全國青少年信息學(xué)奧林匹克聯(lián)賽(National Olympiad in Informatics in Provinces簡(jiǎn)稱NOIP)自1995年至今已舉辦16次。每年由中國計(jì)算機(jī)學(xué)會(huì)統(tǒng)一組織。NOIP在同一時(shí)間、不同地點(diǎn)以各省市為單位由特派員組織。全國統(tǒng)一大綱、統(tǒng)一試卷。初、高中或其他中等專業(yè)學(xué)校的學(xué)生可報(bào)名參加聯(lián)賽。聯(lián)賽分初賽和復(fù)賽兩個(gè)階段。初賽考察通用和實(shí)用的計(jì)算機(jī)科學(xué)知識(shí)，以筆試為主。復(fù)賽為程序設(shè)計(jì)，須在計(jì)算機(jī)上調(diào)試完成。參加初賽者須達(dá)到一定分?jǐn)?shù)線后才有資格參加復(fù)賽。聯(lián)賽分普及組和提高組兩個(gè)組別，難度不同，分別面向初中和高中階段的學(xué)生。獲得提高組復(fù)賽一等獎(jiǎng)的選手即可免高考，而通過大學(xué)的保送生考試直接被錄取。

高考加分和保送

NOIP的部分一等獎(jiǎng)具有保送名?；蛘吒呖技臃?分?jǐn)?shù)的多少視該校自主招生考試結(jié)果而定)的資格。NOIP的部分一等獎(jiǎng)有參加省隊(duì)選拔賽的資格，省隊(duì)的選手可以參加NOI，NOI獲獎(jiǎng)選手有保送資格。

聯(lián)賽命題宗旨

全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）是一項(xiàng)面向全國青少年的信息學(xué)競(jìng)賽和普及活動(dòng)，旨在向那些在中學(xué)階段學(xué)習(xí)的青少年普及計(jì)算機(jī)科學(xué)知識(shí)；給學(xué)校的信息技術(shù)教育課程提供動(dòng)力和新的思路；給那些有才華的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)；通過競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔優(yōu)秀的計(jì)算機(jī)人才。

競(jìng)賽的目的是為了在更高層次上推動(dòng)普及。本競(jìng)賽及其相關(guān)活動(dòng)遵循開放性原則，任何有條件和有興趣的學(xué)校和個(gè)人，都可以在業(yè)余時(shí)間自愿參加。本活動(dòng)不和現(xiàn)行的學(xué)校教學(xué)相沖突，也不列入教學(xué)計(jì)劃，是課外性質(zhì)的因材施教活動(dòng)。參加者可為初高中學(xué)生或其他中等專業(yè)學(xué)校的青少年。

普及的內(nèi)容

．計(jì)算機(jī)的基本組成；

．計(jì)算機(jī)操作系統(tǒng)使用（windows等）； ．計(jì)算機(jī)工作的基本原理；

．計(jì)算機(jī)程序設(shè)計(jì)的基本方法； ．至少一門高級(jí)程序設(shè)計(jì)語言； ．程序設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)。

普及的重點(diǎn)是根據(jù)中學(xué)生的特點(diǎn)，培養(yǎng)學(xué)生學(xué)習(xí)計(jì)算機(jī)的興趣，使得他們對(duì)信息技術(shù)的一些本質(zhì)和核心的東西有更多的了解，提高他們創(chuàng)造性地運(yùn)用程序設(shè)計(jì)知識(shí)解決實(shí)際問題的能力。

對(duì)學(xué)生的能力培養(yǎng)注重

．想象力與創(chuàng)造力；

．對(duì)問題的理解和分析能力；

．?dāng)?shù)學(xué)能力和邏輯思維能力；

．對(duì)客觀問題和主觀思維的口頭和書面表達(dá)能力；

．人文精神。包括與人的溝通和理解能力，團(tuán)隊(duì)精神與合作能力，恒心和毅力，審美能力等。

競(jìng)賽形式和成績(jī)?cè)u(píng)定

聯(lián)賽分兩個(gè)年齡組：初中組和高中組(普及組和提高組)。每組競(jìng)賽分兩輪：初試和復(fù)試。

．初試形式為筆試，側(cè)重考察學(xué)生的計(jì)算機(jī)基礎(chǔ)知識(shí)和編程的基本能力，并對(duì)知識(shí)面的廣度進(jìn)行測(cè)試。程序設(shè)計(jì)的描述語言采用Basic（2005年被取消）、C/C++或Pascal。各省市初試成績(jī)?cè)诒举悈^(qū)前百分之十五的學(xué)生進(jìn)入復(fù)賽，其分?jǐn)?shù)不計(jì)入復(fù)賽的成績(jī)。初賽時(shí)間為10月的第二個(gè)星期六下午 2:30-4:30舉行。

．復(fù)試形式為上機(jī)，側(cè)重考察學(xué)生對(duì)問題的分析理解能力，數(shù)學(xué)抽象能力，駕馭編程語言的能力和編程技巧、想象力和創(chuàng)造性等。程序設(shè)計(jì)語言可采用Basic（2005年后被取消）、Pascal、C或C++。各省市競(jìng)賽的等第獎(jiǎng)在復(fù)試的優(yōu)勝者中產(chǎn)生。時(shí)間為 3小時(shí)。只進(jìn)行一試，約在當(dāng)年的11 月的第三個(gè)周六進(jìn)行。

試題形式

每次聯(lián)賽的試題分四組：初中組初試賽題；初中組復(fù)試賽題；高中組初試賽題；高中組復(fù)試賽題。其中，初中組初試賽題和高中組初試賽題類型相同，初中組復(fù)試賽題和高中組復(fù)試賽題類型相同，但初中組和高中組的題目不完全相同，高中組難度略高；以體現(xiàn)年齡特點(diǎn)和層次要求。

* 初試：初試全部為筆試，滿分100分。試題由四部分組成：

1、選擇題：共20題，每題1．5分，共30分。每題有4個(gè)備選方案。試題內(nèi)容包括計(jì)算機(jī)基本組成與原理、計(jì)算機(jī)基本操作、信息科技與人類社會(huì)發(fā)展的關(guān)系等等。

2、問題求解題：共2題，每題5分，共10分。試題給出一個(gè)敘述較為簡(jiǎn)單的問題，要求學(xué)生對(duì)問題進(jìn)行分析，找到一個(gè)合適的算法，并推算出問題的解。答案以字符串方式給出，考生給出的答案與標(biāo)準(zhǔn)答案的字符串相同，則得分；否則不得分。

3、程序閱讀理解題：共4題，每題8分，共32分。題目給出一段程序（沒有關(guān)于程序功能的說明），有時(shí)也會(huì)給出程序的輸入，要求考生通過閱讀理解該段程序給出程序的輸出。輸出以字符串的形式給出，如果與標(biāo)準(zhǔn)答案一致，則得分；否則不得分。

4、程序完善題：共 2題，第一題10分，共4空，每空2.5分；第二題18分，共6空，每空3分。兩題共28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個(gè)語句并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對(duì)的，則得分；否則不得分。

（2009年普及組試題為第一題5空，每空3分，第二題前三空每空3分，后兩空每空2分）

*復(fù)試：復(fù)試的題型和形式向全國信息學(xué)奧賽（NOI）靠攏，全部為上機(jī)編程題，但難度略低。復(fù)試為決出競(jìng)賽成績(jī)的最后一個(gè)環(huán)節(jié)。題目包括 4道題，每題100分，共計(jì)400分。難度有易有難，既考慮普及面，又考慮選拔的梯度要求。每一道試題包括：題目、問題描述、樣例說明（輸入、輸出及必要的說明）、數(shù)據(jù)范圍（數(shù)據(jù)限制條件）。測(cè)試時(shí)，測(cè)試程序?yàn)槊康李}提供了5~10組測(cè)試數(shù)據(jù)，考生程序每答對(duì)一組得10~20 分；累計(jì)分即為該道題的得分。

試題的知識(shí)范圍

考試內(nèi)容主要包括：計(jì)算機(jī)發(fā)展史、計(jì)算機(jī)組成、計(jì)算機(jī)基本原理、計(jì)算機(jī)程序設(shè)計(jì)、計(jì)算機(jī)日常應(yīng)用等。要求考生掌握至少一門高級(jí)程序設(shè)計(jì)語言（詳見競(jìng)賽大綱）。為了保持競(jìng)賽內(nèi)容的相對(duì)連續(xù)性，試題涵蓋的知識(shí)點(diǎn)和題型至少60％應(yīng)出現(xiàn)在普及類的參考書目中，其余內(nèi)容可能超出該范圍。

為了考核學(xué)生的基礎(chǔ)知識(shí)、綜合應(yīng)用能力，激發(fā)學(xué)生的求知欲和創(chuàng)新思維，體現(xiàn)“與時(shí)俱進(jìn)”的特點(diǎn)，競(jìng)賽題型在保持大綱相對(duì)穩(wěn)定、優(yōu)秀學(xué)生可能接受和理解的基礎(chǔ)上，按照下述趨勢(shì)適當(dāng)變化

1、增大與課內(nèi)知識(shí)結(jié)合的緊密度；

2、增大解題方法的多樣性和靈活程度；

3、增大開放性試題的比例。

試題的知識(shí)范圍具體如下：

一．初賽內(nèi)容與要求：

A．計(jì)算機(jī)的基本常識(shí)：

1．計(jì)算機(jī)和信息社會(huì)（信息社會(huì)的主要特征、計(jì)算機(jī)的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化）

2．信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式）

3．信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲(chǔ)結(jié)構(gòu)、指令，程序，和存儲(chǔ)程序原理、程序的三種基本控制結(jié)構(gòu)）

4．信息的存儲(chǔ)、組織與管理（存儲(chǔ)介質(zhì)、存儲(chǔ)器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理）

5．信息系統(tǒng)組成及互連網(wǎng)的基本知識(shí)（計(jì)算機(jī)構(gòu)成原理、槽和端口的部件間可擴(kuò)展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP/IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點(diǎn)）

6．人機(jī)交互界面的基本概念（窗口系統(tǒng)、人和計(jì)算機(jī)交流信息的途徑（文本及交互操作））

7．信息技術(shù)的新發(fā)展、新特點(diǎn)、新應(yīng)用等。

B．計(jì)算機(jī)的基本操作：

1.Windows和LINUX的基本操作知識(shí)

2.互聯(lián)網(wǎng)的基本使用常識(shí)（網(wǎng)上瀏覽、搜索和查詢等）

3.常用的工具軟件使用（文字編輯、電子郵件收發(fā)等）

C．?dāng)?shù)據(jù)結(jié)構(gòu)：

1．程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長(zhǎng)整數(shù)、浮點(diǎn))

2.浮點(diǎn)運(yùn)算中的精度和數(shù)值比較

3．一維數(shù)組（串）與線性表

4．記錄類型（PASCAL）/ 結(jié)構(gòu)類型（C）

D．程序設(shè)計(jì)：

1．結(jié)構(gòu)化程序設(shè)計(jì)的基本概念

2．閱讀理解程序的基本能力

3．具有將簡(jiǎn)單問題抽象成適合計(jì)算機(jī)解決的模型的基本能力

4．具有針對(duì)模型設(shè)計(jì)簡(jiǎn)單算法的基本能力

5．程序流程描述（自然語言/偽碼/NS圖/其他）

6．程序設(shè)計(jì)語言（PASCAL/C/C++，2003仍允許BASIC）

E．基本算法處理：

1．初等算法（計(jì)數(shù)、統(tǒng)計(jì)、數(shù)學(xué)運(yùn)算等）

2．排序算法（冒泡法、插入排序、合并排序、快速排序）

3．查找（順序查找、二分法）

4．回溯算法

二、復(fù)賽內(nèi)容與要求：

在初賽的內(nèi)容上增加以下內(nèi)容：

A．?dāng)?shù)據(jù)結(jié)構(gòu)：

1．指針類型

2．多維數(shù)組

3．單鏈表及循環(huán)鏈表

4．二叉樹

5．文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中）

B．程序設(shè)計(jì)

1．算法的實(shí)現(xiàn)能力

2．程序調(diào)試基本能力

3．設(shè)計(jì)測(cè)試數(shù)據(jù)的基本能力

4．程序的時(shí)間復(fù)雜度和空間復(fù)雜度的估計(jì)

C．算法處理

1．離散數(shù)學(xué)知識(shí)的應(yīng)用（如排列組合、簡(jiǎn)單圖論、數(shù)理邏輯）

2．分治思想

3．模擬法

4．貪心法

5．簡(jiǎn)單搜索算法（深度優(yōu)先 廣度優(yōu)先）搜索中的剪枝

6．動(dòng)態(tài)規(guī)劃的思想及基本算法

評(píng)測(cè)環(huán)境

NOIP2010比賽環(huán)境規(guī)范依照使用Linux平臺(tái)、統(tǒng)一編譯器、提供多種集成開發(fā)環(huán)境選擇的原則制定。

NOIP2010的比賽環(huán)境中，操作系統(tǒng)平臺(tái)選擇Linux；在固定的操作系統(tǒng)平臺(tái)下，對(duì)應(yīng)不同的語言，使用統(tǒng)一的編譯器，消除編譯器不同給選手帶來的不利影響；對(duì)應(yīng)每種語言，提供了多種集成開發(fā)環(huán)境，選手可以根據(jù)自己的習(xí)慣選擇集成開發(fā)環(huán)境。

在全國評(píng)測(cè)時(shí)，評(píng)測(cè)環(huán)境保持與比賽環(huán)境的操作系統(tǒng)及編譯器一致。也就是說全國評(píng)測(cè)時(shí)，使用與選手比賽時(shí)一致的平臺(tái)對(duì)選手的程序進(jìn)行評(píng)測(cè)，以消除平臺(tái)不一致帶來的不利影響。

以下是NOIP2010比賽環(huán)境要求的詳細(xì)描述：

使用Linux操作系統(tǒng)平臺(tái)：

（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作為編譯器。

第三篇：2011年春學(xué)期江蘇省華羅庚中學(xué)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)計(jì)劃

2011年春學(xué)期江蘇省華羅庚中學(xué)

信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)計(jì)劃

一、培養(yǎng)目標(biāo)：

（1）知識(shí)目標(biāo)：程序語言、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)、離散數(shù)學(xué)基本知識(shí)

（2）能力目標(biāo)：分析問題與程序設(shè)計(jì)解決問題的基本能力，問題意識(shí)，表達(dá)能力，協(xié)作學(xué)習(xí)能力

二、培訓(xùn)內(nèi)容：

1、高級(jí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)及應(yīng)用

(1)動(dòng)態(tài)型序列化數(shù)據(jù)的組織與應(yīng)用(堆、堆排序)(2)集合型數(shù)據(jù)的組織與應(yīng)用(并查集)? 什么是并查集 ? 并查集的求解適用性 ? 并查集方法的基本程序思想與框架解析 ? 并查集方法的應(yīng)用(3)區(qū)間型數(shù)據(jù)的組織與應(yīng)用(線段樹)? 什么是線段樹 ? 線段樹的求解適用性 ? 線段樹方法的基本程序思想與框架解析 ? 線段樹方法的應(yīng)用

2、數(shù)學(xué)與程序設(shè)計(jì)

(1)組合數(shù)學(xué)基礎(chǔ)及其應(yīng)用? 排列與組合 ? 母函數(shù)與遞推 ? 容斥原理與鴿巢原理(2)常用公式及方法解析? Catelan ? 統(tǒng)計(jì) ? 加、乘 ? 其他

(3)思維遷移與拓展(與遞推、動(dòng)規(guī)的聯(lián)系等)(4)數(shù)學(xué)建?；痉椒?/p>

3、實(shí)戰(zhàn)技巧

(1)程序編寫方面? 數(shù)據(jù)范圍估算與數(shù)據(jù)類型選擇 ? 優(yōu)化方法 ? 掐時(shí)技巧 ? 審題與解題順序選擇技巧 ? 其他(2)算法選擇方面? 數(shù)據(jù)規(guī)模估算 ? 最值、可能值問題……

第四篇：2009年春學(xué)期江蘇省華羅庚中學(xué)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)計(jì)劃

2009年春學(xué)期江蘇省華羅庚中學(xué)

信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)計(jì)劃

一、培養(yǎng)目標(biāo)：

（1）初步掌握PASCAL語言程序設(shè)計(jì)的基本知識(shí)

（2）了解結(jié)構(gòu)化程序設(shè)計(jì)的思想方法

（3）初步掌握數(shù)據(jù)結(jié)構(gòu)與算法方面的基礎(chǔ)知識(shí)

二、課程設(shè)置：

（1）全國青少年信息學(xué)奧林匹克培訓(xùn)教材及其習(xí)題集（中級(jí)本）

（2）簡(jiǎn)明數(shù)據(jù)結(jié)構(gòu)教程

（3）全國青少年信息學(xué)奧林匹克競(jìng)賽中學(xué)試題解析

三、培訓(xùn)時(shí)間：

四、培訓(xùn)內(nèi)容：

1、全面學(xué)習(xí)PASCAL語言的基礎(chǔ)知識(shí)、程序的調(diào)試，使學(xué)生能熟練掌握每周星期六14:10----17:15。PASCAL，并熟練應(yīng)用常用基本算法。

2、深入學(xué)習(xí)各類算法設(shè)計(jì)思想，讓學(xué)生形成一定的分析和解決問題的能力，在算法設(shè)計(jì)中展開各種數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。

3、以實(shí)例為基礎(chǔ)，展開強(qiáng)化訓(xùn)練，使學(xué)生能初步達(dá)到靈活運(yùn)用的程度，獨(dú)立解決實(shí)際問題。加強(qiáng)與其他學(xué)科的合作。信息學(xué)競(jìng)賽中的“信息”二字，其實(shí)就是計(jì)算機(jī)對(duì)現(xiàn)實(shí)世界的數(shù)字化表示。用計(jì)算機(jī)解決現(xiàn)實(shí)問題其中最重要的一步表就是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。數(shù)據(jù)模型的建立、數(shù)學(xué)公式的應(yīng)用，在計(jì)算機(jī)中是關(guān)鍵。因此，加強(qiáng)與其他學(xué)科的橫向聯(lián)系非常必要，特別是數(shù)學(xué)特長(zhǎng)生的培養(yǎng)。

第五篇：第十四屆全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽匯總

第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（提高組 Pascal 語言 二小時(shí)完成）

●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●

一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案）。

1.在以下各項(xiàng)中，（）不是操作系統(tǒng)軟件。

Symbian 2．微型計(jì)算機(jī)中，控制器的基本功能是（）。

A.控制機(jī)器各個(gè)部件協(xié)調(diào)工作 B.實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算 C.存儲(chǔ)各種控制信息 D.獲取外部信息

3.設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（）。A.29 B.28 C.16 D.17 E.7 4．完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（）。

A.N-1 B.2*N C.N D.2N-1 E.N/2 5．將數(shù)組{8, 23, 4, 16, 77,-5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次。

A.4 B.5 C.6 D.7 E.8 6．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（）。A.6 B.5 C.4 D.3 E.2 7.與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（）。

A.123.21 B.131.22 C.130.22 D.130.21 E.130.20 8． 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

A.隊(duì)列 B.多維數(shù)組 C.線性表 D.鏈表 E.棧

E.存放程序和數(shù)據(jù) A.Solaris B.Linux C.Sybase D.Windows Vista E.9.TCP/IP是一組構(gòu)成互聯(lián)網(wǎng)基礎(chǔ)的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議（TCP）和網(wǎng)際協(xié)議（IP）。TCP/IP 協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有四個(gè)層次功能的網(wǎng)絡(luò)模型,其中提供源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能的是（）。

A.鏈路層 B．網(wǎng)絡(luò)層 C.傳輸層 D.應(yīng)用層 E.會(huì)話層

10． 對(duì)有序數(shù)組{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}進(jìn)行二分查找，等概率的情況下查找成功的平均查找長(zhǎng)度（平均比較次數(shù)）是（）。A.35/11 B.34/11 C.33/11 D.32/11 E.34/10

二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)大于或等于1。多選或少選均不得分）。

11.在下列關(guān)于圖靈獎(jiǎng)的說法中，正確的有（）。

A.圖靈獎(jiǎng)是美國計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立的，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人

B.圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱

C.迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮

D.圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈 12．計(jì)算機(jī)在工作過程中，若突然停電，（）中的信息不會(huì)丟失。A.硬盤 B.CPU C.ROM D.RAM 13.設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的有（A.(A∧B)∨(C∧D∨?A)B.((?A∧B)∨C)∧?D C.(B∨C∨D)∨D∧A D.A∧(D∨?C)∧B 14．Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（是典型的Web2.0應(yīng)用。A.Sina B.Flickr C.Yahoo D.Google 15.(2008)10 +(5B)16的結(jié)果是（）。

A.(833)16 B.(2099)10 C.(4063)8(100001100011)2 16.二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是4 2 7 5 6 3 1，則該二叉樹的可能的中根遍歷是（）。）D.）A.4 2 1 7 5 3 6 B.2 4 1 7 5 3 6 C.4 2 1 7 5 6 3 D.2 4 1 5 7 3 6 17.面向?qū)ο蟪绦蛟O(shè)計(jì)（Object-Oriented Programming）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說法中，正確的是（）。

A.面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。

B.面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性（polymorphism）等幾大特點(diǎn)。

C.支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C++、JAVA、C#等。

D.面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于Simula語言，后來在SmallTalk語言的完善和標(biāo)準(zhǔn)化的過程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。

18.設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說法正確的是（）。

A.T是連通的、無環(huán)的 B.T是連通的，有n-1條邊 C.T是無環(huán)的，有n-1條邊 D.以上都不對(duì) 19.NOIP競(jìng)賽推薦使用的語言環(huán)境有（）。

A.Dev-C++ B.Visual C++ C.free pascal D.Lazarus 20.在下列防火墻（firewall）的說法中，正確的有（）。

A.防火墻是一項(xiàng)協(xié)助確保信息安全的設(shè)備，其會(huì)依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過

B.防火墻可能是一臺(tái)專屬的硬件或是安裝在一般硬件上的一套軟件

C.網(wǎng)絡(luò)層防火墻可以視為一種 IP 數(shù)據(jù)包過濾器，只允許符合特定規(guī)則的數(shù)據(jù)包通過，其余的一概禁止穿越防火墻

D.應(yīng)用層防火墻是在 TCP/IP的“應(yīng)用層”上工作，可以攔截進(jìn)出某應(yīng)用程序的所有數(shù)據(jù)包

三．問題求解（共2題，每題5分，共計(jì)10分）

1．有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_____________。

2．書架上有21本書，編號(hào)從1到21，從其中選4本，其中每?jī)杀镜木幪?hào)都不相鄰的選法一共有______種。

四．閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1.var i,a,b,c,d:integer;f:array[0..3] of integer;begin for i:=0 to 3 do read(f[i]);a := f[0] + f[1] + f[2] + f[3];a := a div f[0];b := f[0] + f[2] + f[3];b := b div a;

c :=(b * f[1] + a)div f[2];d := f[(b div c)mod 4];if(f[(a + b + c + d)mod 4] > f[2])then begin a := a + b;writeln(a);end else begin c := c + d;writeln(c);end;end.輸入：9 19 29 39 輸出：_______________ 2．procedure foo(a,b,c:integer);begin if a>b then foo(c,a,b)else writeln(a, ',', b, ',', c)end;var a,b,c:integer;begin read(a, b, c);foo(a,b,c);end.輸入：2 1 3 輸出:__________ 3．procedure f(a,b,c:integer);begin write(a, b, c, '/');if(a = 3)and(b = 2)and(c = 1)then exit;if b

s:string;i,j,len,k:integer;begin read(s);len:=length(s);for i:=1 to len do if(ord(s[i])>= ord('A'))and(ord(s[i])<= ord('Z'))then s[i] := chr(ord(s[i])-ord('A')+ ord('a'));for i:=1 to len do if(ord(s[i]) b)then begin

t := a;a := b;b := t;end;end;function FindKth(left,right,n:integer):integer;var tmp,value,i,j:integer;begin if left = right then exit(left);tmp:= random(right-left)+ left;swap(a[tmp],a[left]);value := ①;i := left;j := right;while i

if in then begin dec(i);exit(⑥);end;exit(i);end;var i:integer;begin randomize;ans :=-1;

m:=5;for i:=1 to m do read(a[i]);read(n);ans:= FindKth(1,m,n);writeln(a[ans]);end.2．（矩陣中的數(shù)字）有一個(gè)n*n(1<=n<=5000)的矩陣a，對(duì)于1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩陣中左右相鄰的兩個(gè)元素，右邊的元素一定比左邊的大。上下相鄰的兩個(gè)元素，下面的元素一定比上面的大。給定矩陣a中的一個(gè)數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩陣中的數(shù)各不相同）。

var n,k,answerx,answery:integer;a:array[1..5000,1..5000] of integer;procedure FindKPosition;var i,j:integer;begin i:=n;j:=n;while j>0 do begin if a[n,j] < k then break;dec(j);end;①

while a[i,j]<>k do begin while(②)and(i>1)do dec(i);while(③)and(j<=n)do inc(j);end;④ ⑤ end;var i,j:integer;

begin read(n);for i:=1 to n do for j:=1 to n do read(a[i,j]);read(k);FindKPosition;writeln(answerx, ' ', answery);end.