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

1、精品word 名師歸納總結(jié) - - - - - - - - - - - -Teaching PlanFor“Basis of Software of Computer”ByZhonghua LiangDepartment of Communication Engineering, School of Information Engineering,Chang an University, Xi an, 710064, People sRepublic of ChinaDate of Creation: September 19, 2021精選名師 優(yōu)秀名師 - - - - - - - - -

2、-第 1 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -Teaching Program（教學(xué)大綱）一本課程的性質(zhì)和任務(wù)本課程是通信工程專業(yè)的一門重要基礎(chǔ)課程；其任務(wù)為通過對軟件工程、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)和數(shù)據(jù)庫等方面的基本概念及基本技術(shù)的學(xué)習(xí)和把握，使同學(xué)對運(yùn)算機(jī)軟件有比較深化、系統(tǒng)的明白，為將來能夠嫻熟地編寫比較復(fù)雜的應(yīng)用程序打下堅(jiān)實(shí)的基礎(chǔ)；二本課程的基本要求1對才能培育的要求1). 軟件開發(fā)方法和技術(shù) ：要求同學(xué)學(xué)習(xí)和把握軟件的基本概念，軟件的研制過程、軟件工程概述、軟件設(shè)計(jì)方法、程序結(jié)構(gòu)、算法描述工具，如

3、流程圖和算法語言；2). 數(shù)據(jù)結(jié)構(gòu) ：要求同學(xué)學(xué)習(xí)和把握數(shù)據(jù)結(jié)構(gòu)的基本概念與原理、線性表、次序儲備結(jié)構(gòu)和鏈?zhǔn)絻浣Y(jié)構(gòu)、算法實(shí)現(xiàn)、數(shù) 組、棧、隊(duì)列、樹等；3). 操作系統(tǒng) ：要求同學(xué)學(xué)習(xí)和把握操作系統(tǒng)的基本概念與原理、操作系統(tǒng)供應(yīng)的接口、進(jìn)程與進(jìn)程治理、多道程序技術(shù)、同步與互斥、內(nèi)存治理、設(shè)備治理、文件系統(tǒng)的原理、文件的使用；4). 數(shù)據(jù)庫技術(shù) ：要求同學(xué)學(xué)習(xí)和把握數(shù)據(jù)庫的基本概念與原理、數(shù)據(jù)模型、關(guān)系數(shù)據(jù)庫；精選名師 優(yōu)秀名師 - - - - - - - - - -第 2 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - -

4、 - -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先修課程：運(yùn)算機(jī)基礎(chǔ)； C 語言；三課程內(nèi)容1理論學(xué)問：（ 22 學(xué)時）1). 運(yùn)算機(jī)軟件概述 ：運(yùn)算機(jī)軟件的基本概念、程序設(shè)計(jì)技術(shù)、數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語、算法描述及算法分析初步；2). 線性表：線性表的規(guī)律結(jié)構(gòu)、線性表的次序儲備結(jié)構(gòu)、線性表的鏈?zhǔn)絻浣Y(jié)構(gòu)、表的基本運(yùn)算在特定儲備結(jié)構(gòu)中的實(shí)現(xiàn)及應(yīng)用；3). 棧和隊(duì)列 ：棧的定義、表示和實(shí)現(xiàn)、棧的應(yīng)用、隊(duì)列的定

5、義、表示和實(shí)現(xiàn)、隊(duì)列的應(yīng)用；4). 樹：樹的定義和基本操作、二叉樹定義和表示、遍歷二叉樹和線索二叉樹、樹和森林、哈夫曼樹及其應(yīng)用；5). 串和圖 ：串及圖的定義、表示和操作、儲備結(jié)構(gòu)圖的遍歷；6). 查找和排序：查找和排序及其運(yùn)算的基本學(xué)問和算法；精選名師 優(yōu)秀名師 - - - - - - - - - -第 3 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -7). 操作系統(tǒng) ：學(xué)習(xí)和把握操作系統(tǒng)的基本概念與原理、操作系統(tǒng)供應(yīng)的接口、進(jìn)程與進(jìn)程治理、多道程序技術(shù)、同步與互斥、內(nèi)存治理、設(shè)備治理、文件系統(tǒng)的原理、文

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

