研究生復試大綱

《軟件技術基礎》

第一章 數據結構

【要點】

第一節 數據結構的基本概念

一、 什么是數據結構

數據結構主要研究計算機系統中數據的組織形式及其相互關系。

二、數據結構中的基本概念

數據、數據元素、數據項、數據結構、線性結構、非線性結構。

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

三、抽象數據類型

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

第二節 線性表

一、線性表的概念

線性結構的基本特點是數據元素有序并有限。線性表是n(n≥0)個相同類型的元素a1，a2，an所構成的有限線性序列。

二、順序表

在順序表的存儲結構中，數據元素按其邏輯次序依次存放在一組地址連續的存儲單元里。

三、線性鏈表

采用鏈式存儲結構的鏈表是用一組任意的存儲單元來存放線性表的數據元素，這組存儲單元既可以是連續的，也可以是不連續的，甚至可以是零散分布在內存中的任何位置上。

四、循環鏈表

循環鏈表是一種首尾相接的鏈表。

第三節 棧、隊列及數組

一、棧

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

二、隊列

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

三、棧和隊列的應用

棧和隊列是應用非常廣泛的數據結構之一。

第四節 非線性結構

一、樹結構及其基本概念

樹結構是結點之間有分支、層次關系的結構。

二、二叉樹結構

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

三、圖

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

四、圖的遍歷

第五節 查找與排序

一、查找

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

二、排序

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

【要求】

本章要求學生掌握數據結構、線性表、棧、隊列、二叉樹等概念，了解和掌握順序表的插入算法、單鏈表的插入運算算法、二叉樹的有關操作、圖的有關操作、查找與排序算法等。

第二章 操作系統

【要點】

第一節 操作系統概論

一、操作系統的功能

操作系統主要有五大功能：處理機、存儲器管理、設備管理、文件管理和作業管理。

二、操作系統的特征

操作系統具有以下特征：并發行、共享性、虛擬性和不確定性。

三、操作系統的分類

操作系統的基本類型有:批處理操作系統、分時操作系統、實時操作系統、網絡操作系統、分布式操作系統。

第二節 處理機管理

一、進程的概念

進程是可并發執行的程序在給定數據集合上的一次執行過程;是系統進行資源分配合調度的一個獨立的基本單位和實體;是指執行一個映象程序的總環境。

二、進程控制與進程調度

進程控制是對進程在其生命期的各種活動及狀態轉變實施有效的控制;進程調度的任務是協調和控制各進程對CPU的使用，按照某種策略動態地將處理機分配給處于就緒狀態的某個進程。

三、進程互斥與同步

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

四、進程的通信

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

五、死鎖

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

第三節 作業管理

一、作業的概念

一個作業，就是用戶請求計算機系統執行的一次獨立的上機任務，是能共享公共資源區域的一族有關進程(進程家族)。

二、作業控制

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

三、作業調度

作業從用戶提交開始到真正占有處理機而被執行，要經過多級調度才能實現。

第四節 存儲管理

一、存儲管理的功能

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

二、分區存儲管理

分區存儲管理的基本思想是把內存劃分成若干個大小不等的連續區域，稱為分區。每個作業可占用一個或多個分區。

三、覆蓋與交換技術

覆蓋就是一個作業的若干程序段，或幾個作業的某些部分共享某一內存區域，即一個內存區域可以先后被不同的程序段重復使用，當某程序段不再需要該內存區域時另一程序段可占用。

交換技術是指在內外存之間交換程序和數據。

第五節 設備管理

一、數據傳送控制方式

外設與內存間常用的數據傳送方式有：中斷控制方式、DMA方式和通道方式。

二、緩沖技術

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

四、設備分配

設備分配的原則由設備特性及用戶請求、系統中設備使用情況而定。

第六節 文件管理

一、文件系統的概念

由于軟件資源是以文件形式存儲的，因此，對軟件資源的管理也就導致了文件系統的出現。

二、文件的組織

文件組織是指文件中信息的配置和構造方式。

三、文件目錄

文件一般有一級目錄結構、二級目錄結構和多級目錄結構。

【要求】

本章要求學生掌握操作系統的概念和功能、進程、作業概念，掌握進程調度的過程、作業調度過程以及存儲管理和設備管理中的常用技術。

第三章 軟件工程

【要點】

第一節 軟件與軟件生存周期

一、 軟件工程及軟件工程學的概念

軟件工程學主要包括軟件開發技術和軟件工程管理兩方面的內容。

二、軟件生存周期的概念

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

第二節 軟件的需求分析與軟件設計

一、需求分析概述

需求分析的主要內容有：技術可行性、經濟可行性和操作可行性。

二、結構分析方法

結構化分析方法簡稱SA方法，它適用于分析大型數據處理系統，它與設計階段的結構化設計方法一起聯合使用，能夠較好地實現一個軟件系統的研制。

三、數據流圖

對數據流圖中包含的所有元素的定義的集合構成了數據詞典。

四、數據詞典

對數據流圖中包含的所有元素的定義的集合構成了數據詞典。

五、軟件設計準則

軟件設計準則涉及軟件結構的準則、模塊化的準則以及模塊獨立性的準則幾個方面的問題。

第三節 軟件編程、軟件測試及軟件維護

一、程序設計語言

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

二、編程風格

編程風格是指一個程序員在編程時，對程序的結構形式，行文方式及編寫特點的要求。

三、面向對象的程序設計概念

面向對象軟件開發方法又稱OOSD(Object-Oriented Software Development);OOSD包括面向對象分析(OOA)、面向對象設計(OOD)和面向對象程序設計(OOP)三個方面。

四、軟件測試策略

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

五、常用的測試方法

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

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

具體的維護工作需要經過理解分析、修改和重新驗證現有軟件系統三個過程。

七、軟件維護的副作用

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

【要求】

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

第四章 數據庫技術

【要點】

第一節 數據庫技術概論

一、 數據、信息與數據處理

數據是一種物理符號序列，它的內容是事物特性的反映;信息是經過加工處理的數據，是人們消化理解了的數據，是數據的具體含義;數據處理是指將數據轉換成信息的過程。

二、數據管理技術的發展

數據庫管理技術的發展大致經歷四個階段：手工管理階段、文件系統階段、數據庫系統階段以及分布式數據庫系統階段。

三、數據庫系統的組成

數據庫系統由五個部分組成：硬件系統、數據庫集合、數據庫管理系統及相關軟件、數據庫管理員(DBA)和用戶。

四、數據和數據聯系的描述

第二節 數據模型及結構化查詢語言――SQL

一、非關系模型

非關系模型有層次模型、網狀模型和面向對象模型。

二、關系模型

關系模型是以二維表格結構作為基礎的由若干個關系模式組成的集合。

三、關系運算

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

四、數據庫的基本查詢

查詢是從數據庫中提取出滿足用戶需要的數據，查詢是由SELECT命令實現的。

【要求】

本章要求學生掌握數據庫系統概念和數據模型的種類，掌握主要的SQL語句。

五、教材及主要參考資料

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

2、《C程序設計(第三版)》，譚浩強，清華大學出版社,2005年8月第三版。