計算機科學技術導論教程第2章

計算機科學技術的基礎知識

內容提要：計算機的運算基礎命題邏輯與邏輯代數(shù)基礎計算機的基本結構與工作原理程序設計基礎算法基礎數(shù)據結構基礎要求：通過本章的學習，應掌握數(shù)制間的轉換方法以及數(shù)據在計算機內部的表示形式，理解邏輯代數(shù)、計算機的工作原理、程序設計以及算法與數(shù)據結構的基本知識，為學習本書的以下各章和后續(xù)課程打好基礎

1數(shù)制十進制：是使用數(shù)字1、2、…、9、0等符號來表示數(shù)值且采用“逢十進一”的進位計數(shù)制位權表示法數(shù)制的特點：數(shù)字的總個數(shù)等于基數(shù)。如十進制使用10個數(shù)字（0～9）最大的數(shù)字比基數(shù)小1。如十進制中最大的數(shù)字為9每個數(shù)字都要乘以基數(shù)的冪次，該冪次由每個數(shù)字所在的位置決定任何一個N進制數(shù)A＝AnAn－1…A1A0.A－1A－2…A－m2二進制二進制：使用數(shù)字0和1等符號來表示數(shù)值且采用“逢二進一”的進位計數(shù)制二進制數(shù)制的特點：

僅使用0和1兩個數(shù)字最大的數(shù)字為1，最小的數(shù)字為0每個數(shù)字都要乘以基數(shù)2的冪次，該冪次由每個數(shù)字所在的位置決定

二進制加法和乘法運算規(guī)則：

0＋0＝0; 0×0＝0; 0＋1＝1; 0×1＝01＋0＝1; 1×0＝0; 1＋1＝1; 1×1＝1

3八進制與十六進制八進制：使用數(shù)字0、1、2、3、4、5、6、7等符號來表示數(shù)值的，且采用“逢八進一”的進位計數(shù)制十六進制：使用數(shù)字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符號來表示數(shù)值，其中A、B、C、D、E、F分別表示數(shù)字10、11、12、13、14、15。十六進制的計數(shù)方法為“逢十六進一”

4十進制整數(shù)轉換為非十進制整數(shù)

除基取余法：“除基取余，先余為低（位），后余為高（位）”〖例2-1〗（55）10＝（110111）2

2222221551276130131110余數(shù)5十進制整數(shù)轉換為非十進制整數(shù)（續(xù)）〖例2-2,例2-3〗（55）10=（67）8=（37）16886555516166703703余數(shù)余數(shù)6十進制小數(shù)轉換為非十進制小數(shù)

乘基取整法:“乘基取整，先整為高（位），后整為低（位）”〖例2-4〗（0.625）10＝（0.101）2

20.6250.251.250.521.021整數(shù)10×××7十進制小數(shù)轉換為非十進制小數(shù)

十進制小數(shù)并不是都能夠用有限位的其他進制數(shù)精確地表示,這時應根據精度要求轉換到一定的位數(shù)為止，作為其近似值如果一個十進制數(shù)既有整數(shù)部分，又有小數(shù)部分，則應將整數(shù)部分和小數(shù)部分分別進行轉換8十進制小數(shù)轉換為非十進制小數(shù)(續(xù))〖例2-5〗（0.32）10＝（0.0101…）2

20.320.641.2820.5620整數(shù)01×××0.282×1.121…9非十進制數(shù)轉換為十進制數(shù)位權法：把各非十進制數(shù)按權展開，然后求和

〖例2-7〗（10110）2＝1×24＋0×23＋1×22＋1×21＋0×20

＝16＋0＋4＋2＋0＝（22）10

〖例2-8〗（10101.1011）2＝1×24＋0×23＋1×22＋0×21＋1×20＋1×2-1+0×2－2＋1×2－3＝16＋0＋4＋0＋1＋0.5＋0＋0.125＝（21.625）10

