大學計算機基礎：計算機科學概論

第一部分　計算機組成與結構
第1章　計算機發(fā)展歷史　1
1.1　計算機的史前時代　1
1.1.1　石頭計算到算盤　1
1.1.2　計算尺和計算器　2
1.2　機械式計算機　4
1.2.1　契卡德計算機　4
1.2.2　帕斯卡加法機　4
1.2.3　萊布尼茲乘法機　5
1.2.4　“編織”的程序　5
1.2.5　差分機和分析機　7
1.2.6　手搖計算機　8
1.3　從機械到電子的進程　9
1.3.1　穿孔制表機　9
1.3.2　電子文明的曙光——電子二極管、三極管　10
1.3.3　沖擊最后的技術壁壘　11
1.4　電子計算機發(fā)展歷史　14
1.4.1　電子管計算機　14
1.4.2　晶體管計算機　16
1.4.3　集成電路計算機　17
1.4.4　大規(guī)模集成電路計算機　19
1.4.5　第五代計算機　21
1.4.6　總結　21
1.5　奠定現(xiàn)代計算機理論基礎的重要人物和思想　22
1.5.1　布爾及邏輯代數(shù)　22
1.5.2　香農及計算機開關電路　23
1.5.3　圖靈及圖靈機、圖靈測試　24
1.5.4　阿塔納索夫及ABC計算機　28
1.5.5　維納及計算機設計五原則　29
1.5.6　馮·諾依曼及馮·諾依曼結構　30
1.6　計算機在中國　32
1.7　計算機的發(fā)展趨勢　35
1.7.1　高性能計算　36
1.7.2　普適計算　37
1.7.3　下一代計算機　41
1.8　小結　43
習題　44
第2章　計算機組成與工作原理　47
2.1　計算機常用的數(shù)制及機內信息表示　47
2.1.1　數(shù)制及其轉換　47
2.1.2　計算機內信息的表示　49
2.2　門和電路　53
2.2.1　門　54
2.2.2　電路　57
2.3　計算機硬件組成　59
2.3.1　馮·諾依曼結構　59
2.3.2　計算機系統(tǒng)的硬件組成　60
2.3.3　總線訪問　65
2.4　計算機的工作過程　65
2.4.1　指令執(zhí)行過程　65
2.4.2　計算機工作過程　66
2.5　計算機系統(tǒng)的組成　68
2.5.1　計算機硬件系統(tǒng)　69
2.5.2　計算機軟件系統(tǒng)　77
2.6　小結　80
習題　80

第二部分　網(wǎng)絡與安全
第3章　計算機網(wǎng)絡　83
3.1　網(wǎng)絡的起源　83
3.1.1　聯(lián)機系統(tǒng)階段　83
3.1.2　網(wǎng)絡互連階段　83
3.1.3　標準化網(wǎng)絡階段　84
3.1.4　網(wǎng)絡互連與高速網(wǎng)絡　85
3.2　網(wǎng)絡的定義　85
3.3　數(shù)據(jù)傳輸　85
3.3.1　傳輸介質　85
3.3.2　帶寬　88
3.3.3　協(xié)議　88
3.4　網(wǎng)絡的分類　89
3.4.1　按距離劃分　89
3.4.2　按網(wǎng)絡的功能劃分　90
3.5　網(wǎng)絡的拓撲結構　91
3.5.1　拓撲的概念　91
3.5.2　鏈路與通路　91
3.5.3　網(wǎng)絡拓撲結構　91
3.6　服務模型　93
3.6.1　終端網(wǎng)絡模型　94
3.6.2　客戶機/服務器模型　94
3.6.3　對等網(wǎng)絡模型　94
3.7　網(wǎng)絡的體系結構　95
3.8　網(wǎng)絡互連　97
3.9　Internet和TCP/IP　99
3.9.1　Internet的起源　99
3.9.2　TCP/IP　99
3.9.3　IP地址　100
3.9.4　Internet提供的主要服務　101
3.9.5　內網(wǎng)與外網(wǎng)　104
3.10　網(wǎng)絡管理　105
3.10.1　網(wǎng)絡管理基礎　105
3.10.2　網(wǎng)絡管理功能　106
3.10.3　Internet的管理信息庫　108
3.10.4　網(wǎng)絡管理協(xié)議　109
3.11　小結　110
習題　111
第4章　信息安全　113
4.1　信息安全的基本概念　113
4.1.1　信息安全特征　113
4.1.2　信息安全保護技術　114
4.2　密碼技術及應用　115
4.2.1　基本概念　115
4.2.2　對稱密鑰密碼系統(tǒng)　116
4.2.3　公開密鑰密碼系統(tǒng)　116
4.2.4　計算機網(wǎng)絡中的數(shù)據(jù)加密　117
4.2.5　數(shù)字簽名　119
4.3　防火墻技術　119
4.3.1　防火墻的基本概念　119
4.3.2　防火墻的功能　120
4.3.3　防火墻的基本類型　120
4.3.4　防火墻的優(yōu)缺點　121
4.4　惡意軟件　122
4.4.1　病毒及相關的威脅　122
4.4.2　計算機病毒的防治　126
4.5　入侵檢測技術　128
4.5.1　入侵者　128
4.5.2　入侵檢測　129
4.6　小結　133
習題　133

