計(jì)算機(jī)軟件技術(shù)基礎(chǔ)自學(xué)指導(dǎo)書(shū)

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)自學(xué)指導(dǎo)書(shū)東南大學(xué)電氣工程系 王 磊說(shuō)明1、使用教材： 沈被娜等編著計(jì)算機(jī)軟件技術(shù)基礎(chǔ) （第三版），清華大學(xué)出版社2、先修課程： 高級(jí)程序設(shè)計(jì)語(yǔ)言（ C或 Pasca）l3、計(jì)劃學(xué)時(shí)數(shù)：90小時(shí)自學(xué)， 30小時(shí)面授4、答疑與作業(yè)： 在自學(xué)過(guò)程中，若有問(wèn)題可通過(guò)信函（包括 E-mail ）進(jìn)行答疑。每章作業(yè)應(yīng) 按要求完成。第一章 軟件工程技術(shù)基礎(chǔ)一、 教學(xué)目的與要求： 通過(guò)本章的學(xué)習(xí)， 掌握軟件工程的基本理論知識(shí)， 了解和掌握當(dāng)前流行的軟 件開(kāi)發(fā)工具與環(huán)境，提高軟件開(kāi)發(fā)的能力與水平。本章內(nèi)容提要：1、信息與計(jì)算機(jī)2、軟件工程概述：（1）軟件的定義、特性、分類、軟件質(zhì)量的評(píng)價(jià)。（

2、2）軟件危機(jī)的表現(xiàn)、原因（3）軟件工程的概念、三要素。（4）軟件的生命周期。（5）軟件開(kāi)發(fā)模型（瀑布 /快速原型 /面向?qū)ο?/組件）、主要特點(diǎn)3、軟件開(kāi)發(fā)過(guò)程：各階段的任務(wù)、方法、步驟、文檔1）可行性分析2）需求分析3）概要設(shè)計(jì)4）詳細(xì)設(shè)計(jì)5）面向?qū)ο蠓治雠c設(shè)計(jì)方法6）軟件編碼7）軟件測(cè)試8）軟件維護(hù)4、軟件開(kāi)發(fā)管理：本章的難點(diǎn)與重點(diǎn)：1、軟件和軟件工程的基本概念2、軟件生命周期各階段的任務(wù)及文檔3、軟件開(kāi)發(fā)的常用模型與方法4、面向?qū)ο蟮幕靖拍詈吞卣魉摹?習(xí)題：P.21 1.8P.263 6.1 6.2第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算本章的教學(xué)目的與要求通過(guò)本章的學(xué)習(xí)，要求學(xué)生掌握基本數(shù)據(jù)結(jié)果

3、的定義、實(shí)現(xiàn)和應(yīng)用。基 本數(shù)據(jù)結(jié)構(gòu)包括線性表、樹(shù)、圖等。在求解問(wèn)題時(shí)能選擇合理的數(shù)據(jù)結(jié)構(gòu)， 采用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)出合理可行的算法。在學(xué)習(xí)過(guò)程中可選擇部分算法上機(jī)練習(xí)。本章內(nèi)容提要1、數(shù)據(jù)結(jié)構(gòu)概念（1）數(shù)據(jù)結(jié)構(gòu) +算法 =程序（2）抽象數(shù)據(jù)類型（3）邏輯結(jié)構(gòu) /物理結(jié)構(gòu)（4）算法及其效率的分析方法2、線性表（1）線性表的定義、特性（2）基本操作（3）順序存儲(chǔ)的向量：特點(diǎn)、不足（ 4） 線性鏈表：?jiǎn)蜗蜴湵?、循環(huán)鏈表、雙向鏈表（5）棧和隊(duì)列（ LIFO/FIFO 、存儲(chǔ)方式、基本操作、應(yīng)用）（ 6） 數(shù)組（特點(diǎn)、運(yùn)算、稀疏矩陣的處理方法：特殊稀疏矩陣，隨機(jī) 稀疏矩陣）3、樹(shù)（1）樹(shù)的定義、基本術(shù)

