2022年《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)教案》

1、Teaching Plan For “Basis of Software of Computer”By Zhonghua LiangDepartment of Communication Engineering, School of Information Engineering, Changan University, Xian, 710064, Peoples Republic of China Date of Creation: September 19, 2010 Teaching Program 一本課程的性質(zhì)和任務(wù)（教學(xué)大綱）本課程是通信工程專業(yè)的一門重要基礎(chǔ)課程。其任務(wù)為 通過對(duì)

2、軟件工程、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)和數(shù)據(jù)庫等方面的基本 概念及基本技術(shù)的學(xué)習(xí)和掌握，使學(xué)生對(duì)計(jì)算機(jī)軟件有比較深 入、系統(tǒng)的了解，為將來能夠熟練地編寫比較復(fù)雜的應(yīng)用程序 打下堅(jiān)實(shí)的基礎(chǔ)。二本課程的基本要求1對(duì)能力培養(yǎng)的要求1). 軟件開發(fā)方法和技術(shù) ：要求學(xué)生學(xué)習(xí)和掌握軟件的基本概 念，軟件的研制過程、軟件工程概述、軟件設(shè)計(jì)方法、程序結(jié) 構(gòu)、算法描述工具，如流程圖和算法語言。2). 數(shù)據(jù)結(jié)構(gòu) ：要求學(xué)生學(xué)習(xí)和掌握數(shù)據(jù)結(jié)構(gòu)的基本概念與原 理、線性表、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、算法實(shí)現(xiàn)、數(shù) 組、棧、隊(duì)列、樹等。3). 操作系統(tǒng) ：要求學(xué)生學(xué)習(xí)和掌握操作系統(tǒng)的基本概念與原 理、操作系統(tǒng)提供的接口、進(jìn)程與進(jìn)

3、程管理、多道程序技術(shù)、同步與互斥、內(nèi)存管理、設(shè)備管理、文件系統(tǒng)的原理、文件的 使用。4). 數(shù)據(jù)庫技術(shù) ：要求學(xué)生學(xué)習(xí)和掌握數(shù)據(jù)庫的基本概念與原 理、數(shù)據(jù)模型、關(guān)系數(shù)據(jù)庫。5). 網(wǎng)絡(luò)及數(shù)據(jù)安全技術(shù) ：要求學(xué)生學(xué)習(xí)和掌握網(wǎng)絡(luò)及數(shù)據(jù)安 全技術(shù)的基本概念與原理。2重點(diǎn)和難點(diǎn)1). 本課程的重點(diǎn) ：第二章 數(shù)據(jù)結(jié)構(gòu)。2). 本課程的難點(diǎn) ：(a) 線性鏈表； (b) 樹、圖的遍歷；(c) 查 找、索引和排序技術(shù)運(yùn)算及其應(yīng)用。3先修課程： 計(jì)算機(jī)基礎(chǔ)； C 語言。三課程內(nèi)容1理論知識(shí)： （22 學(xué)時(shí)）1). 計(jì)算機(jī)軟件概述 ：計(jì)算機(jī)軟件的基本概念、程序設(shè)計(jì)技 術(shù)、數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語、算法描述及算

4、法分析初步。2). 線性表：線性表的邏輯結(jié)構(gòu)、線性表的順序存儲(chǔ)結(jié)構(gòu)、線 性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、表的基本運(yùn)算在特定存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)及應(yīng)用。3). 棧和隊(duì)列 ：棧的定義、表示和實(shí)現(xiàn)、棧的應(yīng)用、隊(duì)列的定 義、表示和實(shí)現(xiàn)、隊(duì)列的應(yīng)用。4). 樹：樹的定義和基本操作、二叉樹定義和表示、遍歷二叉 樹和線索二叉樹、樹和森林、哈夫曼樹及其應(yīng)用。5). 串和圖 ：串及圖的定義、表示和操作、存儲(chǔ)結(jié)構(gòu)圖的遍 歷。6). 查找和排序 ：查找和排序及其運(yùn)算的基本知識(shí)和算法。7). 操作系統(tǒng) ：學(xué)習(xí)和掌握操作系統(tǒng)的基本概念與原理、操作 系統(tǒng)提供的接口、進(jìn)程與進(jìn)程管理、多道程序技術(shù)、同步與互斥、內(nèi)存管理、設(shè)備管理、文件系統(tǒng)的

