學習必備 歡迎下載學習必備 歡迎下載《軟件技術基礎》課程復習要點第一章數據結構第一節數據結構的基本概念1數據結構的定義，識記計算機系統中數據的組織形式及其相互關系2、 術語：數據、數據元素、數據項，識記，識記3、 數據結構三個層次：邏輯結構、存儲結構、算法（數據的操作集合），識記4、 數據結構三個層次之間的關系，領會5、 類C語言風格的算法描述方法，簡單應用6、 運用數據結構方法，抽象描述物理對象，簡單應用7、 存儲結構的四種類型，識記順序（經常進行查找運算）鏈接（經常進行插入刪除的話選這個）索引散列第二節線性結構1線性表的定義和特點，識記2、 順序表的結構聲明，識記3、 順序表的插入、刪除算法，領會和熟練應用4、 單向鏈表的結構聲明、特點，識記5、 單向鏈表的創建、插入、刪除、查找算法，領會和熟練應用6、 雙向鏈表的結構及插入和刪除算法，識記7、 循環鏈表的結構特點，領會8利用順序表和鏈表解決簡單問題，綜合應用9、 棧的定義、特點，順序棧、鏈棧的入棧和出棧算法，識記10、 禾U用棧的特點解決簡單問題，綜合應用11隊列的定義、特點，循環隊列的特點，識記12、 禾U用隊列的特點解決簡單問題，綜合應用13、 二維矩陣數據元素的位置計算，簡單應用14、 二維矩陣的壓縮方法，特別是三元組方法，領會15、 串的特點和串的存儲結構，了解第三節非線性結構1樹結構的定義，識記2、 樹的相關術語：節點、度、深度、有序樹、無序樹、森林等，識記3、 二叉樹的定義和結構聲明，識記4、 二叉樹記7、二叉樹的遍歷算法，領會和簡單應用8二叉排序樹的創建，領會和簡單應用8樹、森林和二叉樹的轉換，領會9、 圖的定義和相關術語，識記10、 利用鄰接矩陣存儲圖，識記和簡單應用11、 利用鄰接表存儲圖，識記和簡單應用12、 圖的深度優先和廣度優先遍歷算法，領會（能根據圖寫出遍歷順序）第四節查找和排序排序：簡單排序法簡單插入排序（從無序表中取插入到有序表中）簡單選擇排序（從無序表選擇最大或最小的元素交換到有序表的另一端）冒泡排序快速排序（出現逆序就交換位置）歸并排序（合二為一）1、 順序查找算法，識記，平均查找長度的計算，領會2、 二分查找的特點和算法，識記和簡單應用（順序儲存，排列有序）3、 分塊查找的特點，了解塊內無序塊間有序4、 二叉排序樹的查找算法和特點，領會和簡單應用5、 哈希查找的特點及線性探測再散列、二次探測再散列方法，領會和簡單應用（不需要進行關鍵字值比較）6、 排序的基本概念，排序算法的穩定性，識記7、 簡單插入算法、簡單選擇算法，識記8冒泡排序算法，領會9、 快速排序算法，領會（出現逆序就交換位置）（不穩定的）10、 歸并排序算法，了解第二章操作系統第一節操作系統概述1、 操作系統的定義，識記操作系統由硬件軟件兩部分組成， 是計算機最重要的系統軟件， 在計算機系統中占據了特殊重要的地位。不僅是硬件與所有其他軟件的接口， 而且是整個計算機系統的控制和管理中心。2、 操作系統的發展過程，領會3、 操作系統的功能，識記處理機管理（cpu，基本任務：按一定的調度策略，對處理機進行分配及資源回收）儲存器管理（內存管理，任務市委多道程序的執行提供必要和良好的環境， 提高存儲器的利用率，并為用戶提供足夠大的存儲空間）文件管理（對計算機軟件資源的管理，幼教信息管理）用戶接口4、 操作系統的特征，識記并發性（輪流交替的被cpu所調用）共享性（兩種方式：互斥共享，并發訪問）虛擬性不確定性（指程序的不確定）5、 批處理系統、分時系統和實時系統的特點，領會批處理系統分時系統：多個用戶聯機使用交互方式特點：多路，交互，獨立，及時實時系統：特點：多路，交互（簡單的交互） ，及時，高可靠6、 其它操作系統，了解第二節處理機管理1程序并發執行的特征，領會2、 進程的定義，識記一個具有一定獨立功能的程序關于某個數據集合的一次運行活動，是資源分配和調度的基本單位3、 進程的特征，識記動態性（暫時掛起條件滿足時繼續執行）并發性獨立性異步性【簡答】與程序的關系：進程是程序的執行過程，指一次運行的活動，是動態的概念；程序是一組指令的集合，是靜態的概念；進程是程序的執行過程具有一定的生命期， 而程序可以作為一種資源以文件的形式長期保存—個進程可以執行多個程序，一段程序也可以被多個程序執行進程控制塊的概念、內容和作用，識記概念：PCB是操作系統為了反映進程的動態特性，便于系統控制和描述進程的活動過程而專門定義的一種數據結構。用于記錄和描述進程執行情況和狀態變化內容：進程標識信息處理機狀態信息進程調度信息：描述進程的當前狀況進程控制信息PCB是進程存在的唯一標志進程狀態及轉換，領會就緒狀態（萬事俱備只差cpu正在被其他進程占用）（就緒的進程占有處理器）執行狀態（單個cpu只有一個進程處于執行狀態）等待狀態（等待條件發生，暫時不能運行，條件可能是內存等待 ，10等待，文件等待等）（判斷題：但不是一旦等待的事情發生就轉為執行狀態）6、 進程控制的步驟，了解7、 進程調度的原因及方式，識記原因：正在執行的進程已運行完畢正在執行的進程由于等待某種條件的發生（如 io請求）分時系統中執行進程的時間片已用完就緒隊列中出現高優先級的進程申請試用 CPU方式：剝奪式非剝奪式（知道由于時間片到或是進程自己進入阻塞狀態才讓出 CPU）8進程調度算法及評價和應用環境，領會9、 臨界資源和臨界區，識記臨界資源：以互斥關系共享的資源成為臨界資源 （具有一次只允許一個進程使用的屬性， 具體可以是硬件可以是軟件）臨界區：每個進程中訪問臨界資源的那段代碼區10、 進程同步原則，識記空閑讓進忙則等待優先等待讓權等待11、 信號量的P、V操作，識記12、 利用信號量進行進程的互斥和進程同步，領會及簡單應用（進程之間互斥關系主要體現在進程的互斥和同步）13、 進程間通信的方式，領會消息緩沖通信：利用內存中公共消息緩沖區實現進程間信息交換管道通信信箱通信：郵箱14、 死鎖產生原因、和必要條件，識記；預防死鎖、避免死鎖和死鎖的監測和解除方法，領會原因：爭奪資源進程推行順序不當必要條件：互斥條件不剝奪條件部分分配條件環路條件預防：采用資源的靜態與分配策略，破壞“部分分配”條件允許進程剝奪使用其他進程占有的資源，從而破壞“不剝奪”條件采用資源順序使用法，破壞“環路”條件第三節作業管理1作業的概念，領會用戶請求計算機系統執行的一次獨立的上機任務，是能共享公共資源區域的一組有關進程2、 作業的狀態，了解進入后備運行完成3、 作業控制的方法，了解聯機控制命令驅動方式菜單驅動方式窗口環境脫機控制方式4、 作業調度算法，領會先來先服務算法最高優先級算法最短作業有限算法最高響應比優先算法（作業調度：往內存調進程調度：往CPU調作業調度是進程調度的基礎，進程調度室作業在運行狀態下的執行過程）作業調度最常用方法：時間片輪轉法 （并列的有先來先去，最高優先級等）第四節存儲管理存儲管理的目的是提高內存利用率1存儲管理的功能，識記內存分配和回收管理內存分配表制定分配策略內存區域的劃分方式內存空間的共享存儲保護地址映射空間地址與儲存地址重定位內存空間的擴充2、 地址映射和重定位，領會及簡單應用3、 分區存儲管理方法及分區分配算法，領會；基本思想：（實存）把內存劃分成若干個大小不等的連續區域， 成為分區。每個作業客棧用一個或多個分區4、 內零頭和外零頭，識記5、 覆蓋和交換技術，了解6、 虛擬存儲管理概念，識記用大容量的外存對內存進行邏輯擴充， 利用虛擬技術為用戶提供一個比有限的實際內存空間大得多的虛擬內存空間，以便能夠有效的支持多道程序系統中大型作業的需要（分頁分段段頁式）7、 分頁存儲管理基本原理，識記；地址轉換結構及過程，領會及簡單應用將程序的邏輯地址空間分為大小相同的頁，成為虛頁面（通過地址轉換機制，能明顯消除內外存之間的差別，見外村堪稱內存的擴充和眼神眼神，并能很好解決外零頭問題）8分段存儲管理基本原理，識記；地址轉換機構及過程，領會及簡單應用在分段村池管理系統中，一個作業分為若干段，每段都有自己的段名，程序經編譯鏈接后，段名轉換為段號，一段號唯一標識一個段段是信息的邏輯單位，他有完整和相對獨立的意義。一個段必須分配在內存的一個連續空間中（容易產生碎片）對內存中數據進行一次訪問，要訪問兩次內存邏輯地址是有段號和段內偏移形成的二位地址（對）9、 快表，領會為了提高查找頁表的速度， 通常在地址變換機構中增加一個小容量的聯想寄存器， 他是一個專用的高速緩存存儲器，用來存放也表中當前訪問最頻繁的表項10、 段頁式存儲管理基本原理，領會第五節設備管理1、 設備管理的任務和功能，識記；設備分類，了解任務：向用戶提供使用外設的方便接口。 按照用戶的要求和設備的類型， 控制設備的工作，完成用戶的輸入輸出請求充分發揮設備的使用效率，提高 CPU與設備之間設備與設備之間的并行工作程度，在多道程序環境下，按一定策略對設備進行分配和管理，保證設備高效運行。功能：1?建立統一的并且獨立與設備的接口2?按照設備類型和相應算法，進行設備的分配與回收3?進行設備驅動，實現真正的 io操作及設備的分配和回收4?實現輸入輸出緩沖區管理，解決高速 CPU與慢速CPU設備速度不匹配的問題5?實現虛擬設備管理2、 數據傳送控制方式及特點，領會中斷控制方式需要輸入數據是，通過cpu發出指令啟動外設，進程應放棄處理劑，等待輸入完成（不適宜需要交換大量數據的情況：消耗時間或者數據丟失）DMA方式直接內存訪問方式通道方式3、各種緩沖技術原理及特點，識記基本思想：在內存中開辟一個或多個專用的區域， 即緩沖區，作為CPU與10設備之間信息傳輸的集散地4、 設備分配的數據結構，識記；設備分配過程，領會數據結構：設備控制表DCT系統設備控制表（連接到系統中的物理設備的使用情況）控制器表（反映io控制器的使用情況）通道控制表（描述通道的使用情況）5、 虛擬設備基本原理，領會用大容量的快速設備如此潘模擬慢速度的獨占設備， 使一臺獨占設備，成為若干臺可并行操作的虛擬設備，把獨占設備變成邏輯上的共享設備。6、 I/O控制系統和I/O設備驅動過程，領會第六節文件管理1文件的分類，了解2、 文件系統的功能，識記1?統一管理文件儲存空間（外存），試試存儲空間的分配與回收2?確定文件信息的存放位置及存放形式3?實現文件從名字空間道外存地址空間的映射，即實現穩健的案名存取。4?實現對文件的控制操作和存取操作5?實現文件信息的共享，并提供可靠的文件保護與秘密措施總之，文件系統提供了用戶與外村的界面，用戶可通過文件名，按照文件的邏輯結構， 使用簡單直接的操作存取和管理所需的信息3、 文件的邏輯結構，文件的物理結構，了解物理結構：連續文件，鏈接文件4、 文件控制塊，領會5、 文件目錄結構，領會6、 文件的共享