第一章 數(shù)據(jù)結(jié)構(gòu)

【要點】

第一節(jié) 數(shù)據(jù)結(jié)構(gòu)的基本概念

一、 什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)主要研究計算機系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系。

二、數(shù)據(jù)結(jié)構(gòu)中的基本概念

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

數(shù)據(jù)的存儲方法可分為：順序存儲、鏈式存儲、索引存儲、散列存儲。

三、抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型的定義由一個值域和定義在該值域上的一組操作組成。抽象數(shù)據(jù)類型的定義與使用實現(xiàn)了數(shù)據(jù)的封裝和隱藏，為對象程序設(shè)計方法提供了基礎(chǔ)，也使過程語言的可維護性大大提高。

第二節(jié) 線性表

一、線性表的概念

線性結(jié)構(gòu)的基本特點是數(shù)據(jù)元素有序并有限。線性表是n（n≥0）個相同類型的元素a1，a2，an所構(gòu)成的有限線性序列。

二、順序表

在順序表的存儲結(jié)構(gòu)中，數(shù)據(jù)元素按其邏輯次序依次存放在一組地址連續(xù)的存儲單元里。

三、線性鏈表

采用鏈式存儲結(jié)構(gòu)的鏈表是用一組任意的存儲單元來存放線性表的數(shù)據(jù)元素，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以是零散分布在內(nèi)存中的任何位置上。

四、循環(huán)鏈表

循環(huán)鏈表是一種首尾相接的鏈表。

第三節(jié) 棧、隊列及數(shù)組

一、棧

棧是限制僅在表的一端進行插入和刪除運算的線性表，它的特點是后進先出。

二、隊列

隊列是允許在線性表的一端進行數(shù)據(jù)元素插入操作而在另一端才能進行數(shù)據(jù)元素刪除操作的線性表。

三、棧和隊列的應(yīng)用

棧和隊列是應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)之一。

第四節(jié) 非線性結(jié)構(gòu)

一、樹結(jié)構(gòu)及其基本概念

樹結(jié)構(gòu)是結(jié)點之間有分支、層次關(guān)系的結(jié)構(gòu)。

二、二叉樹結(jié)構(gòu)

二叉樹是n個結(jié)點的有限集合（n≥0），它或者是空集（n=0）或者由一個根結(jié)點及兩棵互不相交的、分別稱做這個根的左子樹和右子樹的二叉樹組成。

三、圖

圖G由兩個集合V和E組成，記為G=(V,E)，其中V是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集。

四、圖的遍歷

第五節(jié) 查找與排序

一、查找

查找分為簡單查找方法（順序查找、二分查找、分塊查找）、樹表查找和哈希查找。

二、排序

排序分為簡單排序、快速排序以及歸并排序。

【要求】

本章要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)、線性表、棧、隊列、二叉樹等概念，了解和掌握順序表的插入算法、單鏈表的插入運算算法、二叉樹的有關(guān)操作、圖的有關(guān)操作、查找與排序算法等。

第二章 操作系統(tǒng)

【要點】

第一節(jié) 操作系統(tǒng)概論

一、操作系統(tǒng)的功能

操作系統(tǒng)主要有五大功能：處理機、存儲器管理、設(shè)備管理、文件管理和作業(yè)管理。

二、操作系統(tǒng)的特征

操作系統(tǒng)具有以下特征：并發(fā)行、共享性、虛擬性和不確定性。

三、操作系統(tǒng)的分類

操作系統(tǒng)的基本類型有:批處理操作系統(tǒng)、分時操作系統(tǒng)、實時操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)。

第二節(jié) 處理機管理

一、進程的概念

進程是可并發(fā)執(zhí)行的程序在給定數(shù)據(jù)集合上的一次執(zhí)行過程；是系統(tǒng)進行資源分配合調(diào)度的一個獨立的基本單位和實體；是指執(zhí)行一個映象程序的總環(huán)境。

二、進程控制與進程調(diào)度

進程控制是對進程在其生命期的各種活動及狀態(tài)轉(zhuǎn)變實施有效的控制；進程調(diào)度的任務(wù)是協(xié)調(diào)和控制各進程對CPU的使用，按照某種策略動態(tài)地將處理機分配給處于就緒狀態(tài)的某個進程。

三、進程互斥與同步

進程的互斥是由多個進程競爭同一共享資源而產(chǎn)生的相互制約的關(guān)系；進程之間通過執(zhí)行時序上的某種限制而達到相互合作，這種因相互合作而產(chǎn)生的制約關(guān)系稱為進程的同步。

四、進程的通信

