2022年《計算機軟件技術基礎教案》

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

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

4、 - -5). 網(wǎng)絡及數(shù)據(jù)安全技術 ：要求同學學習和把握網(wǎng)絡及數(shù)據(jù)安全技術的基本概念與原理；2重點和難點1). 本課程的重點：其次章數(shù)據(jù)結構；2). 本課程的難點 ： a線性鏈表； b樹、圖的遍歷；c查找、索引和排序技術運算及其應用；3先修課程：運算機基礎； C 語言；三課程內(nèi)容1理論學問：（ 22 學時）1). 運算機軟件概述 ：運算機軟件的基本概念、程序設計技術、數(shù)據(jù)結構的基本概念及術語、算法描述及算法分析初步；2). 線性表：線性表的規(guī)律結構、線性表的次序儲備結構、線性表的鏈式儲備結構、表的基本運算在特定儲備結構中的實現(xiàn)及應用；3). 棧和隊列 ：棧的定義、表示和實現(xiàn)、棧的應用、隊列的定

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

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

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

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

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

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

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

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

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

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

15、初始數(shù)據(jù)所占的儲備空間以及算法執(zhí)行過程中所需要的額外空間；其中額外空間包括算法程序執(zhí)行過程中的工作單元精選名師 優(yōu)秀名師 - - - - - - - - - -第 8 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結 - - - - - - - - - - - -以及某種數(shù)據(jù)結構所需要的附加儲備空間（例如在鏈式結構中，除了要儲備數(shù)據(jù)本身外，仍需要儲備連接信息）；4習題講解及作業(yè)布置： 舉例講解： 1.1 、 1.3 ；第一次上機試驗：1.2 、1.4 、1.5三題中任選2題（三題難度系數(shù)分別為1.0, 1.0, 1.2）；第 2 章數(shù)據(jù)結構及其運算1數(shù)據(jù)結構的

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

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

18、1. 需要懂得的概念名詞：根節(jié)點；終端結點；內(nèi)部節(jié)點；(2). 數(shù)據(jù)結構的基本運算：插入和刪除；其它運算仍有：查找分類合并分解復制和修改等；(3). 數(shù)據(jù)結構中依據(jù)各數(shù)據(jù)元素之間前后件關系的復雜度，一般將數(shù)據(jù)結構分為：線性結構和非線性結構；一般來說，假如一個非空的數(shù)據(jù)結構滿意兩個條件：a 有且只有一個根節(jié)點；b 每個節(jié)點最多有一個前件，也最多只有一個后件；就稱該數(shù)據(jù)結構為線性結構，又稱線性表；精選名師 優(yōu)秀名師 - - - - - - - - - -第 10 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結 - - - - - - - - - - - -此外：

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

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

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

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

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

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

25、空（NULL ），而是指向表頭結點；即在循環(huán)鏈表中，全部結點的指針域構成了一個環(huán)狀鏈；3. 多項式的表示與運算 ：略4數(shù)組二維數(shù)組：矩陣在程序設計語言中的表示；程序設計語言中的數(shù)組在運算機中是次序儲備的；當矩陣中的絕大部分元素為零時，采納一般的兩維數(shù)組儲備方式會鋪張大量的儲備空間，同時也做了大量不必要的運算；1. 數(shù)組的次序儲備結構 ：1. 二維數(shù)組以行為主的次序儲備：逐行、從左至右的次序；精選名師 優(yōu)秀名師 - - - - - - - - - -第 14 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結 - - - - - - - - - - - -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. 操作：生成；輸出；轉置；相加；相乘；(2). 線性鏈表：(3). 十字鏈表： （自學，不考）精選名師 優(yōu)秀名師 - - - - - - - - - -第 15 頁，共 19 頁 - - - - - - - - - -精品word 名師歸納總結 - - - - - - - - - - - -5樹與二叉樹1). 樹的基本概念：一種簡潔的非線性結構；1. 基

28、本概念： a.父結點； b.子結點； c.根； d.度； e.樹的度； f. 葉子結點2). 二叉樹及其基本性質：一種有用的非線性結構（binary tree ）1. 特點： a.非空二叉樹只有一個根結點；b.每個結點最多有兩顆子樹（稱為左子樹和右子樹）；2. 基本性質： 1 ， 2， 3， 4， 5， 63. 遍歷： a. 前序遍歷； b. 中序遍歷； c. 后序遍歷；6圖（自學，不考）7習題講解及作業(yè)布置： 舉例講解： 2.1 0；第一次作業(yè)： 2.5 、2.6 、2.8其次次試驗：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 名師歸納總結 - - - - - - - - - - - -第 3 章查找與排序技術1基本的查找技術基本概念：所謂查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素；通常依據(jù)不同的數(shù)據(jù)結構，采納不同的查找方 法；1). 次序查找 ：次序搜尋；從線性表的第一個元素開頭，依次比較，結果為找到或失??；平均搜尋比較次數(shù)為n/2 ；以下兩種情形下必需使用次序查找：a.無序表； b. 鏈式儲備結構；2). 對分查找：適用于有序表；3). 分塊查找 ：索引次序查找；分塊有序表的結構：a.線性表本身采納次序儲備結構；b.建立一個索引表