計(jì)算機(jī)軟件技術(shù)基礎(chǔ)知識(shí)點(diǎn)總結(jié)

《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》第一章算法1.1算法的基本概念算法：指解題方案的準(zhǔn)確而完整的描述算法的基本特征：能行性（算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)；算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的）確定性（算法中的每一個(gè)步驟都必須是有明確定義的，不能摸棱兩可，也不能有多義性）有窮性（算法必須能在執(zhí)行有限個(gè)步驟之后終止）擁有足夠的情報(bào)（算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)。不同輸入對(duì)應(yīng)不同輸出）算法：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的、明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法的基本要素：1.算法中對(duì)數(shù)據(jù)的運(yùn)算和操作（算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸【賦值、輸入、輸出】）2.算法的控制結(jié)構(gòu)（算法中各操作之間的執(zhí)行順序）1.2算法描述語言C語言描述和簡單的算法描述語言（1）符號(hào)與表達(dá)式：符號(hào)主要用以表述變量名、數(shù)組名等（2）賦值語句（3）控制轉(zhuǎn)移語句：無條件轉(zhuǎn)移語句形式：GOTO標(biāo)號(hào)條件轉(zhuǎn)移語句形式IFCTHENSIFCTHENS1ELSES2（4）循環(huán)語句WHILE語句：WHILECDOSFOR語句：FORi=initTOlimitBYstepDOS（5）其他語句EXIT語句：退出某個(gè)循環(huán)，使控制轉(zhuǎn)到包含EXIT語句的最內(nèi)層的WHILE或FOR循環(huán)后面的一個(gè)語句去執(zhí)行RETURN語句：結(jié)束算法的執(zhí)行（允許使用用引號(hào)括起來的注釋信息）READ(INPUT)和WRITE(PRINT/OUTPUT)語句：用于輸入輸出（6）算法中的注釋總是用一對(duì)方括號(hào)【】括起來；復(fù)合語句用一對(duì)花括號(hào){}括起來1.3算法設(shè)計(jì)基本方法1.列舉法【例1.1】基本思想：根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的（通常解決“是否存在”“有多少種可能”類型問題）特點(diǎn)：算法比較簡單，但列舉情況較多時(shí)，工作量將很大尋找路徑、查找、搜索等問題采用列舉法有效2.歸納法基本思想：通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系3.遞推法（數(shù)學(xué)例題）指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果（本質(zhì)屬于歸納法）4.遞歸基本思想：將問題逐層分解的過程，實(shí)際上并沒有對(duì)問題進(jìn)行求解，而只是當(dāng)解決了最后那些簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合【例1.3】自己調(diào)用自己的過程稱為遞歸調(diào)用過程遞歸分為直接遞歸：一個(gè)算法P顯式地調(diào)用自己間接遞歸：算法P調(diào)用另一個(gè)算法Q，而算法Q又調(diào)用算法P5.減半遞推技術(shù)（分治法）減半：將問題的規(guī)模減半，而問題的性質(zhì)不變遞推：重復(fù)“減半”的過程【例1.4】6.回溯法通過對(duì)問題的分析，找出一個(gè)解決問題的線索；然后沿著這個(gè)線索逐步試探。對(duì)于每一步的試探，如果成功，就得到問題的解；若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。（處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)方面有廣泛應(yīng)用）【例1.5】1.4算法的復(fù)雜度分析算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量，同時(shí)還需對(duì)問題的規(guī)模進(jìn)行度量綜上，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)其中，n是問題的規(guī)模在同一個(gè)問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí)，可以用以下兩種方法來分析算法的工作量（1）平均性態(tài)：用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均數(shù)來度量算法分工作量A(n)）（2）最壞情況復(fù)雜性：在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)W(n)【例1.6】算法的空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間一個(gè)算法所占用的存儲(chǔ)空間包括：算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括：算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間如果額外空間量相對(duì)于問題規(guī)模來說是常數(shù)，則稱該算法是原地（inplace）工作的實(shí)際問題中，為減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不必要的額外空間

