1、信息系統(tǒng)管理工程師考點分析與真題預(yù)測詳解第1章 計算機(jī)科學(xué)基本 計算機(jī)科學(xué)是一門涉及多種各樣與計算和信息解決有關(guān)主題的系統(tǒng)學(xué)科，從抽象的算法分析、形式化語法，到具體的如編程語言、程序設(shè)計、軟件和硬件。作為一門學(xué)科，它與數(shù)學(xué)、計算機(jī)程序設(shè)計、軟件工程和計算機(jī)工程有顯著的不同，卻一般被混淆，盡管這些學(xué)科之間存在不同限度的交叉和覆蓋。 根據(jù)信息系統(tǒng)管理工程師考試大綱與歷年試題分布，本章重點講述：數(shù)制及轉(zhuǎn)換 二進(jìn)制、十進(jìn)制和十六進(jìn)制等常用數(shù)制及其互相轉(zhuǎn)換數(shù)據(jù)的表達(dá) 數(shù)的表達(dá)：原碼、補(bǔ)碼、發(fā)碼，整數(shù)和實數(shù)的機(jī)內(nèi)表達(dá)措施，精度與溢出 非數(shù)值表達(dá)：字符和中文的機(jī)內(nèi)表達(dá)，聲音和圖像的機(jī)內(nèi)表達(dá) 校驗措施和校驗編

2、碼算術(shù)運算和邏輯運算 計算機(jī)中二進(jìn)制的運算措施 邏輯代數(shù)基本運算數(shù)據(jù)構(gòu)造與算法基本概念歷年真題預(yù)測詳解與模擬題1.1數(shù)制及轉(zhuǎn)換1.1.1數(shù)制按進(jìn)位的原則進(jìn)行計數(shù)，稱為進(jìn)位計數(shù)制，簡稱數(shù)制或進(jìn)制.在平常生活中常常要用到數(shù)制，一般以十進(jìn)制進(jìn)行計數(shù)，除了十進(jìn)制計數(shù)以外，尚有許多非十進(jìn)制的計數(shù)措施。例如，60分鐘為1小時，用的是60進(jìn)制計數(shù)法；1星期有7天，是7進(jìn)制計數(shù)法；1年有12個月，是12進(jìn)制計數(shù)法。固然，在生活中尚有許多其她多種各樣的進(jìn)制計數(shù)法。在計算機(jī)系統(tǒng)中采用二進(jìn)制，其重要因素是由于電路設(shè)計簡樸、運算簡樸、工作可靠、邏輯性強(qiáng)。不管是哪一種數(shù)制，其計數(shù)和運算均有共同的規(guī)律和特點。人們最熟悉的

3、是十進(jìn)制數(shù)，但在計算機(jī)中，采用二進(jìn)制數(shù)0和1可以很以便的表達(dá)機(jī)內(nèi)的數(shù)據(jù)與信息。在計算機(jī)系統(tǒng)中采用二進(jìn)制，其重要因素是由于電路設(shè)計簡樸、運算簡樸、工作可靠、邏輯性強(qiáng)。不管是哪一種數(shù)制，其計數(shù)和運算均有共同的規(guī)律和特點。1.十進(jìn)制數(shù)我們熟悉的十進(jìn)制數(shù)有兩個重要特點：有十個不同的數(shù)字符號：0、1、2、9;低位向高位進(jìn)、借位的規(guī)律是逢十進(jìn)一、借一當(dāng)十的計數(shù)原則進(jìn)行計數(shù)。2.二進(jìn)制數(shù)在二進(jìn)制中只有兩個不同數(shù)碼：0和1,進(jìn)位規(guī)律是逢二進(jìn)一、借一當(dāng)二的計數(shù)原則進(jìn)行計數(shù)。二進(jìn)制數(shù)用B結(jié)尾表達(dá)。3.八進(jìn)制數(shù)在八進(jìn)制中有0、1、2、7八個不同數(shù)碼，采用逢八進(jìn)一、借一當(dāng)八的計數(shù)原則進(jìn)行計數(shù)。八進(jìn)制數(shù)用Q結(jié)尾表達(dá)。4

4、.十六進(jìn)制數(shù)在十六進(jìn)制中有0、1、2、9、A、B、C、D、E、F共十六個不同的數(shù)碼，采用逢十六進(jìn)一、借一當(dāng)十六的計數(shù)原則進(jìn)行計數(shù)。十六進(jìn)制數(shù)用H結(jié)尾表達(dá)。1.1.2數(shù)制之間的轉(zhuǎn)換將數(shù)由一種數(shù)制轉(zhuǎn)換成另一種數(shù)制稱為數(shù)制間的轉(zhuǎn)換。由于計算機(jī)采用二進(jìn)制，但用計算機(jī)解決實際問題時對數(shù)值的輸入輸出一般使用十進(jìn)制，這就有一種十進(jìn)制向二進(jìn)制轉(zhuǎn)換或由二進(jìn)制向十進(jìn)制轉(zhuǎn)換的過程。也就是說，在使用計算機(jī)進(jìn)行數(shù)據(jù)解決時一方面必須把輸入的十進(jìn)制數(shù)轉(zhuǎn)換成計算機(jī)所能接受的二進(jìn)制數(shù)；計算機(jī)在運營結(jié)束后，再把二進(jìn)制數(shù)轉(zhuǎn)換為人們所習(xí)慣的十進(jìn)制數(shù)輸出。下面是數(shù)制之間的轉(zhuǎn)化措施：1.二、八、十六進(jìn)制轉(zhuǎn)十進(jìn)制的措施：乘權(quán)相加法。例如：

