第一章 atingdaode 計算機基礎(chǔ)知識
1.1 第一臺計算機
1946年 eniac
1.2 發(fā)展階段的標志
1.3 四個發(fā)展階段
人們以電子元器件更新作為計算機更新?lián)Q代的標志。
第一代：約1946到1958年間，這個時期構(gòu)成計算機的主要邏輯元件是電子管，稱為電子管時代。
第二代：約1959到1964年間。第二代計算機用晶體管代替了體積龐大的電子管，人們將這一時代稱為晶體管計算機時代。
第三代：約1965到1970年間，此階段以中、小規(guī)模集成電路作為計算機的邏輯元件。這一時代稱為集成電路計算機時代。
第四代：從70年代起，隨著集成電路集成度的不斷提高，采用大規(guī)模、超大規(guī)模集成電路作邏輯元件, 這一時代稱為大規(guī)模集成電路計算機時代
第二章 計算機發(fā)展簡史
2.1 計算機原理
計算機的基本原理是存貯程序和程序控制。預先要把指揮計算機如何進行操作的指令序列（稱為程序）和原始數(shù)據(jù)通過輸入設(shè)備輸送到計算機內(nèi)存貯器中。每一條指令中明確規(guī)定了計算機從哪個地址取數(shù)，進行什么操作，然后送到什么地址去等步驟。
計算機在運行時，先從內(nèi)存中取出第一條指令，通過控制器的譯碼，按指令的要求，從存貯器中取出數(shù)據(jù)進行指定的運算和邏輯操作等加工，然后再按地址把結(jié)果送到內(nèi)存中去。接下來，再取出第二條指令，在控制器的指揮下完成規(guī)定操作。依此進行下去，直至遇到停止指令。
程序與數(shù)據(jù)一樣存貯，按程序編排的順序，一步一步地取出指令，自動地完成指令規(guī)定的操作是計算機最基本的工作原理。這一原理最初是由美籍匈牙利數(shù)學家馮.諾依曼于1945年提出來的，故稱為馮.諾依曼原理。
2.2 馮.諾依曼計算機體系結(jié)構(gòu)計算機的組成部分
1.計算機由控制器、運算器、存儲器、輸入設(shè)備、輸出設(shè)備五大部分組成。
2.程序和數(shù)據(jù)以二進制代碼形式不加區(qū)別地存放在存儲器中，存放位置由地址確定。
3.控制器根據(jù)存放在存儲器中地指令序列（程序）進行工作，并由一個程序計數(shù)器控制指令地執(zhí)行?？刂破骶哂信袛嗄芰?，能根據(jù)計算結(jié)果選擇不同的工作流程。
人們把馮諾依曼的這個理論稱為馮諾依曼體系結(jié)構(gòu)。從ENIAC到當前最先進的計算機都采用的是馮諾依曼體系結(jié)構(gòu)。所以馮諾依曼是當之無愧的數(shù)字計算機之父。
根據(jù)馮諾依曼體系結(jié)構(gòu)構(gòu)成的計算機，必須具有如下功能：
把需要的程序和數(shù)據(jù)送至計算機中。
必須具有長期記憶程序、數(shù)據(jù)、中間結(jié)果及最終運算結(jié)果的能力。
能夠完成各種算術(shù)、邏輯運算和數(shù)據(jù)傳送等數(shù)據(jù)加工處理的能力。
能夠根據(jù)需要控制程序走向，并能根據(jù)指令控制機器的各部件協(xié)調(diào)操作。
能夠按照要求將處理結(jié)果輸出給用戶。
為了完成上述的功能，計算機必須具備五大基本組成部件，包括：
輸入數(shù)據(jù)和程序的輸入設(shè)備；
記憶程序和數(shù)據(jù)的存儲器；
完成數(shù)據(jù)加工處理的運算器；
控制程序執(zhí)行的控制器；
輸出處理結(jié)果的輸出設(shè)備 。
附：非馮諾依曼體系，哈佛結(jié)構(gòu)的程序和數(shù)據(jù)是分開尋址的。
如51單片機。有16根地址線，但它可以尋址64K的程序和64K的數(shù)據(jù)。
而馮諾依曼體系結(jié)構(gòu)程序和數(shù)據(jù)是統(tǒng)一編址的。
8086中20根的地址線1MB的空間地址和數(shù)據(jù)是共用的。
程序加數(shù)據(jù)共1MB
2.3 cpu組成
控制器和運算器
2.4 內(nèi)存分類
隨機存取存儲器（RAM） 虛擬內(nèi)存 高速緩存（Cache）只讀存儲器（ROM）
輸入輸出設(shè)備
鍵盤 定位設(shè)備 數(shù)據(jù)掃描設(shè)備 語音識別設(shè)備/顯示器 音頻輸出打印機 繪圖儀
系統(tǒng)組成
硬件系統(tǒng)和軟件系統(tǒng)（系統(tǒng)軟件與應(yīng)用軟件）
2.5 數(shù)值轉(zhuǎn)換
同進位計數(shù)制之間的轉(zhuǎn)換原則：不同進位計數(shù)制之間的轉(zhuǎn)換是根據(jù)兩個有理數(shù)如相等，則兩數(shù)的整數(shù)和分數(shù)部分一定分別相等的原則進行的。也就是說，若轉(zhuǎn)換前兩數(shù)相等，轉(zhuǎn)換后仍必須相等。
有四進制
十進制：有10個基數(shù)：0 ~~ 9 ，逢十進一
二進制：有2 個基數(shù)：0 ~~ 1 ，逢二進一
八進制：有8個基數(shù)：0 ~~ 7 ，逢八進一
十六進制：有16個基數(shù)：0 ~~ 9，A，B，C，D，E，F (A=10,B=11,C=12,D=13,E=14,F=15) ，逢十六進一
1、數(shù)的進位記數(shù)法
N=a n-1*p n-1+a n-2*p n-2+…+a2*p2+a1*p1+a0*p0
2、十進制數(shù)與P進制數(shù)之間的轉(zhuǎn)換
①十進制轉(zhuǎn)換成二進制：十進制整數(shù)轉(zhuǎn)換成二進制整數(shù)通常采用除2取余法，小數(shù)部分乘2取整法。例如，將(30)10轉(zhuǎn)換成二進制數(shù)。
將(30)10轉(zhuǎn)換成二進制數(shù)
2| 30 ….0 ----最右位
2 15 ….1
2 7 ….1
2 3 ….1
1 ….1 ----最左位
∴ (30)10=（11110)2
將(30)10轉(zhuǎn)換成八、十六進制數(shù)
8| 30 ……6 ------最右位
3 ------最左位
∴ (30)10 =(36)8
16| 30 …14(E)----最右位
1 ----最左位
∴ （30)10 =（1E)16
3、將P進制數(shù)轉(zhuǎn)換為十進制數(shù)
把一個二進制轉(zhuǎn)換成十進制采用方法：把這個二進制的最后一位乘上20，倒數(shù)第二位乘上21，……,一直到最高位乘上2n,然后將各項乘積相加的結(jié)果就它的十進制表達式。
把二進制11110轉(zhuǎn)換為十進制
（11110）2=1*24+1*23+1*22+1*21+0*20=
=16+8+4+2+0
=（30）10
把一個八進制轉(zhuǎn)換成十進制采用方法：把這個八進制的最后一位乘上80，倒數(shù)第二位乘上81，……,一直到最高位乘上8n,然后將各項乘積相加的結(jié)果就它的十進制表達式。
把八進制36轉(zhuǎn)換為十進制
（36）8=3*81+6*80=24+6=（30）10
把一個十六進制轉(zhuǎn)換成十進制采用方法：把這個十六進制的最后一位乘上160，倒數(shù)第二位乘上161，……,一直到最高位乘上16n,然后將各項乘積相加的結(jié)果就它的十進制表達式。
把十六制1E轉(zhuǎn)換為十進制
（1E）16=1*161+14*160=16+14=（30）10
3、二進制轉(zhuǎn)換成八進制數(shù)
(1)二進制數(shù)轉(zhuǎn)換成八進制數(shù)：對于整數(shù)，從低位到高位將二進制數(shù)的每三位分為一組，若不夠三位時，在高位左面添0，補足三位，然后將每三位二進制數(shù)用一位八進制數(shù)替換，小數(shù)部分從小數(shù)點開始，自左向右每三位一組進行轉(zhuǎn)換即可完成。例如：
將二進制數(shù)1101001轉(zhuǎn)換成八進制數(shù)，則
(001 101 001)2
| | |
( 1 5 1)8
( 1101001)2=(151)8
(2)八進制數(shù)轉(zhuǎn)換成二進制數(shù)：只要將每位八進制數(shù)用三位二進制數(shù)替換，即可完成轉(zhuǎn)換，例如，把八進制數(shù)(643.503)8，轉(zhuǎn)換成二進制數(shù)，則
(6 4 3 . 5 0 3)8
| | | | | |
(110 100 011 . 101 000 011)2
(643.503)8=(110100011.101000011)2
4、二進制與十六進制之間的轉(zhuǎn)換
(1)二進制數(shù)轉(zhuǎn)換成十六進制數(shù)：由于2的4次方=16，所以依照二進制與八進制的轉(zhuǎn)換方法，將二進制數(shù)的每四位用一個十六進制數(shù)碼來表示，整數(shù)部分以小數(shù)點為界點從右往左每四位一組轉(zhuǎn)換，小數(shù)部分從小數(shù)點開始自左向右每四位一組進行轉(zhuǎn)換。
(2)十六進制轉(zhuǎn)換成二進制數(shù)
如將十六進制數(shù)轉(zhuǎn)換成二進制數(shù)，只要將每一位十六進制數(shù)用四位相應(yīng)的二進制數(shù)表示，即可完成轉(zhuǎn)換。
例如：將(163.5B)16轉(zhuǎn)換成二進制數(shù)，則
( 1 6 3 . 5 B )16
| | | | |
(0001 0110 0011. 0101 1011 )2
(163.5B)16=(101100011.01011011)2
第三章 軟硬件系統(tǒng)知識
3.1 總線的作用（計算機主要部件（處理器，主存，I/O模塊）為了交換數(shù)據(jù)和控制信號，需要進行互聯(lián)。最流行的方式互聯(lián)是使用多條線路組成的共享系統(tǒng)總線：當代系統(tǒng)中通常采用層次式總線以改善性能;計算機系統(tǒng)含有多種總線，它們在計算機系統(tǒng)的各個層次提供部件之間的通信線路） 總線的特征（機械特性/電氣特性/功能特性/時間特性）
3.2 存儲器分類（按存取方法
順序存取 直接存取 隨機存取 按存儲介質(zhì) 半導體存儲器磁表面存儲器 光盤）
存儲器層次結(jié)構(gòu)（緩存 貯存層次和貯存 賦存層次）
3.3 cpu結(jié)構(gòu)與功能
（CPU基本功能：指令控制 操作控制 時間控制 數(shù)據(jù)加工）
3.4 輸入輸出接口的功能 接口的類型
（功能：控制與定時 處理器通信 設(shè)備通信 數(shù)據(jù)緩沖 檢錯）
（類型 按數(shù)據(jù)傳送方式 串口和并口）
3.5 輸入輸出信息的傳遞控制方式
（1）程序查詢方式 （2）程序中斷方式 （3）直接存儲器存取方式（DMA）（4） I/O通道控制方式
3.6 操作系統(tǒng)概念（計算機系統(tǒng)就是按人的要求接受和存儲信息，自動進行數(shù)據(jù)處理和計算，并輸出結(jié)果信息的系統(tǒng)操作系統(tǒng)是計算機系統(tǒng)中的系統(tǒng)軟件，是能有效地組織和管理計算機系統(tǒng)中的硬件和軟件資源，合理地組織計算機工作流程，控制程序的執(zhí)行，并向用戶提供各種服務(wù)功能，是的用戶能夠靈活、方便、有效使用計算機、并使整個計算機系統(tǒng)能有效地運行的一組程序模塊的集合）
分類（單用戶單任務(wù) 單用戶多任務(wù) 多用戶單任務(wù)） 特征（并發(fā) 共享虛擬 異步性） 功能（存儲管理功能 處理機管理功能 設(shè)備管理功能 文件管理功能 用戶接口）
3.7 計算機網(wǎng)絡(luò)分類（根據(jù)傳輸技術(shù)分類 廣播式網(wǎng)絡(luò) 點對點式網(wǎng)絡(luò) 根據(jù)覆蓋范圍 lan wan can ） 計算機網(wǎng)絡(luò)功能 （通信 資源共享 ）計算機網(wǎng)絡(luò)的體系結(jié)構(gòu)OSI/RM模型（開放系統(tǒng)互聯(lián)參考模型）組成（物理層 數(shù)據(jù)鏈路層 網(wǎng)絡(luò)層 傳輸層 會話層 表示層 應(yīng)用層） TCP/IP參考模型（主機網(wǎng)絡(luò)層 互聯(lián)層 傳輸層和應(yīng)用層） 網(wǎng)絡(luò)拓撲結(jié)構(gòu)（總線型拓撲、星型拓撲、環(huán)型拓撲、樹型拓撲和混合型拓撲） IP地址的概念與分類（用小數(shù)點分開的四個十進制整數(shù) 每個十進制數(shù)編碼成一個字節(jié)即最大255 四種格式 A最大16777216 B65536 C256D） 域名系統(tǒng)（用字母表示的計算機叫域名 網(wǎng)絡(luò)中用于標示一臺計算機名字通常有4部分組成：四個部分主機名 組織名 組織類型名 國家名 mil軍事 net網(wǎng)絡(luò)服務(wù)公司 org非com類組織） 網(wǎng)絡(luò)協(xié)議概念（為計算機網(wǎng)絡(luò)中進行數(shù)據(jù)交換而建立的規(guī)則、標準或約定的集合。） 數(shù)據(jù)保護措施（數(shù)據(jù)加密 數(shù)據(jù)完整性保護）
第四章 程序設(shè)計基礎(chǔ)知識
4.1 程序和算法的概念 算法表示方法
為解決一個問題而采取的方法和步驟，稱為算法
計算機程序是指為讓計算機完成特定任務(wù)為設(shè)計的指令序列。程序時編程者寫的、計算機能夠理解并執(zhí)行的一些命令的集合）
算法的特征：有窮性 確定性 有效性
算法的表示：自然語言 傳統(tǒng)流程圖（順序結(jié)構(gòu) 分類結(jié)構(gòu) 循環(huán)結(jié)構(gòu) ）偽碼
4.2 C語言的基本結(jié)構(gòu) C語言數(shù)據(jù)類型（整形 實型 字符型）
數(shù)組元素地址計算方法 C語言的控制語句 循環(huán)語句（課本P131—134）
一個c程序有一個或多個函數(shù)組成 一個c程序可以包含一個或多個源文件 每個源文件，有一個或多個函數(shù)組成
C程序是由函數(shù)組成
計算方法：維的下界是不是1,二維數(shù)組A(mn)按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占用d個存儲單元。元素a(ij)的存儲地址應(yīng)是數(shù)組的基地址加上排在a(ij)前面的元素所占用的單元數(shù)。因為a(ij)位于第i行、第j列，前面i-1行一共有(i-1)×n個元素，第i行上a(ij)前面又有j-1個元素，故它前面一共有(i-1) ×n+j-1個元素。
因此，a（ij）的地址計算函數(shù)為：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d。
同樣，三維數(shù)組A(ijk)按“行優(yōu)先順序”存儲，其地址計算函數(shù)為：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d。
上述討論均是假設(shè)數(shù)組各維的下界是1，更一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是1。a(ij)前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個元素，第i行上a(ij)前一共有j-c2個元素。
因此，a(ij)的地址計算函數(shù)為：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d。
例如，在C語言中，數(shù)組各維下標的下界是0，因此在C語言中，二維數(shù)組的地址計算公式為：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d。
4.3 數(shù)據(jù)結(jié)構(gòu)
概念（數(shù)據(jù)是信息的載體，他能夠夠被計算機識別、存儲和加工處理。在計算機科學中，所謂數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)也可以是非數(shù)值數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種會多種關(guān)系的數(shù)據(jù)元素的集合）
研究對象
基本術(shù)語
四類基本結(jié)構(gòu)（集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu)）
存儲結(jié)構(gòu)的兩種方法（順序/鏈式）
線性結(jié)構(gòu)有哪些 （線性表（如結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體鏈表）、一維數(shù)組、字符串、堆棧、隊列）
單鏈表（鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始）
棧和隊列的特點 （棧 先進后出 隊列 先進后出）
二叉樹的概念和特點（二叉樹是有限個元素的集合，該集合或者為空、或者由一個稱為gender元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，在二叉樹中一個元素也稱為一個節(jié)點）
二叉樹的特點（（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。
二叉樹的基本性質(zhì)：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點；
（2）深度為m的二叉樹最多有2m-1個結(jié)點；
（3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；
（4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；
（5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1；
（6）設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，….n給結(jié)點進行編號（k=1,2….n），有以下結(jié)論：
①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點編號為INT(k/2)；
②若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；
③若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。
滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k-1個結(jié)點深度為m的滿二叉樹有2m-1個結(jié)點。
完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。
二叉樹存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。 ）
圖的存儲架構(gòu)有（鄰接矩陣 鄰接表）
有何特點 查找表(靜態(tài)查找表結(jié)構(gòu) 順序結(jié)構(gòu) 有序表的折半查找) 動態(tài)查找表
4.4 編譯程序概念（計算機只能直接執(zhí)行用機器語言編寫的程序，用匯編語言或高級語言編寫的程序需要首先轉(zhuǎn)換成等價的機器機器語言程序，計算機才能執(zhí)行。把這種轉(zhuǎn)換程序統(tǒng)稱為翻譯程序。吧匯編語言的翻譯程序成為匯編程序，把高級語言的翻譯程序成為編譯程序.）
編譯和解釋的不同（對高級語言的處理也可采用另一種方式，即它并不把源程序編譯成機器語言程序然后執(zhí)行該機器語言的語言程序，而是采用邊編譯邊執(zhí)行的解釋執(zhí)行方式。這種處理程序成為解釋程序。
編譯程序的工作有哪些（詞法分析 語法分析 中間代碼生成 中間代碼優(yōu)化及目標代碼生成的等工作）
第五章 軟件開發(fā)知識
5.1數(shù)據(jù)管理技術(shù)的發(fā)展階段（人工管理階段；文件系統(tǒng)階段；數(shù)據(jù)庫階段）關(guān)系模型的概念和事務(wù)的概念（所謂關(guān)系模型就是指用若干關(guān)系表示的實體及其聯(lián)系。事務(wù)是數(shù)據(jù)庫恢復和并發(fā)控制的基本單位）數(shù)據(jù)庫恢復能與實現(xiàn)技術(shù) （實現(xiàn)恢復的基本原理很簡單，就是冗余，即數(shù)據(jù)的重復存儲，兩種方法，定期數(shù)據(jù)轉(zhuǎn)儲和建立日志文件）數(shù)據(jù)庫安全性（數(shù)據(jù)庫的安全性控制一般采用用戶標示和口令鑒別，存取控制，視圖機制，數(shù)據(jù)加密）
5.2 軟件工程提出的背景（軟件危機：軟件開發(fā)成本和開發(fā)進度的估計往往不準確；用戶對已完成的軟件系統(tǒng)不滿意現(xiàn)象經(jīng)常發(fā)生；軟件產(chǎn)品的質(zhì)量往往不可靠；軟件沒有適當?shù)奈臋n資料；軟件通常是不可維護的）軟件開發(fā)方法有哪些（生命周期法 快速原型法 面向?qū)ο蠓?/SPAN>） 生命周期法的主要階段（系統(tǒng)分析；程序設(shè)計，系統(tǒng)實施，系統(tǒng)運行和維護）
第六章 計算機領(lǐng)域典型問題
解決實際問題的步驟（首先從這個實際問題中抽象出一個數(shù)學模型，然后設(shè)計一個解此數(shù)據(jù)模型的算法，然后根據(jù)算法編寫程序，經(jīng)過調(diào)試和運行，從而完成該問題的求解）漢諾塔 哲學家 共餐問題反應(yīng)得是計算機科學什么問題（計算機程序設(shè)計中多進程共享單個處理機資源時的并發(fā)控制問題）