第三部分　算法與程序設計
第5章　算法　135
5.1　算法的概念　135
5.1.1　概述　135
5.1.2　算法的定義　136
5.1.3　算法的基本性質　138
5.1.4　算法的基本結構　138
5.2　算法的表示　141
5.2.1　自然語言　142
5.2.2　流程圖　143
5.2.3　偽碼　145
5.3　基本算法　149
5.3.1　求和　149
5.3.2　求積　150
5.3.3　求最大值和最小值　150
5.3.4　排序　151
5.3.5　查找　152
5.4　算法效率　153
5.4.1　算法的規(guī)?！?54
5.4.2　時間復雜度　154
5.4.3　空間復雜度　155
5.5　小結　156
習題　156
第6章　程序設計語言　158
6.1　程序設計語言概述　158
6.1.1　什么是程序語言　158
6.1.2　程序語言的發(fā)展歷史　158
6.1.3　程序語言的分類　160
6.1.4　機器語言　161
6.1.5　匯編語言　163
6.1.6　高級語言　164
6.2　高級程序語言的類型　165
6.2.1　常用高級程序語言　165
6.2.2　過程化語言　167
6.2.3　函數(shù)式語言　168
6.2.4　邏輯式語言　169
6.2.5　面向對象語言　169
6.2.6　專用語言　170
6.3　程序設計的基本概念　171
6.3.1　標識符　172
6.3.2　變量與數(shù)據(jù)類型　172
6.3.3　常量和文字　174
6.3.4　表達式和賦值語句　174
6.3.5　控制語句　176
6.3.6　注釋　178
6.4　程序單元　178
6.4.1　過程　179
6.4.2　參數(shù)　179
6.4.3　函數(shù)　180
6.4.4　輸入與輸出　181
6.5　程序設計語言的執(zhí)行　181
6.5.1　程序翻譯　182
6.5.2　鏈接程序　183
6.5.3　集成開發(fā)環(huán)境　184
6.6　高級話題　184
6.6.1　面向對象程序設計　185
6.6.2　程序語言的發(fā)展趨勢　187
6.7　小結　187
習題　188

第四部分　數(shù)據(jù)組織
第7章　數(shù)據(jù)結構　191
7.1　概述　191
7.1.1　數(shù)據(jù)結構的定義　191
7.1.2　數(shù)據(jù)的邏輯結構　192
7.1.3　數(shù)據(jù)的存儲結構　192
7.1.4　數(shù)據(jù)的運算　193
7.2　線性表　193
7.2.1　基于數(shù)組的實現(xiàn)　193
7.2.2　基于鏈表的實現(xiàn)　194
7.2.3　基于線性表的檢索　195
7.3　堆?！?97
7.3.1　堆棧的基本概念　197
7.3.2　棧的實現(xiàn)　197
7.3.3　棧的操作　197
7.3.4　棧的應用　198
7.4　隊列　199
7.4.1　隊列的定義　199
7.4.2　隊列的實現(xiàn)　199
7.4.3　隊列的基本操作　200
7.4.4　隊列的應用　201
7.5　樹　201
7.5.1　二叉樹的基本概念　202
7.5.2　二叉樹的實現(xiàn)　203
7.5.3　二叉樹的遍歷　203
7.5.4　二叉檢索樹　205
7.6　圖　206
7.6.1　圖的定義和術語　206
7.6.2　圖的實現(xiàn)　207
7.6.3　圖的基本操作　208
7.6.4　圖的應用　209
7.7　小結　210
習題　210
第8章　文件結構　213
8.1　文件系統(tǒng)　213
8.1.1　文件命名　213
8.1.2　文件訪問　214
8.2　文件結構　215
8.2.1　順序文件　215
8.2.2　索引文件　216
8.2.3　散列文件　216
8.3　小結　217
習題　218
第9章　數(shù)據(jù)庫概述　220
9.1　數(shù)據(jù)庫管理系統(tǒng)　220
9.1.1　數(shù)據(jù)庫管理系統(tǒng)概述　220
9.1.2　數(shù)據(jù)庫模式　220
9.1.3　數(shù)據(jù)模型　221
9.2　關系數(shù)據(jù)庫　222
9.2.1　關系數(shù)據(jù)庫的設計　223
9.2.2　關系的操作　225
9.2.3　結構化查詢語言　227
9.3　數(shù)據(jù)庫應用　229
9.3.1　決策支持系統(tǒng)　230
9.3.2　空間數(shù)據(jù)庫　230
9.3.3　多媒體數(shù)據(jù)庫　230
9.3.4　移動數(shù)據(jù)庫　231
9.3.5　信息檢索系統(tǒng)　231
9.3.6　分布式信息系統(tǒng)　232
9.4　小結　232
習題　232
參考文獻　234