5、2.十進(jìn)制化二進(jìn)制的措施：整數(shù)部分除二取余法，小數(shù)部分乘二取整法。圖1-1所示為整數(shù)部分除二取余過程，（43）10=（101011）2.圖1-2所示為小數(shù)部分乘二取整過程，（0.375）10=（0.011）2.3.二進(jìn)制轉(zhuǎn)八進(jìn)制的措施二進(jìn)制轉(zhuǎn)八進(jìn)制的措施，是對二進(jìn)制以小數(shù)點為分隔，往前去后每三位劃為一組，局限性三位補(bǔ)0,按表1-1用相應(yīng)的八進(jìn)制數(shù)字代入即可。例如：（10111011.01100111）=010,111,011.011,001,110=（273.316）8表1-1 1位數(shù)八進(jìn)制與二進(jìn)制相應(yīng)表4.二進(jìn)制轉(zhuǎn)十六進(jìn)制的措施二進(jìn)制轉(zhuǎn)十六進(jìn)制的措施，是對二進(jìn)制以小數(shù)點為分隔，往前去后每四位

6、劃為一組，局限性四位補(bǔ)0,按表1-2用相應(yīng)的十六進(jìn)制數(shù)字代入即可。例如：（10111011.01100111）=1011,1011.0110,0111=（BB.67）16表1-2 1位數(shù)十六進(jìn)制與二進(jìn)制相應(yīng)表表1-3列出了二、八、十、十六進(jìn)制數(shù)之間的相應(yīng)關(guān)系，熟記這些相應(yīng)關(guān)系對后續(xù)內(nèi)容的學(xué)習(xí)會有較大的協(xié)助。表1-3 多種進(jìn)位制的相應(yīng)關(guān)系1.2數(shù)據(jù)的表達(dá)1.2.1數(shù)的表達(dá)1.常用數(shù)值編碼由于機(jī)器數(shù)在計算時，如果符號位和數(shù)值位同步參與運算，則也許會產(chǎn)生錯誤成果；而如果單獨考慮符號問題，又會增長運算器件的實現(xiàn)難度。因此，為了使計算機(jī)可以以便地對數(shù)值進(jìn)行多種算術(shù)邏輯運算，必須對數(shù)值型數(shù)據(jù)進(jìn)行二進(jìn)制編碼

7、解決。所謂編碼是采用少量的基本符號（如0和1），按照一定的組合原則，來表達(dá)大量復(fù)雜多樣信息的技術(shù)。編碼的優(yōu)劣直接影響到計算機(jī)解決信息的速度。數(shù)值型數(shù)據(jù)的常用編碼措施涉及：原碼、反碼和補(bǔ)碼。原碼原碼的編碼規(guī)則是：符號位0表達(dá)正，1表達(dá)負(fù)，數(shù)值部分用該數(shù)絕對值的二進(jìn)制數(shù)表達(dá)。當(dāng)整數(shù)時，小數(shù)點隱含在最低位之后；當(dāng)純小數(shù)時，小數(shù)點隱含在符號位和數(shù)值位之間，均不占位，一般用X原表達(dá)數(shù)X的原碼。例如，設(shè)機(jī)器字長為8位，+1原=00000001 +127原=01111111 +0原=00000000-1原=10000001 -127原=11111111 -0原=10000000顯然，按原碼的編碼規(guī)則，零有兩

8、種表達(dá)形式。原碼表達(dá)法簡要易懂，與其真值的轉(zhuǎn)換以便，比較容易進(jìn)行乘除運算。但是在進(jìn)行加減運算時，原碼運算很不以便。由于符號位不能和數(shù)值同樣參與運算，因此要根據(jù)兩數(shù)的符號狀況，同號相加，異號相減，還要根據(jù)兩數(shù)的絕對值大小，令大數(shù)減去小數(shù)，最后還要判斷成果的符號。這樣不僅規(guī)定運算器既能作加法，又能作減法，還必須附加許多條件判斷的解決，最后既增長了運算器的實現(xiàn)復(fù)雜性，又延長了運算的時間。反碼反碼的編碼規(guī)則是：符號位0表達(dá)正，1表達(dá)負(fù)，正數(shù)的反碼等于原碼，負(fù)數(shù)的反碼等于原碼除符號位外按位取反，即0變1,1變0.一般用X反表達(dá)數(shù)X的反碼。例如，設(shè)機(jī)器字長為8位。+1反=00000001 +127反=01

9、111111 +0反=00000000-1反=11111110 -127反=10000000 -0反=11111111顯然，按反碼的編碼規(guī)則零也有兩種表達(dá)形式。反碼很容易由原碼獲得，但同樣不以便運算，一般在求補(bǔ)碼的過程中用到反碼。補(bǔ)碼補(bǔ)碼的編碼規(guī)則是：符號位0表達(dá)正，1表達(dá)負(fù)，正數(shù)的補(bǔ)碼等于原碼，負(fù)數(shù)的補(bǔ)碼等于反碼末位加1.一般用X補(bǔ)表達(dá)數(shù)X的補(bǔ)碼。例如，設(shè)機(jī)器字長為8位，+1補(bǔ)=00000001 +127補(bǔ)=01111111 +0補(bǔ)=00000000-1補(bǔ)=11111111 -127補(bǔ)=10000001 -0補(bǔ)=00000000顯然，按補(bǔ)碼的編碼規(guī)則，零有唯一的表達(dá)形式。補(bǔ)碼的概念來源于數(shù)學(xué)