5、原理、文件的使用。8). 數(shù)據(jù)庫 ：學(xué)習(xí)和掌握數(shù)據(jù)庫的基本概念與原理、數(shù)據(jù)模 型、關(guān)系數(shù)據(jù)庫、SQL 語言。9). 計(jì)算機(jī)網(wǎng)絡(luò) ：學(xué)習(xí)和掌握計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)互聯(lián) 與互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全及防火墻技術(shù)、計(jì)算機(jī)病毒及防治。10). 軟件工程 ：學(xué)習(xí)和掌握軟件開發(fā)與技術(shù)，要求學(xué)生學(xué)習(xí)和 掌握軟件的基本概念，軟件的研制過程、軟件工程概述、軟件 設(shè)計(jì)方法、程序結(jié)構(gòu)、算法描述工具，如流程圖和算法語言。2課外作業(yè)：加深對(duì)課內(nèi)所學(xué)的理論知識(shí)的理解，鍛煉分析 問題和解決問題的能力。3上機(jī)實(shí)驗(yàn)：圍繞本課程學(xué)習(xí)的重點(diǎn)和難點(diǎn)，實(shí)踐理論知 識(shí)，上機(jī)完成題目（8 學(xué)時(shí)）。4考核方式：考核成績主要根據(jù)：學(xué)生平時(shí)聽課、完成

6、作業(yè) 情況 20% ；上機(jī)實(shí)驗(yàn)、完成實(shí)驗(yàn)報(bào)告 20% ；期末考試成績60% 來綜合評(píng)定。四課程教材及主要參考書1課程教材：1. 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第三版，沈被娜等編著，清華大 學(xué)出版社。2教學(xué)參考書：1. 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)，龐麗萍編，華南理工大學(xué)出版社。2.Operating Systems-Design and Implementation，Second Edition, Andrew S, Tanenbaum, Albert S. Woodhull, 清 華 大 學(xué) 出 版 社 和PRENTICE HALL. 3.Software Engineering-A Practitioners

7、Approach， Fourth Edition, Roger, S. Pressman, 機(jī)械工業(yè)出版社和 McGraw-Hill. 4. Data Structure Algorithms, and Applications in C+ ， First Edition, Sartaj Sahni, 機(jī)械工業(yè)出版社和McGraw-Hill. 第 1 章 算法1算法的基本概念1). 算法的基本特征 ：(1). 能行性 (effectiveness) a). 算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)，例如在算法執(zhí)行中，分母不能為零，實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)的平方根等等；b). 算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期

8、目的，例如需要考慮計(jì)算精度的影響。(2). 確定性 (definiteness) 算法中的每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩 可的解釋或多義性。(3). 有窮性 (finitenes s) 算法必須能在有限的時(shí)間內(nèi)昨晚，計(jì)算法必須能在執(zhí)行有限個(gè) 步驟后終止。例如無窮級(jí)數(shù)的計(jì)算只能是根據(jù)精讀要求取有限 項(xiàng)的有窮計(jì)算；如果一個(gè)算法需要執(zhí)行千萬年，則失去了實(shí)用 價(jià)值。(3). 擁有足夠的情報(bào)（sufficient information）通常算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算的對(duì)象上，而這 些對(duì)象又可能具有某種初始狀態(tài)，這是算法執(zhí)行的起點(diǎn)或依 據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初

9、始數(shù)據(jù)有關(guān)，不同 的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤 時(shí)，算法本身也就無法執(zhí)行或?qū)е聢?zhí)行有錯(cuò)。一般來說，當(dāng)算 法擁有足夠的情報(bào)時(shí)，此算法才是有效的，而當(dāng)情報(bào)不夠時(shí)，算法并不有效。綜上所述 ：所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜?次數(shù)下終止。2). 算法的基本要素 ：(1). 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作：a). 算術(shù)運(yùn)算，加、減、乘、除等運(yùn)算；b). 邏輯運(yùn)算，“ 與” 、“ 或” 、“ 非” 等運(yùn)算；c). 關(guān)系運(yùn)算，“ 大于” 、“ 小于” 、“ 等于” 、“ 不等于”等運(yùn)算；d). 數(shù)據(jù)傳輸，主要包括賦值、輸入、輸出等操