4、語(yǔ)、性質(zhì)（ E=N-1）、存儲(chǔ)（2）二叉樹(shù)的定義、滿二叉樹(shù)、完全二叉樹(shù)、平衡二叉樹(shù)、性質(zhì)（3）二叉樹(shù)的存儲(chǔ)（順序、二叉鏈）（4）樹(shù)的二叉樹(shù)表示（5）二叉樹(shù)的遍歷及其應(yīng)用（6）二叉樹(shù)的應(yīng)用（二叉排序樹(shù)、哈夫曼樹(shù)、 WPL 、判定樹(shù)）5、圖（1）圖的定義、術(shù)語(yǔ)（度、有向圖 /無(wú)向圖、完全圖、子圖等）（2）圖的存儲(chǔ)（鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、十字鏈表）（3）（4）6、檢索（1）（2）（3）（4）7、排序（1）圖的遍歷（ DFS/BFS）圖的應(yīng)用檢索的概念、方法分類（靜態(tài) /動(dòng)態(tài) /哈希）、ASL 靜態(tài)方法：線性 /折半 /分塊的基本思想、 ASL 動(dòng)態(tài)方法：二叉排序樹(shù)查找 哈希方法： Hash 函

5、數(shù)、沖突及其解決方法、查找方法、 ASL概念、基本操作（比較 /移動(dòng)）、分類（內(nèi)排序 /外排序）、分析方法 （趟、時(shí)空復(fù)雜度、穩(wěn)定性）（2）（3）（4）（5）插入：直接插入 /折半插入選擇：直接選擇 /堆排序交換：冒泡 /快速 各種方法的排序思想、比較（空間、時(shí)間、穩(wěn)定性）本章難點(diǎn)與重點(diǎn)1、線性表的操作算法2、二叉樹(shù)的概念、遍厲及其應(yīng)用3、檢索算法的各自特點(diǎn)及適用情況4、排序算法的各自特點(diǎn)及適用情況，算法的比較四、 習(xí)題P.1012.5 2.9 2.10 2.12 2.18 2.19 2.24 2 25 2.262.29 2.30 2.31(1) (3) 2.32 2.332.34 2.352

6、.40 2.41 2.42第三章 操作系統(tǒng)一、 本章的教學(xué)目的與要求 學(xué)生通過(guò)本章的學(xué)習(xí)，了解操作系統(tǒng)的發(fā)展史，掌握操作系統(tǒng)的各個(gè)管理功 能的作用及其實(shí)現(xiàn)方法， 掌握用戶接口的作用及使用方法。 從而達(dá)到理解如何控 制和管理計(jì)算機(jī)系統(tǒng)中軟硬件資源的目的。本章內(nèi)容提要、1、OS 的基本概念：定義、配置 OS 的目的、產(chǎn)生、發(fā)展、分類、功能、特 點(diǎn)2、作業(yè)管理：作業(yè)及其分類（交互式 /批處理）、批處理作業(yè)的狀態(tài)轉(zhuǎn)換、 JCB、 作業(yè)調(diào)度3、存儲(chǔ)管理：（1）功能、地址映射（2）實(shí)存管理（分區(qū)分配、覆蓋、交換）（3）虛存管理：虛存概念、程序的局部性原理、請(qǐng)求分頁(yè)式管理、請(qǐng)求分段式管理、請(qǐng)求分段頁(yè)式管理、

7、動(dòng)態(tài)鏈接（4）各種管理方法的特點(diǎn)：（5）地址映射的方法、存儲(chǔ)保護(hù)的實(shí)現(xiàn)4、進(jìn)程管理（1）進(jìn)程的概念、特點(diǎn)、與程序的關(guān)系（2）進(jìn)程的狀態(tài)及其轉(zhuǎn)換（3）進(jìn)程實(shí)體：程序、數(shù)據(jù)、 PCB（4）進(jìn)程調(diào)度方法（5）多道程序并發(fā)中互斥 /同步問(wèn)題及其實(shí)現(xiàn)：臨界資源 /臨界區(qū)、PV 操作（6）死鎖的概念5、設(shè)備管理（1）設(shè)備的分類（2）設(shè)備的獨(dú)立性、設(shè)備管理的功能（3）I/O 的控制方式、通道技術(shù)（4）緩沖技術(shù)（5）虛擬設(shè)備與 Spooling 技術(shù)6、文件管理（1）功能：（2）文件組織與存取方法（3）文件目錄管理： FCB、各種目錄結(jié)構(gòu)的特點(diǎn)（4）文件使用一般模型7、用戶接口三、 本章難點(diǎn)與重點(diǎn)1、虛擬存儲(chǔ)