10、上的模和補(bǔ)數(shù)。例如，將鐘表的時針順時針撥快5小時和逆時針撥慢7小時，最后批示的位置相似，則稱5和-7互為模12狀況下的補(bǔ)數(shù)。計算機(jī)中機(jī)器數(shù)受機(jī)器字長限制，因此是有限字長的數(shù)字系統(tǒng)。對于整數(shù)來說，機(jī)器字長為n位（含符號位），模是2n;對于有符號純小數(shù)來說，模是2.求補(bǔ)運算一般運用反碼來實現(xiàn)。例如，求X=+1011,Y=1101的原碼，反碼和補(bǔ)碼。求解過程：X原=01011 Y原=11101X反=01011 Y反=10010X補(bǔ)=01011 Y補(bǔ)=10011采用補(bǔ)碼進(jìn)行加減運算十分以便。通過對負(fù)數(shù)的編碼解決，容許符號位和數(shù)值一起參與運算，可以把減法運算轉(zhuǎn)化為加法運算。不管求和求差，也不管操作數(shù)為正

11、為負(fù)，運算時一律只做加法，從而大大簡化運算器的設(shè)計，加快了運算速度。例如，（-9）+（-5）的運算如下：-9補(bǔ)=11110111 11110111-5補(bǔ)=11111011+11111011由于機(jī)器字長的限制，丟失高位1,運算成果機(jī)器數(shù)為11110010,是-14的補(bǔ)碼形式。目前，由于計算機(jī)中最多的運算是加減運算，為了簡化運算器設(shè)計，加快運算速度，有些計算機(jī)在數(shù)值表達(dá)，存儲，運算時均采用補(bǔ)碼表達(dá)法，也有些計算機(jī)，數(shù)用原碼進(jìn)行存儲和傳送，運算時采用補(bǔ)碼，尚有些計算機(jī)在進(jìn)行加減法時采用補(bǔ)碼運算，而在進(jìn)行乘除法時采用原碼運算。2.整數(shù)和實數(shù)的機(jī)內(nèi)表達(dá)措施在計算機(jī)內(nèi)部，并不顯式地表達(dá)出小數(shù)點，而是通過對

12、小數(shù)點的位置加以規(guī)定來表達(dá)。因此，整數(shù)和實數(shù)在機(jī)內(nèi)的表達(dá)是不同的。整數(shù)整數(shù)沒有小數(shù)部分，因此可以覺得小數(shù)點固定在數(shù)的最右邊。整數(shù)可以分為無符號整數(shù)和有符號整數(shù)兩類。無符號整數(shù)的所有二進(jìn)制位所有用來表達(dá)數(shù)值的大小，常被用來表達(dá)計算機(jī)中的地址。有符號整數(shù)一般最高位表達(dá)數(shù)的正負(fù)號，而其她位表達(dá)數(shù)值的大小。一般把計算機(jī)可以直接解決的二進(jìn)制位數(shù)稱為機(jī)器字長。整數(shù)表達(dá)的數(shù)值是精確的，但可以表達(dá)的數(shù)值范疇受機(jī)器字長的限制?，F(xiàn)代計算機(jī)的機(jī)器字長一般為8、16、32、64、128位等，每種狀況可以表達(dá)的整數(shù)范疇不同。實數(shù)在進(jìn)行科學(xué)計算時，計算機(jī)解決更多的是實數(shù)。實數(shù)是既有整數(shù)部分又有小數(shù)部分的數(shù)，純小數(shù)可看作實

13、數(shù)的特例。由于實數(shù)也許很大或者很小，因此人們一般采用浮點數(shù)表達(dá)法來表達(dá)，即把一種實數(shù)的范疇和精度用階碼和尾數(shù)兩部分來分別表達(dá)。例如，0.3429 106,其中0.3429稱為尾數(shù)，6稱為階碼。由于階碼可以取不同數(shù)值，使得小數(shù)點的位置不固定，對于一種實數(shù)可以有多種表達(dá)形式，因此稱為浮點數(shù)表達(dá)法。例如，十進(jìn)制實數(shù)-12345.6789可以表達(dá)為：-0.105,-12.3456789103,-12345.6789100,-1234567.89102.二進(jìn)制的表達(dá)類似，例如，1010.1011可表達(dá)為：10.101011210,101010.11210,0.101010112100.在計算機(jī)中，為了提

14、高數(shù)據(jù)表達(dá)精度，必須唯一地規(guī)定小數(shù)點的位置，因此規(guī)定浮點數(shù)必須寫成規(guī)格化的形式，即當(dāng)尾數(shù)不為0時，其絕對值不小于等于0.5且不不小于1.尾數(shù)表達(dá)數(shù)值的有效數(shù)字，是純小數(shù)，其位數(shù)將影響數(shù)的精度，其符號決定數(shù)的符號。階碼相稱于數(shù)學(xué)中的指數(shù)，其大小用來批示尾數(shù)中的小數(shù)點應(yīng)當(dāng)向左或向右移動的位數(shù)，其位數(shù)將決定數(shù)的表達(dá)范疇。在浮點數(shù)表達(dá)中，數(shù)符和階符一般各占一位，并且商定小數(shù)點的位置在數(shù)符和尾數(shù)之間。一種浮點數(shù)的機(jī)內(nèi)表達(dá)形式。3.精度和溢出現(xiàn)代數(shù)字計算機(jī)是有限字長的數(shù)字系統(tǒng)，機(jī)器數(shù)表達(dá)的范疇受到機(jī)器字長和數(shù)據(jù)類型的限制，一旦機(jī)器字長和數(shù)據(jù)類型擬定了，機(jī)器數(shù)所能表達(dá)的數(shù)的范疇和精度也就擬定了。所謂精度，是