10、作；注意 ：計(jì)算機(jī)程序僅作為算法的一種描述；但通常不直接用 計(jì)算機(jī)程序來描述算法，而是用別的描述工具（如流程圖、專 門的算法描述語言，甚至自然語言）來描述算法。(2). 算法的控制結(jié)構(gòu)：一個(gè)算法的功能不僅取決于所選用的操作，而且還與各操作之 間執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控 制結(jié)構(gòu)。一個(gè)算法一般可以用順序、選擇、循環(huán) 3 種基本的 控制結(jié)構(gòu)組合而成。2算法設(shè)計(jì)基本方法 1). 列舉法：舉例白雞問題，畫出搜索空間的立體示意圖。2). 歸納法：基本思想和本質(zhì)（抽象）。3). 遞推法：本質(zhì)（歸納法）。4). 遞歸法：基本思想（逐層分解）；基礎(chǔ)（歸納）。5). 減半遞推法 ：又稱

11、為分治法?！?減半” 是將問題的規(guī)模減 半；“ 遞推” 是指重復(fù)“ 減半” 。舉例：矩陣相乘；二分法求 實(shí)根。6). 回溯法：基本思想（“ 試” ），處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)方面有廣泛應(yīng)用。舉例：求解皇后問題，用方格圖 講解。3算法的復(fù)雜度分析 1). 算法的時(shí)間復(fù)雜度 ：所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算 法所需要的計(jì)算工作量。可用算法在執(zhí)行過程中所需基本運(yùn)算 的執(zhí)行次數(shù)來度量算法的工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)（see page 10 ）。在同一問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于 某一特定輸入時(shí)，可以用以下兩種方法來分析

12、算法的工作量：(a) 平均性態(tài)（ average behaviour）分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量（定義，see page 10 ）。(b) 最壞情況復(fù)雜性（worst-case complexity）分析是指在規(guī)模為 n 時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)（上界），更具使用價(jià)值（定義，see page 10 ）。兩者的分析比較舉例（例1.5, see pages 10-11）。注意 ：本小節(jié)最后一段的論述（提及算法的工作量與輸入無 關(guān)時(shí)的情況）。2). 算法的空間復(fù)雜度 ：一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存 空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占

13、的空間，輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的 額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間（例如在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存儲(chǔ)數(shù)據(jù)本身外，還需要存儲(chǔ)連接信息）。4習(xí)題講解及作業(yè)布置：舉例講解： 1.1、 1.3 。第一次上機(jī)實(shí)驗(yàn)：1.2 、1.4、1.5 三題中任選 2 題（三題難度系數(shù)分別為 1.0, 1.0, 1.2 ）。第 2 章數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究以下三個(gè)方面的問 題：(a). 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù) 的邏輯結(jié)構(gòu)；(b). 在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)

14、元素在計(jì)算機(jī)中的存儲(chǔ)關(guān) 系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；(c). 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。討論以上各問題的主要目的是為了提高數(shù)據(jù)處理的效率。所謂 提高數(shù)據(jù)處理的效率，主要包括兩個(gè)方面：一是提高數(shù)據(jù)處理 的速度；二是盡量節(jié)省數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空 間。1). 兩個(gè)實(shí)例 ：(a). 無序表和有序表的查找效率對(duì)比；(b). 學(xué)生情況登記表。1). 數(shù)據(jù)結(jié)構(gòu)的定義 ：相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。(a). 數(shù)據(jù)元素的含義；(b). 前后件關(guān)系。(1). 數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。兩個(gè)要素：一是數(shù)據(jù)元素的集合 D ；二是 D 上的關(guān)系R 。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為 B=(D,R

15、) 。舉例（see page 18）更正：page 18 中最后一行和 Ai。page 19 中第一行： D i 應(yīng)改為(2). 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī) 存儲(chǔ)空間中的存放形式。常用的存儲(chǔ)結(jié)構(gòu)：順序；鏈接；索引。3).數(shù)據(jù)結(jié)構(gòu)的圖形表示：直觀(1). 需要理解的概念名詞：根節(jié)點(diǎn)；終端結(jié)點(diǎn)；內(nèi)部節(jié)點(diǎn)；(2). 數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：插入和刪除；其它運(yùn)算還有：查找 分類合并分解復(fù)制和修改等。(3). 數(shù)據(jù)結(jié)構(gòu)中根據(jù)各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜度，一 般將數(shù)據(jù)結(jié)構(gòu)分為：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。一般來說，如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足兩個(gè)條件：(a)有且只有一個(gè)根節(jié)點(diǎn)；(b)每個(gè)節(jié)