目前常用的進程通信的高級方式有消息緩沖通信，管道通信和信箱通信。

五、死鎖

對資源的管理使用不當(dāng)，在一定條件下會導(dǎo)致系統(tǒng)發(fā)生隨機故障，出現(xiàn)進程被阻塞的現(xiàn)象，即若干進程彼此互相等待對方所擁有且又不放的資源，其結(jié)果是誰也無法得到繼續(xù)運行所需的全部資源，因而永遠等待下去。這種現(xiàn)象稱為死鎖。

第三節(jié) 作業(yè)管理

一、作業(yè)的概念

一個作業(yè)，就是用戶請求計算機系統(tǒng)執(zhí)行的一次獨立的上機任務(wù)，是能共享公共資源區(qū)域的一族有關(guān)進程（進程家族）。

二、作業(yè)控制

作業(yè)控制包括兩方面含義：從用戶角度看，作業(yè)控制是用戶通過作業(yè)控制級接口，組織和控制其作業(yè)在計算機上的運行的全過程。從系統(tǒng)管理的角度看，作業(yè)控制是系統(tǒng)接受、分析并執(zhí)行用戶發(fā)出的控制命令，為作業(yè)的每個發(fā)展階段提供必要的系統(tǒng)服務(wù)。

三、作業(yè)調(diào)度

作業(yè)從用戶提交開始到真正占有處理機而被執(zhí)行，要經(jīng)過多級調(diào)度才能實現(xiàn)。

第四節(jié) 存儲管理

一、存儲管理的功能

存儲管理主要有五個方面的功能：內(nèi)存分配和回收、內(nèi)存空間的共享、存儲保護、地址映射、內(nèi)存空間的擴充。

二、分區(qū)存儲管理

分區(qū)存儲管理的基本思想是把內(nèi)存劃分成若干個大小不等的連續(xù)區(qū)域，稱為分區(qū)。每個作業(yè)可占用一個或多個分區(qū)。

三、覆蓋與交換技術(shù)

覆蓋就是一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一內(nèi)存區(qū)域，即一個內(nèi)存區(qū)域可以先后被不同的程序段重復(fù)使用，當(dāng)某程序段不再需要該內(nèi)存區(qū)域時另一程序段可占用。

交換技術(shù)是指在內(nèi)外存之間交換程序和數(shù)據(jù)。

第五節(jié) 設(shè)備管理

一、數(shù)據(jù)傳送控制方式

外設(shè)與內(nèi)存間常用的數(shù)據(jù)傳送方式有：中斷控制方式、DMA方式和通道方式。

二、緩沖技術(shù)

緩沖技術(shù)的基本思想是：在內(nèi)存中開辟一個或多個專用的區(qū)域，即緩沖區(qū)，作為CPU與I/O設(shè)備之間信息傳送的集散地。

四、設(shè)備分配

設(shè)備分配的原則由設(shè)備特性及用戶請求、系統(tǒng)中設(shè)備使用情況而定。

第六節(jié) 文件管理

一、文件系統(tǒng)的概念

由于軟件資源是以文件形式存儲的，因此，對軟件資源的管理也就導(dǎo)致了文件系統(tǒng)的出現(xiàn)。

二、文件的組織

文件組織是指文件中信息的配置和構(gòu)造方式。

三、文件目錄

文件一般有一級目錄結(jié)構(gòu)、二級目錄結(jié)構(gòu)和多級目錄結(jié)構(gòu)。

【要求】

本章要求學(xué)生掌握操作系統(tǒng)的概念和功能、進程、作業(yè)概念，掌握進程調(diào)度的過程、作業(yè)調(diào)度過程以及存儲管理和設(shè)備管理中的常用技術(shù)。

第三章 軟件工程

【要點】

第一節(jié) 軟件與軟件生存周期

一、 軟件工程及軟件工程學(xué)的概念

軟件工程學(xué)主要包括軟件開發(fā)技術(shù)和軟件工程管理兩方面的內(nèi)容。

二、軟件生存周期的概念

一個軟件從用戶提出開發(fā)要求，到廢棄不用為止的全過程，稱為軟件的生存周期。

第二節(jié) 軟件的需求分析與軟件設(shè)計

一、需求分析概述

需求分析的主要內(nèi)容有：技術(shù)可行性、經(jīng)濟可行性和操作可行性。

二、結(jié)構(gòu)分析方法

結(jié)構(gòu)化分析方法簡稱SA方法，它適用于分析大型數(shù)據(jù)處理系統(tǒng)，它與設(shè)計階段的結(jié)構(gòu)化設(shè)計方法一起聯(lián)合使用，能夠較好地實現(xiàn)一個軟件系統(tǒng)的研制。