15、指可以給出的有效數(shù)字的位數(shù)。一般來說，機(jī)器字長越長，可以表達(dá)的數(shù)的范疇越大，精度越高；當(dāng)字長相似時，浮點數(shù)一般比整數(shù)可以表達(dá)的數(shù)的范疇要大；浮點數(shù)表達(dá)時，階碼位數(shù)越多，可以表達(dá)的數(shù)的范疇越大，尾數(shù)位數(shù)越多，可以表達(dá)的數(shù)的精度越高。如果一種數(shù)的大小超過了計算機(jī)所能表達(dá)的數(shù)的范疇，則產(chǎn)生溢出.如果兩個正數(shù)相加， 成果不小于機(jī)器所能表達(dá)的最大正數(shù)，稱為上溢;如果兩個負(fù)數(shù)相加，成果不不小于機(jī)器所能表達(dá)的最小負(fù)數(shù)，稱為下溢.例如，字長為n位的有符號整數(shù)，最高1位為符號位，數(shù)值位為n-1位，用補(bǔ)碼表達(dá)時，數(shù)的表達(dá)范疇為-2n-12n-1-1,一旦運算時發(fā)生成果超過此范疇的狀況，就產(chǎn)生溢出。產(chǎn)生溢出時，將導(dǎo)

16、致運算成果錯誤。因此當(dāng)產(chǎn)生溢出時，計算機(jī)狀態(tài)字寄存器（PSW）的溢出標(biāo)志位將自動置為1,否則為0.在計算機(jī)中有諸多判斷溢出的措施，一般通過邏輯電路自動檢測到溢出后執(zhí)行相應(yīng)的中斷解決。要想盡量避免產(chǎn)生溢出錯誤，在設(shè)計計算機(jī)硬件時可以考慮增長機(jī)器字長以表達(dá)更大范疇的數(shù)值。1.2.2非數(shù)值表達(dá)1.字符的表達(dá)由于計算機(jī)是以二進(jìn)制的形式存儲、運算、辨認(rèn)和解決數(shù)據(jù)的，因此，字母和多種字符也必須按特定的規(guī)則變?yōu)槎M(jìn)制編碼才干輸入計算機(jī)。字符編碼事實上就是為每一種字符擬定一種相應(yīng)的整數(shù)值，以及相相應(yīng)的二進(jìn)制編碼。但是，由于字符（涉及拉丁字母）與整數(shù)值之間沒有什么必然的聯(lián)系，某一種字符究竟相應(yīng)哪個整數(shù)完全可以任

17、意規(guī)定。為了信息互換中的統(tǒng)一性，人們已經(jīng)建立了某些字符編碼原則，常用的有ASCII（American Standard Code for Information Interchange,美國原則信息互換代碼）字符編碼原則以及IBM公司提出的EBCDIC代碼等，其中以ASCII碼使用的范疇最廣泛。國際原則化組織（ISO）和國內(nèi)都頒發(fā)了與ASC II一致的編碼原則（ISO-646和GB-1988-80）。ASCII編碼原則用7位二進(jìn)制數(shù)編碼，用來表達(dá)128種不同的字符，如表1-4所示。其中的95個編碼相應(yīng)鍵盤上能輸入，并且可以顯示和打印的95個字符。這95個字符可分為幾大類：大寫、小寫各26個英文

18、字母；09共10個數(shù)字；通用的運算符和標(biāo)點符號：+、-、/、=、！等。此外的33個字符，其編碼值為031和127,即000 0000000 0001和111 1111,不相應(yīng)任何一種可顯示或打印的實際字符，它們被用作控制碼，控制計算機(jī)某些外圍設(shè)備的工作特性和某些計算機(jī)軟件的運營狀況。例如，編碼0000010（碼值為10）表達(dá)換行.由7位編碼構(gòu)成的ASC碼基本字符集能表達(dá)的字符只有128個，不能滿足信息解決的需要，因此又對ASC碼字符集進(jìn)行擴(kuò)大，采用一種字節(jié)（8位二進(jìn)制位數(shù)）表達(dá)一種字符，編碼范疇：0000000011111111,一共可表達(dá)256種字符和圖形符號，成為擴(kuò)大的ASC碼字符集。表1

19、-4 ASCII字符集對計算機(jī)字符的解決事實上是對字符編碼進(jìn)行解決。例如：比較字符A和E的大小，事實上是對A和E的ASCII碼65和69進(jìn)行比較。字符輸入時，按一下鍵，該鍵所相應(yīng)的ASCII碼即存入計算機(jī)。把一文本文獻(xiàn)中的所有字符錄入到計算機(jī)，計算機(jī)里寄存的事實上是一大串ASCII碼。2.中文表達(dá)法英文是拼音文字，一種不超過128種字符的字符集，就可滿足英文解決的需要。中文是象形構(gòu)造，字?jǐn)?shù)多，字形復(fù)雜，計算機(jī)存儲和解決都比較復(fù)雜。用計算機(jī)解決中文，一方面要解決中文編碼問題。根據(jù)記錄，在人們平常生活交往中常常使用的中文約有四五千個。原則上，兩個字節(jié)可以表達(dá)256256=65536 種不同的符號，

20、作為中文編碼表達(dá)的基本是可行的。國內(nèi)國標(biāo)局采用了加以修正的兩字節(jié)中文編碼方案，只用了兩個字節(jié)的低7位，該方案可以容納128128=16384種不同的中文，但為了與原則ASCII碼兼容，每個字節(jié)只能用94個編碼。國標(biāo)中文字符集GB2312-80共收集了7445個中文和圖形符號，其中中文6763個，分為二級，一級中文3755個，二級中文3008個，此外還涉及：一般符號202個：涉及間隔符、標(biāo)點、運算符和制表符號；序號60個：它們是120（20個）、（20）、和（一）（+）；數(shù)字22個：09、；英文字母52個；日文假名169個（83,86）；希臘字母48個；俄文字母66個；漢語拼音符號26個；漢語注