第4章資源管理技術(shù)計(jì)算機(jī)系統(tǒng)主要包括硬件（即物理設(shè)備）和軟件（即程序及其文檔的總稱）兩大部分；計(jì)算機(jī)系統(tǒng)中所有的硬件和軟件統(tǒng)稱為計(jì)算機(jī)資源。操作系統(tǒng)是最基本和核心的系統(tǒng)軟件，是用以控制和管理系統(tǒng)資源、方便用戶使用計(jì)算機(jī)的程序的集合。操作系統(tǒng)的功能和任務(wù)主要有處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理、文件管理、作業(yè)管理。操作系統(tǒng)發(fā)展過程：手工操作階段（手編程序）、成批處理系統(tǒng)（脫機(jī)技術(shù)）、執(zhí)行程序系統(tǒng)（主機(jī)與通道并行工作）、多道程序系統(tǒng)（并行性、共享性）。為使主機(jī)和輸入輸出設(shè)備并行工作，人們使用以通道技術(shù)、中斷技術(shù)和多道程序設(shè)計(jì)技術(shù)為基礎(chǔ)的假脫機(jī)技術(shù)。多道程序技術(shù)是指在計(jì)算機(jī)內(nèi)存中同時(shí)存放多道相互獨(dú)立的程序，他們?cè)诓僮飨到y(tǒng)的控制下，共享系統(tǒng)的硬件和軟件資源。操作系統(tǒng)的分類（按使用環(huán)境及訪問方式）：多道批處理操作系統(tǒng)分時(shí)操作系統(tǒng)，特點(diǎn)：同時(shí)性、獨(dú)立性、及時(shí)性、交互性；分時(shí)是指若干個(gè)并發(fā)程序?qū)PU的分時(shí)，其中每個(gè)程序?qū)PU的時(shí)間分享單位稱為時(shí)間片；第一個(gè)分時(shí)操作系統(tǒng)是UNIX操作系統(tǒng)。實(shí)時(shí)操作系統(tǒng)通用操作系統(tǒng)多窗口系統(tǒng)，特點(diǎn)：靈活、方便的窗口操作，彈出式菜單、命令對(duì)話框；代表：MicrosoftWindows系統(tǒng)。順序程序的特點(diǎn)：順序性（按順序執(zhí)行）、封閉性（一旦執(zhí)行其結(jié)果不受外界因素影響）、可再現(xiàn)性（結(jié)果與運(yùn)行速度無關(guān)）。在單處理機(jī)的情況下，所謂并發(fā)執(zhí)行是指多個(gè)程序的運(yùn)行在時(shí)間上是重疊的，一個(gè)程序的運(yùn)行尚未結(jié)束，另一個(gè)程序的運(yùn)行已經(jīng)開始，而并不是說這些程序在某一時(shí)刻同時(shí)占用處理機(jī)在運(yùn)行。并發(fā)程序特點(diǎn)：并發(fā)程序沒有封閉性（結(jié)果與各程序執(zhí)行的相對(duì)速度有關(guān)，結(jié)果的不確定性）；程序與其執(zhí)行過程不是一一對(duì)應(yīng)的關(guān)系（共享）；程序并發(fā)執(zhí)行可以相互制約。所謂進(jìn)程，是指一個(gè)具有一定獨(dú)立能力的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)，簡單地說，進(jìn)程可以是并發(fā)執(zhí)行的程序的執(zhí)行過程，是控制程序管理下的基本的多道程序單位。進(jìn)程與程序的區(qū)別：進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，是動(dòng)態(tài)的概念；而程序只是一組指令的有序集合，是一個(gè)靜態(tài)的概念。進(jìn)程是程序的執(zhí)行過程，是一次運(yùn)行活動(dòng)，具有一定的生命期；而程序是可以作為一種軟件資源長期保存的。進(jìn)程的組成包括程序、數(shù)據(jù)以及進(jìn)程控制塊（PCB）。一個(gè)程序可能對(duì)應(yīng)多個(gè)進(jìn)程。一個(gè)進(jìn)程可以包含多個(gè)程序。進(jìn)程三種基本狀態(tài)：運(yùn)行狀態(tài)（進(jìn)程只能在運(yùn)行狀態(tài)下結(jié)束）、就緒狀態(tài)、等待狀態(tài)（又叫阻塞狀態(tài)或封鎖狀態(tài)），三種基本狀態(tài)之間在一定條件下可相互轉(zhuǎn)換。對(duì)進(jìn)程的物理組織方式通常有線性表和鏈接表兩種。由于各進(jìn)程互相獨(dú)立地動(dòng)態(tài)獲得，不斷申請(qǐng)和釋放系統(tǒng)中的軟硬件資源，這就有可能使系統(tǒng)出現(xiàn)這樣一種狀態(tài)：其中若干個(gè)進(jìn)程均因互相“無知地”等待對(duì)方所占有的資源而無限地等待。這種狀態(tài)稱為死鎖。發(fā)生死鎖的四個(gè)必要條件：資源的獨(dú)占使用、資源的非搶占分配、資源的部分分配、對(duì)資源的循環(huán)等待。當(dāng)其中某一條件滿足時(shí)，有可能發(fā)生死鎖，但也并不是一定會(huì)發(fā)生死鎖。當(dāng)多個(gè)進(jìn)程共享數(shù)據(jù)塊或其他排他性使用資源時(shí)，不能同時(shí)進(jìn)入存取或使用，但進(jìn)入的次序可以任意，這些進(jìn)程之間的這種相互制約關(guān)系稱為互斥（多個(gè)操作決不能在同一時(shí)刻執(zhí)行）。進(jìn)程之間為了合作完成一個(gè)任務(wù)，而需要互相等待和互相交換信息的相互制約關(guān)系稱為同步。一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源，訪問臨界資源的程序段稱為臨界區(qū)或臨界段。進(jìn)程通信可分為互斥與同步兩類，互斥是一種特殊的同步關(guān)系。根據(jù)通信情況的不同，可把進(jìn)程之間的同步分為信號(hào)同步（低級(jí)通信原語用于信號(hào)同步，如P/V操作）與信件同步（高級(jí)通信原語用于信件同步，消息緩沖是一種高級(jí)通信工具）。處理機(jī)調(diào)度一般分為兩級(jí)：作業(yè)調(diào)度（又稱為高級(jí)調(diào)度或宏調(diào)度）與進(jìn)程調(diào)度（又稱為低級(jí)調(diào)度或微調(diào)度）在進(jìn)行地址變換時(shí)（又稱地址映射，當(dāng)用戶程序進(jìn)入內(nèi)存執(zhí)行時(shí)，必須要把用戶程序中所有相對(duì)地址轉(zhuǎn)換為內(nèi)存中的實(shí)際地址，否則用戶程序就無法進(jìn)行），必須修改程序中所有與地址有關(guān)的項(xiàng)，也就是說，要對(duì)程序中的指令地址以及指令中的有關(guān)地址的部分（稱為有效地址）進(jìn)行調(diào)整，這個(gè)調(diào)整的過程稱為地址重定位。存儲(chǔ)管理的功能：地址變換、內(nèi)存分配、存儲(chǔ)共享與保護(hù)、存儲(chǔ)器擴(kuò)充。基本的存儲(chǔ)管理技術(shù)：界地址存儲(chǔ)管理、分頁存儲(chǔ)管理、分段存儲(chǔ)管理、段頁式存儲(chǔ)管理。分頁存儲(chǔ)管理與分段存儲(chǔ)管理的優(yōu)缺點(diǎn)：分頁存儲(chǔ)管理的優(yōu)點(diǎn)：a.用戶地址空間不再受內(nèi)存大小的限制；b.更有利地利用了內(nèi)存；c.動(dòng)態(tài)分頁管理提供了虛擬存儲(chǔ)器（受外存容量的限制），更有利于多道程序的運(yùn)行。分頁存儲(chǔ)管理帶來的問題：a.不利于程序的動(dòng)態(tài)連接裝配；b.不利于程序與數(shù)據(jù)的共享。分段存儲(chǔ)管理正好解決了這兩個(gè)問題。文件的物理組織形式主要有連續(xù)文件、鏈接文件和索引文件（建議看看P263多級(jí)索引結(jié)構(gòu)）；文件系統(tǒng)對(duì)磁盤空閑空間的管理方式有空閑文件項(xiàng)和空閑區(qū)表、空閑塊鏈、位示圖、空閑塊成組鏈接法。

