研究生復試大綱
《軟件技術基礎》
第一章 數(shù)據(jù)結構
【要點】
第一節(jié) 數(shù)據(jù)結構的基本概念
一、 什么是數(shù)據(jù)結構
數(shù)據(jù)結構主要研究計算機系統(tǒng)中數(shù)據(jù)的組織形式及其相互關系。
二、數(shù)據(jù)結構中的基本概念
數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構、線性結構、非線性結構。
數(shù)據(jù)的存儲方法可分為：順序存儲、鏈式存儲、索引存儲、散列存儲。
三、抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型的定義由一個值域和定義在該值域上的一組操作組成。抽象數(shù)據(jù)類型的定義與使用實現(xiàn)了數(shù)據(jù)的封裝和隱藏，為對象程序設計方法提供了基礎，也使過程語言的可維護性大大提高。
第二節(jié) 線性表
一、線性表的概念
線性結構的基本特點是數(shù)據(jù)元素有序并有限。線性表是n(n≥0)個相同類型的元素a1，a2，an所構成的有限線性序列。
二、順序表
在順序表的存儲結構中，數(shù)據(jù)元素按其邏輯次序依次存放在一組地址連續(xù)的存儲單元里。
三、線性鏈表
采用鏈式存儲結構的鏈表是用一組任意的存儲單元來存放線性表的數(shù)據(jù)元素，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以是零散分布在內(nèi)存中的任何位置上。
四、循環(huán)鏈表
循環(huán)鏈表是一種首尾相接的鏈表。
第三節(jié) 棧、隊列及數(shù)組
一、棧
棧是限制僅在表的一端進行插入和刪除運算的線性表，它的特點是后進先出。
二、隊列
隊列是允許在線性表的一端進行數(shù)據(jù)元素插入操作而在另一端才能進行數(shù)據(jù)元素刪除操作的線性表。
三、棧和隊列的應用
棧和隊列是應用非常廣泛的數(shù)據(jù)結構之一。
第四節(jié) 非線性結構
一、樹結構及其基本概念
樹結構是結點之間有分支、層次關系的結構。
二、二叉樹結構
二叉樹是n個結點的有限集合(n≥0)，它或者是空集(n=0)或者由一個根結點及兩棵互不相交的、分別稱做這個根的左子樹和右子樹的二叉樹組成。
三、圖
圖G由兩個集合V和E組成，記為G=(V,E)，其中V是頂點的有窮非空集合，E是V中頂點偶對(稱為邊)的有窮集。
四、圖的遍歷
第五節(jié) 查找與排序
一、查找
查找分為簡單查找方法(順序查找、二分查找、分塊查找)、樹表查找和哈希查找。
二、排序
排序分為簡單排序、快速排序以及歸并排序。
【要求】
本章要求學生掌握數(shù)據(jù)結構、線性表、棧、隊列、二叉樹等概念，了解和掌握順序表的插入算法、單鏈表的插入運算算法、二叉樹的有關操作、圖的有關操作、查找與排序算法等。
第二章 操作系統(tǒng)
【要點】
第一節(jié) 操作系統(tǒng)概論
一、操作系統(tǒng)的功能
操作系統(tǒng)主要有五大功能：處理機、存儲器管理、設備管理、文件管理和作業(yè)管理。
二、操作系統(tǒng)的特征
操作系統(tǒng)具有以下特征：并發(fā)行、共享性、虛擬性和不確定性。
三、操作系統(tǒng)的分類
操作系統(tǒng)的基本類型有:批處理操作系統(tǒng)、分時操作系統(tǒng)、實時操作系統(tǒng)、網(wǎng)絡操作系統(tǒng)、分布式操作系統(tǒng)。
第二節(jié) 處理機管理
一、進程的概念
進程是可并發(fā)執(zhí)行的程序在給定數(shù)據(jù)集合上的一次執(zhí)行過程;是系統(tǒng)進行資源分配合調度的一個獨立的基本單位和實體;是指執(zhí)行一個映象程序的總環(huán)境。
二、進程控制與進程調度
進程控制是對進程在其生命期的各種活動及狀態(tài)轉變實施有效的控制;進程調度的任務是協(xié)調和控制各進程對CPU的使用，按照某種策略動態(tài)地將處理機分配給處于就緒狀態(tài)的某個進程。
三、進程互斥與同步
進程的互斥是由多個進程競爭同一共享資源而產(chǎn)生的相互制約的關系;進程之間通過執(zhí)行時序上的某種限制而達到相互合作，這種因相互合作而產(chǎn)生的制約關系稱為進程的同步。
四、進程的通信
目前常用的進程通信的高級方式有消息緩沖通信，管道通信和信箱通信。
五、死鎖
對資源的管理使用不當，在一定條件下會導致系統(tǒng)發(fā)生隨機故障，出現(xiàn)進程被阻塞的現(xiàn)象，即若干進程彼此互相等待對方所擁有且又不放的資源，其結果是誰也無法得到繼續(xù)運行所需的全部資源，因而永遠等待下去。這種現(xiàn)象稱為死鎖。
第三節(jié) 作業(yè)管理
一、作業(yè)的概念
一個作業(yè)，就是用戶請求計算機系統(tǒng)執(zhí)行的一次獨立的上機任務，是能共享公共資源區(qū)域的一族有關進程(進程家族)。
二、作業(yè)控制
作業(yè)控制包括兩方面含義：從用戶角度看，作業(yè)控制是用戶通過作業(yè)控制級接口，組織和控制其作業(yè)在計算機上的運行的全過程。從系統(tǒng)管理的角度看，作業(yè)控制是系統(tǒng)接受、分析并執(zhí)行用戶發(fā)出的控制命令，為作業(yè)的每個發(fā)展階段提供必要的系統(tǒng)服務。
三、作業(yè)調度
作業(yè)從用戶提交開始到真正占有處理機而被執(zhí)行，要經(jīng)過多級調度才能實現(xiàn)。
第四節(jié) 存儲管理
一、存儲管理的功能
存儲管理主要有五個方面的功能：內(nèi)存分配和回收、內(nèi)存空間的共享、存儲保護、地址映射、內(nèi)存空間的擴充。
二、分區(qū)存儲管理
分區(qū)存儲管理的基本思想是把內(nèi)存劃分成若干個大小不等的連續(xù)區(qū)域，稱為分區(qū)。每個作業(yè)可占用一個或多個分區(qū)。
三、覆蓋與交換技術
覆蓋就是一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一內(nèi)存區(qū)域，即一個內(nèi)存區(qū)域可以先后被不同的程序段重復使用，當某程序段不再需要該內(nèi)存區(qū)域時另一程序段可占用。
交換技術是指在內(nèi)外存之間交換程序和數(shù)據(jù)。
第五節(jié) 設備管理
一、數(shù)據(jù)傳送控制方式
外設與內(nèi)存間常用的數(shù)據(jù)傳送方式有：中斷控制方式、DMA方式和通道方式。
二、緩沖技術
緩沖技術的基本思想是：在內(nèi)存中開辟一個或多個專用的區(qū)域，即緩沖區(qū)，作為CPU與I/O設備之間信息傳送的集散地。
四、設備分配
設備分配的原則由設備特性及用戶請求、系統(tǒng)中設備使用情況而定。
第六節(jié) 文件管理
一、文件系統(tǒng)的概念
由于軟件資源是以文件形式存儲的，因此，對軟件資源的管理也就導致了文件系統(tǒng)的出現(xiàn)。
二、文件的組織
文件組織是指文件中信息的配置和構造方式。
三、文件目錄
文件一般有一級目錄結構、二級目錄結構和多級目錄結構。
【要求】
本章要求學生掌握操作系統(tǒng)的概念和功能、進程、作業(yè)概念，掌握進程調度的過程、作業(yè)調度過程以及存儲管理和設備管理中的常用技術。
第三章 軟件工程
【要點】
第一節(jié) 軟件與軟件生存周期
一、 軟件工程及軟件工程學的概念
軟件工程學主要包括軟件開發(fā)技術和軟件工程管理兩方面的內(nèi)容。
二、軟件生存周期的概念
一個軟件從用戶提出開發(fā)要求，到廢棄不用為止的全過程，稱為軟件的生存周期。
第二節(jié) 軟件的需求分析與軟件設計
一、需求分析概述
需求分析的主要內(nèi)容有：技術可行性、經(jīng)濟可行性和操作可行性。
二、結構分析方法
結構化分析方法簡稱SA方法，它適用于分析大型數(shù)據(jù)處理系統(tǒng)，它與設計階段的結構化設計方法一起聯(lián)合使用，能夠較好地實現(xiàn)一個軟件系統(tǒng)的研制。
三、數(shù)據(jù)流圖
對數(shù)據(jù)流圖中包含的所有元素的定義的集合構成了數(shù)據(jù)詞典。
四、數(shù)據(jù)詞典
對數(shù)據(jù)流圖中包含的所有元素的定義的集合構成了數(shù)據(jù)詞典。
五、軟件設計準則
軟件設計準則涉及軟件結構的準則、模塊化的準則以及模塊獨立性的準則幾個方面的問題。
第三節(jié) 軟件編程、軟件測試及軟件維護
一、程序設計語言
程序設計語言可以分為機器語言、匯編語言和高級語言三類。
二、編程風格
編程風格是指一個程序員在編程時，對程序的結構形式，行文方式及編寫特點的要求。
三、面向對象的程序設計概念
面向對象軟件開發(fā)方法又稱OOSD(Object-Oriented Software Development);OOSD包括面向對象分析(OOA)、面向對象設計(OOD)和面向對象程序設計(OOP)三個方面。
四、軟件測試策略
軟件的測試過程是按單元測試、組裝測試、確認測試和系統(tǒng)測試四個步驟進行的。
五、常用的測試方法
常用的測試方法有黑盒測試和白盒測試兩種。
六、軟件維護的步驟與方法
具體的維護工作需要經(jīng)過理解分析、修改和重新驗證現(xiàn)有軟件系統(tǒng)三個過程。
七、軟件維護的副作用
軟件維護的副作用可以分為三類：修改程序的副作用、修改數(shù)據(jù)的副作用和文檔的副作用。
【要求】
要求學生掌握軟件、軟件生存周期概念，掌握軟件工程方法的各個階段的任務和工作流程。
第四章 數(shù)據(jù)庫技術
【要點】
第一節(jié) 數(shù)據(jù)庫技術概論
一、 數(shù)據(jù)、信息與數(shù)據(jù)處理
數(shù)據(jù)是一種物理符號序列，它的內(nèi)容是事物特性的反映;信息是經(jīng)過加工處理的數(shù)據(jù)，是人們消化理解了的數(shù)據(jù)，是數(shù)據(jù)的具體含義;數(shù)據(jù)處理是指將數(shù)據(jù)轉換成信息的過程。
二、數(shù)據(jù)管理技術的發(fā)展
數(shù)據(jù)庫管理技術的發(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)及相關軟件、數(shù)據(jù)庫管理員(DBA)和用戶。
四、數(shù)據(jù)和數(shù)據(jù)聯(lián)系的描述
第二節(jié) 數(shù)據(jù)模型及結構化查詢語言――SQL
一、非關系模型
非關系模型有層次模型、網(wǎng)狀模型和面向對象模型。
二、關系模型
關系模型是以二維表格結構作為基礎的由若干個關系模式組成的集合。
三、關系運算
從集合論的觀點來定義關系，關系是一個元數(shù)為K的元組集合，即這個關系有若干個元組，每個元組有K個屬性值。
四、數(shù)據(jù)庫的基本查詢
查詢是從數(shù)據(jù)庫中提取出滿足用戶需要的數(shù)據(jù)，查詢是由SELECT命令實現(xiàn)的。
【要求】
本章要求學生掌握數(shù)據(jù)庫系統(tǒng)概念和數(shù)據(jù)模型的種類，掌握主要的SQL語句。
五、教材及主要參考資料
1、《軟件技術基礎》 張選芳 李廷元 付茂洺，中國鐵道出版社，2016年1月
2、《C程序設計(第三版)》，譚浩強，清華大學出版社,2005年8月第三版。