21、音字母37個。每個中文符號都相應(yīng)一種國標(biāo)碼和一種區(qū)位碼，國標(biāo)碼是一種四位十六進(jìn)制數(shù)，區(qū)位碼是一種四位十進(jìn)制數(shù)。由于十六進(jìn)制數(shù)很少用到，因此常用的是區(qū)位碼，它的前兩位叫做區(qū)碼，后兩位叫做位碼，區(qū)的序號和位的序號都是從194.相應(yīng)地，國標(biāo)碼的第一字節(jié)可視為寄存位置的行號，從21H7EH,第二字節(jié)可視為寄存位置的列號，也從21H7EH,如表1-5所示。表1-5 GB2312-80字符集構(gòu)造例如：中文第一字節(jié)第二字節(jié)國標(biāo)碼區(qū)位碼啊水 01001011 E4314在國標(biāo)碼中，一種中文占兩個字節(jié)，每個字節(jié)最高位為0,為了在計算機(jī)中將ASCII碼和國標(biāo)碼辨別開，一般將國標(biāo)碼的最高位置為1,變換后的國標(biāo)碼就叫

22、做中文機(jī)內(nèi)碼。由于歷史和地區(qū)因素，中文有不少編碼原則。最常用的是GB2312和BIG5.在Unicode（統(tǒng)一碼）被完全接受前，它們將共存相稱長的一段時間。Unicode碼是由Unicode學(xué)術(shù)學(xué)會制定的字符編碼系統(tǒng)，旨在支持多種語言書面文本的互換、解決和顯示。Unicode碼4.0版本于推出，該版本涉及了中文簡體字、日文平假名、片假名、泰文、韓文、阿拉伯文等世界重要語系的文字。3.圖形數(shù)字化編碼在計算機(jī)中，圖形（Graphics）和圖像（Image）是兩個不同的概念，圖形一般指使用繪畫軟件繪制出的由直線、曲線等構(gòu)成的畫面，圖形文獻(xiàn)中寄存的是描述圖形的指令，以矢量圖形文獻(xiàn)存儲。圖像則是由掃描儀

23、、數(shù)碼相機(jī)等輸入的畫面，數(shù)字化后以點陣（位圖）形式存儲。點陣表達(dá)法一幅圖像可以看作由排列成若干行、若干列的黑白或彩色的光點構(gòu)成，每個光點叫做一種像素（Pixels），從而形成一種像素點陣列。陣列中的像素總數(shù)決定了圖像的精細(xì)限度。像素的數(shù)目越多，圖像越精細(xì)，其細(xì)節(jié)的辨別限度也就越高，但同步也必然要占用更大的存儲空間。對圖像的點陣表達(dá)，其行列數(shù)的乘積稱為圖像的辨別率。例如，若一種圖像的陣列共有480行，每行640個點，則該圖像的辨別率為640480像素。在計算機(jī)中存儲和解決圖像同樣要用二進(jìn)制數(shù)字編碼的形式。將每個像素點用若干個二進(jìn)制位進(jìn)行編碼，表達(dá)圖像顏色的過程就叫做圖像數(shù)字化。描述圖像的重要屬性

24、是圖像辨別率和顏色深度，因此圖像數(shù)字化編碼可以分為如下幾類。黑白色如果一種像素點只有黑白兩種顏色，那么只用一種二進(jìn)位就可以表達(dá)一種像素。這時，一種640480的像素陣列需要640480/8=38400B=37.5KB.256色灰度由黑白二色像素構(gòu)成的圖像也可以用像素的灰度來模擬彩色顯示，一種像素的灰度就是像素的亮度，即介于純黑和純白之間的多種狀況。計算機(jī)中采用分級方式表達(dá)灰度：例如提成256個不同的灰度級別（可以用0到255的數(shù)表達(dá)），用8個二進(jìn)位就能表達(dá)一種像素的灰度。采用灰度方式，使圖像的體現(xiàn)力增強(qiáng)了，但同步存儲一幅圖像所需要的存儲量也增長了。例如采用上述256級灰度，與采用256種顏色同

25、樣，表達(dá)一幅640480像素的圖像就需要大概30萬個字節(jié)（300KB）。真彩色圖像顯示通過不同的強(qiáng)度混合而成。所謂真彩色的圖像顯示，就是用三個字節(jié)表達(dá)一種像素點的色彩，其中每個字節(jié)表達(dá)一種基色的強(qiáng)度，強(qiáng)度提成256個級別。由此可知，要表達(dá)一種640480像素的真彩色的點陣圖像，需要將近1MB的存儲空間。由此可見，圖像點陣表達(dá)法的缺陷是：保存一幅圖像所需的存儲空間很大。因此后 來又發(fā)展出了許多壓縮圖像文獻(xiàn)格式來節(jié)省存儲空間，常用的有BMP、JPEG、GIF、AVI、MPEG等。矢量表達(dá)法基本原理是用直線逼近曲線，用直線段兩端點位置表達(dá)直線段。采用此類措施表達(dá)圖形存儲量非常少。矢量圖形由矢量定義的

26、直線和曲線構(gòu)成，Adobe Illustrator、CorelDraw、CAD等軟件是以矢量圖形為基本進(jìn)行創(chuàng)作的。矢量圖形根據(jù)輪廓的幾何特性進(jìn)行描述，圖形的輪廓畫出后，被放在特定位置并填充顏色，移動、縮放或更改顏色不會減少圖形的品質(zhì)。矢量圖形與辨別率無關(guān)，可以將它縮放到任意大小和以任意辨別率在輸出設(shè)備上打印出來，都不會影響清晰度。1.2.3校驗措施和校驗編碼計算機(jī)中數(shù)據(jù)在進(jìn)行存儲和傳播過程中也許會發(fā)生錯誤。為了及時發(fā)現(xiàn)和糾正此類錯誤，在數(shù)據(jù)傳播（存儲）過程中要進(jìn)行校驗，常用的校驗措施就是奇偶校驗措施、循環(huán)冗余校驗措施、海明碼校驗措施。奇偶校驗法是計算機(jī)中廣泛采用的檢查傳播數(shù)據(jù)精確性的措施1.奇

