軟件技術(shù)基礎(chǔ)復(fù)習(xí)提綱

1、軟件技術(shù)基礎(chǔ)2 課程內(nèi)容第一部分 數(shù)據(jù)結(jié)構(gòu)第二部分 操作系統(tǒng) 第三部分 軟件工程3第1章 基礎(chǔ)概論一、計(jì)算機(jī)軟件的基本概念（p5）什么是計(jì)算機(jī)軟件？系統(tǒng)軟件？應(yīng)用軟件？41.2 計(jì)算機(jī)軟件基礎(chǔ)軟件的概論： 軟件是指計(jì)算機(jī)程序、程序所使用的數(shù)據(jù)以及有關(guān)的文檔資料的集合，即 軟件=程序+數(shù)據(jù)+文檔 (P5)軟件的分類： (1)系統(tǒng)軟件是直接控制和協(xié)調(diào)計(jì)算機(jī)、通信設(shè)備及其他外部設(shè)備的軟件，這類軟件一般緊靠硬件，是用戶與計(jì)算機(jī)之間的第一層界面。 (2)應(yīng)用軟件是指用戶借助系統(tǒng)軟件而開發(fā)編制的用來(lái)解決各種實(shí)際問題的軟件。 51 算法的基本概念什么是算法？算法的基本特征(參數(shù)限制)1. 能行性(effec

2、tiveness）2. 確定性(definiteness）3. 有窮性(finiteness）4.算法必須擁有足夠的情報(bào)第2章 數(shù)據(jù)結(jié)構(gòu)概述71、什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)？數(shù)據(jù)元素？數(shù)據(jù)對(duì)象？2、程序、算法和數(shù)據(jù)結(jié)構(gòu)之間的區(qū)別和聯(lián)系？3、數(shù)據(jù)結(jié)構(gòu)的分類？邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)？典型題目：課后習(xí)題8 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 散列存儲(chǔ)索引存儲(chǔ)串及數(shù)組檢索(查找)排序插入修改刪除邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)9小結(jié)： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的。（2）

3、存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像，必須依賴于計(jì)算機(jī)。（3）運(yùn)算是指所施加的一組操作總稱。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必須依賴于存儲(chǔ)結(jié)構(gòu)。 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。10第3章 線性結(jié)構(gòu)一、線性表1、順序表：線性表的順序表示與實(shí)現(xiàn)2、鏈表：線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)3、二者的優(yōu)缺點(diǎn)？4、什么時(shí)候選用鏈表？什么時(shí)候選用順序表？5、帶頭結(jié)點(diǎn)的單鏈表和不帶頭節(jié)點(diǎn)單鏈表的區(qū)別？6、不帶頭結(jié)點(diǎn)的單鏈表的建立操作、插入操作、刪除操作（如習(xí)題四.2和五.2）11二、堆棧 是限制僅在線性表的一端進(jìn)行

4、插入和刪除運(yùn)算的線性表。 后進(jìn)先出線性表（LIFO表，Last In First Out），或先進(jìn)后出(FILO)線性表。 棧的應(yīng)用：進(jìn)制轉(zhuǎn)換；實(shí)現(xiàn)遞歸函數(shù)調(diào)用 典型題目： 習(xí)題一.913，四.612三、隊(duì)列 隊(duì)列是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。 循環(huán)隊(duì)列的引入？如何判斷“空”？如何判斷“滿”？ 比如：習(xí)題一.12和一.1413第4章 樹 樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。 一、二叉樹的基本概念 二、二叉樹的特點(diǎn) 滿二叉樹和完全二叉樹 三、二叉樹的主要性質(zhì) 四、二叉樹遍歷算法：先序、中序、后序 五、二叉樹遍歷算法應(yīng)用舉

5、例：例題4-1，習(xí)題3、414習(xí)題3EFHIKJGBADC15習(xí)題4BCAED16六、二叉排序樹例題4-5，習(xí)題8943557679834567817七、哈夫曼樹及哈夫曼編碼 構(gòu)造Huffman樹時(shí)，為了規(guī)范，規(guī)定F=T1,T2, ,Tn中權(quán)值小的二叉樹作為新構(gòu)造的二叉樹的左子樹，權(quán)值大的二叉樹作為新構(gòu)造的二叉樹的右子樹；在取值相等時(shí)，深度小的二叉樹作為新構(gòu)造的二叉樹的左子樹，深度大的二叉樹作為新構(gòu)造的二叉樹的右子樹。 例題4-4.習(xí)題718習(xí)題710.40.190.210.60.320.280.110.050.020.030.060.170.070.1000000011111110.32：1

6、10.19：000.21：010.02：100000.03：100010.06：10010.07：10100.1：101119第5章 圖一、圖的基本概念如：有向圖、無(wú)向圖、完全圖等二、圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣表示；鄰接表表示法三、圖的遍歷：深度優(yōu)先和廣度優(yōu)先遍歷四、圖的應(yīng)用：最小生成樹，prim算法和克魯斯卡爾算法典型題目書上例題和課后習(xí)題20習(xí)題三.101234v1v2v3v4v521習(xí)題三.3V1V2V3V4V5深度優(yōu)先搜索：V5v4v3v2v1廣度優(yōu)先：v5v4v2v3v122習(xí)題三.6v1v2v4v5v31542U V-UV1 v2,v3,v4,v5V1,v2 v3,v4,v5V1,v2,v4 v3,v5V1,v2,v4,v5 v323第8章 操作系統(tǒng)一、操作系統(tǒng)的概念操作系統(tǒng)的特征？基本功能？二、什么是進(jìn)程？為什么要引入進(jìn)程的概念？三、進(jìn)程的互斥和共享。四、進(jìn)程有幾種狀態(tài)？進(jìn)程幾種狀態(tài)之間的變化過(guò)程？五、進(jìn)程和程序的區(qū)