〖例2-9〗（1207）8＝1×83＋2×82＋0×81＋7×80＝512＋128＋0＋7＝（647）10

〖例2-10〗（1B2E）16＝1×163＋B×162＋2×161＋E×160

＝1×4096＋11×256＋2×16＋14×1＝（6958）10

10二進制與八進制之間的轉換二進制數(shù)轉換為八進制數(shù)：以小數(shù)點為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每三位為一組（不足三位用0補足），然后將各個三位二進制數(shù)轉換為對應的一位八進制數(shù)八進制數(shù)轉換為二進制數(shù)：把每一位八進制數(shù)轉換為對應的三位二進制數(shù)

〖例2-11〗（10111001010.1011011）2＝（010111001010.101101100）2＝（2712.554）8

〖例2-12〗（456.174）8＝（100101110.001111100）2＝（100101110.0011111）2

11二進制與十六進制之間的轉換

二進制數(shù)轉換為十六進制數(shù)：以小數(shù)點為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每四位為一組，不足四位用0補足，然后將各個四位二進制數(shù)轉換為對應的一位十六進制數(shù)十六進制數(shù)轉換為二進制數(shù)：把每一位十六進制數(shù)轉換為對應的四位二進制數(shù)

〖例2-13〗（10111001010.1011011）2＝（010111001010.10110110）2

＝（5CA.B6）16

〖例2-14〗（1A9F.1BD）16＝（0001101010011111.000110111101）2

＝（1101010011111.000110111101）2

12碼制原碼表示法：用符號位和數(shù)值表示帶符號數(shù)，正數(shù)的符號位用“0”表示，負數(shù)的符號位用“1”表示，數(shù)值部分用二進制形式表示反碼表示法：正數(shù)的反碼與原碼相同，負數(shù)的反碼為對該數(shù)的原碼除符號位外各位取反補碼表示法：正數(shù)的補碼與原碼相同，負數(shù)的補碼為對該數(shù)的原碼除符號位外各位取反，然后在最后一位加1數(shù)的原碼表示適合于進行乘除運算；補碼用于進行加減運算

13定點小數(shù)格式

定點小數(shù)格式：把小數(shù)點固定在數(shù)值部分最高位的左邊

數(shù)的范圍：二進制的（m+1）位定點小數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤1－2-m比例因子：對于絕對值大于1的數(shù)，如果直接使用定點小數(shù)格式將會產生“溢出”，需根據實際需要使用一個比例因子，將原始數(shù)據按該比例縮小，以定點小數(shù)格式表示，得出結果后再按該比例擴大得到實際的結果N0NnNn-1……N1.符號位數(shù)值部分小數(shù)點14定點整數(shù)格式

定點整數(shù)格式：把小數(shù)點固定在數(shù)值部分最低位的右邊數(shù)的范圍：二進制的（m+1）位定點整數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤2m－1比例因子：對于絕對值大于該范圍的數(shù)，如果直接使用定點小數(shù)格式也將會產生“溢出”，需根據實際需要選擇一個比例因子進行調整，使所表示的數(shù)據在規(guī)定的范圍之內N0N-1N-2……N-m.符號位數(shù)值部分小數(shù)點15浮點表示法浮點表示法：小數(shù)點的位置不固定，一個浮點數(shù)分為階碼和尾數(shù)兩部分階碼：用于表示小數(shù)點在該數(shù)中的位置，是一個整數(shù)尾數(shù)：用于表示數(shù)的有效數(shù)值，可以采用整數(shù)或純小數(shù)兩種形式可供選擇的一種位數(shù)分配形式：設字長為32位規(guī)格化的浮點數(shù)：為了提高浮點數(shù)表示的精度通常規(guī)定其尾數(shù)的最高位必須是非零的有效位，稱為浮點數(shù)的規(guī)格化形式

