Pascal程序設計初賽紹興市長城中學-----陳龍（一）初賽

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

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

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

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

4、程序完善題：共2題，每題14分，共計28分。題目給出一段關于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。1、計算機的基本常識考綱2、計算機的基本操作3、程學設計的基本知識初賽內容與要求5．信息系統組成及互連網的基本知識（計算機構成原理、槽和端口的部件間可擴展互連方式、層次式的互連結構、互聯網絡、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））7．信息技術的新發展、新特點、新應用等。1、計算機的基本常識2、計算機的基本操作1.Windows和LINUX的基本操作知識2.

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

常用的工具軟件使用（文字編輯、電子郵件收發等）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．動態規劃的思想及基本算法復賽內容與要求一、計算機歷史與發展階段時間邏輯器件應用范圍圖片第一代1946-1958真空電子管科學計算、軍事研究第二代1959-1964晶體管數據處理、事務處理第三代1965-1970集成電路包括了工業控制的各個領域第四代1971-至今大規模集成電路應用到各個領域5.4.控制器是計算機的指揮系統，由程序計數器、指令寄存器、指令譯碼器、時序產生器和操作控制器組成，用來完成協調和指揮整個計算機系統的操作；二、計算機硬件知識5.CPU（中央處理器）負責完成大部分的信息處理操作，是執行各種運算的中心和控制調度全機工作的中心。由運算器、控制器和一些寄存器組成。寄存器用于在指令執行過程中存放操作數和中間數據，存取速度遠遠大于內存和外存。CPU的主要指標是主頻和字長；品牌：intelAMDIBM二、計算機硬件知識8.輸出設備：音響、耳機、顯示器、打印、繪

圖儀等9.輸入輸出接口：VGA（視頻）DVI（數字）HDMI（高清）10.各個部件之間傳送信息的公共通路叫總線

分三類：數據總線、地址總線和控制總線11.臺式機內部各個硬件形態（1）CPU（2）主板（3）內存（4）硬盤二、計算機硬件知識11.臺式機內部各個硬件形態二、計算機硬件知識（5）電源（6）顯卡12.計算機工作原理

各種各樣的信息，通過輸入設備，進入計算機的存儲器，最后通過輸出設備顯示出來。整個過程由控制器進行控制。計算機的整個工作過程及基本硬件結構如下圖：二、計算機硬件知識輸入設備內存儲器運算器控制器輸出設備外存儲器信息（如程序、原始數據）（存）數據輸入命令輸出信息數據程序命令存取指令運算指令（取）數據（存）數據輸出命令12.計算機工作原理三、計算機軟件知識2.操作系統：管理和控制計算機系統中的所有

軟硬件資源；常見的操作系統:

微軟公司的Dos、Windows系列、

LINUX系列，UNIX系列，Mac（蘋果）1.計算機軟件系統分為：系統軟件和應用軟件

系統軟件通常負責管理、控制和維護計算機的各種軟硬件資源，并未用戶提供有好多操作界面，如操作系統；應用軟件是用戶為解決實際問題開發的專門程序。三、計算機軟件知識2.常見的操作系統：（2）UNIXUNIX基本都是安裝在服務器上，沒有用戶界面，基本上都是命令操作。所以你進入該系統的時候就是一個黑乎乎的界面，然后就之后一個光標在閃呀閃。沒有什么娛樂軟件，不能看圖片，不能聽歌。有SOLARIS,BSD系列三、計算機軟件知識2.常見的操作系統：（3）LINUX系列Linux算是UNIX的孩子吧，他繼承了UNIX的許多特性，還加入自己的一些新的功能。有的linux有界面有的沒有。而且Linux是開源的，免費的。誰都可以拿去做修改，然后開發出有自己特色的操作系統。做的比較好的有：紅旗，ubuntu，Fedora，Debian等。這些都可以裝在臺式機或筆記本上。也有相應的軟件可以用，比如：QQ，IE等一些常用的軟件。三、計算機軟件知識3.應用軟件分類類型軟件名稱辦公軟件微軟office，金山WPS圖像處理ACDSee，AdobePhotoshop，美圖秀秀，光影魔術手媒體播放器WindowsMdiaPlayer，暴風影音，千千靜聽，酷狗音樂盒，媒體編輯軟件CoolEdit，GoldWave，會聲會影，Primere，Vegas,AE瀏覽器360安全，360極速，遨游，獵豹，QQ，百度，搜狗通信工具QQ，MSN，阿里旺旺，飛信網絡電視騰訊視頻，PPlive，PPS，風行，迅雷看看，愛奇藝，優酷下載軟件迅雷，QQ旋風，快車，電驢，百度下載器，維棠，碩鼠殺毒軟件瑞星，360殺毒，卡巴斯基，金山毒霸數據庫管理系統Access，SQLServer，Oracle，sybase系統優化360安全衛士，魯大師，電腦管家，瑞星卡卡，超級兔子其他Flash（動畫制作），Dreamwear（網頁制作）AodbeReader(pdf閱讀器)，格式工廠，有道詞典，winrar壓縮軟件，Nero（光盤刻錄）瀏覽器軟件聊天軟件輸入法軟件下載軟件視頻軟件音樂軟件圖像軟件壓縮軟件殺毒軟件辦公軟件三、計算機軟件知識3.應用軟件分類三、計算機軟件知識5.驅動程序

