研究生復(fù)試大綱

《軟件技術(shù)基礎(chǔ)》

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

【要點(diǎn)】

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

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

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

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

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

數(shù)據(jù)的存儲(chǔ)方法可分為：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。

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

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

第二節(jié) 線性表

一、線性表的概念

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

二、順序表

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

三、線性鏈表

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

四、循環(huán)鏈表

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

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

一、棧

棧是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，它的特點(diǎn)是后進(jìn)先出。

二、隊(duì)列

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

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

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

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

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

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

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

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

三、圖

圖G由兩個(gè)集合V和E組成，記為G=(V,E)，其中V是頂點(diǎn)的有窮非空集合，E是V中頂點(diǎn)偶對(duì)(稱為邊)的有窮集。

四、圖的遍歷

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

一、查找

查找分為簡(jiǎn)單查找方法(順序查找、二分查找、分塊查找)、樹(shù)表查找和哈希查找。

二、排序

排序分為簡(jiǎn)單排序、快速排序以及歸并排序。

【要求】

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

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

【要點(diǎn)】

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

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

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

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

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

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

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

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

一、進(jìn)程的概念

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

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

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

三、進(jìn)程互斥與同步

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

四、進(jìn)程的通信

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

五、死鎖

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

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

一、作業(yè)的概念

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

二、作業(yè)控制

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

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

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

第四節(jié) 存儲(chǔ)管理

一、存儲(chǔ)管理的功能

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

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

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

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

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

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

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

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

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

二、緩沖技術(shù)

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

四、設(shè)備分配

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

第六節(jié) 文件管理

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

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

二、文件的組織

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

三、文件目錄

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

【要求】

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

第三章 軟件工程

【要點(diǎn)】

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

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

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

二、軟件生存周期的概念

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

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

一、需求分析概述

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

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

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

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

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

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

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

五、軟件設(shè)計(jì)準(zhǔn)則

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

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

一、程序設(shè)計(jì)語(yǔ)言

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

二、編程風(fēng)格

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

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

面向?qū)ο筌浖_(kāi)發(fā)方法又稱OOSD(Object-Oriented Software Development);OOSD包括面向?qū)ο蠓治?OOA)、面向?qū)ο笤O(shè)計(jì)(OOD)和面向?qū)ο蟪绦蛟O(shè)計(jì)(OOP)三個(gè)方面。

四、軟件測(cè)試策略

軟件的測(cè)試過(guò)程是按單元測(cè)試、組裝測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試四個(gè)步驟進(jìn)行的。

五、常用的測(cè)試方法

常用的測(cè)試方法有黑盒測(cè)試和白盒測(cè)試兩種。

六、軟件維護(hù)的步驟與方法

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

七、軟件維護(hù)的副作用

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

【要求】

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

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

【要點(diǎn)】

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

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

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

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

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

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

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

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

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

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

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

二、關(guān)系模型

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

三、關(guān)系運(yùn)算

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

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

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

【要求】

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

五、教材及主要參考資料

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

2、《C程序設(shè)計(jì)(第三版)》，譚浩強(qiáng)，清華大學(xué)出版社,2005年8月第三版。