符號位尾數(shù)部分階碼部分1位8位23位16BCD碼與ASCII碼BCD碼：是一種二－十進制的編碼，即使用四位二進制數(shù)表示一位十進制數(shù)十進制數(shù)與BCD碼之間的轉換：可以按位（或四位二進制數(shù)組）直接進行ASCII（AmericanStandardsCommitteeofInformation）碼：是由美國信息交換標準委員會制定的、國際上使用最廣泛的字符編碼方案ASCII碼的編碼方案：采用7位二進制數(shù)表示一個字符，把7位二進制數(shù)分為高三位（b7b6b5）和低四位（b4b3b2b1）。7位ASCII編碼表：利用該表可以查找數(shù)字、運算符、標點符號以及控制符等字符與ASCII碼之間的對應關系

17漢字編碼體系漢字輸入碼：由輸入設備產生的漢字編碼，如區(qū)位碼、國標碼、拼音碼、新全拼、新雙拼、五筆字型碼、簡碼、表形碼、自然碼智能ABC漢字輸入碼等漢字內碼：用于計算機內部存儲和處理的漢字編碼，通常是由該漢字的國標碼的兩個字節(jié)（最高位置“1”）形成的漢字字形碼：是確定一個漢字字形點陣的編碼，用于漢字顯示和打印輸出。保留在存儲介質中的全部漢字字形碼稱為字庫漢字交換碼：用于在不同的漢字信息處理系統(tǒng)之間或與其他計算機系統(tǒng)之間進行信息交換漢字地址碼：表示漢字字形信息在漢字庫中的地址，用于在漢字庫中查找漢字字形信息的漢字地址碼等

18數(shù)據校驗碼奇偶校驗碼：在表示數(shù)據的N位代碼中增加一位奇偶校驗位，使N＋1位中“1”的個數(shù)為奇數(shù)（奇校驗）或偶數(shù)（偶校驗）海明校驗碼：在有效信息代碼中增加校驗位，用來校驗代碼中“1”的個數(shù)是奇數(shù)（奇校驗）還是偶數(shù)（偶校驗），通過奇偶校驗可以發(fā)現(xiàn)代碼傳輸過程中的錯誤并自動校正應用：數(shù)據校驗碼用于計算機各部件之間信息傳輸以及計算機網絡的信息傳輸

19命題命題：一個有具體意義且能夠判斷真假的陳述句命題的真值：命題所具有的值“真”（true，簡記為T）或“假”（false,簡記為F）稱為其真值命題標識符：表示命題的符號，該標識符稱為命題常量原子命題：不能分解為更為簡單的陳述句的命題復合命題：將原子命題用連接詞和標點符號復合而成的命題

20“與”（∧）

“與”（∧）:兩個命題A和B的“與”（又稱為A和B的“合取”）是一個復合命題，記為A∧B。當且僅當A和B同時為真時A∧B為真，在其他的情況下A∧B的真值均為假A∧B的真值表:

ABA∧BTTTTFFFTFFFF21“或”（∨）

“或”（∨）：兩個命題A和B的“或”（又稱為A和B的“析取”）是一個復合命題，記為A∨B。當且僅當A和B同時為假時A∨B為假，在其他的情況下A∨B的真值均為真A∨B的真值表：

ABA∨BTTTTFTFTTFFF22“非”（┑）

“非”（┑）：命題A的“非”（又稱為A的“否定”）是一個復合命題，記為┑A。若A為真，則┑A為假；若A為假，則┑A為真┑A的真值表：

A┑ATFFT23“異或”（⊕）

“異或”（⊕）：兩個命題的A和B的“異或”（又稱為A和B的“不可兼或”）是一個復合命題，記為A⊕B。當且僅當A和B同時為真或者同時為假時A⊕B為假，在其他的情況下A⊕B的真值為真A⊕B的真值表：

ABA⊕BTTFTFTFTTFFF24“條件”（→）