是一種可以使計算機和設備通信的特殊程序。相當于硬件的接口，操作系統只有通過這個接口，才能控制硬件設備的工作，假如某設備的驅動程序未能正確安裝，便不能正常工作。6.BIOS（BasicInputOutputSystem）基本輸入輸出系統：它是一組固化到計算機內主板上一個ROM芯片上的程序，它保存著計算機最重要的基本輸入輸出的程序、開機后自檢程序和系統自啟動程序，它可從CMOS中讀寫系統設置的具體信息。四、計算機學科知識1.程序設計語言分為機器語言、匯編語言、高

級語言。常用的高級語言：Fortran，Algol，Cobol，Pascal，C，C++，VisualBasic等；2.支持部分或絕大部分面向對象特征的語言成

為面向對象的語言。如Java，C#，Eiffel；

比較早的面向過程的語言業吸收了對象的概

念，如C->C++，Basic->VisualBasic，Pascal->ObjectPascal,Ada->Ada953.數據庫是長期純屬在計算機內，有組織、可共享的數據集合。數據庫管理系統是位于用戶和操作系統間的一層數據管理軟件。

四、計算機學科知識4.數據庫語言-SQL語言（結構化查詢語言）5.進制轉換

（1）二進制：由0和1組成，每位計滿2就向高位進1，即逢二進一；除了二進制，還會接觸到八進制、十六進制；為了區分我們常用下標“2”來表示，如（10）2=3；而十六進制中，我們通常用A，B，C….表示10,11,12…

（2）R進制轉化為十進制如二進制轉化為十進制：(110111)2=1*25+1*24+0*23+1*22+1*21+1*20=32+16+0+4+2+1=59四、計算機學科知識（3）十進制轉換成R進制(26)10=(11010)22613631222201011整數轉化倒著寫(0.3125)10=（0.0101）20.3125*2=0.625……整數部分為00.625*2=1.25……整數部分為10.25*2=0.5……整數部分為00.5*2=1……整數部分為1四、計算機學科知識（3）十進制轉換成R進制小數轉化順著寫注意：十進制小數常常不能準確地換算為等值的二進制小數，例如：四、計算機學科知識（3）十進制轉換成R進制(0.5627)10

轉換成二進制數0.5627*2=1.1254……整數部分為10.1254*2=0.2508……整數部分為00.2508*2=0.5016……整數部分為00.5016*2=1.0032……整數部分為1…此過程會不斷進行下去，因此只能取到一定精度：（0.5627）10=（0.1001）2四、計算機學科知識（4）二、八、十六進制相互轉換

由于這三個數制存在聯系，即23=824=16，所以每位八進制數相當于三位二進制數，每位十六進制數相當于四位二進制數。在轉換時，以小數點為中心，向左右兩邊延伸，兩頭不夠用0補；（1011010.10）2轉換成八進制和十六進制：八進制001011010.100132.4=（132.4）8十六進制01011010.10005A.8=（5A.8）166.計算機內碼

計算機中運算的數有正負之分，數的符號也用二進制表示（最高位），常用機器碼有原碼、反碼、補碼；

（1）原碼：正數符號位為0，負數符號位為1；

如：X=+1110001則X原=01110001X=-1110001則X原=11110001（2）反碼：符號位法則與原碼相同，負數時除

符號位其它各位取值求反；

如：X=+1110001則X反=01110001X=-1110001則X反=10001110四、計算機學科知識四、計算機學科知識

6.計算機內碼

（3）補碼：正數與原碼一致，負數在反碼的

基礎上末尾加一