16、點(diǎn)最多有一個(gè)前件，也最多只有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表。此外：在插入或刪除任何一個(gè)節(jié)點(diǎn)后還應(yīng)該滿足上述條件。2線性表及其順序存儲(chǔ)結(jié)構(gòu) 1). 線性表及其運(yùn)算 ：(1). 什么是線性表 (a). 需要理解的概念名詞：記錄；文件。(b). 非空線性表的結(jié)構(gòu)特征（(2). 線性表的順序存儲(chǔ)結(jié)構(gòu)see page 22 ）。(a). 基本特點(diǎn)：（ see page 22 ）。(b). 初始化線性表的順序存儲(chǔ)空間（delete 語句成對(duì)使用的習(xí)慣：申請(qǐng)空間see page 23 ）， new 和-釋放空間。(c). 線性表的主要運(yùn)算：（see page 23 ）(3). 線性表在順序存

17、儲(chǔ)下的插入運(yùn)算：例 2.7 (a). 插入前后兩線性表中的元素關(guān)系（(b). 平均移動(dòng)元素?cái)?shù)量的計(jì)算：see page 24 ）(0+1+ +n)/(n+1)=(n+1)(0+n)/2/(n+1)=n/2 (c). 由于 C+ 中數(shù)組下標(biāo)從 要減去 1。0 開始，涉及到數(shù)組下標(biāo)的變量均(4). 線性表在順序存儲(chǔ)下的刪除運(yùn)算(a). 刪除前后兩線性表中的元素關(guān)系（(b). 平均移動(dòng)元素?cái)?shù)量的計(jì)算：see page 26 ）(0+1+ +n-1)/n=(n)(0+n-1)/2/n=(n-1)/2 更正： page 26 中最后一行應(yīng)改為：素，即無此元素。(5). 順序表類 認(rèn)為刪除第 (n+1)

18、個(gè)元將順序表的數(shù)據(jù)和基本操作（包括初始化、輸出、插入和刪 除）封裝成類。更正： page 30 中第二段應(yīng)該為：用2).棧及其應(yīng)用 ： 如果順序表非空，則調(diào)(1). 什么是棧（ stack ）：一種特殊的線性表，其插入和刪除都 只在線性表的一端進(jìn)行，即一端封閉，另一端開口。概念名詞：棧頂（top ）；棧底（ bottom ）；入棧（ push ）；退棧（ pop ）(2). 棧的順序存儲(chǔ)及其運(yùn)算：see 34 注意：程序中數(shù)組下標(biāo)減一的操作。(3). 順序棧類 (4). 表達(dá)式的計(jì)算 (4). 遞歸的實(shí)現(xiàn) 3).隊(duì)列及其應(yīng)用 ：(1). 什么是隊(duì)列（queue ）：一種特殊的線性表，允許在一端

19、進(jìn)行插入，而在另一端進(jìn)行刪除。FIFO or LILO 概念名詞：排頭指針（front ）；隊(duì)尾指針（rear ）；入隊(duì)運(yùn)算；退隊(duì)運(yùn)算(2). 循環(huán)隊(duì)列及其運(yùn)算：see 43 (3). 循環(huán)隊(duì)列類 (4). 隊(duì)列的應(yīng)用： a. 分配工作； b. IO 緩沖區(qū)； c. 加油模擬 3線性鏈表及其運(yùn)算 1). 線性鏈表的基本概念 ：(1). 線性表的順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：a. 插入或刪除線性表中元素過程中需要移動(dòng)大量數(shù)據(jù)元素；b. 存儲(chǔ)空間不便于擴(kuò)充；c. 不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。(2). 鏈?zhǔn)酱鎯?chǔ)方式中的存儲(chǔ)結(jié)點(diǎn)構(gòu)成：a.數(shù)據(jù)域； b.指針域(3). 線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(4). 基