7、機(jī)試驗(yàn)、完成試驗(yàn)報(bào)告20% ；期末考試成果 60% 來綜合評定；四課程教材及主要參考書1課程教材：1.運(yùn)算機(jī)軟件技術(shù)基礎(chǔ)第三版，沈被娜等編著，清華高校出版社；2教學(xué)參考書：精選名師 優(yōu)秀名師 - - - - - - - - - -第 4 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -1. 運(yùn)算機(jī)軟件技術(shù)基礎(chǔ)，龐麗萍編，華南理工高校出版社；2.OperatingSystems-DesignandImplementation ， Second Edition, Andrew S, Tanenbaum, Albert

8、 S. Woodhull, 清 華 大 學(xué) 出 版 社 和PRENTICE HALL.3.SoftwareEngineering-APractitionersApproach， FourthEdition,Roger,S.Pressman,機(jī)械工業(yè)出版社和McGraw-Hill.4. DataStructureAlgorithms,andApplicationsinC+ ， FirstEdition,McGraw-Hill.SartajSahni,機(jī)械工業(yè)出版社和第 1 章算法1算法的基本概念1). 算法的基本特點(diǎn) ：(1). 能行性 effectivenessa). 算法中的每一個步驟必需能

9、夠?qū)崿F(xiàn)，例如在算法執(zhí)行中，分母不能為零，實(shí)數(shù)范疇內(nèi)不能求一個負(fù)數(shù)的平方根等等；b). 算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期目的，例如需要考慮運(yùn)算精度的影響；(2). 確定性 definiteness精選名師 優(yōu)秀名師 - - - - - - - - - -第 5 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -算法中的每一個步驟都必需是有明確定義的，不答應(yīng)有模棱兩可的說明或多義性；(3). 有窮性 finiteness算法必需能在有限的時間內(nèi)昨晚，運(yùn)算法必需能在執(zhí)行有限個步驟后終止；例如無窮級數(shù)的運(yùn)算只能是依據(jù)精讀要求取

10、有限項(xiàng)的有窮運(yùn)算；假如一個算法需要執(zhí)行千萬年，就失去了有用價(jià)值；3. 擁有足夠的情報(bào)（sufficient information）通常算法中的各種運(yùn)算總是要施加到各個運(yùn)算的對象上，而這些對象又可能具有某種初始狀態(tài)，這是算法執(zhí)行的起點(diǎn)或依 據(jù)；因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出；當(dāng)輸入不夠或輸入錯誤時，算法本身也就無法執(zhí)行或?qū)е聢?zhí)行有錯；一般來說，當(dāng)算法擁有足夠的情報(bào)時，此算法才是有效的，而當(dāng)情報(bào)不夠時，算法并不有效；綜上所述 ：所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算次序的規(guī)章， 并且每一個規(guī)章都是有效的，且是明確的，此次序?qū)⒃谟邢薜拇螖?shù)下終止；2). 算

11、法的基本要素 ：(1). 對數(shù)據(jù)對象的運(yùn)算和操作：a). 算術(shù)運(yùn)算，加、減、乘、除等運(yùn)算；b). 規(guī)律運(yùn)算，“與”、“或”、“非”等運(yùn)算；精選名師 優(yōu)秀名師 - - - - - - - - - -第 6 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -c). 關(guān)系運(yùn)算，“大于”、“小于”、“等于”、“不等于”等運(yùn)算；d). 數(shù)據(jù)傳輸，主要包括賦值、輸入、輸出等操作；留意：運(yùn)算機(jī)程序僅作為算法的一種描述；但通常不直接用運(yùn)算機(jī)程序來描述算法，而是用別的描述工具（如流程圖、特地的算法描述語言，甚至自然語言）來描述算法；

12、(2). 算法的掌握結(jié)構(gòu)：一個算法的功能不僅取決于所選用的操作，而且仍與各操作之間執(zhí)行次序有關(guān)；算法中各操作之間的執(zhí)行次序稱為算法的控制結(jié)構(gòu)；一個算法一般可以用次序、挑選、循環(huán)3種基本的掌握結(jié)構(gòu)組合而成；2算法設(shè)計(jì)基本方法1). 列舉法：舉例白雞問題，畫出搜尋空間的立體示意圖；2). 歸納法：基本思想和本質(zhì)（抽象）；3). 遞推法：本質(zhì)（歸納法）；4). 遞歸法：基本思想（逐層分解）；基礎(chǔ)（歸納）；5). 減半遞推法 ：又稱為分治法；“減半”是將問題的規(guī)模減半；“遞推”是指重復(fù)“減半”；舉例：矩陣相乘；二分法求實(shí)根；6). 回溯法：基本思想（“試”），處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)方面有廣泛應(yīng)用；舉例：求解