如：X=+1110001則X補=01110001X=-1110001則X補=10001111

7.數之間的邏輯運算

與（and∧&）兩個都真才為真

或（or∨|）一個為真就為真

非（not┓!）反一反異或（xor⊕）同為0，異為10⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0四、計算機學科知識

8.運算優先級（由高到低）：一元運算（負號－、not）→乘除運算（*、/、div、mod、and）→加減運算（+、－、orxor）→關系運算（=、<>、<、>、<=、>=）

9.（1）ASCII碼（美國標準信息交換碼），用7位二進制數來編碼（占一個字節），可表示128個字符，ord(‘0’)=48ord(‘A’)=65ord(‘a’)=97（2）漢字編碼，一個漢字由兩個ASCII碼（94個）組成（兩個字節）。10.1Byte=8bit1KB=1024B以下單位均已1024倍轉換，從小到大為：ByteKBMBGBTBPBEBZB11.多媒體技術：用計算機綜合處理文本、圖形、圖像、音頻和視頻等多種媒體信息，使他們建立邏輯連接，即成為一個具有交互性的系統。12.三基色：紅、綠、藍，大多數的顏色可以

通過紅綠藍三色不同比例合成產生。四、計算機學科知識13.位圖與矢量圖（圖像與圖形）

位圖又稱點陣圖，有許多像素點構成；矢量圖：以數學向量的方式來計算圖像內容；四、計算機學科知識14.動態圖（GIF），每一幅畫面稱為一幀，由于人眼的視覺惰性，每秒24幀的電影畫面就形成了連續活動影像；15.音頻數字化（脈沖編碼調制技術PCM）包括采樣、量化、編碼三個步驟四、計算機學科知識16.病毒：是人編寫的用來破壞計算機功能或者數據的程序。具有傳播性、隱蔽性、感染性、潛伏性、可激發性、表現性或破壞性；

木馬：病毒的一種，不破壞不感染其他程序，以竊取數據為目的；17.防火墻、殺毒軟件、安全衛士

防火墻相當于防盜門防入侵，殺毒軟件則用于電腦內部殺毒，安全衛士修復漏洞優化系統；四、計算機學科知識18.黑客(hacker)：通常是指對計算機科學、編程和設計方面具高度理解的人；五、網絡知識1.網絡的分類：局域網LAN、城域網MAN、廣域網WAN；最大的廣域網：Internet2.網絡的主要功能（1）資源共享（2）信息傳輸（3）分布處理（4）綜合信息服務3.拓撲結構：總線拓撲、星型拓撲、環形拓撲五、網絡知識4.網絡協議：在計算機網絡中一系列的通信規則稱為網絡協議，如數據的格式是怎么樣的，以什么樣的控制信號聯絡，具體傳送方式是什么，發送法師怎么樣保證數據的完整性、正確性等等；這些都是網絡協議需要的功能。常見的網絡協議有TCP/IP協議，IPX/SPX協議；五、網絡知識5.OSI7層參考模型：

為了解決不同網絡中網絡協議可能不一致的情況，國際標準化組織在1981年推出了OSI標準。希望所有網絡系統向該標準靠攏，消除不同系統之間因協議不同造成的通信障礙。OSI不是一個實際的物理模型，僅僅是一個標準，網絡開發者可以根據這個標準開發網絡系統，制定網絡協議；五、網絡知識5.OSI7層參考模型：

通常把計算機網絡分成通信子網和資源子網兩部分，低三層為通信子網，高三層為資源子網，傳輸層起承上啟下作用；6.網絡的發展階段，4個階段（1）20世紀60年代中期之前，以單臺計算機為中心的遠程聯機系統（2）20世紀60年代中期至70年代，稱為計算機-計算機網絡（3）20世紀70年代末至90年代，開放式標準化的網絡（4）20世紀90年代末至今，新一代的計算機網絡五、網絡知識7.網絡操作系統：Windows類，NetWare類，Unix系統，LINUX系統五、網絡知識8.各英文縮寫匯總

FTP：文件傳輸協議HTTP：超文本傳輸協議POP3/SMTP：接收/發送郵件協議TCP：傳輸控制協議UDP：用戶數據報協議Telnet：遠程登錄P2P：點對點

9.云計算：一種按使用量付費的模式，這種模式提供便捷的、按需的網絡訪問，進入計算資源共享池（資源包括網絡，服務器，存儲，應用軟件，服務），這些資源能夠被快速提供，只需投入很少的管理工作或與服務供應商進行很少的交互。五、網絡知識10.網絡硬件系統