27、偶校驗措施奇偶校驗措施的原理是在每組數(shù)據(jù)信息上附加一種校驗位，校驗位的取值（0或1）取決于這組信息中1的個數(shù)和校驗方式（奇或偶校驗）。如果采用奇校驗，則這組數(shù)據(jù)加上校驗碼位后數(shù)據(jù)中1的個數(shù)應(yīng)為奇數(shù)個。如果采用偶校驗，則這組數(shù)據(jù)加上校驗碼位后數(shù)據(jù)中1的個數(shù)應(yīng)為偶數(shù)個。例如：奇偶校驗措施八位信息10101011中共有5個1,附加校驗位后變?yōu)榫盼弧Ｈ舨捎闷嫘ｒ?，則附加的校驗位應(yīng)取0值，保證1的個數(shù)為奇數(shù)個即 0 10101011 ;若采用偶校驗則附加的校驗位應(yīng)取1值即 1 10101011 .奇偶校驗的特點：奇偶校驗法使數(shù)據(jù)的碼距為2,因而可檢出數(shù)據(jù)傳送過程中奇數(shù)個數(shù)位出錯的狀況；實際中兩位同步出錯

28、的概率極低，奇偶校驗法簡便可靠易行，但它只能發(fā)現(xiàn)錯誤，卻不知錯在何處，因而不能自動糾正。2.海明碼校驗措施海明碼校驗措施以奇偶校驗法為基本，其校驗位不是一種而是一組，故其碼距不小于2 .海明碼校驗措施可以檢測出具體錯誤并糾正原理是在數(shù)據(jù)中加入r個校驗位，將數(shù)據(jù)的碼距按照一定規(guī)則拉長。r個校驗位可以表達(dá)2r個信息，除一種表達(dá)無誤信息外，其他2r-1信息可以用來標(biāo)明錯誤的具體位置，但由于校驗位自身也也許在傳送中出錯，因此只有2r-1-r個信息可用，即r位校驗碼只可標(biāo)明2r-1-r個錯誤信息。例如：用4個校驗位能可靠傳播24-1-4=11位信息；而要校驗32位數(shù)據(jù)則需至少6個校驗位。如要能檢測與自動

29、校正一位錯并發(fā)現(xiàn)兩位錯此時校驗位的位數(shù)r和數(shù)據(jù)位的位數(shù)k應(yīng)滿足下述關(guān)系：2r-1 k+r.根據(jù)表1-6,可計算出數(shù)據(jù)位k與校驗位r的相應(yīng)關(guān)系。表1-6 數(shù)據(jù)位k與校驗位r的相應(yīng)關(guān)系編碼措施（以四個校驗位進(jìn)行闡明）四個校驗位最多可以校驗11位數(shù)據(jù)。設(shè)：D10D9D8D7D6D5D4D3D2D1D0為11個數(shù)據(jù)位，P4P3P2P1分別為四個校驗碼，則編碼規(guī)則是：海明碼的總位數(shù)等于數(shù)據(jù)位與校驗位之和；每個校驗位Pi排放在2i-1的位置，例如P4排放在第24-1=8位，其他數(shù)據(jù)位依序排列。即：D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1海明碼的每一位用多種校驗位一起進(jìn)行校驗，被校驗的

30、位號等于校驗它的各校驗位位號和；各校驗位的值為它參與校驗的數(shù)據(jù)位的異或。表1-7 海明碼校驗表各校驗位形成公式：P1=D0D1D3D4D6D8D10 （1）P2=D0D2D3D5D6D9D10 （2）P3=D1D2D3D7D8D9D10 （3）P4=D4D5D6D7D8D9D10 （4）按上述方式Pi的取值是采用偶校驗時的取值，當(dāng)采用奇校驗時，Pi則取反。這樣Pi連同數(shù)據(jù)位一起形成了海明碼的各位。檢查糾錯（以四個校驗位進(jìn)行闡明）海明碼數(shù)據(jù)傳送到接受方后，再將各校驗位的值與它所參與校驗的數(shù)據(jù)位的異或成果進(jìn)行異或運算。運算成果稱為校驗和，校驗和共有四個。對偶校驗來說，如果校驗和不為零則傳播過程中間

31、有錯誤，而錯誤的具體位置則由四個校驗和依序排列后直接指明。如果四個校驗和S4S3S2S1 依序排列后等于（1001）2=（9）10時，就表白海明碼的第九位也就是D4發(fā)生了錯誤，此時只要將D4取反，也就糾正了錯誤。校驗和Si的體現(xiàn)式：S1 =D0D1D3D4D6D8D10P1S2 =D0D2D3D5D6D9D10P2S3 =D1D2D3D7D8D9D10P3S4 =D4D5D6D7D8D9D10P4當(dāng)采用偶校驗方式其傳送數(shù)據(jù)對的時，校驗和S1 S4的值分別都為0;當(dāng)采用奇校驗方式其傳送數(shù)據(jù)對的時，校驗和 S1 S4的值分別都為1.當(dāng)不為上述值時，傳送就發(fā)生了錯誤。例如：采用4位校驗位、偶校驗方式

32、，寫出的海明碼。解：已知D10D9D8D7D6D5D4D3D2D1D0=,由于被校驗位的位號等于校驗它的各校驗位位號之和以及各校驗位的取值等于它參與校驗的數(shù)據(jù)位取值的異或，因此校驗位的取值以及所求海明碼為：P1=D0D1D3D4D6D8D10=1P2=D0D2D3D5D6D9D10=1P3=D1D2D3D7D8D9D10=1P4=D4D5D6D7D8D9D10=0D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=011傳送對的時校驗和的值為0,如果不等于0,則是幾就是第幾位出錯，是7則是第7位D3出錯，此時將其取反即可糾正錯誤。3.循環(huán)冗余校驗措施（CRC碼）循環(huán)冗余校驗措施是通