8、器的概念、請(qǐng)求分頁(yè)式管理方法2、進(jìn)程與程序的關(guān)系3、多道程序并發(fā)中互斥 /同步問(wèn)題及其實(shí)現(xiàn)4、中斷、通道的概念，設(shè)備管理中的若干技術(shù)問(wèn)題5、文件目錄在文件管理中的作用6、用戶接口的作用及使用方法四、 習(xí)題P.1713.1 3.7 3.8 3.11 3.12 3.14 3.18 3.21 3.22 3.26第四章 數(shù)據(jù)庫(kù)系統(tǒng)一、 本章的教學(xué)目的與要求 通過(guò)本章的學(xué)習(xí)，要求學(xué)生了解數(shù)據(jù)庫(kù)的基本概念，理解關(guān)系數(shù)據(jù)庫(kù)的結(jié)構(gòu) 與原理，掌握數(shù)據(jù)庫(kù)處理數(shù)據(jù)的方法，能進(jìn)行簡(jiǎn)單的數(shù)據(jù)庫(kù)設(shè)計(jì)，使用基本的 SQL操縱數(shù)據(jù)庫(kù)。本章內(nèi)容提要1、幾種數(shù)據(jù)管理方式的特點(diǎn)2、數(shù)據(jù)庫(kù)系統(tǒng)的概念（1） 數(shù)據(jù)庫(kù)（2） 數(shù)據(jù)庫(kù)系統(tǒng)

9、（軟件、硬件、 DBA 、用戶等 ）（3）數(shù)據(jù)模型（概念模型、數(shù)據(jù)模型、存儲(chǔ)模型）（4）三種數(shù)據(jù)模型（5）數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)（三層模式、兩個(gè)映射、三個(gè)視圖、 數(shù)據(jù)獨(dú)立性的實(shí)現(xiàn)）（6）DBMS （功能、組成、工作過(guò)程）（7）數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的構(gòu)成 （用戶角度的數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)）3、關(guān)系數(shù)據(jù)庫(kù)（1） 基本概念（關(guān)系、域、屬性、關(guān)鍵字、元組、階、基數(shù)、關(guān)系模 式等）（2） 關(guān)系代數(shù)：運(yùn)算（3）數(shù)據(jù)依賴及關(guān)系的規(guī)范化（4）SQL 語(yǔ)言基礎(chǔ)4、數(shù)據(jù)庫(kù)設(shè)計(jì)（1）設(shè)計(jì)步驟（2）概念設(shè)計(jì)、E-R 圖（3）邏輯設(shè)計(jì)、E-R 圖向關(guān)系模型的轉(zhuǎn)化、優(yōu)化三、 本章難點(diǎn)與重點(diǎn)1、數(shù)據(jù)庫(kù)的基本概念：特點(diǎn)、數(shù)據(jù)庫(kù)的體系

10、結(jié)構(gòu)與數(shù)據(jù)獨(dú)立性、數(shù)據(jù)模型2、關(guān)系數(shù)據(jù)模型的特點(diǎn)3、關(guān)系規(guī)范化理論4、SQL語(yǔ)言基礎(chǔ)5、E-R方法四、 習(xí)題P2094.1 4.3 4.74.8 （1） 、（2） 、（3） 、（4） 、（5）給出滿足第三范式的關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)結(jié)果，并指出各關(guān)系的關(guān)鍵字。自學(xué)時(shí)間分配及進(jìn)度表周次內(nèi)容時(shí)間作業(yè)11.1- 1.46.1 6.25P.21 1.8P.263 6.12 6.2 - 6.45P.263 6.232.1 2.2（線性表、 向量、鏈 表）7P.1012.5 2.9 2.10 2.1242.3 （隊(duì)列 /棧及其應(yīng)用）32.18 2.19 2.2452.4 （數(shù)組概念及稀疏矩陣處 理）52 25 2

11、.2662.5.1- 2.5.3（ 樹(shù)、二叉樹(shù)概 念、二叉樹(shù)遍歷、 ）52.29 2.30 2.31(1)(3)72.5.4 二叉樹(shù)應(yīng)用 （ 二叉排序 樹(shù)、哈夫曼樹(shù)、判定樹(shù) ）52.32 2.3382.6 圖 （概念、存儲(chǔ)、遍歷 ）52.34 2.3592.7 查找（靜態(tài)、動(dòng)態(tài)、哈希表）62.40 2.4192.8 排序（插入、選擇、交換）62.42103.1 引言3.2 存儲(chǔ)管理5P.1713.1 3.7 3.8113.3（ 作業(yè)管理、進(jìn)程管理 ）53.11 3.1212 3.3.4 并發(fā)3.4 設(shè)備管理53.14 3.18133.5 文件管理3.6 用戶接口53.21 3.22 3.261