13、皇后問題，用方格圖 講解；精選名師 優(yōu)秀名師 - - - - - - - - - -第 7 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -3算法的復(fù)雜度分析1). 算法的時間復(fù)雜度 ：所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的運(yùn)算工作量；可用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量；算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所 執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)（see page 10）；在同一問題規(guī)模下，假如算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時，可以用以下兩種方法來分析算法

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

15、初始數(shù)據(jù)所占的儲備空間以及算法執(zhí)行過程中所需要的額外空間；其中額外空間包括算法程序執(zhí)行過程中的工作單元精選名師 優(yōu)秀名師 - - - - - - - - - -第 8 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加儲備空間（例如在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要儲備數(shù)據(jù)本身外，仍需要儲備連接信息）；4習(xí)題講解及作業(yè)布置： 舉例講解： 1.1 、 1.3 ；第一次上機(jī)試驗(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)的

16、基本概念數(shù)據(jù)結(jié)構(gòu)作為運(yùn)算機(jī)的一門學(xué)科，主要爭論以下三個方面的問題：(a). 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的規(guī)律關(guān)系，即數(shù)據(jù)的規(guī)律結(jié)構(gòu)；(b). 在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在運(yùn)算機(jī)中的儲備關(guān)系，即數(shù)據(jù)的儲備結(jié)構(gòu)；(c). 對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算；爭論以上各問題的主要目的是為了提高數(shù)據(jù)處理的效率；所謂提高數(shù)據(jù)處理的效率，主要包括兩個方面：一是提高數(shù)據(jù)處理的速度；二是盡量節(jié)約數(shù)據(jù)處理過程中所占用的運(yùn)算機(jī)儲備空間；精選名師 優(yōu)秀名師 - - - - - - - - - -第 9 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - -

17、- - - -1.兩個實(shí)例 ： a.無序表和有序表的查找效率對比；b.學(xué)生情形登記表； 1.數(shù)據(jù)結(jié)構(gòu)的定義 ：相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合； a.數(shù)據(jù)元素的含義；b.前后件關(guān)系；(1). 數(shù)據(jù)的規(guī)律結(jié)構(gòu)：反映數(shù)據(jù)元素之間規(guī)律關(guān)系的數(shù)據(jù)結(jié)構(gòu)；兩個要素：一是數(shù)據(jù)元素的集合D ；二是D上的關(guān)系R ；一個數(shù)據(jù)結(jié)構(gòu)可以表示為B=D,R；舉例（seepage 18 ）更正： page18中最終一行和page19中第一行： D i 應(yīng)改為Ai；(2). 數(shù)據(jù)的儲備結(jié)構(gòu)（物理結(jié)構(gòu)）：數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)儲備空間中的存放形式；常用的儲備結(jié)構(gòu)：次序；鏈接；索引；3. 數(shù) 據(jù) 結(jié) 構(gòu) 的 圖 形 表 示 ： 直 觀

18、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)；一般來說，假如一個非空的數(shù)據(jù)結(jié)構(gòu)滿意兩個條件：a 有且只有一個根節(jié)點(diǎn)；b 每個節(jié)點(diǎn)最多有一個前件，也最多只有一個后件；就稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表；精選名師 優(yōu)秀名師 - - - - - - - - - -第 10 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -此外：

19、在插入或刪除任何一個節(jié)點(diǎn)后仍應(yīng)當(dāng)滿意上述條件；2線性表及其次序儲備結(jié)構(gòu)1). 線性表及其運(yùn)算 ：(1). 什么是線性表 a. 需要懂得的概念名詞：記錄；文件；b. 非空線性表的結(jié)構(gòu)特點(diǎn)（see page 22）；(2). 線性表的次序儲備結(jié)構(gòu)(a). 基本特點(diǎn)：（ see page 22）；(b). 初始化線性表的次序儲備空間（seepage23 ）， new和delete語句成對使用的習(xí)慣：申請空間-釋放空間；(c). 線性表的主要運(yùn)算：（see page 23）(3). 線性表在次序儲備下的插入運(yùn)算：例2.7(a). 插入前后兩線性表中的元素關(guān)系（see page 24）(b). 平均移動

