全國青少年信息學奧林匹克競賽聯賽試題大綱

　　全國青少年信息學奧林匹克競賽聯賽試題大綱

　　一、試題形式

　　每次聯賽的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型相同，A2和B2類型相同，但題目不完全相同，提高組難度高于普及組。（一般初中學生參加普及組，高中或中專學生參加提高組）

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

　　1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），后10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。

　　2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。考生給出的答案與標準答案相同，則得分；否則不得分。

　　3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關于程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標準答案一致，則得分；否則不得分。

　　4、程序完善題：共2題，每題14分，共計28分。題目給出一段關于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。

　　復賽：復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。題目包括4道題，每題100分，共計400分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。

　　二、試題的知識范圍

　　1．初賽內容與要求：

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．指針類型；2．多維數組；3．單鏈表及循環鏈表；4．二叉樹； 5．文件操作（從文本文件中讀入數據，并輸出到文本文件中）。
程序 設計	1．算法的實現能力；2．程序調試基本能力； 3．設計測試數據的基本能力；4．程序的時間復雜度和空間復雜度的估計。
算法 處理	1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）；2．分治思想； 3．模擬法；4．貪心法；5．簡單搜索算法（深度優先 廣度優先）搜索中的剪枝； 6．動態規劃的思想及基本算法。