第6章編譯技術(shù)概述編譯程序是將用高級(jí)語言編寫的源程序翻譯成機(jī)器語言程序的實(shí)用程序。編譯程序的基本組成：（1）詞法分析程序（讀詞程序）；（2）語法分析程序：編譯程序的主要組成成分；（3）加工程序：直接影響翻譯質(zhì)量的關(guān)鍵一步，包括大量的造表和查表的過程；（4）優(yōu)化修飾部分；（5）裝配程序或鏈接程序：將分塊編譯得到的半目標(biāo)程序（包括庫程序）進(jìn)行總裝配。狀態(tài)矩陣法的核心是一張狀態(tài)表（也稱狀態(tài)矩陣）。所謂狀態(tài)，是表示過去已經(jīng)掃描了什么語法成分，以便當(dāng)遇到新的語法符號(hào)時(shí)，在不同的狀態(tài)下對(duì)該語法符號(hào)作出不同的處理。（關(guān)于狀態(tài)矩陣的具體編譯過程建議看書299-307）狀態(tài)矩陣是稀疏矩陣，為節(jié)省存儲(chǔ)空間，通常對(duì)狀態(tài)矩陣進(jìn)行壓縮。通過詞法分析，可將一個(gè)常數(shù)用V×10m表示，其中V為正整數(shù)，m=ep-n，e為階碼符號(hào)（+、-），p為階碼絕對(duì)值，n為小數(shù)位數(shù)。如FROTRAN常數(shù)0.032E-1中，e=-，p=1，n=3，經(jīng)詞法分析，其結(jié)果為32×10-1-3=32×10-4（V=32，m=-4）。在多遍掃描的編譯系統(tǒng)中，源程序每經(jīng)過一遍掃描都要產(chǎn)生一種等效的中間語言表示。所謂中間語言，可概略地理解為能用來表達(dá)源程序并與之等效的一種編碼方式，如波蘭表示、三元組表示等。一個(gè)表達(dá)式的波蘭表示就是后綴表示，即表達(dá)式中的運(yùn)算對(duì)象寫在前面，運(yùn)算符寫在后面。三元組表示的一般形式為k,(θo1o2)，其意義為：對(duì)o1和o2作θ運(yùn)算，并將結(jié)果存放在一個(gè)虛擬的累加器k中。（關(guān)于波蘭表示和三元組表示的具體編譯過程建議看書310-316）語法分析和加工是編譯系統(tǒng)的核心部分，其主要任務(wù)有：（1）識(shí)別出各種類型的語句，并進(jìn)行語法檢查；（2）語法的加工處理；（3）編譯程序工作的最后結(jié)果是產(chǎn)生目標(biāo)程序或半目標(biāo)程序。語法分析的方法主要有優(yōu)先矩陣法（設(shè)置優(yōu)先對(duì)象棧和算符棧）、優(yōu)先數(shù)法（構(gòu)造棧內(nèi)優(yōu)先數(shù)表和棧外優(yōu)先數(shù)表）、狀態(tài)矩陣法（用表格形式描述編譯過程）、遞歸子程序法（處理遞歸定義）等。