20、元素?cái)?shù)量的運(yùn)算：0+1+n/n+1=n+10+n/2/n+1=n/2(c). 由于 C+ 中數(shù)組下標(biāo)從0開頭，涉及到數(shù)組下標(biāo)的變量均要減去 1 ；(4). 線性表在次序儲備下的刪除運(yùn)算 a. 刪除前后兩線性表中的元素關(guān)系（see page 26） b. 平均移動元素?cái)?shù)量的運(yùn)算：精選名師 優(yōu)秀名師 - - - - - - - - - -第 11 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -0+1+n-1/n=n0+n-1/2/n=n-1/2更正： page26中最終一行應(yīng)改為：認(rèn)為刪除第 n+1 個元素，即無此

21、元素；(5). 次序表類將次序表的數(shù)據(jù)和基本操作（包括初始化、輸出、插入和刪除）封裝成類；更正： page30中其次段應(yīng)當(dāng)為：假如次序表非空，就調(diào)用2). 棧及其應(yīng)用：(1). 什么是棧（ stack ）：一種特別的線性表，其插入和刪除都只在線性表的一端進(jìn)行，即一端封閉，另一端開口；概念名詞：棧頂（top ）；棧底（ bottom ）；入棧（ push ）；退棧（ pop ）(2). 棧的次序儲備及其運(yùn)算：see page 33-34留意：程序中數(shù)組下標(biāo)減一的操作； 3. 次序棧類4. 表 達(dá) 式 的 計(jì) 算4. 遞 歸 的 實(shí) 現(xiàn)3. 隊(duì)列及其應(yīng)用 ：1. 什么是隊(duì)列（queue ）：一種特

22、別的線性表，答應(yīng)在一端進(jìn)行插入，而在另一端進(jìn)行刪除；FIFO or LILO精選名師 優(yōu)秀名師 - - - - - - - - - -第 12 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -概念名詞：排頭指針（front ）；隊(duì)尾指針（rear ）；入隊(duì)運(yùn)算；退隊(duì)運(yùn)算 2. 循環(huán)隊(duì)列及其運(yùn)算：see page 42-43 3. 循環(huán)隊(duì)列類4. 隊(duì)列的應(yīng)用： a. 安排工作； b. IO緩沖區(qū)； c.加油模擬3線性鏈表及其運(yùn)算1). 線性鏈表的基本概念 ：(1). 線性表的次序儲備結(jié)構(gòu)的缺點(diǎn)：a. 插入或刪除線性

23、表中元素過程中需要移動大量數(shù)據(jù)元素；b. 儲備空間不便于擴(kuò)充；c. 不便于對儲備空間的動態(tài)安排；(2). 鏈?zhǔn)絻浞绞街械膬浣Y(jié)點(diǎn)構(gòu)成：a. 數(shù)據(jù)域； b. 指針域(3). 線性鏈表：線性表的鏈?zhǔn)絻浣Y(jié)構(gòu)；(4). 基本概念： a.Head指針； b.NULL或 0； c. 線性單鏈表； d.線性雙向鏈表；e. 左指針（ Llink ）； f.右指針（ Rlink ）(3). 線性鏈表類(4). 鏈棧及其基本操作：a. 初始化； b.入棧； c. 退棧； d.讀棧頂元素；(5). 鏈隊(duì)及其基本操作：a. 初始化； b.入隊(duì)； c. 退隊(duì)；精選名師 優(yōu)秀名師 - - - - - - - - -

24、-第 13 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -2). 線性鏈表的基本運(yùn)算 ：1. 插入：在指定元素的結(jié)點(diǎn)之前插入一個新元素；2. 刪除：刪除包含制定元素的結(jié)點(diǎn)；(3). 合并：將兩個線性鏈表按要求合并為一個線性鏈表；(4). 分解：將一個線性鏈表按要求進(jìn)行分解；5. 逆轉(zhuǎn)； 6. 復(fù)制； 7. 排序； 8. 查找；3). 循環(huán)鏈表：為了克服對空表與非空表運(yùn)算的不統(tǒng)一問題；(1). 增加一個表頭結(jié)點(diǎn)：其數(shù)據(jù)域?yàn)槿我饣蛞罁?jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點(diǎn)；(2). 最終一個結(jié)點(diǎn)的指針域不是

