[工學(xué)]計算機(jī)導(dǎo)論復(fù)習(xí)提綱(編輯修改稿)
2025-02-05 14:38 本頁面
【文章內(nèi)容簡介】 性是指兩個或多個事件在同一時刻發(fā)生，而并發(fā)性是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生。 (2) 共享 (Sharing ) ：所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程共 同使用。由于資源的屬性不同，故多個進(jìn)程對資源的共享方式也不同，可分為以下兩種資源共享方式： ① 互斥共享方式 ② 同時訪問方式 (3) 虛擬 (Virtual )：在操作系統(tǒng)中的所謂 “ 虛擬 ” ，是指通過某種技術(shù)把一個物理實(shí)體變成若干個邏輯上的對應(yīng)物。 (4) 異步性 (Asynchronism) ：在多道程序環(huán)境下，允許多個進(jìn)程并發(fā)執(zhí)行，但由于資源等因素的限制，通常進(jìn)程的執(zhí)行并非 “ 一氣呵成 ” ，而是以 “ 走走停停 ” 的方式運(yùn)行。 2）操作系統(tǒng)的服務(wù) (1) 操作系統(tǒng)的公共服務(wù)類型 ： ① 程序執(zhí)行； ② I/O 操作； ③ 文件系統(tǒng)操縱 (filesystem manipulation) ； ④ 通信； ⑤ 差錯檢測。 (2) 系統(tǒng)調(diào)用的作用： OS 可用不同的方法提供 OS 服務(wù)，但幾乎在所有的 OS 中所采用的最基本方法是以系統(tǒng)調(diào)用（ System Call）的方式提供的。 (3) 系統(tǒng)調(diào)用的類型： 根據(jù)操作系統(tǒng)所提供服務(wù)的功能，可把系統(tǒng)調(diào)用分為進(jìn)程管理、設(shè)備管理、文件操縱、信息維護(hù)以及通信五大類。 5. 進(jìn)程與程序的異同點(diǎn) 進(jìn)程和程序是緊密相關(guān)而又完全不同的兩個概念。 (1)每個進(jìn)程實(shí)體中包含了程序段和數(shù)據(jù)段這兩個部 分，因此說進(jìn)程與程序是緊密相關(guān)的。但從結(jié)構(gòu)上看，進(jìn)程實(shí)體中除了程序段和數(shù)據(jù)段外，還必須包含一個數(shù)據(jù)結(jié)構(gòu)，即進(jìn)程控制塊 PCB。 (2)進(jìn)程是程序的一次執(zhí)行過程，因此是動態(tài)的；動態(tài)性還表現(xiàn)在進(jìn)程由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行、由撤消而消亡，即它具有一定的生命周期。而程序則只是一組指令的有序集合，并可永久地存放在某種介質(zhì)上，其本身不具有運(yùn)動的含義，因此是靜態(tài)的。 (3)多個進(jìn)程實(shí)體可同時存放在內(nèi)存中并發(fā)地執(zhí)行，其實(shí)這正是引入進(jìn)程的目的。而程序 (在沒有為它創(chuàng)建進(jìn)程時 )的并發(fā)執(zhí)行具有不可再現(xiàn)性，因此程序不能正確地并發(fā)執(zhí)行 。 (4)進(jìn)程是一個能夠獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位。而因程序 (在沒有為它創(chuàng)建進(jìn)程時 )不具有 PCB，所以它是不可能在多道程序環(huán)境下獨(dú)立運(yùn)行的。 (5)進(jìn)程與程序不一一對應(yīng)。同一個程序的多次運(yùn)行，將形成多個不同的進(jìn)程；同一個程序的一次執(zhí)行也可以產(chǎn)生多個進(jìn)程 (如 UNIX中通過 fork 調(diào)用 )；而一個進(jìn)程也可以執(zhí)行多個程序 (如 UNIX中通過 exec調(diào)用 )。 第五章 數(shù)據(jù)結(jié)構(gòu)與算法 1. 數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu) 1) 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，這個 關(guān)系描述的是數(shù)據(jù)元素之間的邏輯關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)分為三種典型結(jié)構(gòu)，第一種是集合，第二種是線性結(jié)構(gòu)，第三種是非線性結(jié)構(gòu)。 （ 1）集合是元素間為松散的關(guān)系，只是同屬于一個集合而已。 （ 2）線性結(jié)構(gòu)的邏輯特征是有且僅有一個起始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)只有一個直接前趨和一個直接后繼。 （ 3）非線性結(jié)構(gòu)的特征是一個結(jié)點(diǎn)可能有多個直接前趨或多個直接后繼。 2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)內(nèi)部的表示或?qū)崿F(xiàn)，又稱為數(shù)據(jù)的物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。它與計算機(jī)語言無 關(guān)。 在計算機(jī)內(nèi)有四種基本的存儲表示方法： （ 1）順序存儲方法 （ 2）鏈?zhǔn)酱鎯Ψ椒? （ 3）索引存儲方法 （ 4）散列存儲方法 這四種方法既可以單獨(dú)使用，也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲。同一種邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。 2. 算法的特征、算法的效率 1） 5個重要特性： （ 1）輸入 ：一個算法具有 0個或多個輸入的外界量，是算法開始前對算法給出的初始量。 （ 2）輸出 ：一個算法至少產(chǎn)生一個輸出，它們是同輸入有一定關(guān)系的量。 （ 3）有窮性 ：算法中的每一條指令的執(zhí)行次數(shù)必須是有限的，且 在有窮時間內(nèi)完成。 （ 4）確定性 ：算法中每一條指令的含義都必須明確定義，即在任何條件下，相同的輸入只能得到相同的輸出。 （ 5）可行性 ：一個算法的執(zhí)行時間是有限的。 2）算法的效率 （ 算法分析） 評價一個算法的好壞，前提是這個算法首先是正確的，并具有算法的五個特性。此外，還需要考慮以下幾點(diǎn)：執(zhí)行算法所耗費(fèi)的時間，即效率問題；執(zhí)行算法所耗費(fèi)的存儲空間，主要考慮輔助的存儲空間；算法應(yīng)易于理解（具有可讀性），易于編碼，易于調(diào)試等；健壯性，即當(dāng)輸入一些非法數(shù)據(jù)時，算法也應(yīng)做出適當(dāng)?shù)姆从郴蜻M(jìn)行處理。 在討論一個 算 法的效率 時通常是指 算法的時間特性和空間特性 。算法的時間特性用時間復(fù)雜度來表示，時間復(fù)雜度就是該算法的時間耗費(fèi)。一個算法的耗費(fèi)時間是該算法的所有語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)和執(zhí)行一次所需要的時間乘積。 3. 線性表的基本概念、順序存儲、鏈?zhǔn)酱鎯Φ幕驹?、?yōu)缺點(diǎn) 1） 線性表的基本概念： 線性表是一種最簡單、常用的數(shù)據(jù)結(jié)構(gòu)，通常一個線性表是由 n(n0)個性質(zhì)相同的數(shù)據(jù)元素組成的有限序列。 2） 線性表的 順序存儲 指的就是把線性表的各個數(shù)據(jù)元素依次存儲在一組地址連續(xù)的存儲單元里。用這種 方法存儲的線性表簡稱為順序表。 3）順序存儲的基本原理（見課本 100） 4）順序存儲結(jié)構(gòu)的特點(diǎn) 順序存儲結(jié)構(gòu)是線性表中最簡單、最常用的存儲方式。其主要優(yōu)點(diǎn)有：無須為表示結(jié)點(diǎn)間的
試題試卷相關(guān)推薦
鄂ICP備17016276號-1