20、本概念： a.Head 指針； b.NULL 或 0；c.線性單鏈表； d.線性雙向鏈表；e. 左指針（ Llink ）； f.右指針（ Rlink ）(3). 線性鏈表類 (4). 鏈棧及其基本操作：a.初始化； b.入棧； c.退棧； d.讀棧頂元素。(5). 鏈隊(duì)及其基本操作：a.初始化； b.入隊(duì)； c.退隊(duì)。2). 線性鏈表的基本運(yùn)算 ：(1). 插入：在指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。(2). 刪除：刪除包含制定元素的結(jié)點(diǎn)。(3). 合并：將兩個(gè)線性鏈表按要求合并為一個(gè)線性鏈表。(4). 分解：將一個(gè)線性鏈表按要求進(jìn)行分解。(5). 逆轉(zhuǎn)； (6). 復(fù)制； (7). 排序； (

21、8). 查找。3). 循環(huán)鏈表：為了克服對(duì)空表與非空表運(yùn)算的不統(tǒng)一問題。(1). 增加一個(gè)表頭結(jié)點(diǎn)：其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。(2). 最后一個(gè)結(jié)點(diǎn)的指針域不是空（NULL ），而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針域構(gòu)成了一個(gè)環(huán)狀 鏈。3). 多項(xiàng)式的表示與運(yùn)算 ：略4數(shù)組 二維數(shù)組：矩陣在程序設(shè)計(jì)語言中的表示； 程序設(shè)計(jì)語言中的數(shù)組在計(jì)算機(jī)中是順序存儲(chǔ)的。當(dāng)矩陣中 的絕大部分元素為零時(shí)，采用一般的兩維數(shù)組存儲(chǔ)方式會(huì)浪費(fèi) 大量的存儲(chǔ)空間，同時(shí)也做了大量不必要的運(yùn)算。1). 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) ：(1). 二維數(shù)組以行為主的順序存儲(chǔ)：逐行、從

22、左至右的順序。ADR(a ij)=ADR(a 11)+(i-1)n+j-1L, where 1i m, 1j n BASIC、C中的多維數(shù)組采用以行為主的順序存儲(chǔ)。(2). 二維數(shù)組以列為主的順序存儲(chǔ)：逐列、從上至下的順序。ADR(a ij)=ADR(a 11)+(j-1)m+i-1L, where 1i m, 1j nFORTORAN 中的多維數(shù)組采用以列為主的順序存儲(chǔ)。2).規(guī)則矩陣的壓縮(1). 下三角陣（ lower triangular matrix）；(2). 對(duì)稱陣（ symmetrical matrix）；(3). 三對(duì)角陣（ tridiagonal matrix）；3).一般

23、稀疏矩陣（sparse matrix ）的表示(1). 三列二維數(shù)組：a. 矩 陣 的 大 小 總 行 數(shù) （ number （number of columns）；b.非零元素的位置（行號(hào)和列號(hào)）；c. 非零元素的值；d.POS 和 NUM ；of rows ） 和 總 列 數(shù)e.操作：生成；輸出；轉(zhuǎn)置；相加；相乘。(2). 線性鏈表：(3). 十字鏈表： （自學(xué)，不考）5樹與二叉樹 1). 樹的基本概念 ：一種簡單的非線性結(jié)構(gòu)。(1). 基本概念： a. 父結(jié)點(diǎn)； b. 子結(jié)點(diǎn)； c. 根； d. 度； e. 樹的 度； f. 葉子結(jié)點(diǎn)2). 二叉樹及其基本性質(zhì)：一種實(shí)用的非線性結(jié)構(gòu)（bi

24、nary tree ）(1). 特點(diǎn)： a. 非空二叉樹只有一個(gè)根結(jié)點(diǎn)；兩顆子樹（稱為左子樹和右子樹）；(2). 基本性質(zhì)： 1，2，3， 4，5，6 b. 每個(gè)結(jié)點(diǎn)最多有(3). 遍歷： a. 前序遍歷； b. 中序遍歷； c. 后序遍歷；6圖（自學(xué)，不考）7習(xí)題講解及作業(yè)布置：舉例講解： 2.10。第一次作業(yè)： 2.5 、2.6、2.8 第二次實(shí)驗(yàn)：2.9 、 2.13 中選 1 題； 2.10 、 2.11 、2.12 、2.14 中選 1 題（各題難度系數(shù)均為 1.0）。第二次作業(yè)：2.15 、 2.16 、 2.17 中選 1 題； 2.20 、2.21 、2.22 第 3 章 1基本的查找技術(shù)查找與排序技術(shù) 基本概念：所謂查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè) 指定的元素。通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方 法。1). 順序查找 ：順序搜索。從線性表的第一個(gè)元素開始，依次 比較，結(jié)果為找到或失敗。平均搜索比較次數(shù)為 n/2 。以下兩種情況下必須使