信息學(xué)競賽計(jì)算機(jī)基礎(chǔ)知識(shí)講義-范奐壘.doc

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