信息競賽高手進

國際標準書號（International Standard Book Number）簡稱ISBN。

ISBN 978-7-107-17648-7 是普通高中課程標準實驗教科書《化學必修2》的書號。

關於信息競賽，請參考附檔(無法插入文檔，請參考以下內容）。

課題： §1 信息競賽及壹些術語簡介備課：蓋建華審稿：

目標（1）了解信息競賽背景知識，掌握競賽的知識結構。

（2）會初步運用信息科學的思想去考慮問題。

概要重點：競賽要掌握的知識結構、數據結構、算法的概念。

難點：壹些術語及其內涵，要求深刻掌握數據結構、算法的概念。

背景知識 1 信息學奧賽的全稱是青少年信息學（計算機）奧林匹克競賽（早期稱為青少年計算機程序設計競賽），是旨在廣大青少年中普及計算機教育，推廣計算機應用的壹項學科性競賽活動。全國性的信息學奧賽可分為三個層次：先舉辦全國信息學(計算機)奧林匹克分區聯賽（簡稱NOIP）,聯賽分高中組,初中組進行, 以普及為主。在分區聯賽的基礎上,各省市組成自己的代表隊(壹般為3名選手),參加第二個層次的比賽，即全國青少年信息學奧林匹克競賽 (簡稱 NOI), 第三個層次是從 NOI 中選拔優秀選手(壹般為 15 人), 經過培訓, 考試選拔,組成國家隊(壹般 4—5 人). 參加國際信息學奧林匹克競賽, 即IOI, 這是國際性的最高水平的競賽。競賽分兩輪：初試和復試。初試形式為筆試，側重考察學生的計算機基礎知識和編程的基本能力，並對知識面的廣度進行測試。初試為資格測試，各省初試成績在本賽區前15%的學生進入復賽。復試形式為上機，著重考察學生對問題的分析理解能力，數學抽象能力，編程語言的能力和編程技巧、想象力和創造性等。各省聯賽的等第獎在復試的優勝者中產生。

2 初賽內容與要求

▲計算機的基本常識

1．計算機和信息社會（信息社會的主要特征、計算機的主要特征、數字通信網絡的主要特征、數字化）

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

3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）

4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、數據庫管理）

5．信息系統組成及互連網的基本知識（計算機構成原理、槽和端口的部件間可擴展互連方式、層次式的互連結構、互聯網絡、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）

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

7．信息技術的新發展、新特點、新應用等。

▲計算機的基本操作

1. WINDOWS和LINUX的基本操作知識

2. 互聯網的基本使用常識（網上瀏覽、搜索和查詢等）

3. 常用工具軟件使用（文字編輯電子郵件收發等）

▲數據結構

1．程序語言中基本數據類型(字符、整數、長整數、浮點)

2. 浮點運算中的精度和數值比較

3．壹維數組（串）與線性表

4．記錄類型（PASCAL）/ 結構類型（C）

▲程序設計

1．結構化程序設計的基本概念

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

3．具有將簡單問題抽象成適合計算機解決的模型的基本能力

4．具有針對模型設計簡單算法的基本能力

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

6．程序設計語言（PASCAL/C/C++，2003仍允許BASIC）

▲基本算法處理

1．初等算法（計數、統計、數學運算等）

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

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

4．回溯算法

課前預習說說對下列概念的理解

（1）TCP/IP協議（2）數據結構

（3）PASCAL語言（4）算法

思考

探究 1、思考回答下列情景題：

TCP/IP 是供已連接因特網的計算機進行通信的通信協議。TCP/IP 定義了電子設備（比如計算機）如何連入因特網，以及數據如何在它們之間傳輸的標準。數據以TCP/IP協議進行傳輸時，可以拿信件的處理過程來類比。數據好比是________。IP地址好比是________。TCP端口好比是_________。假如有人不按協議操作，或者是向所有群體發送大量信息，或者是向某個人發送大量信息，最終導致網絡擁塞或者癱瘓，這叫做___________。

程序設計中，數組可以用數學上的數列來類比。假設數列{an}的通項公式為an=4n+1(n>=1)，則a[10]=____________。下面是計算機上存儲的壹個4*4的數陣，如果用數列的通項公式來表示，應該為_________________。如果把它看做壹個4*4的表格，比如第4行第4列的數字為a[4,4]=8，則a[m,n](m，n取1..4)的通式為___________________ (用m,n來表示)。

1 4 9 16

1 2 3 4

25 36 49 64

5 6 7 8

遞推算法是壹種用若幹步可重復的簡單運算（規律）來描述復雜問題的方法。比如要把任何壹個自然數的立方寫成壹串連續奇數之和。可以按如下方法遞推：

13=1

23=3+5=8

33=7+9+11=27

43=13+15+17+19=64

……………………….

設n為輸入的壹個任意自然數，它的立方是由m個奇數之和構成的，其中第壹個奇數為p，則n3=p+____+...+______。n+1立方是由____個奇數之和構成，其中第壹個奇數為_______。另外當n=1時，m=_____，p= ______。

（1）把數組a[n]中的元素進行平方運算，得到的新的數組如何表達？

（2）把{1,5,9,11,8}按從大到小順序排列。

（3）以信件來類比，數據按TCP/IP協議組裝好後，應該包含哪些地址信息？

（4）如果有人不按業界定制的協議去實現自己的網絡通信，那他用的是什麽協議？

（5）如果不用遞推算法，妳能使用數學歸納法得出n3的表達方法嗎？妳能否從中體會到計算機處理方法和數學思考方法的壹些區別？

新知探究思考下列問題：

1 假設有壹個數組(array)，裏面有8個元素{1, 5, 10, 20, 15, 8, 6, 90}。

觀察其特點，發現裏面的元素都是_____，具有相同類型，並且他們是____的形式組織起來。我們把這些按序排列的同類數據元素的集合稱為數組。

在整數數組的基礎上，我們可以定義壹些標準的操作，比如找最大最小數，排序等等。大家考察壹下，在數組上還可以定義哪些操作？

因此，在計算機科學中，數據結構是壹門研究非數值計算的程序設計問題中計算機的操作對象（數據元素）以及它們之間的關系和運算等的學科，而且確保經過這些運算後所得到的新結構仍然是原來的結構類型。

另外，我們也可以從集合和函數的觀點來考察數據結構。例如上述數組的元素可以組成壹個集合，他們之間的先後關系、大小關系、排序等都可以理解為______關系。

數據結構可以形式地定義為（K，R）（或（D，S）），其中，K是數據元素的有限集，R是K上的關系的有限集。

2 通過上面遞歸算法的例題，我們總結壹下算法的特征：

算法（Algorithm）是壹系列解決問題的清晰指令，也就是說，能夠對壹規範的_____，在有限時間內獲得所要求的____。算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決壹類問題。

壹個算法應該具有以下五個重要的特征：

1、有窮性：壹個算法必須保證執行有限步之後結束；

2、確切性：算法的每壹步驟必須有確切的定義；

3、輸入：壹個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；

4、輸出：壹個算法有壹個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的；

5、可行性：算法原則上能夠精確地運行，用筆和紙做有限次運算後即可完成。

例題說明 [例1] 植樹節那天，有五位參加了植樹活動，他們完成植樹的棵數都不相同。問第壹位同學植了多少棵時，他指著旁邊的第二位同學說比他多植了兩棵；追問第二位同學，他又說比第三位同學多植了兩棵；…如此，都說比另壹位同學多植兩棵。最後問到第五位同學時，他說自己植了10 棵。到底第壹位同學植了多少棵樹？

[例2]斐波列契數列（Faibonacci）0，1，1，2，3，5，8，13，21，34……求此數列第n項。

[例3]用篩法求出25以內的全部素數。

[例4]輸入4名學生數學、物理、英語、化學、pascal五門課的考試成績，求出每名學生的平均分，打印出表格。

當堂反饋練習 1、微型計算機的運算器、控制器及內存儲器的總稱是____。

A)CPU B)ALU

C)MPU D)主機

2、反映計算機存儲容量的基本單位是____。

A)二進制位 B)字節

C)字 D)雙字

3、十進制數123變換為等值的二進制數是____。

A)110101 B)110110

C)111011 D)110011