“條件”（→）：兩個命題的A和B的“條件”是一個復合命題，記為A→B，讀作“如果A，則B”。當且僅當A的真值為真，B的真值為假時，A→B為假，在其他的情況下A→B的真值均為真A→B的真值表：

ABA→BTTTTFFFTTFFT25“雙條件”()

“雙條件”()：兩個命題的A和B的“雙條件”（又稱為A當且僅當B）是一個復合命題，讀作“A當且僅當B”，記為AB，。當且僅當A的真值與B的真值相同時，AB為真，否則AB的真值均為假AB的真值表：

ABABTTTTFFFTFFFT26命題公式命題公式：由命題變元、連接詞和括號組成的合式的式子稱為命題公式命題公式等價：如果兩個不同的命題公式P和Q，無論其命題變元取什么值它們的真值都相同，則稱該兩個命題公式等價，記為P＝Q

〖例2-25〗證明┑（A→B）與A∧┑B是等價的

AB┑（A→B）

A∧┑B

TTFFTFTTFTFFFFFF27命題公式的等價律其中A、B、C等為命題變元，T表示“真”，F(xiàn)表示“假”零律：A∨F＝A；A∧F＝F 幺律：A∨T＝T；A∧T＝A冪等律：A∨A＝A；A∧A＝A 求補律：A∨┓A＝T；A∧┓A＝F交換律：A∨B＝B∨A；A∧B＝B∧A結合律：A∨（B∨C）＝（A∨B）∨C； A∧（B∧C）＝（A∧B）∧C分配律：A∧（B∨C）＝A∧B∨A∧C； A∨B∧C＝（A∨B）∧（A∨C）吸收律：A∧B∨A∧┓B＝A；（A∨B）∧（A∨┓B）＝A 狄－摩根定律：┓（A∨B）＝┓A∧┓B；┓（A∧B）＝┓A∨┓B雙重否定律：┓┓A＝A28證明狄－摩根定律〖例2-26〗證明狄－摩根定律之一： ┓（A∧B）＝┓A∨┓BAB（A∧B）┓（A∧B）┓A

┓B

┓A∨┓B

TTTFFFFTFFTFTTFTFTTFTFFFTTTT29邏輯代數(shù)等價律零律：A＋0＝A；A0＝0 幺律：A＋1＝1；A1＝A冪等律：A＋A＝A；AA＝A求補律：A＋A＝1；AA＝0交換律：A＋B＝B＋A； AB＝BA結合律：A＋（B＋C）＝（A＋B）＋C A（BC）＝（AB）C分配律：A（B＋C）＝AB＋AC A＋BC＝（A＋B）（A＋C）吸收律：AB＋AB＝A；（A＋B）（A＋B）＝A 狄－摩根定律：（A＋B）＝AB；（AB）＝A＋B雙重否定律：

A＝A

30邏輯函數(shù)的化簡〖例2-27〗試將邏輯函數(shù)F＝A＋AB化簡

解：F ＝A＋AB ＝（A＋A）(A＋B) （分配律） ＝1(A＋B) （求補律） ＝A＋B （幺律）〖例2-28〗試將邏輯函數(shù)F＝AB＋AB＋AB＋AB化簡。解：F ＝AB＋AB＋AB＋AB ＝A（B＋B）＋A（B＋B） （分配律） ＝A＋A

（求補律） ＝1 （求補律）31計算機硬件的基本結構輸入設備內存儲器輔助存儲器控制器運算器輸出設備程序原始數(shù)據運算結果數(shù)據控制32運算器運算器：對二進制數(shù)進行運算的部件。它在控制器的控制下執(zhí)行程序中的指令，完成各種算術運算、邏輯運算、比較運算、移位運算以及字符運算等運算器的組成：算術邏輯部件（ALU）完成加、減、乘、除等四則運算以及與、或、非、移位等邏輯運算；寄存器用來暫存參加運算的操作數(shù)或中間結果，常用的寄存器有累加寄存器、暫存寄存器、標志寄存器和