25、空（NULL ），而是指向表頭結(jié)點(diǎn)；即在循環(huán)鏈表中，全部結(jié)點(diǎn)的指針域構(gòu)成了一個環(huán)狀鏈；3. 多項(xiàng)式的表示與運(yùn)算 ：略4數(shù)組二維數(shù)組：矩陣在程序設(shè)計(jì)語言中的表示；程序設(shè)計(jì)語言中的數(shù)組在運(yùn)算機(jī)中是次序儲備的；當(dāng)矩陣中的絕大部分元素為零時，采納一般的兩維數(shù)組儲備方式會鋪張大量的儲備空間，同時也做了大量不必要的運(yùn)算；1. 數(shù)組的次序儲備結(jié)構(gòu) ：1. 二維數(shù)組以行為主的次序儲備：逐行、從左至右的次序；精選名師 優(yōu)秀名師 - - - - - - - - - -第 14 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -ADRa

26、 ij=ADRa11 +i-1n+j-1L, where 1 i m, 1 j nBASIC、C 中的多維數(shù)組采納以行為主的次序儲備； 2. 二維數(shù)組以列為主的次序儲備：逐列、從上至下的次序；ADRa ij =ADRa 11 +j-1m+i-1L, where 1 i m, 1 j nFORTORA中N 的多維數(shù)組采納以列為主的次序儲備；2. 規(guī)章矩陣的壓縮(1). 下三角陣（ lower triangular matrix）；(2). 對稱陣（ symmetrical matrix）；(3). 三對角陣（ tridiagonal matrix）；3. 一般稀疏矩陣（sparse matrix

27、）的表示(1). 三列二維數(shù)組：a. 矩 陣 的 大 小 總 行 數(shù) （ numberofrows） 和 總 列 數(shù)（ number of columns）；b. 非零元素的位置（行號和列號）；c. 非零元素的值；d. POS和 NUM ；e. 操作：生成；輸出；轉(zhuǎn)置；相加；相乘；(2). 線性鏈表：(3). 十字鏈表： （自學(xué)，不考）精選名師 優(yōu)秀名師 - - - - - - - - - -第 15 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -5樹與二叉樹1). 樹的基本概念：一種簡潔的非線性結(jié)構(gòu)；1. 基

28、本概念： a.父結(jié)點(diǎn)； b.子結(jié)點(diǎn)； c.根； d.度； e.樹的度； f. 葉子結(jié)點(diǎn)2). 二叉樹及其基本性質(zhì)：一種有用的非線性結(jié)構(gòu)（binary tree ）1. 特點(diǎn)： a.非空二叉樹只有一個根結(jié)點(diǎn)；b.每個結(jié)點(diǎn)最多有兩顆子樹（稱為左子樹和右子樹）；2. 基本性質(zhì)： 1 ， 2， 3， 4， 5， 63. 遍歷： a. 前序遍歷； b. 中序遍歷； c. 后序遍歷；6圖（自學(xué)，不考）7習(xí)題講解及作業(yè)布置： 舉例講解： 2.1 0；第一次作業(yè)： 2.5 、2.6 、2.8其次次試驗(yàn)：2.9 、 2.13 中選1題 ； 2.10 、 2.11 、2.12 、2.14 中選 1 題（各題難度系

29、數(shù)均為1.0 ）；其次次作業(yè)：2.15 、 2.16 、 2.17 中選1題 ； 2.20 、2.21 、2.22 精選名師 優(yōu)秀名師 - - - - - - - - - -第 16 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -第 3 章查找與排序技術(shù)1基本的查找技術(shù)基本概念：所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素；通常依據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采納不同的查找方 法；1). 次序查找 ：次序搜尋；從線性表的第一個元素開頭，依次比較，結(jié)果為找到或失敗；平均搜尋比較次數(shù)為n/2 ；以下兩種情形下必需使用次序查找：a.無序表； b. 鏈?zhǔn)絻浣Y(jié)構(gòu)；2). 對分查找：適用于有序表；3). 分塊查找 ：索引次序查找；分塊有序表的結(jié)構(gòu)：a.線性表本身采納次序儲備結(jié)構(gòu)；b.建立一個索引表