（1）服務器：一臺速度快，存儲量大的計算機，負責網絡資源管理和用戶服務；（2）工作站：具有獨立處理能力的計算機，用戶可以在工作站上處理日產工作，隨時向服務器索取信息，請求服務器提供服務；

（3）網卡（網絡適配器）：它的作用是將計算機與通信設備相連接，將計算機的數字信號轉換成通信線路能夠傳送的電子信號和電磁信號；

五、網絡知識10.網絡硬件系統

（4）調制解調器（modem，貓）：把計算機的數字信號“調制”成通信線路的模擬信號，將通信線路的模擬信號“解調”回計算機的數字信號；（5）路由器：它會根據信道的情況自動選擇和設定路由，以最佳路徑，按前后序發送信號。現在主要實現有線和無線、一支和多支的轉化；五、網絡知識10.網絡硬件系統

（6）交換機：主要用于企業中，多臺上網設備，如機房、一幢住宅樓；實現多臺上網設備之間的匯聚與數據交換；（7）中繼器用于完全相同的兩類網絡的互連，主要功能是通過對數據信號的重新發送或者轉發，來擴大網絡傳輸的距離。中繼器是對信號進行再生和還原的網絡設備；五、網絡知識（8）雙絞線（網線）由兩根具有絕緣保護層的銅導線組成（9）光纖：是一種由玻璃或塑料制成的纖

維，可作為光傳導工具。五、網絡知識光纖與雙絞線（10）無線網卡五、網絡知識10.IP地址Internet中的每一臺主機分配一個在全球范圍唯一地址。IPv4地址是由32位二進數碼表示的，每8個一段用“.”隔開，再把每一段的二進制數化成十進制數，也就得到我們現在所看到的IP地址形式，每個數字取值為0—255。如00IPv4地址分A、B、C、D、E五類，目前大量使用的是A、B、C三類，D類為Internet體系結構委員會IAB專用，E類保留在今后使用。最高位1..126為A類，128..191是B類，192..223是C類。五、網絡知識10.IP地址

IPv6用于替代現行版本IP協議（IPv4）的下一代IP協議，號稱可以為全世界的每一粒沙子編上一個網址。IPv6的地址長度為128位，是IPv4地址長度的4倍。一個IPv6地址中問可能包含很長的一段0，可以把連續的一段0壓縮為“::”五、網絡知識11.域名：ip地址對于使用者來說，太難記憶，于是又研究出一種字符型的地址：域名。域名地址采用層次結構，一個域名一般有3－5個子段，中間用“.”隔開。如：頂級域名有三類：國家頂級域名,如cn（中國）、us（美國）、uk（英國）；國際頂級域名:ini，國際性組織可在ini下注冊；通用頂級域名，如：com（商業機構）、

net（網絡服務機構）、edu（教育、科研機構）、

gov（政府）、org（專業團體）、……

六、數據結構1.數組二維數組/多維數組2.鏈表單鏈表、循環鏈表、雙向鏈表3.哈希表六、數據結構4.棧先進后出（FILO）5.隊列先進先出（FIFO）

循環隊列6.樹和二叉樹

高度、度、葉子

完全二叉樹、滿二叉樹

先序、中序、后序遍歷

最小生成樹六、數據結構7.堆：大根堆、小根堆8.圖：有向圖和無向圖完全圖最小生成樹算法：Prim算法和Kruskal算法

基于點基于邊最短路算法：Dijkstra算法和Floyd算法七、算法1.時空復雜度常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...，k次方階O(nk),指數階O(2n)2.遞歸和分治七、算法3.排序

選擇、插入、冒泡、快排、歸并4.貪心算法5.動態規劃七、算法6.搜索

廣度優先搜索BFS和深度優先搜索DFS7.高精度（壓位）八、數學1.對數函數（1）ab=N（a>0,a≠1），則b叫做以a為底N的對數，b=logaN。當a=10時稱作常用對數lgN，當a=e時稱作自然對數InN。（2）基本運算loga+logb=log（a*b）loga-logb=log（a/b）n*loga=log(an)logab/logac=logcblogab*logca=logcb（3）一棵完全二叉樹共有N個節點，它的深度是多少？Alog2NBlog2N+1C[log2N]D[log2N]+1[x]表示向下取整D八、數學2.排列與組合（1）排列：從n個不同元素中，任取m個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m