33、過某種數(shù)學(xué)公式建立信息位和校驗位之間的商定關(guān)系-可以校驗傳送信息的對錯，并且能自動修正錯誤。廣泛用于通信和磁介存儲器中。CRC編碼格式是在k位信息后加r位檢查碼。CRC碼的編碼措施CRC整個編碼長度為 n=k+r 位，故CRC碼又叫（n,k）碼。其編碼措施如下：假設(shè)被傳送的k位二進(jìn)制信息位用C（x）表達(dá)， 系統(tǒng)選定的生成多項式用G（X）表達(dá)，將C（x）左移 G（X）的最高次冪（即等于需要添加的校驗位的位數(shù)r），寫作 C（x）* 2r然后將其C（x）*2r除以生成多項式G（x），所得商用Q（x）表達(dá)，余數(shù)用R（x）表達(dá)。則：C（x）*2r/G（x）=Q（x）+R（x）/G（x）兩邊同步乘以G（x

34、）并左移 R（x） 得到：C（x）*2r-R（x）=Q（x）*G（x）。由于CRC編碼采用的加、減法是按位加減法，即不考慮進(jìn)位與借位，運算規(guī)則為：0+0=0,0+1=1,1+0=1,1+1=0故有：C（x）*2r+R（x）=Q（x）*G（x） 式中，等式左邊即為所求的n位CRC碼，其中余數(shù)體現(xiàn)式R（x）就是校驗位（r位）。且等式兩邊都是G（x）的倍數(shù)。 發(fā)送信息時將等式左邊生成的n位CRC碼送給對方。當(dāng)接受方接到n位編碼后，同樣除以G（x），如果傳播對的則余數(shù)為0,否則則可以根據(jù)余數(shù)的數(shù)值擬定是哪位數(shù)據(jù)出錯。例如有一種（7,4）碼（即CRC碼為7位，信息碼為4位），已擬定生成多項式為：G（X）

35、=X3+X+1= 1011 被傳播的信息C（x）=1001,求C（x）的CRC碼。解：C（x）左移 r=nk=3 位，即：C（x）*2r=1001*23,將上式模2采用除法 除以給定的 G（x）=1011:1001000/1011=1010+110/1011,得到余數(shù)體現(xiàn)式：R（x） =110 所求CRC碼為：C（x）*23+R（x）=1001000+110=1001110表1-8 CRC碼的查錯表收到的CRC碼除以商定的生成多項式G（x），如果余數(shù)為0則傳播無誤，否則傳播錯誤，根據(jù)所得余數(shù)值就可找出錯誤并取反糾正。表1-8具體闡明了CRC碼1001110在傳送時某一位出錯后的判斷與糾正措施C

36、（X）=1001、G（X）=1011.生成多項式G（x）的擬定G（x）是一種商定的除數(shù)，用來產(chǎn)生校驗碼。從檢錯和糾錯的規(guī)定出發(fā)，它并不是隨意選擇的，它應(yīng)滿足下列規(guī)定：任何一位發(fā)生錯誤都應(yīng)使余數(shù)不為0;不同位發(fā)生錯誤應(yīng)使余數(shù)不同；余數(shù)繼續(xù)模2 除，應(yīng)使余數(shù)循環(huán)；CRC的譯碼與糾錯將收到的循環(huán)校驗碼用商定的生成多項式G（X）清除，如果碼字無誤則余數(shù)應(yīng)為0,如有某一位出錯，則余數(shù)不為0,不同位數(shù)出錯余數(shù)不同。如果循環(huán)碼有一位出錯，用G（X）作模2除將得到一種不為0的余數(shù)、如果對余數(shù)補(bǔ)1個0繼續(xù)除下去我們將發(fā)現(xiàn)一種現(xiàn)象；各次余數(shù)將按表1-8順序循環(huán)、例如第七位出錯，余數(shù)將為OO1,補(bǔ)0后再除，第二次余

37、數(shù)為010,后來依次為100,011,，反復(fù)循環(huán)，這是一種有價值的特點。如果我們在求出余數(shù)不為0后，一邊對余數(shù)補(bǔ)0繼續(xù)做模2除，同步讓被檢錯的校驗碼字循環(huán)左移。表1-8闡明當(dāng)浮現(xiàn)余數(shù)（101）時，出錯位也移到A1位置、對通過異或門將它糾正后在下一次移位時送回A1.繼續(xù)移滿一種循環(huán)（對7,4碼共移七次）就得到一種糾正后的碼字。這樣我們就不必像海明校驗?zāi)菢佑米g碼電路對每一位提供糾正條件、當(dāng)位數(shù)增多時循環(huán)碼校驗?zāi)苡行У販p少硬件代價。1.3算術(shù)運算和邏輯運算1.3.1二進(jìn)制的算術(shù)運算 1.加法運算規(guī)則0+0=0 0+1=1 1+0=1 1+1=102.減法運算規(guī)則0-0=0 0-1=1（向高位借1）

38、1-0=1 1-1=03.乘法運算規(guī)則00=0 01=0 10=0 11=11.3.2邏輯運算 1.基本運算邏輯乘，也稱與運算，運算符為或.00=0 01=0 10=0 11=1使用邏輯變量時，AB可以寫成AB邏輯加，也乘或運算，運算符為+或.0+0=0 0+1=1 1+0=1 1+1=1邏輯非，也稱反運算，運算符是在邏輯值或變量符號上加-.-0=1 -1=02.常用運算異或運算：AB=AB+AB1.3.3基本公式1.0,1律A0=0 A1=AA+0=AA+1=12.互換律A+B=B+A AB=BA3.結(jié)合律A+B+C=（A+B）+C=A+（B+C）ABC=（AB）C=A（BC）4.分派律A（

