信息學競賽計算機基礎知識講義-范奐壘.doc

初試：初試全部為筆試，滿分100分。試題由四部分組成：1、選擇題：共20題，每題15分，共30分。每題有5個備選方案；前10個題為單選題門每題有且只有一個正確答案），后 10題為復選題（即每題有1至5個正確答案，只有全部選對才得分）。試題內(nèi)容包括計算機基本組成與原理、計算機基本操作、信息科技與人類社會發(fā)展的關(guān)系等等。2、問題求解題：共2題，每題5分，共10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。答案以字符串方式給出，考生給出的答案與標準答案的字符串相同，則得分；否則不得分。3、程序閱讀理解題：共4題，每題8分，共32分。題目給出一段程序（沒有關(guān)于程序功能的說明），有時也會給出程序的輸入，要求考生通過閱讀理解該段程序給出程序的輸出。輸出以字符串的形式給出，如果與標準答案一致，則得分；否則不得分。4、程序完善題：共 2題，每題 14分，共 28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對的，則得分；否則不得分。內(nèi)容與要求：1、計算機的基本常識計算機和信息社會(信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡的主要特征、數(shù)字化)信息輸入輸出基本原理(信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式)信息的表示與處理(信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu))信息的存儲、組織與管理(存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理)信息系統(tǒng)組成及互連網(wǎng)的基本知識(計算機構(gòu)成原理、槽和端口的部件間可擴展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡、TCPIP協(xié)議、HTTP協(xié)議、WEB應用的主要方式和特點)人機交互界面的基本概念(窗口系統(tǒng)、人和計算機交流信息的途徑(文本及交互操作)信息技術(shù)的新發(fā)展、新特點、新應用等。2、 計算機的基本操作WINDOWS和LINUX的基本操作知識聯(lián)網(wǎng)的基本使用常識 (網(wǎng)上瀏覽、搜索和查詢等)常用的工具軟件使用(文字編輯、電子郵件收發(fā)等)3、程序設計的基本知識數(shù)據(jù)結(jié)構(gòu)：程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點)浮點運算中的精度和數(shù)值比較一維數(shù)組(串)與線性表記錄類型(PASCAL)結(jié)構(gòu)類型(C)程序設計：結(jié)構(gòu)化程序設計的基本概念閱讀理解程序的基本能力具有將簡單問題抽象成適合計算機解決的模型的基本能力具有針對模型設計簡單算法的基本能力程序流程描述(自然語言偽碼NS圖其他)程序設計語言(PASCALCC+，)基本算法處理：初等算法(計數(shù)、統(tǒng)計、數(shù)學運算等)排序算法(冒泡法、插入排序、合并排序、快速排序)查找(順序查找、二分法)回溯算法計算機基礎知識1、 計算機的誕生與發(fā)展第一臺電子計算機的誕生：1946年世界上第一臺數(shù)字式電子計算機是由美國賓夕法尼亞大學的物理學家約翰莫克利和工程師普雷斯伯?？颂仡I導研制的取名為ENIAC的計算機。由于這臺計算機使用了電子器電子管和電子線路，因此其功能在當時確實是出類拔萃，例如，它可以在一秒鐘內(nèi)進行5000次加減法運算，3毫秒便可以進行一次乘法運算，與手工計算相比速度大大加快。但是，它也明顯地存在著缺點，它體積龐大，機器中約有18800只電子管，1500個繼電器，70000只電阻及其他各類電氣元件，重30噸，占地170平方米，運行時耗電量很大；存儲容量很小，只能存儲20個字長為10位的十進制數(shù)；另外，它采用線路連接的方法來編排程序，因此每次解題都要靠人工改接連線，準備時間大大超過實際計算時間；它沒有存儲程序的能力，不具備自動計算功能。計算機發(fā)展的四個階段與計算機相關(guān)的幾個重要人物：艾倫圖靈（Alan Turing）英國科學家，他是計算機人工智能技術(shù)的鼻祖。1937年他提出了能思考的計算機圖靈機的概念，推進了計算機理論的發(fā)展。圖靈機模型是一種抽象計算模型，用來精確定義可計算函數(shù)，是實現(xiàn)機器人的最基本的一個理論模型。1950年，艾倫圖靈發(fā)表題為計算機能思考嗎的論文，設計了著名的圖靈測驗，解決了如何判定機器人是否具有同人類相等的智力的問題。馮諾依曼 （John Von Neumann）1945年，他寫了一篇題為關(guān)于離散變量自動電子計算機的草案的論文，第一次提出了在數(shù)字計算機內(nèi)部的存儲器中存放程序的概念。這成為所有現(xiàn)代計算機的基礎理論，被稱為“馮諾依曼結(jié)構(gòu)”。如今，各式各樣的電腦無論看起來差別多大，實質(zhì)上絕大多數(shù)是屬于馮諾依曼結(jié)構(gòu)的。1.計算機硬件設備由：存儲器、運算器、控制器、輸入設備、輸出設備構(gòu)成2.存儲程序、程序控制：把計算過程描述為由許多命令按一定順序組成的程序，然后把程序和數(shù)據(jù)一起輸入計算機中，計算機對已存入的程序和數(shù)據(jù)處理后輸出結(jié)果3.采用二進制高登摩爾（Gordon Moore）“每過18個月，計算機芯片依賴的集成電路由于內(nèi)部晶體管數(shù)量的幾何級數(shù)的增長，而使性能幾乎提高一倍，同時集成電路的價格也恰好減少為原來的一半。”這就是計算機界著名的摩爾定律，他的發(fā)明人就是高登摩爾。1968年他與羅伯特諾伊斯一起率領一群工程師創(chuàng)建了一家叫集成電子的公司，簡稱“Intel”，這就是當今名震世界的英特爾公司。法國人帕斯卡于17世紀制造出的一種機械式加法機，是世界上第一臺機械式計算機。算盤是人類最早的手動計算工具，機械式計算機是在此之后出現(xiàn)的一種用機械技術(shù)來實現(xiàn)數(shù)學運算的計算工具。 英國著名詩人拜倫的女兒Ada Lovelace(愛達).由于她在程序設計上的開創(chuàng)性工作，Ada Lovelace被稱為世界上”第一位程序員”?！笆澜缟系谝晃卉浖こ處煛?。 董鐵寶是“中國第一個程序員”。董鐵寶1945年赴美國學習，在伊利諾伊大學學習、研究時，他參與了第一代電子計算機伊利亞克機的設計、編程和使用。董鐵寶于1956年回到中國并任教于北京大學，成為王選（計算數(shù)學專業(yè)院士）的老師。計算機的發(fā)展趨勢2、 計算機的應用1、數(shù)值計算：主要應用于彈道軌跡、高能物理等2、數(shù)據(jù)和信息處理：其特點是數(shù)據(jù)量大，但計算相對簡單。其中數(shù)據(jù)泛指計算機能處理的各種數(shù)字、圖形、文字，以及聲音、圖像等信息。數(shù)據(jù)處理指對數(shù)據(jù)的收集、存儲、加工、分析和傳送的全過程。主要應用于企業(yè)管理、物資管理等3、過程控制：是生產(chǎn)自動化的重要技術(shù)內(nèi)容和手段，是由計算機對所采集到的數(shù)據(jù)按一定方法經(jīng)過計算，然后輸出到指定執(zhí)行機構(gòu)去控制生產(chǎn)的過程。主要應用于工業(yè)自動化控制、衛(wèi)星飛行方向控制等。4、計算機輔助系統(tǒng)：是指利用計算機幫助人們完成各種任務，包括：CAD：計算機輔助設計；CAM：計算機輔助制造；CAI：計算機輔助教學；CAT：計算機輔助測試；CAE：計算機輔助工程； CIMS：計算機集成制造系統(tǒng)5、人工智能：是指用計算機模擬人腦的思維過程，是計算機應用的重要領域。3、 計算機分類和性能指標1、 按規(guī)模分：巨型、大型、中型、小型、微型計算機。我們學校和家庭使用的計算機都微型計算機，簡稱微機，又稱個人計算機，或簡稱PC機。2、按用途分：專業(yè)計算機、通用計算機。3、按原理分：模擬計算機、數(shù)字計算機。1、字長：指計算機能夠直接處理的二進制數(shù)據(jù)的位數(shù)。單位為位（BIT）。2、主頻：指計算機主時鐘在一秒鐘內(nèi)發(fā)出的脈沖數(shù)，在很大程度上決定了計算機的運算速度。3、內(nèi)存容量：是標志計算機處理信息能力強弱的一向技術(shù)指標。單位為字節(jié)（BYTE）。8BIT=1BYTE 1024B=1KB 1024KB=1MB4、外存容量：一般指軟盤、硬盤、光盤。4、 計算機系統(tǒng)組成1.計算機硬件系統(tǒng)計算機系統(tǒng)由硬件系統(tǒng)和軟件系統(tǒng)組成。硬件是軟件賴以生存的驅(qū)殼，軟件卻是硬件的靈魂。光只有硬件的裸機是無法工作的，而軟件則必須存放在硬件中。只有硬件沒有安裝軟件的計算機稱為“裸機”計算機硬件是指有形的物理設備，它是計算機系統(tǒng)中實際物理設備的總稱，由各種元器件和電子線路組成。計算機硬件系統(tǒng)主要包括運算器、控制器、存儲器(分為主存儲器、輔助存儲器)、輸入設備、輸出設備，并且由總線將它們連接在一起。其中：運算器是對數(shù)據(jù)進行運算和加工，完成算術(shù)和邏輯運算的部件；控制器是計算機的指揮中心，控制各部分協(xié)調(diào)工作，完成對指令的解釋和執(zhí)行；運算器和控制器被集成在一起，統(tǒng)稱為中央處理器，簡稱CPU（Central Processing Unit），是計算機的“中樞神經(jīng)”。中央處理器是計算機的心臟，CPU品質(zhì)的高低直接決定了計算機系統(tǒng)的檔次。能夠處理數(shù)據(jù)的位數(shù)是CPU的一個最重要的品質(zhì)標志。人們通常所說的8位機、16位機、32位機即指CPU可同時處理8位、16位、32位的二進制數(shù)據(jù)。如：計算機的配置：“Intel奔騰IV2.8GHz/512M/80GB/50X” 每秒運算次數(shù)是：2.8*210*210*210CPU、主存儲器構(gòu)成了計算機的主機，輸入輸出設備和輔助存儲器則統(tǒng)稱為外部設備，簡稱外設。存儲器是記憶部件，用于存放程序和數(shù)據(jù)。 主存儲器又稱內(nèi)存或主存，它直接與CPU交換信息，是計算機的工作存儲器，即當前正在運行的數(shù)據(jù)和程序都必須存放在主存內(nèi)，它的存取速度快但容量較小(容量太大，成本昂貴)。主存又可分為隨機存儲器RAM(Random Access Memory)和只讀存儲器ROM(Read Only Memory)兩類。隨機存儲器RAM中的內(nèi)容可以進行讀寫操作，但斷電時RAM中的信息會丟失。ROM的內(nèi)容只能反復讀取，而不能重新寫入，因此在ROM中存放固定不變的程序和數(shù)據(jù)，斷電后其內(nèi)容仍然保留。輔助存儲器又稱外存，它需要通過內(nèi)存才能與CPU聯(lián)系，輔助存儲器存取速度慢而容量較大。硬磁盤（HDD）：容量大、速度快、價格高。軟磁盤（FDD）：容量小，速度慢，便于攜帶、價廉。光盤（CD）：容量較大、價格便宜、便于攜帶。信息的輸入和輸出要通過輸入輸出設備來完成。 總線是連接計算機中各組成部件的一組物理信號線及相關(guān)的控制電路，總線一般都指系統(tǒng)總線。系統(tǒng)總線上有三類信號：數(shù)據(jù)信號、地址信號和控制信號。負責在部件間傳輸數(shù)據(jù)的一組信號線稱為數(shù)據(jù)總線（DB）；負責指出數(shù)據(jù)存放的存儲位置的一組信號線(也可標識是哪一個IO設備)稱為地址總線（AB）；在傳輸與交換數(shù)據(jù)時起控制作用的一組控制信號線稱為控制總線（CB）。由運算器、存儲器、控制器、輸入、輸出設備五大基本部件組成計算機硬件系統(tǒng)，工作流程如圖：多級存貯器體系為提高CPU的處理速度，當今計算機中大都配有高速緩沖存儲器（cache），也稱緩存，實際上是一種特殊的高速存儲器。緩存的存取速度比內(nèi)存要快，所以就提高了處理速度。多數(shù)現(xiàn)代計算機都配有兩級緩存。一級緩存也叫做主緩存，或內(nèi)部緩存，直接設計在CPU芯片內(nèi)部。一級緩存容量很小，通常在8KB 64KB之間。二級緩存也叫外部緩存，不在CPU內(nèi)部而是獨立的SRAM芯片，其速度比一級緩存稍慢，但容量較大，多在64KB 2MB之間。人們討論緩存時，通常是指外部緩存。存貯速度最快的而容量最小的要算CPU內(nèi)部的寄存器。當CUP需要指令或數(shù)據(jù)時，實際檢索存儲器的順序是：首先檢索一級緩存，然后二級緩存，再往后是RAM。即寄存器一級緩存主存二級緩存輔存。2.計算機軟件系統(tǒng) 計算機軟件又稱計算機程序，是控制計算機實現(xiàn)用戶需求的計算機操作以及管理計算機自身資源的指令集合，是指在硬件上運行的程序和相關(guān)的數(shù)據(jù)及文檔，是計算機系統(tǒng)中不可缺少的主要組成部分，可分成兩大部分：系統(tǒng)軟件和應用軟件。 一、系統(tǒng)軟件：是計算機最基本的軟件，它負責實現(xiàn)操作者對計算最基本的操作，管理計算機的軟件與硬件資源，具有通用性，主要由計算機廠家和軟件公司開發(fā)提供。主要包括操作系統(tǒng)、語言處理程序、數(shù)據(jù)庫管理系統(tǒng)和服務程序。操作系統(tǒng)：是控制和管理計算機的軟硬件資源、合理安排計算機的工作流程以及方便用戶的一組軟件集合，是用戶和計算機的接口。DOS、Windows、UNIX等是操作系統(tǒng)，Windows是最常用的操作系統(tǒng)。語言處理程序：將用匯編語言和高級語言編寫的源程序翻譯成機器語言目標程序的程序。數(shù)據(jù)庫管理系統(tǒng)：是對計算機中所存儲的大量數(shù)據(jù)進行組織、管理、查詢并提供一定處理功能的大型計算機軟件。服務程序：為計算機系統(tǒng)提供各種服務性、輔助性的程序。二、應用軟件：是為解決實際問題所編寫的軟件的總稱，涉及到計算機應用的各個領域。絕大多數(shù)用戶都需要使用應用軟件，為自己的工作和生活服務。如字表處理軟件WPSoffice、Word、Excel等。根據(jù)上述軟硬件資源的關(guān)系，人們通常把一臺完整的計算機劃分成四個結(jié)構(gòu)層次，稱為四個平臺。它們從底層到高層分別為硬件平臺、系統(tǒng)平臺、應用支持平臺和應用平臺。與用戶直接相關(guān)、打交道最多的是應用平臺。三、幾個相關(guān)概念、指令：指令就是指揮機器工作的指示和命令，程序就是一系列按一定順序排列的指令，執(zhí)行程序的過程就是計算機的工作過程。一條指令包含操作碼和地址碼兩個部分，操作碼指示計算機怎么操作，地址碼指定操作對象或操作數(shù)據(jù)在存貯器中的存放位置。格式：操作碼操作數(shù)地址指令：一組二進制代碼，是規(guī)定計算機執(zhí)行程序的一步操作。程序：為解決某一問題而設計的一系列指令。指令系統(tǒng)：計算機能識別并能執(zhí)行的全部指令的集合。 、把一系列的計算機指令組織起來，用來控制計算機完成每一項任務的指令集合，被稱為計算機程序。許多計算機程序，就構(gòu)成了計算機軟件系統(tǒng)。、機器語言機器指令：能直接被計算機接受并執(zhí)行的指令。機器語言：由全部的機器指令構(gòu)成的二進制代碼語言。機器語言程序：用機器語言編制的程序，機器語言程序可以直接在計算機上運行。缺點：不便于記憶、閱讀和書寫。、匯編語言匯編語言：用助記符號表示二進制代碼的語言，是機器語言的符號化。匯編語言程序：用匯編語言編制的程序，匯編語言程序不能直接在計算機上運行。匯編過程：執(zhí)行匯