第七章應(yīng)用軟件設(shè)計(jì)與開發(fā)技術(shù)1.軟件生命周期分為幾個(gè)階段？每個(gè)階段輸出的文檔2.什么是數(shù)據(jù)流程圖？數(shù)據(jù)流程圖與程序流程圖的區(qū)別3.數(shù)據(jù)字典包含內(nèi)容4.什么是軟件支援環(huán)境？舉例熟悉的軟件支援環(huán)境5.有人說：“軟件是不會(huì)用壞的，因此，經(jīng)過測(cè)試和調(diào)試的軟件不需要維護(hù)?！蹦阏J(rèn)為這句話有道理嗎？為什么？6.分段函數(shù)，畫出實(shí)現(xiàn)該功能的程序流程圖，設(shè)計(jì)測(cè)試用例（白箱法、邊值分析法）知識(shí)點(diǎn)（可能考點(diǎn)）總結(jié)：判斷、選擇、填空、簡答（1～2題）一、軟件工程概述計(jì)算機(jī)硬件的發(fā)展經(jīng)歷：電子管、晶體管、集成電路和大規(guī)模集成電路、超大規(guī)模集成電路四個(gè)時(shí)代軟件工程：采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開發(fā)和維護(hù)軟件生命周期：軟件定義期（問題定義、可行性研究、需求分析）、軟件開發(fā)期（系統(tǒng)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼和測(cè)試）、軟件維護(hù)期（運(yùn)行維護(hù)階段）軟件支援環(huán)境：指在宿主硬件和宿主軟件的基礎(chǔ)上，用于輔助、支援其他軟件的研制和維護(hù)的一種軟件，包括環(huán)境數(shù)據(jù)庫、接口軟件、工具組三個(gè)組成部分二、軟件詳細(xì)設(shè)計(jì)的表達(dá)工程上常用的表達(dá)工具：圖形工具、表格工具、語言工具常用算法描述工具：程序流程圖（程序框圖）、NS圖（盒圖）、問題分析圖PAD、判定表、過程設(shè)計(jì)語言PDL（偽碼/結(jié)構(gòu)化語言）三、結(jié)構(gòu)化分析與設(shè)計(jì)方法應(yīng)用軟件開發(fā)的基本原則：自頂向下的系統(tǒng)結(jié)構(gòu)開發(fā)原則、模塊化結(jié)構(gòu)開發(fā)原則應(yīng)用軟件的開發(fā)方法：（1）非自動(dòng)形式的開發(fā)方法：系統(tǒng)流程圖法、結(jié)構(gòu)化分析方法（SA方法）、結(jié)構(gòu)化設(shè)計(jì)方法（SD方法）、數(shù)據(jù)結(jié)構(gòu)法（Jackson法）、層次輸入—處理—輸出方法（HIPO方法）（2）半自動(dòng)形式的開發(fā)方法：SREM方法（軟件需求工程法）、PSL（問題說明語言）/PSA（問題說明分析器）方法（3）自動(dòng)形式的系統(tǒng)開發(fā)方法：HOS方法（可自動(dòng)進(jìn)行系統(tǒng)分析、系統(tǒng)設(shè)計(jì)和自動(dòng)編程）結(jié)構(gòu)化分析方法（SA）特點(diǎn)：分解和抽象、文檔的規(guī)范化、面向用戶、系統(tǒng)的邏輯設(shè)計(jì)和物理設(shè)計(jì)分開進(jìn)行數(shù)據(jù)流程圖：簡稱DFD，是SA方法最主要的一種圖形工具，它從數(shù)據(jù)加工的角度，以圖形方式描述信息處理系統(tǒng)的邏輯結(jié)構(gòu)，能比較直觀地描述信息處理中的業(yè)務(wù)情況數(shù)據(jù)流程圖組成符號(hào)：數(shù)據(jù)流、數(shù)據(jù)處理（加工）、數(shù)據(jù)存儲(chǔ)（文件）、外部實(shí)體畫數(shù)據(jù)流程圖的方法：自頂向下逐層分解、由外向里逐漸深化數(shù)據(jù)字典：是結(jié)構(gòu)化分析方法的另一個(gè)重要工具。主要是給數(shù)據(jù)流程圖中的每一個(gè)數(shù)據(jù)