39、B+C）=AB+AC5.重疊律A+A+A=AAAA=A6.互補(bǔ)律A + A=1 AA=07.吸取律A+AB=A A（A+B）=AA+AB=A+B A（A+B）=AB8.對合律對一種邏輯變量兩次取反仍是它自身9.德摩根定理A+B=ABAB=A+B1.3.4邏輯代數(shù)的應(yīng)用 1.邏輯體現(xiàn)式化簡例如：F=AB+AB+AB=AB+A（B+B） （運用分派律）=AB+A （運用互補(bǔ)律以及0,1律）=A+B （運用吸取律）2.對指定位進(jìn)行運算假設(shè)變量A有八位，內(nèi)容是d7d6d5d4d3d2d1d0.將變量A的d5位清零，A（11011111）A.將變量A的各位置1,A+（11111111）A.1.4數(shù)據(jù)構(gòu)造

40、與算法基本概念1.4.1什么是數(shù)據(jù)構(gòu)造隨著計算機(jī)的飛速發(fā)展，再把計算機(jī)簡樸地看作是進(jìn)行數(shù)值計算機(jī)的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計算機(jī)科學(xué)的觀點，是把計算機(jī)程序解決的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而計算機(jī)則是加工解決數(shù)據(jù)的工具。由于數(shù)據(jù)的表達(dá)措施和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的解決效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模諸多，構(gòu)造相稱復(fù)雜，解決對象又多為非數(shù)值性數(shù)據(jù)。因此，僅憑程序員的經(jīng)驗和技巧已難以設(shè)計出效率高、可靠性強(qiáng)的程序。于是，就規(guī)定人們對計算機(jī)程序加工的對象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系-數(shù)據(jù)構(gòu)造（Data S

41、tructure）。計算機(jī)解決一種具體問題時，大體需要通過下列幾種環(huán)節(jié)：一方面要從具體問題中抽象出一種合適的數(shù)學(xué)模型，然后設(shè)計一種解此數(shù)學(xué)模型的算法，最后編出程序、進(jìn)行測試、調(diào)節(jié)至得到最后解答。謀求數(shù)學(xué)模型的實質(zhì)就是分析問題，從中提取操作的對象，并找出這些操作對象之間具有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計算機(jī)算法與數(shù)據(jù)的構(gòu)造密切有關(guān)，算法無不依附于具體的數(shù)據(jù)構(gòu)造，數(shù)據(jù)構(gòu)造直接關(guān)系到算法的選擇和效率。1.4.2數(shù)據(jù)構(gòu)造基本術(shù)語下面簡介一下數(shù)據(jù)構(gòu)造的常用名詞和術(shù)語的含義。數(shù)據(jù)（Data）是人們運用文字符號、數(shù)字符號以及其她規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的抽象描述。數(shù)據(jù)元素（Data El

42、ement）簡稱元素，是數(shù)據(jù)的基本單位，一般作為一種整體進(jìn)行考慮和解決。對于一種文獻(xiàn)而言，每個記錄就是它的數(shù)據(jù)元素；對于一種字符串而言，每個字符就是它的數(shù)據(jù)元素。數(shù)據(jù)和數(shù)據(jù)元素是相對而言的。有時，一種數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（Data Item）構(gòu)成。數(shù)據(jù)記錄（Data Record）簡稱記錄，它是數(shù)據(jù)解決領(lǐng)域組織數(shù)據(jù)的基本單位，數(shù)據(jù)的每個數(shù)據(jù)元素在許多應(yīng)用場合被組織成記錄的構(gòu)造。一種數(shù)據(jù)記錄由一種或多種數(shù)據(jù)項構(gòu)成，每個數(shù)據(jù)項可以是簡樸數(shù)據(jù)項，也可以是組合數(shù)據(jù)項。核心項（Key Item）指得失在一種表或者文獻(xiàn)中，若所有記錄的某個數(shù)據(jù)項的值都不同，也就是每個值能唯一標(biāo)記一種記錄時，則可以把這

43、個數(shù)據(jù)項作為記錄的核心數(shù)據(jù)項，簡稱核心項。其中核心項的每一種值稱作所在的記錄的核心字（Key Word or Key）。數(shù)據(jù)解決（Data Processing）是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、記錄、簡樸計算、轉(zhuǎn)換、輸入、輸出等的操作過程。數(shù)據(jù)構(gòu)造（Data Structure），簡樸地說，指數(shù)據(jù)以及互相之間的關(guān)系。它是研究數(shù)據(jù)元素（Data Element）之間抽象化的互相關(guān)系和這種關(guān)系在計算機(jī)中的存儲表達(dá)（即所謂數(shù)據(jù)的邏輯構(gòu)造和物理構(gòu)造），并對這種構(gòu)造定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，并且保證通過這些運算后所得到的新構(gòu)造仍然是本來的構(gòu)造類型。數(shù)據(jù)類型（Data Type）是對數(shù)據(jù)的取值范疇、每一數(shù)據(jù)的構(gòu)造以及容許施加操作的一種描述。換言之，它是一種值的集合和定義在這個值集上的一組操作的總稱。數(shù)據(jù)對象（Data Object）簡稱對象，是性質(zhì)相似的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一種子集。如25為一種整形數(shù)據(jù)對象，A為一種字符數(shù)據(jù)數(shù)據(jù)對象等。除了上述常用概念之外，數(shù)據(jù)構(gòu)造尚有許多的別的概念，例如算法、線性構(gòu)造、集合、圖、樹等。1.4.3算法的描述 算法（Algorithm）就是解決特定問題的措施。描述一種算法可以采用