三、數(shù)據(jù)流圖

對數(shù)據(jù)流圖中包含的所有元素的定義的集合構(gòu)成了數(shù)據(jù)詞典。

四、數(shù)據(jù)詞典

對數(shù)據(jù)流圖中包含的所有元素的定義的集合構(gòu)成了數(shù)據(jù)詞典。

五、軟件設(shè)計準則

軟件設(shè)計準則涉及軟件結(jié)構(gòu)的準則、模塊化的準則以及模塊獨立性的準則幾個方面的問題。

第三節(jié) 軟件編程、軟件測試及軟件維護

一、程序設(shè)計語言

程序設(shè)計語言可以分為機器語言、匯編語言和高級語言三類。

二、編程風(fēng)格

編程風(fēng)格是指一個程序員在編程時，對程序的結(jié)構(gòu)形式，行文方式及編寫特點的要求。

三、面向?qū)ο蟮某绦蛟O(shè)計概念

面向?qū)ο筌浖_發(fā)方法又稱OOSD(Object-Oriented Software Development)；OOSD包括面向?qū)ο蠓治觯∣OA）、面向?qū)ο笤O(shè)計（OOD）和面向?qū)ο蟪绦蛟O(shè)計（OOP）三個方面。

四、軟件測試策略

軟件的測試過程是按單元測試、組裝測試、確認測試和系統(tǒng)測試四個步驟進行的。

五、常用的測試方法

常用的測試方法有黑盒測試和白盒測試兩種。

六、軟件維護的步驟與方法

具體的維護工作需要經(jīng)過理解分析、修改和重新驗證現(xiàn)有軟件系統(tǒng)三個過程。

七、軟件維護的副作用

軟件維護的副作用可以分為三類：修改程序的副作用、修改數(shù)據(jù)的副作用和文檔的副作用。

【要求】

要求學(xué)生掌握軟件、軟件生存周期概念，掌握軟件工程方法的各個階段的任務(wù)和工作流程。

第四章 數(shù)據(jù)庫技術(shù)

【要點】

第一節(jié) 數(shù)據(jù)庫技術(shù)概論

一、 數(shù)據(jù)、信息與數(shù)據(jù)處理

數(shù)據(jù)是一種物理符號序列，它的內(nèi)容是事物特性的反映；信息是經(jīng)過加工處理的數(shù)據(jù)，是人們消化理解了的數(shù)據(jù)，是數(shù)據(jù)的具體含義；數(shù)據(jù)處理是指將數(shù)據(jù)轉(zhuǎn)換成信息的過程。

二、數(shù)據(jù)管理技術(shù)的發(fā)展

數(shù)據(jù)庫管理技術(shù)的發(fā)展大致經(jīng)歷四個階段：手工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段以及分布式數(shù)據(jù)庫系統(tǒng)階段。

三、數(shù)據(jù)庫系統(tǒng)的組成

數(shù)據(jù)庫系統(tǒng)由五個部分組成：硬件系統(tǒng)、數(shù)據(jù)庫集合、數(shù)據(jù)庫管理系統(tǒng)及相關(guān)軟件、數(shù)據(jù)庫管理員（DBA）和用戶。

四、數(shù)據(jù)和數(shù)據(jù)聯(lián)系的描述

第二節(jié) 數(shù)據(jù)模型及結(jié)構(gòu)化查詢語言――SQL

一、非關(guān)系模型

非關(guān)系模型有層次模型、網(wǎng)狀模型和面向?qū)ο竽Ｐ汀?/P>

二、關(guān)系模型

關(guān)系模型是以二維表格結(jié)構(gòu)作為基礎(chǔ)的由若干個關(guān)系模式組成的集合。

三、關(guān)系運算

從集合論的觀點來定義關(guān)系，關(guān)系是一個元數(shù)為K的元組集合，即這個關(guān)系有若干個元組，每個元組有K個屬性值。

四、數(shù)據(jù)庫的基本查詢

查詢是從數(shù)據(jù)庫中提取出滿足用戶需要的數(shù)據(jù)，查詢是由SELECT命令實現(xiàn)的。

【要求】

本章要求學(xué)生掌握數(shù)據(jù)庫系統(tǒng)概念和數(shù)據(jù)模型的種類，掌握主要的SQL語句。

五、教材及主要參考資料

1、《軟件技術(shù)基礎(chǔ)》 張選芳 李廷元 付茂洺，中國鐵道出版社，2016年1月

2、《C程序設(shè)計（第三版）》，譚浩強，清華大學(xué)出版社。