信息學(xué)奧賽基礎(chǔ)知識提綱.doc

信息學(xué)競賽知識梳理信息學(xué)奧賽基礎(chǔ)知識提綱 （2014年9月）1 計(jì)算機(jī)系統(tǒng)11概述一個(gè)完整的計(jì)算機(jī)系統(tǒng)包括硬件系統(tǒng)和軟件系統(tǒng)兩大部分，必須具有五大功能：數(shù)據(jù)傳送功能、數(shù)據(jù)存儲功能、數(shù)據(jù)處理功能、操作控制功能、操作判斷功能。它的工作特點(diǎn)是：運(yùn)算速度快、運(yùn)算精度高、記憶能力強(qiáng)、通用性廣、自動運(yùn)算。計(jì)算機(jī)按照規(guī)?？煞譃椋壕扌蜋C(jī)、大型機(jī)、中型機(jī)、小型機(jī)、微型機(jī)、單片機(jī)等幾種類型。根據(jù)用途不同分為通用機(jī)和專用機(jī)。硬件指的是計(jì)算機(jī)的設(shè)備實(shí)體；軟件通常泛指各類程序和文件。軟硬件的關(guān)系：硬件是軟件的基礎(chǔ)。軟件是硬件的擴(kuò)充與完善。硬件與軟件在邏輯上是等價(jià)的。1946年，世界上第一臺計(jì)算機(jī)誕生于賓夕法尼亞大學(xué)，稱為ENIAC。1949年,第一臺存儲計(jì)算機(jī)EDSAC,英國劍橋大學(xué)威爾克斯（Wilkes）設(shè)計(jì)和制造的。1951年，第一臺商用計(jì)算機(jī)是UNIVAC。按照計(jì)算機(jī)采用的電子器件可劃分為四代，分別是：第一代19461958第二代19581964第三代1964-1975第四代1975至今主要電子器件電子管晶體管集成電路大規(guī)模及超大規(guī)模集成電路內(nèi)存汞延遲線磁芯存儲器半導(dǎo)體存儲器半導(dǎo)體存儲器外存儲器穿孔卡片、紙帶磁帶磁帶、磁盤磁盤、光盤等大容量存儲器處理速度（指令數(shù)/秒）幾千條幾百萬條幾千萬條數(shù)億條以上12 硬件系統(tǒng)121 馮諾伊曼（J.von Neumann）機(jī)：美籍匈牙利數(shù)學(xué)家現(xiàn)代計(jì)算機(jī)的基本結(jié)構(gòu)被稱為馮諾伊曼結(jié)構(gòu)。它的主要特點(diǎn)是儲存程序的概念：（1） 采用二進(jìn)制形式表示數(shù)據(jù)和指令。（2） 將程序（包括操作指令和操作數(shù)）事先存入主存儲器中，使計(jì)算機(jī)在工作時(shí)能夠自動高速地從存儲器中取出指令加以執(zhí)行。（3） 由運(yùn)算器、存儲器、控制器、輸入設(shè)備、輸出設(shè)備五大基礎(chǔ)部件組成計(jì)算機(jī)系統(tǒng)。122 計(jì)算機(jī)的總線結(jié)構(gòu)計(jì)算機(jī)的各個(gè)部件需要以某種方式互聯(lián)，進(jìn)行數(shù)據(jù)交換。最常見的互聯(lián)結(jié)構(gòu)就是總線互聯(lián)結(jié)構(gòu)和多總線互聯(lián)結(jié)構(gòu)?？偩€是一種連接多種設(shè)備的信息傳遞通道，實(shí)際上是一組信號線。典型的計(jì)算機(jī)總線結(jié)構(gòu)由內(nèi)部總線和系統(tǒng)總線組成。（1） 內(nèi)部總線：用于連接CPU內(nèi)部的各個(gè)模塊。（2） 系統(tǒng)總線：又稱外部總線，用于連接CPU、存儲器和輸入輸出設(shè)備。系統(tǒng)總線的信號線分為三類：數(shù)據(jù)線、地址線和控制線。數(shù)據(jù)線（Data Bus）：數(shù)據(jù)總線的寬度就是指組成數(shù)據(jù)總線的信號線的數(shù)目，它決定了在該總線上一次可以傳送的二進(jìn)制位數(shù)。地址線（Address Bus）：用以傳遞地址信息，來指示數(shù)據(jù)總線上的數(shù)據(jù)來源和去向。地址線的數(shù)目決定了能夠訪問空間的大小?？刂凭€（Control Bus）：用來控制數(shù)據(jù)總線和地址總線。某SRAM芯片，其存儲容量為64K*16位，則該芯片的地址線數(shù)目和數(shù)據(jù)線的數(shù)目？123 中央處理器（Central Processor Unit）1、CPU包含了馮機(jī)五大部件中的運(yùn)算器（即加法器）和控制器。運(yùn)算器：對信息加工和處理的部件，主要完成各種算術(shù)運(yùn)算和邏輯運(yùn)算。控制器：通過讀取各種指令，并進(jìn)行翻譯、分析，而后對各部件作出相應(yīng)的控制。輸 出 門A L U輸入選擇門A輸入選擇門B通用寄存器組.+12、CPU主要由三大部分組成：寄存器組、算術(shù)邏輯單元（ALU）和控制單元（控制器）。寄存器組：分為通用寄存器（通用寄存器、數(shù)據(jù)寄存器、地址寄存器、標(biāo)志寄存器）和狀態(tài)控制寄存器（程序計(jì)數(shù)器PC、指令寄存器IR、存儲器地址寄存器MAR、存儲器緩沖寄存器MBR）以及程序狀態(tài)字PSW。算術(shù)邏輯單元ALU： 寄存器、存儲器、I/O設(shè)備把待處理的數(shù)據(jù)輸入到ALU。控制單元：控制器的基本功能就是時(shí)序控制和執(zhí)行控制。根據(jù)當(dāng)前運(yùn)行的程序，控制器使CPU按一定的時(shí)序關(guān)系執(zhí)行一序列的微操作從而完成程序。時(shí)鐘信號：控制器根據(jù)時(shí)鐘電路產(chǎn)生的時(shí)鐘信號進(jìn)行定時(shí)，以控制各種操作按指定的時(shí)序進(jìn)行。計(jì)算機(jī)的基本功能是執(zhí)行程序，而程序由一連串的指令組成；計(jì)算機(jī)的執(zhí)行過程由一連串的指令周期組成，每一指令周期完成一條指令。這些指令周期又可進(jìn)一步細(xì)分為更小的單元，直到微操作uop-CPU完成的基本的原子操作。 時(shí)鐘脈沖發(fā)生器的晶振頻率成為機(jī)器的主頻，它產(chǎn)生的時(shí)鐘脈沖信號是整個(gè)機(jī)器的時(shí)間基準(zhǔn)，其周期T稱為該計(jì)算機(jī)的時(shí)鐘周期。 完成一個(gè)微操作的時(shí)間就稱為CPU周期（機(jī)器周期）。執(zhí)行一條機(jī)器指令所需的時(shí)間稱為一個(gè)指令周期。3、指令系統(tǒng)（精簡指令系統(tǒng)）：操作類指令和控制類指令一條指令：操作碼 + 地址碼 一條機(jī)器指令的執(zhí)行：取指令分析指令執(zhí)行指令4、CPU的主要指標(biāo)有：字長：CPU一次所能處理的二進(jìn)制位數(shù)。它決定著寄存器、加法器、數(shù)據(jù)總線等的位數(shù)。主頻：計(jì)算機(jī)的時(shí)鐘頻率。（即內(nèi)頻）單位：MHz或GHz。運(yùn)算速度：CPU每秒鐘能完成的指令數(shù)MIPS。運(yùn)算速度=1 執(zhí)行一條機(jī)器指令所需的時(shí)間124 存儲器存儲單位：（1） 最小單位：位（bit，縮寫b），（2） 基本單位：字節(jié)（Byte，縮寫B(tài)）（3） 常用單位： 1KB(1千字節(jié) )= 1024B 1MB (兆字節(jié))=1024KB 1GB(1千兆字節(jié))= 1024MB 1TB=1024GB存儲器的分類關(guān)系如圖：圖 2內(nèi)存儲器：又稱主存，存儲器按字節(jié)編址。（1） ROM：斷電后信息不會喪失，但是信息只能讀出不能寫入。（BIOS）（2） RAM：信息可讀出和寫入，斷電后信息全部丟失。（如“內(nèi)存”、“顯存”等）外存儲器：又稱作輔助存儲器。外存儲器是一般容量較大且可以移動。例如：硬盤、軟盤、光盤、ZIP盤、MO光磁盤、USB存儲器等。計(jì)算機(jī)硬件系統(tǒng)存取信息的方式如圖：CPUCache(緩存)RAM(主存)Disk( 輔存)存儲器的主要性能指標(biāo)是存儲容量和存取周期（存取周期與存取速度成反比）存儲容量：輔存主存緩存；存取速度：緩存主存輔存125 輸入輸出（I/O）設(shè)備輸入設(shè)備：鍵盤、鼠標(biāo)、光筆、數(shù)字化儀、圖形掃描儀、攝像機(jī)等。輸出設(shè)備：顯示器、打印機(jī)、繪圖儀、磁盤驅(qū)動器等。顯示器：分為陰極射線管（CRT）和液晶顯示（LCD/TFT）兩種。其主要性能指標(biāo)是分辨率。（其他還有如點(diǎn)距、刷新率等）。126 非馮諾伊曼型計(jì)算機(jī)到目前為止，各種類型的計(jì)算機(jī)都屬于馮諾伊曼型計(jì)算機(jī)。正在研制中的第五代智能計(jì)算機(jī)，將具有自動識別自然語言、圖形、圖像的能力，具有理解和推理的能力，具有知識獲取、知識更新的能力，可望突破當(dāng)前計(jì)算機(jī)的結(jié)構(gòu)模式。研制朝兩個(gè)反向努力：1、 創(chuàng)建非馮諾伊曼式語言： LISP、 PROLOG（人工智能語言，用邏輯設(shè)計(jì)取代程序設(shè)計(jì)）、 F.P.（供理論研究用的理想語言）2、 創(chuàng)建以人腦神經(jīng)系統(tǒng)處理信息原理為基礎(chǔ)的非馮諾伊曼式的計(jì)算機(jī) 生物計(jì)算機(jī)、光子計(jì)算機(jī)、量子計(jì)算機(jī)13 軟件系統(tǒng)：包括系統(tǒng)軟件和應(yīng)用軟件。系統(tǒng)軟件：系統(tǒng)軟件指管理、監(jiān)控和維護(hù)計(jì)算機(jī)資源（包括硬件和軟件）的軟件，主要包括操作系統(tǒng)、各種程序設(shè)計(jì)語言及其解釋編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)等。系統(tǒng)軟件中最重要的是操作系統(tǒng)。應(yīng)用軟件：用戶利用計(jì)算機(jī)及其提供的系統(tǒng)軟件為解決各種實(shí)際問題而編制的計(jì)算機(jī)程序。 131 操作系統(tǒng)（Operating System）1、常見的操作系統(tǒng)操作系統(tǒng)建立了用戶與計(jì)算機(jī)之間的接口。當(dāng)前常見的操作系統(tǒng)有DOS（微軟公司，Disk Operating System磁盤操作系統(tǒng)）、Windows 9x/Me/NT/2000/XP（微軟公司，視窗系列操作系統(tǒng)）、UNIX、Linux、SunOS（升陽公司）、IBM OS/2等。DOS是一個(gè)單用戶單任務(wù)操作系統(tǒng)，Windows 95是一個(gè)單用戶多任務(wù)操作系統(tǒng)，Windows NT/2000/XP等屬于多用戶多任務(wù)操作系統(tǒng)。UNIX（多任務(wù)分時(shí)操作系統(tǒng)，網(wǎng)絡(luò)操作系統(tǒng)）：20世紀(jì)70年代初期由美國貝爾實(shí)驗(yàn)室用C語言開發(fā)的。在所有比微機(jī)性能更好的工作站型計(jì)算機(jī)上，都是使用該操作系統(tǒng)。Linux網(wǎng)絡(luò)操作系統(tǒng)。是一個(gè)與UNIX完全兼容的免費(fèi)操作系統(tǒng)，它的內(nèi)核全部重新編寫，并公布了所有源代碼。Linux由芬蘭人Linux Torvalds首創(chuàng)，現(xiàn)在已經(jīng)成為一個(gè)穩(wěn)定可靠、功能完善、性能卓越的操作系統(tǒng)。 2、操作系統(tǒng)的主要功能包括：處理機(jī)管理；存儲管理；設(shè)備管理；文件管理；作業(yè)管理。 3、操作系統(tǒng)管理控制方式：A、分時(shí)操作系統(tǒng)：一臺計(jì)算機(jī)連接多個(gè)終端，分時(shí)系統(tǒng)把CPU的運(yùn)行時(shí)間分成很短的時(shí)間片，按時(shí)間片輪流把CPU分配給各聯(lián)機(jī)作業(yè)使用。B、實(shí)時(shí)操作系統(tǒng)：系統(tǒng)響應(yīng)速度快，他要求計(jì)算機(jī)對輸入的信息做出及時(shí)響應(yīng)，并在規(guī)定時(shí)間內(nèi)完成任務(wù)。C、網(wǎng)絡(luò)操作系統(tǒng)：網(wǎng)絡(luò)用戶與計(jì)算機(jī)網(wǎng)絡(luò)之間的接口。通過通信子網(wǎng)實(shí)現(xiàn)數(shù)據(jù)通信，通過資源子網(wǎng)進(jìn)行數(shù)據(jù)處理，實(shí)現(xiàn)共享。132 程序設(shè)計(jì)語言世界上第一位程序員：英國著名詩人拜倫的女兒Ada Lovelace程序設(shè)計(jì)語言是用戶用來編寫程序的語言。它分為機(jī)器語言、匯編語言和高級語言。機(jī)器語言是最底層的計(jì)算機(jī)語言。它的特點(diǎn)是用機(jī)器語言編寫的程序，每條指令都是二進(jìn)制形式的指令代碼，由和組成。計(jì)算機(jī)硬件可以直接識別，執(zhí)行速度快，但不易調(diào)試、修改，程序的直觀性差、移植性差。所謂指令是指一種規(guī)定CPU執(zhí)行某種特定操作的命令，也稱為機(jī)器指令，它包括操作碼和地址碼。 機(jī)器語言低級語言編譯或解釋匯編匯編語言匯編語言是用指令助記符合地址符號書寫的指令。用匯編指令編寫的程序成為匯編語言源程序。計(jì)算機(jī)不能直接識別匯編語言編寫的源程序，必須由翻譯程序翻譯成機(jī)器語言程序才能執(zhí)行，執(zhí)行效率較高，相對機(jī)器語言程序而言，易讀、易檢查、易修改，但其通用性和移植性仍較差。翻譯的過程稱為，負(fù)責(zé)翻譯的程序稱之為匯編程序。高級語言面向?qū)ο缶幊陶Z言（OOPLs） ：C+，Dephi，Visual Basic，Java，SmallTalk，Object Pascal等。Smalltalk是最早的純面向?qū)ο缶幊陶Z言之一。面向?qū)ο缶幊陶Z言結(jié)構(gòu)化程序設(shè)計(jì)語言結(jié)構(gòu)化程序設(shè)計(jì)語言：FORTRAN、BASIC、PASCAL、C等。 Ada語言是迄今為止 最復(fù)雜，最完備的軟件工具。美國國防部指定的 唯一的一種可用于軍用系統(tǒng)開發(fā)的語言，我國軍方也將Ada做為軍內(nèi)開發(fā)標(biāo)準(zhǔn)（GJB 1383程序設(shè)計(jì)語言Ada）。133 應(yīng)用軟件由于計(jì)算機(jī)有大量的應(yīng)用軟件，它在生活、生產(chǎn)中的應(yīng)用很廣泛。專門用途的應(yīng)用軟件如字處理軟件（如Word）、財(cái)務(wù)軟件、圖形處理軟件（如PhotoShop）已經(jīng)深入了我們的生活。計(jì)算機(jī)常見的應(yīng)用還包括計(jì)算機(jī)輔助教學(xué)（CAI）、計(jì)算機(jī)輔助制造（CAM）、計(jì)算機(jī)輔助設(shè)計(jì)（CAD）等。1-3-6知識產(chǎn)權(quán) 1997 年中華人民共和國刑法 界定了計(jì)算機(jī)犯罪 1991年 計(jì)算機(jī)軟件保護(hù)條例 計(jì)算機(jī)知識產(chǎn)權(quán)方面的法律法規(guī) 2001年11月全國青少年網(wǎng)絡(luò)文明公約針對青少年使用網(wǎng)絡(luò)，團(tuán)中央、教育部等部門 2001年12月公布了新的計(jì)算機(jī)軟件保護(hù)條例，即計(jì)算機(jī)軟件是受法律保護(hù)的，不可以隨便復(fù)制、盜版。137 計(jì)算機(jī)病毒計(jì)算機(jī)病毒指的是會影響計(jì)算機(jī)系統(tǒng)正常工作的一類特殊的程序，它的主要特點(diǎn)是傳播性、潛伏性、破壞性與隱蔽性。按照計(jì)算機(jī)病毒存在的媒體和傳播方式分類，可以把它分為文件型、引導(dǎo)區(qū)型、網(wǎng)絡(luò)型、混合型、宏病毒等。網(wǎng)絡(luò)病毒通過計(jì)算機(jī)網(wǎng)絡(luò)傳播感染網(wǎng)絡(luò)中的可執(zhí)行文件，文件病毒感染計(jì)算機(jī)中的文件（如：com，exe等），引導(dǎo)型病毒感染啟動扇區(qū)（Boot）和硬盤的系統(tǒng)引導(dǎo)扇區(qū)（MBR），還有這三種情況的混合型，例如：多型病毒（文件和引導(dǎo)型）感染文件和引導(dǎo)扇區(qū)兩種目標(biāo)。計(jì)算機(jī)病毒通常都具有復(fù)雜的算法或者很好的心理學(xué)特性。137 數(shù)據(jù)庫（DB-DataBase）1、 數(shù)據(jù)庫的基本概念：在計(jì)算機(jī)存儲設(shè)備上存儲的數(shù)據(jù)集合。建立在微型機(jī)上的關(guān)系型數(shù)據(jù)庫是一張二維表格。2、 數(shù)據(jù)庫特性：（1） 最小冗余：數(shù)據(jù)盡可能不重復(fù)存儲（2） 數(shù)據(jù)共享：數(shù)據(jù)可以為多個(gè)用戶程序服務(wù)（3） 數(shù)據(jù)獨(dú)立性：DB中數(shù)據(jù)與應(yīng)用程序不存在依賴關(guān)系（4） 安全性：保護(hù)DB以防止不合法使用（5） 完整性：存取DB的過程中要確保其正確性、一致性和有效性。3、 常見的數(shù)據(jù)庫管理系統(tǒng)（DBMS）：（1） 高檔數(shù)據(jù)庫產(chǎn)品（分布式數(shù)據(jù)庫管理軟件）：Oracle，Infomix，Sybase，DB2（2） 中、低檔數(shù)據(jù)庫產(chǎn)品(集中式)：Foxpro，DBASE, Access,（3） 數(shù)據(jù)庫開發(fā)工具：Access，Visual Basic，Power Builder，SQL Server ,My SQL?；冢–lient/Server）客戶機(jī)/服務(wù)器環(huán)境中的數(shù)據(jù)庫開發(fā)工具。4、 SQL-數(shù)據(jù)庫的結(jié)構(gòu)查詢語言 select 學(xué)號，姓名 From 學(xué)生表 insert into 學(xué)生表 values(學(xué)號，姓名)14 計(jì)算機(jī)中的數(shù)據(jù)表示141 數(shù)據(jù)類型及其存儲:計(jì)算機(jī)里用到的數(shù)據(jù)類型主要可以分為兩類：表示數(shù)量的數(shù)值數(shù)據(jù)和非數(shù)值性的符號數(shù)據(jù)。所有的數(shù)據(jù)都是以二進(jìn)制的形式在計(jì)算機(jī)里處理和存儲。143 進(jìn)制的運(yùn)算和轉(zhuǎn)換1、N進(jìn)制的數(shù)據(jù)就是由0N1這N個(gè)數(shù)字按照一定的順序排列組合，運(yùn)算上逢N進(jìn)一的數(shù)。（即以N為基數(shù)的數(shù)據(jù)）常見的進(jìn)制有二進(jìn)制（BINary）、八進(jìn)制（OCTonary）、十進(jìn)制（DECimalism），十六進(jìn)制（HEXadecimal）。二進(jìn)制的運(yùn)算分為算術(shù)運(yùn)算與邏輯運(yùn)算兩種：（1） 常用的算術(shù)運(yùn)算（進(jìn)位和借位）： 加法：0000111011110 減法：0001011101110（2） 常用的邏輯運(yùn)算（逐位進(jìn)行）： 邏輯或（OR）：000011101111 邏輯與（AND）：0000101001112、十進(jìn)制數(shù)轉(zhuǎn)換成N進(jìn)制數(shù)：整數(shù)部分除N取余，小數(shù)部分乘N取整第 11 頁 共 12 頁 整數(shù)部分的轉(zhuǎn)換：除二取余例如：(19)10(10011)2 小數(shù)部分的轉(zhuǎn)換：乘2取整例如：(0.125)10(0.001)2并非所有的十進(jìn)制小數(shù)都能用有限位的二進(jìn)制小數(shù)來表示。如(0.63)10。3、 二進(jìn)制與十六、八進(jìn)制的轉(zhuǎn)換1個(gè)十六進(jìn)制位=4個(gè)二進(jìn)制位 1個(gè)八進(jìn)制位=3個(gè)二進(jìn)制位二進(jìn)制0000000100100011010001010110011116進(jìn)制01234567二進(jìn)制1000100110101011110011011110111116進(jìn)制89ABCDEF表1 二進(jìn)制與十六進(jìn)制數(shù)字對照表二進(jìn)制000001010011100101110111八進(jìn)制01234567表2 二進(jìn)制與八進(jìn)制數(shù)字對照表4、 N進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)(各位數(shù)字與權(quán)植乘積累加) (ABCDE.FG)n =A*n4+B*n3+C*n2+D*n1+E*n0+F*n-1 + G*n-2142 數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的存儲為了解決數(shù)據(jù)的表示范圍問題，計(jì)算機(jī)中存儲的數(shù)值數(shù)據(jù)分為定點(diǎn)數(shù)據(jù)和浮點(diǎn)數(shù)據(jù)兩類。定點(diǎn)數(shù)據(jù)是各種數(shù)據(jù)類型中最簡單、最基本的一種數(shù)據(jù)表示，它用以表示二進(jìn)制形式具有固定比例換算的量（即小數(shù)點(diǎn)的位置固定不變）。由于定點(diǎn)位置的不同，定點(diǎn)數(shù)一般分為兩類：整數(shù)（Integer，小數(shù)點(diǎn)固定于最低位右邊的數(shù)）和小數(shù)（Fraction，小數(shù)點(diǎn)固定于數(shù)的左端，在20與21之間，又稱為分?jǐn)?shù)）。計(jì)算機(jī)中浮點(diǎn)數(shù)據(jù)表示的基本原理來源于十進(jìn)制數(shù)中使用的科學(xué)記數(shù)法。一個(gè)數(shù)N的科學(xué)記數(shù)法形式可寫成：NMRE。其中M代表尾數(shù)，E代表階碼，R代表基數(shù)。當(dāng)尾數(shù)、階碼采用二進(jìn)制，基數(shù)R2時(shí)，就是計(jì)算機(jī)中的浮點(diǎn)數(shù)據(jù)表示。浮點(diǎn)數(shù)是實(shí)數(shù)的一種近似表示，存在下溢和上溢，浮點(diǎn)數(shù)格式必須兼顧表示范圍及表示精度的要求。浮點(diǎn)數(shù)的一般表示方式如下：符號階碼E（定點(diǎn)整數(shù)）尾數(shù)M（定點(diǎn)小數(shù)）144 定點(diǎn)數(shù)據(jù)的編碼為了解決數(shù)據(jù)的正、負(fù)問題，定點(diǎn)數(shù)據(jù)引入數(shù)據(jù)的原碼、反碼、補(bǔ)碼表示。位運(yùn)算：not 二進(jìn)制按位取反 and 二進(jìn)制按位與 shr 二進(jìn)制按位右移shl 二進(jìn)制按位左移 or 二進(jìn)制按位或 xor 二進(jìn)制按位異或采用補(bǔ)碼制進(jìn)行運(yùn)算，所以必須確定該數(shù)存儲的字節(jié)數(shù)，再決定該數(shù)的補(bǔ)碼。原理一個(gè)字節(jié)表示的數(shù)據(jù)范圍舉例原碼用最高位（最左位）來表示數(shù)的符號，0為正數(shù)，1為負(fù)數(shù)127127共255個(gè)數(shù)（0）原00000000（0）原100000000010101143，1010101143。反碼正數(shù)的反碼都與它的原碼相同，負(fù)數(shù)的反碼則是它的逐位取反（符號位不變）127127共255個(gè)數(shù)（0）反00000000（0）反11111111(56)原(56)反00111000(56)原10111000(56)反11000111補(bǔ)碼正數(shù)的補(bǔ)碼也與它的原碼相同，負(fù)數(shù)的補(bǔ)碼等于它的反碼加一（進(jìn)位自然舍去）128127共256個(gè)數(shù)(-0)補(bǔ)=11111111+00000001（1）00000000（）補(bǔ)(-1)補(bǔ)=11111111(-2)補(bǔ)=11111110（-128）補(bǔ)=10000000(56)原=(56)反=(56)補(bǔ)00111000（56）補(bǔ)11001000145 非數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的存儲1、ASCII（美國標(biāo)準(zhǔn)信息交換代碼）, 一個(gè)西文字符用一個(gè)7位的ASCII碼表示，最高位填0，存儲需要一個(gè)字節(jié)。2、1980年， 信息交換用漢字編碼字符集基本集（GB2312-80），字符集收入常用漢字6763個(gè)，其中包括一級漢字3755個(gè)（按漢語拼音排列），二級漢字3008個(gè)（按偏旁部首排列）。將6763個(gè)漢字分為94個(gè)區(qū)，每個(gè)區(qū)又分為94位。漢字在代碼表中的區(qū)號、位號就叫做漢字的區(qū)位碼（例如“國”：25-90）；將漢字的區(qū)號、位號各增加32即為國標(biāo)碼（例如“國”：57-122）；國標(biāo)漢字在計(jì)算機(jī)內(nèi)以連續(xù)的兩個(gè)字節(jié)來表示。為了和ASCII碼區(qū)別，這兩個(gè)字節(jié)的最高位都填1，理論上能夠表示的漢字?jǐn)?shù)共28128112812816384個(gè)漢字，國標(biāo)漢字在計(jì)算機(jī)內(nèi)的編碼叫做機(jī)內(nèi)碼。3、當(dāng)前常用的其他漢字字符集編碼： 國家標(biāo)準(zhǔn)（GBK）漢字?jǐn)U展內(nèi)碼規(guī)范；臺灣漢字編碼規(guī)范（BIG5）等4、計(jì)算機(jī)上字符的輸出是通過在計(jì)算機(jī)中預(yù)存字形信息庫，簡稱字庫（Font），以下以漢字為例，字形有兩種表示方法：點(diǎn)陣字形庫和輪廓字形庫。點(diǎn)陣字形庫時(shí)一點(diǎn)振興是描述的漢字字形代碼，其點(diǎn)陣的密度決定了漢字的美觀清晰度。普通的點(diǎn)陣為1616，更高的有2424、3232、6464等。點(diǎn)陣字形庫需要占據(jù)大量的存儲空間。以1616為例，每個(gè)漢字要占用1616位32字節(jié)，6763個(gè)漢字共占用326763256KB。由于點(diǎn)陣字形庫美觀程度差、空間占用大，我們現(xiàn)在所采用的一般都是輪廓字形庫（包括Windows9x內(nèi)的宋體、楷體、黑體）。5、 漢字激光照排系統(tǒng)的創(chuàng)始人王選,“漢字印刷術(shù)的第二次發(fā)明”。15 計(jì)算機(jī)網(wǎng)絡(luò)1-5-1、計(jì)算機(jī)網(wǎng)絡(luò)： 1969年，美國國防部ARPANET (1) 按照距離分類 網(wǎng)絡(luò)類型距離適合的對象局域網(wǎng)LAN幾米10公里位于一個(gè)建筑物或一個(gè)單位內(nèi)城域網(wǎng)MAN10公里100公里 對一個(gè)城市的LAN互聯(lián)位于一座城市中廣域網(wǎng) WAN幾百公里幾千公里國家，郵電部的CHINANET，CHINAPAC，和CHINADDN網(wǎng)互聯(lián)網(wǎng) INTERNET一個(gè)洲或洲際（2）拓?fù)浣Y(jié)構(gòu)：總線型，星形，環(huán)形，樹形應(yīng)用層（Application Layer)表示層（Presentation Layer)會話層（Session Layer）傳輸層（Transport Layer)網(wǎng)絡(luò)層(Network Layer)數(shù)據(jù)鏈路層（Data Link Layer)物理層（Physical Layer)1-5-3、OSI（開放式系統(tǒng)互連參考模型）OSI（開放式系統(tǒng)互連參考模型）是ISO就網(wǎng)絡(luò)體系提出的一個(gè)參考模型，這個(gè)模型把網(wǎng)絡(luò)通信的工作分為7層.1-5-4、TCP/IP協(xié)議 TCP/IP協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有4個(gè)層次功能的網(wǎng)絡(luò)模型應(yīng)用層應(yīng)用程序間溝通的層，如簡單電子郵件傳輸（SMTP）、文件傳輸協(xié)議（FTP）、網(wǎng)絡(luò)遠(yuǎn)程訪問協(xié)議（Telnet）等傳輸層提供了節(jié)點(diǎn)間的數(shù)據(jù)傳送，應(yīng)用程序之間的通信服務(wù)，主要功能是數(shù)據(jù)格式化、數(shù)據(jù)確認(rèn)和丟失重傳等。如傳輸控制協(xié)議（TCP）、用戶數(shù)據(jù)報(bào)協(xié)議（UDP）等，TCP和UDP給數(shù)據(jù)包加入傳輸數(shù)據(jù)并把它傳輸?shù)较乱粚又?，這一層負(fù)責(zé)傳送數(shù)據(jù)，并且確定數(shù)據(jù)已被送達(dá)并接收。互連網(wǎng)絡(luò)層負(fù)責(zé)提供基本的數(shù)據(jù)封包傳送功能，讓每一塊數(shù)據(jù)包都能夠到達(dá)目的主機(jī)（但不檢查是否被正確接收），如網(wǎng)際協(xié)議（IP）網(wǎng)絡(luò)接口層接收IP數(shù)據(jù)報(bào)并進(jìn)行傳輸，從網(wǎng)絡(luò)上接收物理幀，抽取IP數(shù)據(jù)報(bào)轉(zhuǎn)交給下一層，對實(shí)際的網(wǎng)絡(luò)媒體的管理，定義如何使用實(shí)際網(wǎng)絡(luò)（如Ethernet、Serial Line等）來傳送數(shù)據(jù)。1-5-6 、IP地址與子網(wǎng)掩碼IPv4地址：32bit位二進(jìn)制組成，由類型標(biāo)志、網(wǎng)絡(luò)標(biāo)志和主機(jī)標(biāo)識組成。IP地址分為：A、B、C、D、E五類。常用的是A、B、C。 01 8 31A類：0網(wǎng)絡(luò)號主機(jī)號 0 1 2 16 31B類：10網(wǎng)絡(luò)號主機(jī)號 0 1 2 3 24 31C類：110網(wǎng)絡(luò)號主機(jī)號網(wǎng)址范圍子網(wǎng)掩碼A類l -126 . 0 - 255 . : U/ N0 J% 8 Y7 .0-255 . * l7 G$ c3 |+ v* I: m& r, D1-254 & P255000B類128-191 . 0-255 . 0-255 . I1-25425525500C類192-233 . 0 L0-255 . 0-255 . 1-25425525500 第二代中國教育和科研計(jì)算機(jī)網(wǎng)CERNET2是中國下一代互聯(lián)網(wǎng)示范工程CNGI最大的核心網(wǎng)和唯一的全國性學(xué)術(shù)網(wǎng)，CERNET2全國網(wǎng)絡(luò)中心位于清華大學(xué)。CERNET2具有以下特點(diǎn)： 1 . 是中國第一個(gè)IPv6國家主干網(wǎng)。 2 . 是目前世界上規(guī)模最大的純IPv6主干網(wǎng)。 3 . 建成中國下一代IPv6網(wǎng)交換中心。 4 . 采用了自主開發(fā)的關(guān)鍵設(shè)備及技術(shù)，為下一代互聯(lián)網(wǎng)帶動的產(chǎn)業(yè)經(jīng)濟(jì)打下了堅(jiān)實(shí)基礎(chǔ)。 IPV6地址長度為128比特。 2004年3月，CERNET2試驗(yàn)網(wǎng)正式向用戶提供IPv6下一代互聯(lián)網(wǎng)服務(wù)。目前，CERNET2已經(jīng)初具規(guī)模。CERNET2已經(jīng)接入北京大學(xué)、清華大學(xué)、復(fù)旦大學(xué)、上海交通大學(xué)、浙江大學(xué)等100多所國內(nèi)高校，并與谷歌實(shí)現(xiàn)基于IPv6的1Gbps高速互聯(lián)。1-5-6域名系統(tǒng)及DNS服務(wù)器 在Internet網(wǎng)上的主機(jī)就可以用“主機(jī)名域名”的方式唯一的標(biāo)識。如：WWWTONGJIEDIJCN名字中WWW為主機(jī)名，由服務(wù)器管理員命名，TONGJIEDU.CN 為域名，由服務(wù)器管理員申請合法可以使用。 DNS服務(wù)器：/ Z% N2 6 ?: Z: WT) h提供主機(jī)域名與IP地址之間相互轉(zhuǎn)換服務(wù)的計(jì)算機(jī)系統(tǒng)。它保存了一張域名(domain name)和與之相對應(yīng)的IP地址 (IP address)的表，以解析消息的域名。1-5-7 WEB服務(wù)器：WEB服務(wù)器也稱為WWW(WORLD WIDE WEB)服務(wù)器，主要是提供網(wǎng)上信息瀏覽服務(wù)。(1)應(yīng)用層使用HTTP協(xié)議。(2)HTML文檔格式：html 超文本標(biāo)記語言，HTML命令可以說明文字、圖形、動畫、聲音、表格、鏈接等。網(wǎng)頁設(shè)計(jì)中，超鏈接：本站點(diǎn)網(wǎng)頁之間的聯(lián)系 或 指向外部的網(wǎng)絡(luò)資源。標(biāo)簽：本網(wǎng)頁之間的跳轉(zhuǎn)。（3)瀏覽器統(tǒng)一資源定位器(URL)。1-5-8 常見的協(xié)議協(xié)議中 文在網(wǎng)絡(luò)模型中的層次TCP/IP協(xié)議傳輸控制協(xié)議 / 因特網(wǎng)互聯(lián)協(xié)議傳輸層/互連網(wǎng)絡(luò)層Http超文本傳輸協(xié)議應(yīng)用層FTP文件傳輸協(xié)議應(yīng)用層SMTP簡單電子郵件傳輸應(yīng)用層Pop3郵局協(xié)議, 個(gè)人計(jì)算機(jī)連接到互聯(lián)網(wǎng)上的郵件服務(wù)器收發(fā)郵件的協(xié)議應(yīng)用層Telnet網(wǎng)絡(luò)遠(yuǎn)程訪問協(xié)議應(yīng)用層2、競賽與編程環(huán)境全國青少年信息學(xué)奧林匹克競賽系列活動簡介簡稱 描 述NOI全國青少年信息學(xué)奧林匹克（2011年第28屆）NOIP全國青少年信息學(xué)奧林匹克聯(lián)賽(2011年第17屆)冬令營全國青少年信息學(xué)奧林匹克競賽冬令營APIO亞洲與太平洋地區(qū)信息學(xué)奧賽選拔賽（ctsc）選拔參加國際信息學(xué)奧林匹克中國代表隊(duì)的競賽IOI國際信息學(xué)奧林匹克競賽NOI2009、NOIP2009競賽環(huán)境說明 分類軟件版本說明系統(tǒng)軟件NOI Linux內(nèi)核- 2.6.24 NOILinux 1.2操作系統(tǒng)編譯器Gcc4.1.2C編譯器G+4.1.2C+編譯器Freepascal，F(xiàn)pc2.0.4Pascal編譯器調(diào)試器Gdb6.6命令行啟動Ddd3.3.11命令行啟動集成開發(fā)環(huán)境GUIDE1.0.0單文件程序IDE（C/C+/Pascal）Anjuta1.2.4C/C+IDELazarus0.9.22PascalIDE3、圖靈與圖靈獎(jiǎng)圖靈是英國著名的數(shù)學(xué)家和邏輯學(xué)家，被稱為計(jì)算機(jī)科學(xué)之父、人工智能之父，是計(jì)算機(jī)邏輯的奠基者，提出了“圖靈機(jī)”和“圖靈測試”等重要概念。圖靈機(jī)就是指一個(gè)抽象的機(jī)器，理想計(jì)算機(jī)模型?！皥D靈獎(jiǎng)”是美國計(jì)算機(jī)協(xié)會（ACM，Association for