全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考綱

名目二級(jí)公共根底學(xué)問考綱 1第一章數(shù)據(jù)構(gòu)造與算法 2其次章程序設(shè)計(jì)根底 19第三章軟件工程根底 23第四章 數(shù)據(jù)庫設(shè)計(jì)根底.............................................32全國計(jì)算機(jī)等級(jí)考試二級(jí)公共根底學(xué)問考綱考試內(nèi)容一、 根本數(shù)據(jù)構(gòu)造與算法算法的根本概念；算法簡(jiǎn)單度的概念和意義〔時(shí)間簡(jiǎn)單度與空間簡(jiǎn)單度〕。念。線性表的定義；線性表的挨次存儲(chǔ)構(gòu)造及其插入與刪除運(yùn)算。棧和隊(duì)列的定義；棧和隊(duì)列的挨次存儲(chǔ)構(gòu)造及其根本運(yùn)算。線性單鏈表、雙向鏈表與循環(huán)鏈表的構(gòu)造及其根本運(yùn)算。樹的根本概念；二叉樹的定義及其存儲(chǔ)構(gòu)造；二叉樹的前序、中序和后序遍歷。挨次查找與二分法查找算法；根本排序算法〔交換類排序，選擇類排序，插入類排序〕 二、 程序設(shè)計(jì)根底程序設(shè)計(jì)方法與風(fēng)格。構(gòu)造化程序設(shè)計(jì)。面對(duì)對(duì)象的程序設(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、 軟件工程根底軟件工程根本概念，軟件生命周戎概念，軟件工具與軟件開發(fā)環(huán)境。構(gòu)造化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。構(gòu)造化設(shè)計(jì)方法，總體設(shè)計(jì)與具體設(shè)計(jì)。軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、 數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫的根本概念：數(shù)據(jù)庫，數(shù)據(jù)庫治理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。E-RE-R關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫標(biāo)準(zhǔn)化理論。數(shù)據(jù)庫設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、規(guī)律設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?？荚嚪绞紺〔VisualBASICVisualFoxProJava、Access、VisualC++〕的筆試局部合為一張?jiān)嚲?。公共根底局部占全卷?

30分。公共根底學(xué)問有 10道選擇算法的根本特征可行性由于算法的設(shè)計(jì)是為了在某一個(gè)特定的計(jì)算工具上解決某一個(gè)實(shí)際的問題而設(shè)計(jì)的，因此，它總是受到計(jì)算工具的限制，使執(zhí)行產(chǎn)生偏差。因此，在算法設(shè)計(jì)時(shí)，應(yīng)當(dāng)考慮到這一點(diǎn)。確定性算法的設(shè)計(jì)必需是每一個(gè)步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。例如，124xy即設(shè)計(jì)的算法是計(jì)算工具所能夠正常解決問題的過程。有窮性例如，在數(shù)學(xué)中的無窮級(jí)數(shù)，在計(jì)算機(jī)中只能求有限項(xiàng)，即計(jì)算的過程是有窮的。擁有足夠的情報(bào)算法的執(zhí)行與輸入的數(shù)據(jù)和供給的初始條件相關(guān)，不同的輸入或初始條件會(huì)有不同的輸出結(jié)果，供給準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。算法的根本要素一是數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的掌握構(gòu)造。算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法實(shí)際上是按解題要求從環(huán)境能進(jìn)展的全部操作中選擇適宜的操作所組成算法的掌握構(gòu)造算法的功能不僅取決于所選用的操作，而且還與各操作之間的挨次有關(guān)。在算法中，操在算法描述是，有相關(guān)的工具對(duì)這三種構(gòu)造進(jìn)展描述，常用的描述工具有：流程圖、N-S結(jié)構(gòu)圖和算法描述語言等。算法設(shè)計(jì)的根本方法為用計(jì)算機(jī)解決實(shí)際問題而設(shè)計(jì)的算法，即是計(jì)算機(jī)算法。通常的算法設(shè)計(jì)有如下幾種：列舉法例如，我國古代的趣味數(shù)學(xué)題：“百錢買百雞”、“雞兔同籠”等，均可承受列舉法進(jìn)展解決。使用列舉法時(shí)，要對(duì)問題進(jìn)展具體的分析，將與問題有關(guān)的學(xué)問條理化、完備化、系統(tǒng)化，從中找出規(guī)律。種抽象，即從特別現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不行能對(duì)全部的狀況進(jìn)展列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)展證明。遞推身已經(jīng)給定，或是通過對(duì)問題的分析與化簡(jiǎn)而確定。遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。例如，裴波那契數(shù)列，是承受遞推的方法解決問題的。兩種方法。假設(shè)一個(gè)算法直接調(diào)用自己，稱為直接遞歸調(diào)用；假設(shè)一個(gè)算法A調(diào)用另一個(gè)算法B，而算法BA，減半遞推技術(shù)減半遞推馬上問題的規(guī)模減半，然后，重復(fù)一樣的遞推操作。例如，一元二次方程的求解?；厮莘ㄓ行?shí)際的問題很難歸納出一組簡(jiǎn)潔的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對(duì)于這類問題，只能承受摸索的方法，通過對(duì)問題的分析，找出解決問題的線索，然后沿著這個(gè)線索進(jìn)展摸索，假設(shè)摸索成功，就得到問題的解，假設(shè)不成功，再逐步回退，換別的路線進(jìn)展摸索。這種方法，即稱為回溯法。如人工智能中的機(jī)器人下棋。2時(shí)間簡(jiǎn)單度即實(shí)現(xiàn)該算法需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的根本運(yùn)算次數(shù)來計(jì)算。同一個(gè)問題規(guī)模下，假設(shè)算法執(zhí)行所需要的根本次數(shù)取決于某一特定輸入時(shí)，種方法來分析算法的工作量：

可以用以下兩算法工作量=f〔n〕〔1〕平均性態(tài)用各種特定輸入下的根本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。設(shè)x是某個(gè)可能輸入中的某個(gè)特定輸入， p〔x〕是x消滅的概率，t〔x〕是算法在輸入為x時(shí)所執(zhí)行的根本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為：Dnn〔2〕最壞狀況簡(jiǎn)單度n平均性態(tài)：即該數(shù)在數(shù)列中任何位置消滅的數(shù)列是一樣的，也有可能不存在，存在的概率為 假設(shè)有一半的時(shí)機(jī)存在，則概率 q為1/2,平均性態(tài)：假設(shè)查找的元素肯定在數(shù)列中，則每個(gè)數(shù)存在的概率即為 1，則平均性態(tài)為：最壞狀況分析：即要查找的元素度為：算法的空間簡(jiǎn)單度指要執(zhí)行該算法所需要的內(nèi)存空間。

X在數(shù)列的最終或不在數(shù)列中，明顯，它的最壞狀況簡(jiǎn)單算法所占用的內(nèi)存空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間，以及某種數(shù)據(jù)構(gòu)造所需要的附加存儲(chǔ)空間等?！捕硵?shù)據(jù)構(gòu)造的根本概念?概念數(shù)據(jù)構(gòu)造是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。它包括以下兩個(gè)方面：表示數(shù)據(jù)元素的信息表示各數(shù)據(jù)之間的前后件關(guān)系1〕數(shù)據(jù)的規(guī)律構(gòu)造是指反映數(shù)據(jù)元素之間的規(guī)律關(guān)系的數(shù)據(jù)構(gòu)造。數(shù)據(jù)的規(guī)律構(gòu)造有兩個(gè)要素：D

如執(zhí)行過程中工作單元數(shù)據(jù)之間的前后件關(guān)系，記作 則數(shù)據(jù)構(gòu)造B=〔D,R〕2〕數(shù)據(jù)的規(guī)律構(gòu)造在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)構(gòu)造，或數(shù)據(jù)的物理構(gòu)造。即數(shù)據(jù)存儲(chǔ)時(shí)，不僅要存放數(shù)據(jù)元素的信息，而且要存儲(chǔ)數(shù)據(jù)元素之間的前后件關(guān)系的信息。通常的數(shù)據(jù)存儲(chǔ)構(gòu)造有挨次、鏈接、索引等存儲(chǔ)構(gòu)造。?數(shù)據(jù)構(gòu)造的圖形表示數(shù)據(jù)構(gòu)造的圖形表示有兩個(gè)元素：中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，稱為數(shù)據(jù)結(jié)點(diǎn)用有向線段表示數(shù)據(jù)元素之間的前后件關(guān)系，即有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)留意：在構(gòu)造圖中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，結(jié)點(diǎn)。?線性構(gòu)造與非線性構(gòu)造

沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)， 也稱葉子假設(shè)一個(gè)非空的數(shù)據(jù)構(gòu)造滿足如下條件，則該數(shù)據(jù)構(gòu)造為線性構(gòu)造：有且只有一個(gè)根結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，也最多只有一個(gè)后件線性構(gòu)造又稱線性表。留意：在線性構(gòu)造表中插入或刪除元素，該線性表仍舊應(yīng)滿足線性構(gòu)造。假設(shè)一個(gè)數(shù)據(jù)構(gòu)造不滿足線性構(gòu)造，則稱為非線性構(gòu)造?！踩尘€性表及其挨次存儲(chǔ)構(gòu)造根本概念線性表是最常用的數(shù)據(jù)構(gòu)造，它由一組數(shù)據(jù)元素組成。留意：這里的數(shù)據(jù)元素是一個(gè)廣義的數(shù)據(jù)元素，并不僅僅是指一個(gè)數(shù)據(jù)。如，矩陣、學(xué)生記錄表等。非空線性表的構(gòu)造特征：有且只有一個(gè)根結(jié)點(diǎn)，它無前件有且只有一個(gè)終端結(jié)點(diǎn)，它無后件除根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，全部的結(jié)點(diǎn)有且只有一個(gè)前件和一個(gè)后件。個(gè)數(shù)稱為結(jié)點(diǎn)的長(zhǎng)度n。當(dāng)n=0?挨次存儲(chǔ)構(gòu)造挨次存儲(chǔ)構(gòu)造的特點(diǎn)：線性表中全部的元素所占的存儲(chǔ)空間是連續(xù)的線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按規(guī)律挨次依次存放的

線性表中結(jié)點(diǎn)的通常，挨次存儲(chǔ)構(gòu)造中，線性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線性表中的位置序號(hào)唯一確定。線性表的挨次存儲(chǔ)構(gòu)造下的根本運(yùn)算：在指定位置插入一個(gè)元素刪除線性表中的指定元素查找某個(gè)或某些特定的元素線性表的排序按要求將一個(gè)線性表拆分為多個(gè)線性表將多個(gè)線性表合并為一個(gè)線性表復(fù)制線性表逆轉(zhuǎn)一個(gè)線性表?線性表的根本操作挨次表的插入運(yùn)算在挨次存儲(chǔ)構(gòu)造的線性表中插入一個(gè)元素。留意：找到插入位置后，將插入位置開頭的全部元素從最終一個(gè)元素開頭挨次后移。另外，在定義線性表時(shí)，肯定要定義足夠的空間，否則，將不允許插入元素。挨次表的刪除運(yùn)算在挨次在存儲(chǔ)構(gòu)造的線性表中刪除一個(gè)元素。留意：找到刪除的數(shù)據(jù)元素后，從該元素位置開頭，將后面的元素一一向前移動(dòng)，1

在移動(dòng)完?棧及其根本運(yùn)算棧棧是一種特別的線性表，它是限定在一端進(jìn)展插入和刪除的線性表。表的一端進(jìn)展，而另一端是封閉的，不允許進(jìn)展插入和刪除操作。

它的插入和刪除只能在在棧中，允許插入和刪除操作一端稱為棧頂， 不允許插入和刪除操作的一端則稱為棧底。 棧頂?shù)脑乜偸亲罱K被插入的元素，進(jìn)先出。堆棧指針總是指向棧頂元素的。棧的挨次存儲(chǔ)及其運(yùn)算

也是最先被刪除的元素。

它遵循的原則是：先進(jìn)后出或后在棧的挨次存儲(chǔ)空間S(1:m)中，S(bottom)通常為棧底元素，S(top)為棧頂元素。Top=0top=m1〕入棧運(yùn)算即在棧的頂部插入一個(gè)元素。操作方式是：將棧頂指針加 1，再將元素插入至指針?biāo)傅?〕退1。3〕隊(duì)列及其根本運(yùn)算隊(duì)列隊(duì)列即是允許在一端進(jìn)展插入，而在另一端進(jìn)展刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一隊(duì)列遵循的規(guī)章是：先進(jìn)先出或后進(jìn)后出循環(huán)隊(duì)列及其運(yùn)算隊(duì)列的挨次存儲(chǔ)構(gòu)造一般承受循環(huán)隊(duì)列的形式。循環(huán)隊(duì)列，即是次隊(duì)列存儲(chǔ)空間的最終一個(gè)位置繞到第一個(gè)位置，形成規(guī)律上的環(huán)狀空間，供隊(duì)列循環(huán)使用。rearfront因此，從排頭指針front指向的后一個(gè)位置到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。rear=front=mm算和退隊(duì)運(yùn)算。入隊(duì)運(yùn)算：每進(jìn)展一次入隊(duì)運(yùn)算，隊(duì)尾指針加 1。當(dāng)隊(duì)尾指針rear=m+1時(shí)，即表示隊(duì)列空間的尾部已經(jīng)放置了元素，則下一個(gè)元素應(yīng)當(dāng)旋轉(zhuǎn)到隊(duì)列空間的首部，即rear=1退隊(duì)運(yùn)算：每退隊(duì)一個(gè)元素，排頭指針加 1。當(dāng)排頭指針front=m+1時(shí)，即排頭指針指向隊(duì)front=1front=rearrear=front要推斷隊(duì)列空或滿時(shí)，還應(yīng)增加一個(gè)標(biāo)志，定義：推斷隊(duì)列空與隊(duì)列滿的條件下：s=0s=1front=rear〔1〕1，即rear=rear+1rear=m+1rear=1當(dāng)循環(huán)隊(duì)列非空〔s=1〕,且front=rear時(shí)，隊(duì)列滿，不能進(jìn)展入隊(duì)操作。此狀況稱“上溢”

s。front=front+1front=m+1front=1當(dāng)循環(huán)隊(duì)列為空〔s=0〕時(shí)，不能進(jìn)展退隊(duì)運(yùn)算。此種狀況稱為“下溢” 。1前面的線性表均是承受挨次存儲(chǔ)構(gòu)造及在挨次存儲(chǔ)構(gòu)造下的運(yùn)算。1〕2〕要在挨次存儲(chǔ)的線性表中插入一個(gè)元素或刪除一個(gè)元素時(shí)， 線性表仍舊為挨次存儲(chǔ)。在插入或刪除元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)元素，因此運(yùn)算效率較低。假設(shè)一個(gè)線性表安排挨次存儲(chǔ)空間后，元素時(shí)，會(huì)發(fā)生“上溢”錯(cuò)誤。

假設(shè)消滅線性表的存儲(chǔ)空間已滿， 但還需要插入在實(shí)際應(yīng)用時(shí)，可能有多個(gè)線性表同時(shí)使用存儲(chǔ)空間，有可能使有的隊(duì)列空間不夠或過多造成鋪張。

這樣給存儲(chǔ)空間的安排帶來問題，基于上述狀況，對(duì)于大的線性表或元素變動(dòng)頻繁的大線性表不宜承受挨次存儲(chǔ)構(gòu)造， 而應(yīng)采3〕假設(shè)每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)存儲(chǔ)單元，該存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)方式中，要求每一個(gè)結(jié)點(diǎn)由兩局部組成： 據(jù)元素，你為數(shù)據(jù)域；另一局部用于存放指針，稱為指針域。該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，存儲(chǔ)數(shù)據(jù)構(gòu)造的存儲(chǔ)空間可以不連續(xù)， 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)挨次與數(shù)據(jù)元素之間的規(guī)律關(guān)系不全都，而數(shù)據(jù)元素之間的規(guī)律關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)構(gòu)造既可以用于線性構(gòu)造，也可用于非線性構(gòu)造。4〕線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱為線性鏈表。將存儲(chǔ)空間劃分成假設(shè)干的小塊，每塊占用假設(shè)干個(gè)字節(jié)，這些小塊稱為存儲(chǔ)結(jié)點(diǎn)。將存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)局部，一局部用于存儲(chǔ)數(shù)據(jù)元素的值， 稱為數(shù)據(jù)域；另一局部用于存儲(chǔ)元素之間的前后件關(guān)系，即存放下一個(gè)元素在存儲(chǔ)序號(hào)〔即存儲(chǔ)地址〕稱為指針域。

，即指向后件結(jié)點(diǎn)，在線性鏈表中用一個(gè)特地的指針 HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)〔即存放第一個(gè)元素的地址〕。線性表中最終一個(gè)元素沒有后件，因此，線性鏈表中的最終一個(gè)結(jié)點(diǎn)的指針域?yàn)榭铡灿肗ull0〕，表示鏈終結(jié)。在線性鏈表中，各元素的存儲(chǔ)序號(hào)是不連續(xù)的， 元素間的前后件關(guān)系與位置關(guān)系也是不全都的。在線性鏈表中，前后件的關(guān)系依靠各結(jié)點(diǎn)的指針來指示，指向表的第一個(gè)元素的指針HEADHEAD=NULL時(shí)，表示該鏈表為空。對(duì)于線性鏈表，可以從頭指針開頭，沿著各結(jié)點(diǎn)的指針掃描到鏈表中的全部結(jié)點(diǎn)。這種線性鏈表稱為線性單鏈表， 即可以從表頭開頭向后掃描鏈表中的全部結(jié)點(diǎn)， 間或表尾結(jié)點(diǎn)向前掃描位于該結(jié)點(diǎn)之前的元素。這種鏈表構(gòu)造的缺點(diǎn)是不能任意地對(duì)鏈表中的元素按下同的方向進(jìn)展掃描。在某些應(yīng)用時(shí)，假設(shè)對(duì)鏈表中的元素設(shè)置兩個(gè)指針域，一個(gè)為指向前件的指針域， 稱為左指針〔LLink〕，—個(gè)為指向后件的指針域，稱為右指針〔5〕

RLink〕。則這種鏈表是雙向鏈表。帶鏈的棧即是用來收集計(jì)算機(jī)存儲(chǔ)空間中的全部空閑的存儲(chǔ)結(jié)點(diǎn)，棧。

這種帶鏈的棧稱為可利用當(dāng)需要存儲(chǔ)結(jié)點(diǎn)時(shí)，即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)；當(dāng)系統(tǒng)要釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)時(shí)，將該結(jié)點(diǎn)空間放回到可利用棧的棧頂。即在計(jì)算機(jī)中全部空閑的空間， 均可以以結(jié)點(diǎn)的方式鏈接到可利用棧中， 中結(jié)點(diǎn)的插入與刪除，可利用棧處于動(dòng)態(tài)變化之中，即可利用棧常常要進(jìn)展退棧和入棧操作。6)隊(duì)列也是線性表，也可利用鏈?zhǔn)酱鎯?chǔ)構(gòu)造來進(jìn)展保存。?線性鏈表的根本運(yùn)算線性鏈表包括的根本運(yùn)算：在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)元素在鏈表中刪除包含指定元素的結(jié)點(diǎn)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表將一個(gè)線性鏈表按要求進(jìn)展分解逆轉(zhuǎn)線性鏈表復(fù)制線性鏈表線性鏈表的查找線性鏈表中查找指定的元素X結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閄

直到后面已沒有元素的查找，常常是為了進(jìn)展插入或刪除操作而進(jìn)展的，下該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。線性鏈表的插入線性鏈表的插入即在鏈?zhǔn)酱鎯?chǔ)構(gòu)造的線性表中插入一個(gè)元素。在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入元素b,插入過程：

因此，在查找時(shí)，往往是需要記錄從可利用棧中取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p,即取得的結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量p中。并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲。(2)元素x的前一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為(3)體的操作：首先，使結(jié)點(diǎn)后件結(jié)點(diǎn))，然后，使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p。

q。將結(jié)點(diǎn)p插入到結(jié)點(diǎn)qp插入到結(jié)點(diǎn)q之后(即結(jié)點(diǎn)q線性鏈表的插入操作，結(jié)點(diǎn)是為來自于可利用棧，因此不會(huì)造成線性表的溢出。 同樣，由于可利用?？杀欢鄠€(gè)線性表利用，儲(chǔ)空間。線性鏈表的刪除

因此，不會(huì)造成存儲(chǔ)空間的鋪張，大家動(dòng)態(tài)地共同使用存線性鏈表的刪除，即是在鏈?zhǔn)酱鎯?chǔ)構(gòu)造下的線性表中刪除指定元素的結(jié)點(diǎn)。操作方式：(1)在線性表中找到包含指定元素x的前一個(gè)結(jié)點(diǎn)p(2)將該結(jié)點(diǎn)p后的包含元素x的結(jié)點(diǎn)從線性鏈表中刪除，然后將被刪除結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)q的地址供給應(yīng)ppq。(3存儲(chǔ)的線性表所不能實(shí)現(xiàn)的。同時(shí)，此操作還可更有效地利用計(jì)算機(jī)的存儲(chǔ)空間。

這是挨次?循環(huán)鏈表及其根本操作在線性鏈表中，雖然對(duì)數(shù)據(jù)元素的插入和刪除操作比較簡(jiǎn)潔，需要單獨(dú)處理，使得空表與非空表的處理不全都。循環(huán)鏈表，即是承受另一種鏈接方式，它的特點(diǎn)如下：

但由于它對(duì)第一個(gè)結(jié)點(diǎn)和空表在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛞罁?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。(2)循環(huán)鏈表中最終一個(gè)結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成一個(gè)環(huán)狀鏈。在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置， 均可以從它開頭掃描到全部的結(jié)點(diǎn)， 而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能依據(jù)指針的方向進(jìn)展掃描。循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，的運(yùn)算相統(tǒng)一。樹的根本概念

因此，在任何時(shí)候都至少有一個(gè)結(jié)點(diǎn)， 因此空表與非空表樹是一種簡(jiǎn)潔的非線性構(gòu)造。在樹構(gòu)造中，數(shù)據(jù)元素之間有著明顯的層次構(gòu)造。表示中，用直線連接兩端的結(jié)點(diǎn)，上端點(diǎn)為前件，下端點(diǎn)為后件。

在樹的圖形在樹構(gòu)造中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。女口沒有父結(jié)點(diǎn)的結(jié)點(diǎn)只有一個(gè)，稱為根結(jié)點(diǎn)。如上圖所示，結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們均稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。如結(jié)點(diǎn)結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)，稱為葉子結(jié)點(diǎn)。上圖中，葉子結(jié)點(diǎn)有：

A即為結(jié)點(diǎn)B、C、D的父結(jié)點(diǎn)。AG、H、丨是結(jié)點(diǎn)DJ、M、N、L、C、G、H、I。在樹構(gòu)造中，一個(gè)結(jié)點(diǎn)所擁有的后件結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的度。例如，結(jié)點(diǎn)點(diǎn)E的度為1等，按此原則，全部葉子結(jié)點(diǎn)的度均為 0。在樹中，全部結(jié)點(diǎn)中最大的度稱為該樹的度。上圖所示的樹中，全部結(jié)點(diǎn)中最大的度是3。

D3,結(jié)3,樹分層，根結(jié)點(diǎn)為第一層，往下依次類推。同一層結(jié)點(diǎn)的全部子結(jié)點(diǎn)均在下一層。如上圖：A結(jié)點(diǎn)在第1層，B、C、D結(jié)點(diǎn)在第2層；E、F、G、H、丨在第3層；J、K、L在第4層；M、N在第5層。樹的最大層次稱為樹的深度。上圖樹的深度為 5。在樹中，某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱作該結(jié)點(diǎn)的子樹。葉子結(jié)點(diǎn)沒有子樹。在計(jì)算機(jī)中，可以用樹來表示算術(shù)表達(dá)式。原則如下：(1運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹(在樹中的挨次為從左到右)運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)樹在計(jì)算機(jī)中用多重鏈表表示。多重鏈表中的每個(gè)結(jié)點(diǎn)描述了樹中對(duì)應(yīng)結(jié)點(diǎn)的信息，結(jié)點(diǎn)中的鏈域(即指針域)個(gè)數(shù)將隨著樹中該結(jié)點(diǎn)的度而定義。假設(shè)在樹中，每一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的個(gè)數(shù)不一樣， 因此在多重鏈中各結(jié)點(diǎn)的鏈域個(gè)數(shù)也不相

而每個(gè)同，會(huì)導(dǎo)致算法太簡(jiǎn)單。因此，在樹中，常承受定長(zhǎng)結(jié)點(diǎn)來表示樹中的每一個(gè)結(jié)點(diǎn)，即取樹的度作為每個(gè)結(jié)點(diǎn)二叉樹及其根本性質(zhì)1)二叉樹的特點(diǎn)：非空二叉樹只有一個(gè)根結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)，別稱為左子樹和右子樹在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為為二叉樹。

治理相對(duì)簡(jiǎn)化了，但會(huì)造成空間的鋪張， 由于有許且結(jié)點(diǎn)分左右。則一個(gè)結(jié)點(diǎn)最多可以有兩棵子樹， 2,即二叉樹的度為2。在二叉樹中，任何的子樹也均2)二叉樹的性質(zhì)1在二叉樹的第k2k-1(k>1)個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為m2m-1性質(zhì)3：在任意一棵二叉樹中，度為 0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)多一個(gè)。4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[Iog2n]+1,其中[Iog2n]表示Iog2n的整數(shù)部分。3)1滿二叉樹的特點(diǎn)：k2k-12)完全二叉樹m、且有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為1n

m的滿二叉樹中編號(hào)從的最大層次為完全二叉樹具有的性質(zhì)：

p，則其分支下的子孫結(jié)點(diǎn)的最大層次為 p或p+1。5：n[Iog2n]+1性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。假設(shè)從根結(jié)點(diǎn)開頭，按層次(每一層從左到右)用自然數(shù)1、2.....、n給結(jié)點(diǎn)編號(hào)，對(duì)于編號(hào)為 k(k=1,2,n)的結(jié)點(diǎn)有如下結(jié)論：①假設(shè)k=1k>1INT(k/2)②假設(shè)2k<n,則編號(hào)為k2k;否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)(固然也沒有右子結(jié)點(diǎn))③假設(shè)2k+1<n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。3．二叉樹的存儲(chǔ)構(gòu)造二叉樹的存儲(chǔ)常承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造。該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址,稱為右指針域。存儲(chǔ)構(gòu)造如下：LchiIdVaIueRchiIdiL(i)V(i)R(i)即二叉樹的存儲(chǔ)構(gòu)造中每一個(gè)存儲(chǔ)結(jié)點(diǎn)都有兩個(gè)指針域, 因此,二叉樹的鏈?zhǔn)酱鎯?chǔ)構(gòu)造也稱為二叉樹的鏈表。在二叉樹在存儲(chǔ)中,用一個(gè)頭指針指向二叉樹的根結(jié)點(diǎn)的存儲(chǔ)地址。BT56BT56789101112131415iL(iV(i)R(i))12A324B536C748D910E1112F1314G1516H1718I00J00K000LM00160P 0170Q0180R00 N00 0 N00 O0

也可承受挨次存儲(chǔ)的方式，但挨次存儲(chǔ)的方式不適4.二叉樹的遍歷二叉樹的遍歷即是不重復(fù)地訪問二叉樹的全部結(jié)點(diǎn)。在遍歷二叉樹時(shí)，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。前序遍歷

二叉樹的前序遍歷即先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最終遍歷右子樹。在遍歷左子樹和遍歷右子樹時(shí)，照舊是先遍歷根結(jié)點(diǎn)，然后是左子樹，再是右子樹。操作的具體方式：假設(shè)二叉樹為空，則完畢返回。否則：訪問根結(jié)點(diǎn) 前序遍歷左子樹前序遍歷右子樹如上圖所示的完全二叉樹，它的前序遍歷結(jié)果是：C、F、L、M、G、N、O中序遍歷

A、B、D、H、P、Q、I、R、E、J、K、中序遍歷，即先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最終是遍歷右子樹。具體的操作方式：假設(shè)二叉樹為空，則完畢返回。否則：中序遍歷左子樹 訪問根結(jié)點(diǎn) 這里強(qiáng)調(diào)，在遍歷左子樹和右子樹時(shí)，仍舊要承受中序遍歷的方法。如上圖所示的完全二叉樹，它的中序遍歷結(jié)果是：L、F、M、C、N、G、O后序遍歷

P、H、Q、D、R、I、B、J、E、K、A、后序遍歷，即選遍歷左子樹，然后是遍歷右子樹，最終訪問根結(jié)點(diǎn)。具體的操作方式：假設(shè)二叉樹為空，則完畢返回。否則：前序遍歷左子樹 前序遍歷右子樹 訪問根結(jié)點(diǎn)如上圖所示的完全二叉樹，它的后序遍歷結(jié)果是：M、F、N、0、G、C、A〔七〕查找技術(shù)查找即是指在一個(gè)給定的數(shù)據(jù)構(gòu)造中查找某個(gè)指定的元素。

P、Q、H、R、丨、D、J、K、E、B、L、1挨次查找又稱挨次搜尋。一般是在線性表中查找指定的元素。根本操作方法是：從線性表的第一個(gè)元素開頭，與被查元素進(jìn)展比較，相等則查找成功，否則連續(xù)向后查找。假設(shè)全部的元素均查找完畢后都不相等，則該元素在指定的線性表中不存在。對(duì)于線性表而言，挨次查找效率很低。但對(duì)于以下的線性表，也只能承受挨次查找的方法：線性表為無序表，即表中的元素沒有排列不是按大小挨次進(jìn)展排列的，它的存儲(chǔ)方式是挨次存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都只能按挨次查找方式進(jìn)展查找

這類線性表不管即使是有序線性表，假設(shè)承受鏈?zhǔn)酱鎯?chǔ)，也只能承受挨次查找方式例如，現(xiàn)有線性表：7、2、1、5、9、465查找計(jì)次n=167n=2,62n=3,61n=4,65n=5,69n=6,64n=7,超出線性表的長(zhǎng)度，查找完畢，則該表中不存在要查找的元素。2.二分查找二分查找只適用于挨次存儲(chǔ)的有序表。此處所述的有序表是指線性中的元素按值非遞減排列〔即由小到大，但允許相鄰元素值相等〕 二分查找的方法如下：將要查找的元素與有序序列的中間元素進(jìn)展比較：假設(shè)該元素比中間元素大，則連續(xù)在線性表的后半局部〔中間項(xiàng)以后的局部〕進(jìn)展查找假設(shè)要查找的元素的值比中間元素的值小，局部〕進(jìn)展查找

則連續(xù)在線性表的前半局部 〔中間項(xiàng)以前的這個(gè)查找過程始終按一樣的挨次進(jìn)展下去，始終到查找成功或子表長(zhǎng)度為沒有要查找的元素〕有序線性表的二分法查找，條件是必需這個(gè)有序線性表的存儲(chǔ)方式是挨次存儲(chǔ)的。

0〔說明線性表中它的查找效率比挨次查找要高得多，它的最壞狀況的查找次數(shù)是查找次數(shù)是n固然，二分查找的方法也支持挨次存儲(chǔ)的遞減序列的線性表。

Iog2n次，而挨次查找的最壞狀況的有非遞減有序線性表：1、2、4、5、7、9，要查找元素6。查找的方法是：序列長(zhǎng)度為n=6,m=[〔n+1〕/2]=3查找計(jì)次k=16與中間元素即元素4進(jìn)展比較，不等，6>4查找計(jì)次k=2，查找連續(xù)在后半局部進(jìn)展，后半局部子表的長(zhǎng)度為序號(hào)：m=3+[〔3+1〕/2]=5，將元素與后半局部的中間項(xiàng)進(jìn)展比較，即第比較，不等，6<7

3，計(jì)算中間元素的57查找計(jì)次k=3，連續(xù)查找在后半局部序列的前半局部子序列中查找，子表長(zhǎng)度為 1,則中間項(xiàng)序號(hào)即為m=3+[〔1+1〕/2]=4450，則查找完畢〔八〕排序技術(shù)排序即是將一個(gè)無序的序列整理成按值非遞減挨次排列的有序序列。挨次存儲(chǔ)的線性表的排序操作。1交換類排序法，即是借助于數(shù)據(jù)元素之間的相互交換進(jìn)展排序的方法。

在這里，我們爭(zhēng)論的是1〕冒泡排序法冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線性表變成有序序列的操作方法。操作過程如下：從表頭開頭掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小， 假設(shè)相鄰兩個(gè)元素中前一個(gè)元素的值比后一個(gè)元素的值大，序列中最大的元素被放置到序列的最終。

將兩個(gè)元素位置進(jìn)展交換，

再連續(xù)對(duì)序列從頭進(jìn)展掃描，這一次掃描的長(zhǎng)度是序列長(zhǎng)度減 就位了，承受與前一樣的方法，兩兩之間進(jìn)展比較，將次大數(shù)移到子序列的末尾。按一樣的方法連續(xù)掃描，每次掃描的子序列的長(zhǎng)度均比上一次減1例如，有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)展排列。

1,直至子序列的長(zhǎng)度承受冒泡排序法，具體操作步驟如下：承受冒泡排序法，具體操作步驟如下：序列長(zhǎng)度n=7529451第一遍〔從前往后〕726941762594225344911197776662549第一遍完畢后其次遍〔從前往后〕12754■1674996915217176922447241567669第四遍〔從前往后〕n匕1456791245679掃描的次數(shù)，最多需要掃描n-1次，其次遍完畢后2415679第三遍〔從前往后〕24156792 1 456792145679第四遍完畢1245679最終結(jié)果1245679可設(shè)置一個(gè)標(biāo)志，假設(shè)該次掃描沒有數(shù)據(jù)交換，則說明數(shù)據(jù)排序完畢。2〕快速排序法冒泡排序方法每次交換只能轉(zhuǎn)變相鄰兩個(gè)元素之間的逆序，鄰的元素之間進(jìn)展交換，可以消退多個(gè)逆序。快速排序的方法是：

速度相對(duì)較慢。假設(shè)將兩個(gè)不相從線性表中選取一個(gè)元素，設(shè)為 T,將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果將線性表分成兩個(gè)局部〔稱為兩個(gè)子表〕處，這個(gè)過程稱為線性表的分割。對(duì)過對(duì)線性表的一次分割，就以

，T插入到其分界限的位置T為分界限，將線性表分成前后兩個(gè)子表，且前面子表中的全部元素均不大于 T,而后面的全部元素均不小于T。再將前后兩個(gè)子表再進(jìn)展一樣的快速排序，完成快速排序操作。

在快速排序過程中，隨著對(duì)各子表不斷的進(jìn)展分割， 越來越多，但一次又只能對(duì)一個(gè)子表進(jìn)展分割處理，需要將臨時(shí)不用的子表記憶起來，這里可用棧來實(shí)現(xiàn)。對(duì)某個(gè)子表進(jìn)展分割后，可以將分割出的后一個(gè)子表的第一個(gè)元素與最終一個(gè)元素的位置壓入棧中，而連續(xù)對(duì)前一個(gè)子表進(jìn)展再分割；表進(jìn)展分割。

當(dāng)分割出的子表為空時(shí)，可以從棧中退出一個(gè)子這個(gè)過程直到棧為空為止，說明全部子表為空，沒有子表再需分割，排序就完成。2簡(jiǎn)潔插入排序插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。插入排序操作的思路：在線性表中， 只包含第1個(gè)元素的子表，作為該有序表。從線性表的第2個(gè)元素開頭直到最終一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面的有序的子表中。該方法與冒泡排序方法的效率一樣，最壞的狀況下需要 n〔n-1〕/2次比較。例如，有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)展排列。承受簡(jiǎn)潔插入排序法，具體操作步驟如下：序列長(zhǎng)度 n=76j-&6

j-72〕希爾排序法希爾排序法的根本思想：

4 5 6 7 9將整個(gè)無序序列分割成假設(shè)干小的子序列分另燉行插入排序。子序列的分割方法： 將相隔某個(gè)增量h的兀素構(gòu)成一個(gè)子序列，在排序的過程中，逐次減小這個(gè)增量，最終當(dāng)h減小到1時(shí)，再進(jìn)展一次插入排序操作，即完成排序。增量序列一般取ht=n/2k〔k=1,2,…,[log2n]〕，其中n為待排序序列的長(zhǎng)度。3．選擇類排序法1〕簡(jiǎn)潔選擇排序法根本思路：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)后面的子表承受一樣的方法，直到子表為空為止。例如，有序列5、29、1、例如，有序列5、29、1、7、6，將該序列從小到大進(jìn)展排列4、承受簡(jiǎn)潔選擇排序法，具體操作步驟如下：原序列5第一遍掃描第三遍掃描第五遍掃描第六遍掃描排序結(jié)果2941761294576129457612495761245976124567912456791245679堆的定義：具有n個(gè)元素的序列〔h1,h2,…,hn〕,當(dāng)且僅當(dāng)滿足〔1=1,2，…,n/2〕時(shí)稱之為堆。本節(jié)只爭(zhēng)論滿足前者條件的堆。由堆的定義看，堆頂元素〔即第一個(gè)元素〕必為最大項(xiàng)?？梢杂靡痪S數(shù)組或完全二叉樹來表示堆的構(gòu)造。用完全二叉樹表示堆時(shí)，樹中全部非葉子結(jié)點(diǎn)值均不小于其左右子樹的根結(jié)點(diǎn)的值，因此堆頂〔完全二叉樹的根結(jié)點(diǎn)〕元素必需為序列的 n個(gè)元素中的最大項(xiàng)。例如，有序列5、2、9、4、1、7、6，將該序列從小到大進(jìn)展排列。利用堆排序法將該序列進(jìn)展排序。操作方式即：先將無序堆的根結(jié)點(diǎn)5與左右子樹的根結(jié)點(diǎn)2、9進(jìn)展比較，5<9，將5與9進(jìn)展交換；整后，對(duì)左右子樹進(jìn)展堆調(diào)整，左子樹的根結(jié)點(diǎn) 2小于其左葉子結(jié)點(diǎn)5，調(diào)整；右子樹的根結(jié)點(diǎn)5小于其左右子結(jié)點(diǎn)7和6，依據(jù)堆的要求，將5與7依據(jù)堆的定義，可以得到堆排序的方法：〔1〕首先將一個(gè)無序序列建成堆〔2〕然后將堆頂元素〔序列中的最大項(xiàng)〕與堆中最終一個(gè)元素交換〔最大項(xiàng)應(yīng)當(dāng)在序列的最終〕。三、本章應(yīng)考點(diǎn)撥5-610一、內(nèi)容要點(diǎn)〔一〕程序設(shè)計(jì)方法與風(fēng)格程序設(shè)計(jì)方法：主要經(jīng)過了面對(duì)過程的構(gòu)造化程序設(shè)計(jì)和面對(duì)對(duì)象的程序設(shè)計(jì)方強(qiáng)調(diào)簡(jiǎn)潔和清楚，必需是可以讀的，可以理解的。要形成良好的程序設(shè)計(jì)的風(fēng)格，應(yīng)考慮如下因素：1．源程序文檔化符號(hào)名的命名：符號(hào)名的命名要具有肯定的實(shí)際含義，便于對(duì)程序的理解，即通常說的見名思義；程序注釋：正確的程序注釋能夠幫助他人理解程序。注釋一般包括序言性注釋和功能性注釋；視覺組織：為了使程序一目了然，可以對(duì)程序的格式進(jìn)展設(shè)置，適當(dāng)?shù)赝ㄟ^空格、空行、縮進(jìn)等使程序?qū)哟吻宄?．?dāng)?shù)據(jù)說明方法數(shù)據(jù)說明的次序標(biāo)準(zhǔn)化；說明語句中變量安排有序化；使用注釋來說明簡(jiǎn)單的數(shù)據(jù)構(gòu)造。3．語句的構(gòu)造在一行內(nèi)只寫一條語句；程序的編寫應(yīng)當(dāng)優(yōu)先考慮清楚性；除非對(duì)效率有特別的要求，否則，應(yīng)做到清楚第一，效率其次；首先保證程序的正確，然后再要求速度；避開使用臨時(shí)變量使程序的可讀性下降；盡量使用庫函數(shù)，即盡量使用系統(tǒng)供給的資源；避開承受簡(jiǎn)單的條件語句；盡量削減使用“否認(rèn)”條件的條件語句；數(shù)據(jù)構(gòu)造要有利于程序的簡(jiǎn)化；要模塊化，使模塊功能盡可能單一化；利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性；從數(shù)據(jù)動(dòng)身去構(gòu)造程序；不要修補(bǔ)不好的程序，要重編寫。4．輸入和輸出對(duì)全部的輸入輸出數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性；檢查輸入項(xiàng)的各種重要組合的合理性；輸入格式要簡(jiǎn)潔，以使得輸入的步驟和操作盡可能簡(jiǎn)潔；輸入數(shù)據(jù)時(shí)，應(yīng)允許自由格式；應(yīng)允許缺省值；輸入一批數(shù)據(jù)時(shí)，最好使用輸入完畢標(biāo)志；以交互式輸入輸出方式進(jìn)展輸入時(shí)，要在屏幕上使用提示符明確輸入的懇求，同時(shí)在數(shù)據(jù)輸入過程中和輸入完畢時(shí)，應(yīng)在屏幕上給出狀態(tài)信息；當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的全都性；給全部的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式?！捕硺?gòu)造化程序設(shè)計(jì)1．構(gòu)造化程序設(shè)計(jì)的原則構(gòu)造化程序設(shè)計(jì)方法的主要原則：自頂而下、逐步求精，模塊化，限制使用goto語句。自頂而下程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局，后考慮局部目標(biāo)。即先從最上層總目標(biāo)開頭設(shè)計(jì)，逐步使問題具體化。逐步求精對(duì)簡(jiǎn)單問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作為過渡，逐步細(xì)化。模塊化gotogoto語句可以提高效率，但對(duì)程序的可讀性、維護(hù)性都造成影響，因此應(yīng)盡量不用goto語句。2．構(gòu)造化程序設(shè)計(jì)的根本構(gòu)造與特點(diǎn)構(gòu)造化程序設(shè)計(jì)是程序設(shè)計(jì)的先進(jìn)方法和工具，承受構(gòu)造化程序設(shè)計(jì)可以使挨次構(gòu)造挨次構(gòu)造即是挨次執(zhí)行的構(gòu)造，是依據(jù)程序語句行的自然挨次，一條一條語句地執(zhí)行程序。選擇構(gòu)造支來執(zhí)行。重復(fù)構(gòu)造重復(fù)構(gòu)造又稱循環(huán)構(gòu)造，依據(jù)給定的條件，打算是否重復(fù)執(zhí)行某一一樣的或類似的程序段。利用重復(fù)構(gòu)造可以大量簡(jiǎn)化程序行。3．構(gòu)造化程序設(shè)計(jì)原則和方法的應(yīng)用1．使用程序設(shè)計(jì)語言中的挨次、選擇、循環(huán)等有限的掌握構(gòu)造表示程序的掌握規(guī)律；2．選用的掌握構(gòu)造只允許有一個(gè)入口和一個(gè)出口；3．程序語句組成簡(jiǎn)潔識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口；4．簡(jiǎn)單構(gòu)造應(yīng)當(dāng)用嵌套的根本掌握構(gòu)造進(jìn)展組合嵌套來實(shí)現(xiàn)；5．語言中全部沒有的掌握構(gòu)造，應(yīng)當(dāng)承受前后全都的方法來模擬；6goto用一個(gè)非構(gòu)造化的程序設(shè)計(jì)語言去實(shí)現(xiàn)一個(gè)構(gòu)造化的構(gòu)造；goto在某種可以改善而不是損害程序可讀性的狀況下?！踩?．面對(duì)對(duì)象的優(yōu)點(diǎn)：與人類習(xí)慣的思維方法全都傳統(tǒng)的程序設(shè)計(jì)方法是以算法作為核心，將程序與過程相互獨(dú)立。面對(duì)對(duì)象方對(duì)象模擬問題領(lǐng)域中的實(shí)體，以對(duì)象間的聯(lián)系刻畫實(shí)體間的聯(lián)系。可重用性好軟件的重用性是指在不同的軟件開發(fā)過程中重復(fù)使用一樣或相像的軟件元素的過程。易于開發(fā)大型軟件產(chǎn)品在使用面對(duì)對(duì)象進(jìn)展軟件開發(fā)時(shí)，可以把大型產(chǎn)品看作是一系列本質(zhì)上相互獨(dú)立的可維護(hù)性好利用面對(duì)對(duì)象的方法開發(fā)的軟件穩(wěn)定性比較好用面對(duì)對(duì)象的方法開發(fā)的軟件比較簡(jiǎn)潔修改用面對(duì)對(duì)象的方法開發(fā)的軟件比較簡(jiǎn)潔理解2．面對(duì)對(duì)象方法的根本概念單位，它由一組表示其靜態(tài)特征的屬性和它執(zhí)行的一組操作組成。對(duì)象的根本特點(diǎn)：標(biāo)識(shí)的唯一性對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。封裝性從外面看只能看到對(duì)象的外部特征，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體構(gòu)造以及實(shí)現(xiàn)操作的算法。模塊獨(dú)立性好對(duì)象是面對(duì)對(duì)象的軟件的根本模塊，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)獨(dú)立性考慮，對(duì)象內(nèi)容各種元素彼此相結(jié)合得很嚴(yán)密，內(nèi)聚性強(qiáng)。類和實(shí)例將屬性、操作相像的對(duì)象歸為類。具有共同的屬性、共同的方法的對(duì)象的集合，即是類。類是對(duì)息，它統(tǒng)一了數(shù)據(jù)流和掌握流。消息只包含傳遞者的要求，它告知承受者需要做哪些處理，并不指示承受者怎樣去完成這些處理。4〕繼承繼承是使用已有的類定義作為根底建立類的定義技術(shù)。已有的類可當(dāng)作基類來引用，則類相應(yīng)地可作為派生類來引用。繼承即是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。5〕多態(tài)性對(duì)象依據(jù)所承受的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象承受時(shí)可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性。在面對(duì)對(duì)象技術(shù)中，多態(tài)性是指子類對(duì)象可以像父類對(duì)象那樣使用，同樣的消息可以發(fā)送給父類對(duì)象也可以發(fā)送給子類對(duì)象。多態(tài)性機(jī)制增加了面對(duì)對(duì)象軟件系統(tǒng)的敏捷性，

削減了信息冗余，而且顯著提高了軟件的可本章在考試中會(huì)消滅約12分，是出題量較小的一章。本章內(nèi)容比較少，也很簡(jiǎn)潔第三章軟件工程根底一、學(xué)習(xí)目標(biāo)與要求1.了解軟件工程的根本概念；2?了解軟件工程過程與軟件的生命周期，以及軟件工程的目標(biāo)和原則；3?了解利用構(gòu)造化分析法進(jìn)展軟件工程中的需求分析的方法，并了解需求分析的方法和需要完成的任務(wù)；4?了解數(shù)據(jù)流圖的使用方法；5?了解如何利用構(gòu)造化設(shè)計(jì)方法進(jìn)展軟件設(shè)計(jì)，并了解軟件設(shè)計(jì)的一些常用用工具；6?了解軟件測(cè)試的目的和方法，以及軟件測(cè)試的準(zhǔn)則，了解常用的軟件測(cè)試方法的區(qū)分和各自的功能與特點(diǎn)；7?了解程序調(diào)試的方法和原則。二、內(nèi)容要點(diǎn)軟件定義與軟件特點(diǎn)軟件的定義與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)章，以及可能有的文件、文檔及數(shù)據(jù)。軟件的特點(diǎn)軟件是一種規(guī)律實(shí)體，而不是物理實(shí)體，具有抽象性；(2軟件在運(yùn)行、使用期間不存在磨損、老化問題；但為了適應(yīng)硬件、環(huán)境以及需求的變化要進(jìn)展修改，會(huì)導(dǎo)致一些錯(cuò)誤的引入，導(dǎo)致軟件失效率上升，從而使得軟件退化；軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依靠性，受到計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；軟件簡(jiǎn)單性高，本錢昂貴。軟件開發(fā)需要投入大量、高強(qiáng)度的腦力勞動(dòng)，本錢高，風(fēng)險(xiǎn)大；(6制問題以及治理方式等，甚至涉及到人們的觀念和心理，軟件學(xué)問產(chǎn)權(quán)及法律等問題。軟件的分類按功能分，可分為：應(yīng)用軟件：為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件系統(tǒng)軟件：是計(jì)算機(jī)治理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶供給各種效勞的軟件支撐軟件(或工具軟件)：介于系統(tǒng)軟件和應(yīng)用軟件之間，幫助用戶開發(fā)軟件的工具性軟件，包括關(guān)心和支持開發(fā)和維護(hù)應(yīng)用軟件的工具軟件軟件危機(jī)與軟件工程軟件危機(jī)泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)峻問題。它主要表現(xiàn)在：軟件需求的增長(zhǎng)得不到滿足，用戶對(duì)系統(tǒng)不滿足的狀況常常發(fā)生；(2軟件質(zhì)量難以保證；軟件不行維護(hù)或維護(hù)程度格外低；軟件本錢不斷提高；軟件開發(fā)生產(chǎn)率的提高趕不上硬件的進(jìn)展和應(yīng)用需求的增長(zhǎng)。軟件工程軟件工程的定義：是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程包括3個(gè)要素：方法、工具和過程。方法：完成軟件工程工程的技術(shù)手段；工具：支持軟件的開發(fā)?軟件工程過程與軟件生命周期軟件工程過程軟件工程過程把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。內(nèi)涵：

支持軟件工程過程的兩方面軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動(dòng)。它包4P—軟件規(guī)格說明。規(guī)定軟件的功能及其運(yùn)行時(shí)的限制；D—軟件開發(fā)。產(chǎn)生滿足規(guī)格說明的軟件；C—軟件確認(rèn)。確認(rèn)軟件能夠滿足客戶提出的要求；A使用適當(dāng)?shù)馁Y源(包括人員、硬軟件工具、時(shí)間等)，為開發(fā)軟件進(jìn)展的一組開發(fā)活動(dòng)，在過程完畢時(shí)將輸入(用戶要求)轉(zhuǎn)化為輸出(軟件產(chǎn)品)。軟件工程過程是將軟件工程的方法和工具綜合起來，發(fā)的目的。軟件生命周期

以到達(dá)合理、準(zhǔn)時(shí)地進(jìn)展計(jì)算機(jī)軟件開將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停頓使用退役的過程稱為軟件生命周期。 即軟件的生命周期就是軟件產(chǎn)品從開頭考慮其概念開頭， 到軟件產(chǎn)品不能使用為止的整個(gè)時(shí)期都屬于軟件生命周期。一般包括可行性爭(zhēng)論與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。這些活動(dòng)可以有重復(fù)，執(zhí)行時(shí)也可以有迭代。軟件定義軟件維護(hù)軟件生命周期的主要活動(dòng)階段是：可行性爭(zhēng)論與打算制定：確定待開發(fā)軟件系統(tǒng)的開發(fā)目標(biāo)和總的要求，性能、牢靠性以及接口等方面的可能方案，制定完成開發(fā)任務(wù)的實(shí)話打算；(2

給出它的功能、(3)軟件設(shè)計(jì)。系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員給出軟件的構(gòu)造、模塊的劃分、功能的安排以及處理流程；(4)軟件實(shí)現(xiàn)。把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以承受的程序代碼。即完成源程序的編碼，編寫用戶手冊(cè)、操作手冊(cè)等面對(duì)用戶的文檔，編寫單元測(cè)試打算；(5)例的根底上，檢驗(yàn)軟件的各個(gè)組成局部，

軟件測(cè)試。在設(shè)計(jì)測(cè)試用編寫測(cè)試分析報(bào)告；(6)運(yùn)行和維護(hù)。將已交付的軟件投入運(yùn)行，并在運(yùn)行使用中不斷地維護(hù)，依據(jù)提出的需求進(jìn)展必要且可能的擴(kuò)大和刪改。?軟件工程的目標(biāo)與原則軟件工程的目標(biāo)軟件工程的目標(biāo)：在給定本錢、進(jìn)度的狀況下，開發(fā)出具有有效性、牢靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程需要到達(dá)的根本目標(biāo)：付出較低的開發(fā)本錢需要較低的維護(hù)費(fèi)用能按時(shí)完成開發(fā)，準(zhǔn)時(shí)交付使用軟件工程的理論和技術(shù)性爭(zhēng)論的內(nèi)容包括：軟件開發(fā)技術(shù)和軟件工程治理。軟件開發(fā)技術(shù)軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境， 其主體內(nèi)容是軟件開發(fā)方法學(xué)。軟件開發(fā)方法學(xué)是依據(jù)不同的軟件類型，按不同的觀點(diǎn)和原則，對(duì)軟件開發(fā)中應(yīng)遵循的策略、原則、步驟和必需產(chǎn)生的文檔資料都做出規(guī)定，階段。軟件工程治理

從而使軟件開發(fā)能夠進(jìn)入標(biāo)準(zhǔn)化和工程化的軟件工程治理：軟件治理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。軟件工程治理學(xué)包括：人員組織、進(jìn)度安排、質(zhì)量保證、配置治理、工程打算等。軟件工程經(jīng)濟(jì)學(xué)：是爭(zhēng)論軟件開發(fā)中本錢的估算、根本原理事爭(zhēng)論軟件工程開發(fā)中的經(jīng)濟(jì)效益問題。

軟件心理學(xué)：從個(gè)體心理、人類行為、組織行為和企業(yè)文化等角度來爭(zhēng)論軟件治理和軟件工程。軟件工程的原則抽象。抽取事物取根本的特征和行為，無視非本質(zhì)細(xì)節(jié)。承受分層次抽象，自頂向下，逐層細(xì)化的方法掌握軟件開發(fā)過程的簡(jiǎn)單性；(2模塊化。模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。塊太大會(huì)使模塊內(nèi)部過渡簡(jiǎn)單，不利于對(duì)模塊的理解和修改，也不利于模塊局部化。在同一個(gè)物理模塊中集中規(guī)律上相互關(guān)聯(lián)的計(jì)算資源，保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性；確定性。全部的概念表達(dá)應(yīng)是確定的、無歧義且標(biāo)準(zhǔn)。全都性。包括程序、數(shù)據(jù)和文檔的整個(gè)軟件系統(tǒng)的各模塊應(yīng)使用的概念、符號(hào)和術(shù)語；程序內(nèi)外部接口保持全都，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持全都；完備性。軟件系統(tǒng)不喪失任何重要成份，完全實(shí)現(xiàn)系統(tǒng)所需要的功能；(8?軟件開發(fā)工具與軟件開發(fā)環(huán)境1) 最早使用的是單一的程序設(shè)計(jì)語言，沒有相應(yīng)的開發(fā)工具，效率很低，隨著軟件開發(fā)工具的進(jìn)展，供給了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境，2〕軟件開發(fā)環(huán)境

軟件開發(fā)環(huán)境或稱軟件工程環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。計(jì)算機(jī)關(guān)心軟件工程將各種軟件工具、 開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫組成起來，形成軟件工程環(huán)境?！捕硺?gòu)造化分析方法1需求分析軟件需求分析是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、分析的任務(wù)是覺察需求、求精、建模和定義需求的過程。定義

設(shè)計(jì)約束等方面的期望。 需求軟件需求分析是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析階段的工作①需求獵取。需求獵取的目的是確定對(duì)目標(biāo)系統(tǒng)的各方面需求；②需求分析。對(duì)獵取的需求進(jìn)展分析和綜合，最終給出系統(tǒng)的解決方案和目標(biāo)系統(tǒng)的規(guī)律模型；③編寫需求規(guī)格說明書。為用戶、分析人員和設(shè)計(jì)人員之間進(jìn)展溝通供給便利。④需求評(píng)審。對(duì)需求分析階段的工作進(jìn)展復(fù)審，驗(yàn)證需求文檔的全都性、牢靠性、完事性和有效性。2〕〔1〕構(gòu)造化分析方法包括：面對(duì)數(shù)據(jù)流的構(gòu)造化分析方法面對(duì)數(shù)據(jù)構(gòu)造的Jackson方法面對(duì)數(shù)據(jù)構(gòu)造的構(gòu)造化數(shù)據(jù)系統(tǒng)開發(fā)方法面對(duì)對(duì)象的分析方法從需求分析建立模型的特性分，需求分析方法又分為靜態(tài)分析方法和動(dòng)態(tài)分析方法。2關(guān)于構(gòu)造化分析方法構(gòu)造化分析方法的實(shí)質(zhì)是：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的規(guī)律模型。構(gòu)造化分析的步驟：通過對(duì)用戶的調(diào)查，以軟件需求為線索，獲得系統(tǒng)的具體模型；去掉模型的非本質(zhì)因素，抽象出系統(tǒng)的規(guī)律模型；依據(jù)計(jì)算機(jī)的特點(diǎn)分析當(dāng)前系統(tǒng)與目標(biāo)系統(tǒng)的差異，建立目標(biāo)系統(tǒng)的規(guī)律模型；完善目標(biāo)系統(tǒng)交補(bǔ)充細(xì)構(gòu)造化分析的常用工具〔1〕數(shù)據(jù)流圖數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過程。數(shù)據(jù)流圖下的圖形元素：〔圓〕，加工〔轉(zhuǎn)換〕。輸入數(shù)據(jù)經(jīng)過加工變換產(chǎn)生輸出〔箭頭〕，數(shù)據(jù)流。沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名〔平行的二條直線〕，存儲(chǔ)文件〔數(shù)據(jù)源〕。表示處理過程中存放各種數(shù)據(jù)的文件?！查L(zhǎng)方形〕，源，潭。表示系統(tǒng)和環(huán)境的接口，屬于系統(tǒng)之外的實(shí)體。〔2〕數(shù)據(jù)字典數(shù)據(jù)字典是構(gòu)造化分析方法的核心。 對(duì)數(shù)據(jù)流圖中消滅的被命名的圖形元素的精準(zhǔn)解釋。 通常包括：名稱、別名、何處使用/如何使用、內(nèi)容描述、補(bǔ)充信息等。判定樹利用判定樹，對(duì)數(shù)據(jù)構(gòu)造中的數(shù)據(jù)之間的關(guān)系進(jìn)展描述，弄清楚判定條件之間的附屬關(guān)系、并列關(guān)系、選擇關(guān)系。判定表在數(shù)據(jù)流圖中的加工要依靠于多個(gè)條件的取值， 即完成該加工的一組動(dòng)作是由于某一組條件取值的組合而引發(fā)的狀況。它與判定樹是相像的，但更適宜于較簡(jiǎn)單的條件組合。3是需求分析階段的最終成果，是軟件開發(fā)的重要文檔之一。1〕便于用戶、開發(fā)人員進(jìn)展理解和溝通反映用戶問題的構(gòu)造，可以作為軟件開發(fā)工作的根底和依據(jù)作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)2〕在軟件打算中確定的軟件范圍加以開放，檢驗(yàn)標(biāo)準(zhǔn)以及其他與要求有關(guān)的數(shù)據(jù)。3〕

軟件需求規(guī)格說明書是確保軟件質(zhì)量的措施，它的內(nèi)涵是：正確性完整性全都性可修改性可追蹤性1軟件設(shè)計(jì)的根底軟件設(shè)計(jì)包括軟件構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。其中，構(gòu)造設(shè)計(jì)是定義軟件系統(tǒng)各主要部件之間的關(guān)系； 數(shù)據(jù)設(shè)計(jì)是將分析時(shí)創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)構(gòu)造的定義； 接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；構(gòu)造部件轉(zhuǎn)換成軟件的過程性描述。

過程設(shè)計(jì)是把系統(tǒng)次的過程設(shè)計(jì)；穿插進(jìn)展數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。軟件設(shè)計(jì)的根本原理抽象

先進(jìn)展高層次的構(gòu)造設(shè)計(jì)； 后進(jìn)展低層抽象的層次從概要設(shè)計(jì)到具體設(shè)計(jì)漸漸降低。體逐步分析和構(gòu)造出來的。模塊化

在軟件概要設(shè)計(jì)中的模塊分層也是由抽象到具模塊是指把一個(gè)待開發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部。模塊化是指解決一個(gè)簡(jiǎn)單問題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成假設(shè)干模塊的過程?！?〕信息隱蔽在一個(gè)模塊內(nèi)包含的信息〔過程或數(shù)據(jù)〕的。〔4〕模塊獨(dú)立性

，對(duì)于不需要這些信息的其他模塊來說是不能訪問獨(dú)立性是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，單。衡量軟件的模塊獨(dú)立性的標(biāo)準(zhǔn)：

并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)內(nèi)聚性：一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的嚴(yán)密程度的度量耦和性：模塊間相互連接的嚴(yán)密程序的度量構(gòu)造化設(shè)計(jì)方法馬上軟件設(shè)計(jì)成相對(duì)獨(dú)立、單一功能的模塊組成構(gòu)造。概要設(shè)計(jì)①設(shè)計(jì)軟件系統(tǒng)構(gòu)造馬上系統(tǒng)劃分成模塊以及模塊的層次構(gòu)造。②數(shù)據(jù)構(gòu)造及數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)設(shè)計(jì)是實(shí)現(xiàn)需求定義和規(guī)格說明過程中提出的數(shù)據(jù)對(duì)象的規(guī)律表示。數(shù)據(jù)設(shè)計(jì)的具體任務(wù)是：確定輸入、輸出文件的具體數(shù)據(jù)構(gòu)造結(jié)合算法設(shè)計(jì)，確定算法所必需的規(guī)律數(shù)據(jù)構(gòu)造及其操作確定對(duì)規(guī)律數(shù)據(jù)構(gòu)造所必需的那些操作的程序模塊，響范圍

限制和確定各個(gè)數(shù)據(jù)設(shè)計(jì)決策的影需要與操作系統(tǒng)或調(diào)度程序接口所必需的掌握表進(jìn)展數(shù)據(jù)交換時(shí)，構(gòu)和使用規(guī)章數(shù)據(jù)的保護(hù)性設(shè)計(jì)：防衛(wèi)性、全都性、冗余性設(shè)計(jì)③編寫概要設(shè)計(jì)文檔需要編寫的文檔有：

確定其具體的數(shù)據(jù)結(jié)概要設(shè)計(jì)說明書集成測(cè)試打算④概要設(shè)計(jì)文檔評(píng)審需要評(píng)審的內(nèi)容：設(shè)計(jì)局部是否完整地實(shí)現(xiàn)了需求中規(guī)定的功能、 可行性，關(guān)鍵的處理及內(nèi)外部接口定義的正確性、有效性，各局部之間的全都性等軟件構(gòu)造設(shè)計(jì)工具是構(gòu)造圖，描述軟件系統(tǒng)的層次和分塊構(gòu)造關(guān)系，能實(shí)現(xiàn)以及模塊與模塊之間的聯(lián)系與通訊，是將來程序中的掌握層次體系。構(gòu)造圖的元素：矩形表示一個(gè)模塊，在矩形內(nèi)注明模塊的功能和名字

它反映了整個(gè)系統(tǒng)的功箭頭表示模塊間的調(diào)用關(guān)系。表示傳遞的是數(shù)據(jù)構(gòu)造圖中常有的模塊類型：傳入模塊傳出模塊協(xié)調(diào)模塊

帶實(shí)心圓的箭頭表示傳遞的是掌握信息， 帶空心圓的箭頭面對(duì)數(shù)據(jù)流的設(shè)計(jì)方法①數(shù)據(jù)流類型變換型。將數(shù)據(jù)流分成三個(gè)局部：輸入數(shù)據(jù)、中心變換和輸出數(shù)據(jù)三個(gè)局部。事務(wù)型。在事務(wù)中心接收數(shù)據(jù)，分析數(shù)據(jù)以確定它的類型，再選取一條活動(dòng)的通路②面對(duì)數(shù)據(jù)流設(shè)計(jì)方法的實(shí)施要點(diǎn)與設(shè)計(jì)過程設(shè)計(jì)的準(zhǔn)則模塊規(guī)模適中深度、寬度、扇出和扇入適當(dāng)使模塊的作用域在該模塊的掌握域內(nèi)應(yīng)削減模塊的接口和界面的簡(jiǎn)單性設(shè)計(jì)成單入口、單出口的模塊設(shè)計(jì)功能可推測(cè)的模塊具體設(shè)計(jì)具體設(shè)計(jì)，即為軟件構(gòu)造圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)構(gòu)造，算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。常用的設(shè)計(jì)工具有：

用某種工具表示圖形工具：程序流程圖，表格工具：判定表語言工具：PDL〔偽碼〕〔四〕軟件測(cè)試軟件測(cè)試的目的

N-S,PAD,HIPO使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，或是否弄清預(yù)期的結(jié)果與實(shí)際結(jié)果之間的差異。軟件測(cè)試的準(zhǔn)則全部測(cè)試應(yīng)追溯到需求嚴(yán)格執(zhí)行測(cè)試打算，排解測(cè)試的隨便性充分留意測(cè)試中的群集現(xiàn)象程序員應(yīng)避開檢查自己的程序窮舉測(cè)試不行能

其目的在于檢驗(yàn)它是否滿足規(guī)定的需求妥當(dāng)保存測(cè)試打算、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告，為維護(hù)供給便利軟件測(cè)試技術(shù)與方法綜述1〕靜態(tài)測(cè)試包括：代碼檢查、靜態(tài)構(gòu)造分析、代碼質(zhì)量度量等。動(dòng)態(tài)測(cè)試是基于計(jì)算機(jī)的測(cè)試，覺察程序錯(cuò)誤的過程。白盒測(cè)試方法與測(cè)試用例設(shè)計(jì)

依據(jù)軟件需求設(shè)計(jì)測(cè)試用例， 利用這些用例去運(yùn)行程序， 以白盒測(cè)試也稱構(gòu)造測(cè)試或規(guī)律驅(qū)動(dòng)測(cè)試。白盒測(cè)試的原則：保證全部的測(cè)試模塊中每一條獨(dú)立路徑至少執(zhí)行一次； 保證全部的推斷分支至少執(zhí)行一次；保證全部的模塊中每一個(gè)循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗(yàn)證全部?jī)?nèi)部數(shù)據(jù)構(gòu)造的有效性主要的方法有：規(guī)律掩蓋〔包括語句掩蓋、路徑掩蓋、判定掩蓋、條件掩蓋和推斷一條件覆蓋〕、根本路徑測(cè)試等3〕黑盒測(cè)試方法與測(cè)試用例設(shè)計(jì)黑盒測(cè)試方法也稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試， 是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)展測(cè)試和驗(yàn)證。黑盒測(cè)試主要診斷功能不對(duì)或遺漏、初始化和終止條件錯(cuò)。

界面錯(cuò)誤、數(shù)據(jù)構(gòu)造或外部數(shù)據(jù)庫訪問錯(cuò)誤、性能錯(cuò)誤、黑盒測(cè)試方法主要有：等價(jià)類劃分法〔包括有效等價(jià)類和無效等價(jià)類〕誤推想法、因果圖等，主要用于軟件確認(rèn)測(cè)試。1〕對(duì)模塊進(jìn)展測(cè)試，用于覺察模塊內(nèi)部的錯(cuò)誤2〕測(cè)試和組裝軟件的過程，主要用于覺察與接口有關(guān)的錯(cuò)誤。

、邊界值分析法、錯(cuò)集成測(cè)試包括的內(nèi)容：軟件單元的接口測(cè)試、全局?jǐn)?shù)據(jù)構(gòu)造測(cè)試、邊界條件和非法輸入的測(cè)試等。集成測(cè)試分為：增量方式組裝〔包括自頂而下、自底而上、自頂向下和自底向上的混合增量方式〕與非增量方式組裝。確認(rèn)測(cè)試驗(yàn)證軟件的功能和性能及其他特征是否滿足了需求規(guī)格說明中確定的各種需求，置是否完全、正確。系統(tǒng)測(cè)試

以及軟件配將經(jīng)過測(cè)試后的軟件，與計(jì)算機(jī)的硬件、 外設(shè)、支持軟件、數(shù)據(jù)和人員等其他元素組合在一起，在實(shí)際運(yùn)行環(huán)境中進(jìn)展一系列的集成測(cè)試和確認(rèn)測(cè)試。1.根本概念程序調(diào)試活動(dòng)包括：依據(jù)錯(cuò)誤的跡象確定程序中錯(cuò)誤的精準(zhǔn)性質(zhì)、修改，排解錯(cuò)誤。1〕

緣由和位置；對(duì)程序進(jìn)展2〕〔1〕確定錯(cuò)誤的性質(zhì)和位置分析與錯(cuò)誤有關(guān)的信息避開死胡同

進(jìn)展回溯測(cè)試，防止引進(jìn)的錯(cuò)誤。調(diào)試工具只是一種關(guān)心手段，只能幫助思考，不能代替思考避開用摸索法〔2〕修改錯(cuò)誤的原則在消滅錯(cuò)誤的地方，有可能還有別的錯(cuò)誤，在修改時(shí)，肯定要觀看和檢查相關(guān)的代碼，以防止其他的錯(cuò)誤肯定要留意錯(cuò)誤代碼的修改，不要只留意表象，而要留意錯(cuò)誤的本身，把問題解決修改錯(cuò)誤也是程序設(shè)計(jì)的一種形式修改源代碼程序，不要轉(zhuǎn)變目標(biāo)代碼2．軟件調(diào)試方法自動(dòng)調(diào)試工具。回溯法適合小規(guī)模程序的排錯(cuò)。覺察錯(cuò)誤，分析錯(cuò)誤表象，確定位置，再回溯到源程序代碼，找到錯(cuò)誤位置或確定錯(cuò)誤范圍。緣由排解法緣由排解法包括：演繹法、歸納法和二分法。演繹法：是一種從一般原理或前提出法，經(jīng)過排解和精化的過程來推導(dǎo)出結(jié)論的思考方法。的緣由，從而找出錯(cuò)誤。二分法：假設(shè)每個(gè)變量在程序中假設(shè)干個(gè)關(guān)鍵點(diǎn)的正確值，則可以使用定值語句在程序中的某點(diǎn)四周給這些變量賦值，然后運(yùn)行程序并檢查程序的輸出。三、本章應(yīng)考點(diǎn)撥本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共根底局部比較重要的一章。從出題的深度來看，本章主要考察對(duì)根本概念的識(shí)記，有少量對(duì)根本原理的理解，沒有實(shí)際運(yùn)用，因此考生在復(fù)習(xí)本章時(shí)，重點(diǎn)應(yīng)放在根本概念的記憶和根本原理的理解上。一、內(nèi)容要點(diǎn)〔一〕數(shù)據(jù)庫系統(tǒng)的根本概念1．?dāng)?shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫治理系統(tǒng)數(shù)據(jù)數(shù)據(jù)是指存儲(chǔ)在某一種媒體上能夠被識(shí)別的物理符號(hào)，即描述事物的符號(hào)記錄。數(shù)據(jù)是有構(gòu)造的。首先，數(shù)據(jù)有型與值的區(qū)分，型即類型，值是符合指定類型的值。數(shù)據(jù)的概念在數(shù)據(jù)處理領(lǐng)域中已經(jīng)大大地拓寬數(shù)據(jù)庫數(shù)據(jù)庫〔DataBase，DB〕，是存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)設(shè)備上，構(gòu)造化的相互關(guān)聯(lián)的數(shù)據(jù)的集合。它不僅包括描述事物的數(shù)據(jù)本身，而且還包括相關(guān)事物之間的聯(lián)系。有安全機(jī)制，能夠保證數(shù)據(jù)的安全、牢靠，允許并發(fā)地使用數(shù)據(jù)庫，能有效、準(zhǔn)時(shí)地處理數(shù)據(jù)，并能保證數(shù)據(jù)的全都性和完整性。例如，某個(gè)學(xué)校的相關(guān)數(shù)據(jù)，如學(xué)生根本狀況、選課狀況、學(xué)籍治理等所涉及的相關(guān)數(shù)據(jù)的集合。3〕數(shù)據(jù)庫治理系統(tǒng)數(shù)據(jù)庫治理系統(tǒng)〔DataBaseManagementSystem，DBMS〕數(shù)據(jù)庫治理系統(tǒng)主要功能包括以下幾個(gè)方面：〔1〕數(shù)據(jù)模式定義數(shù)據(jù)庫治理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫構(gòu)建模式，也為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架?！?〕數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)庫治理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取及構(gòu)建供給有效的存取方法和手段?！?〕數(shù)據(jù)操縱數(shù)據(jù)庫治理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)供給便利， 一般供給查詢、插入、修改和刪除數(shù)據(jù)的功能，此外，還具有簡(jiǎn)潔的算術(shù)運(yùn)算和統(tǒng)計(jì)功能，還具有專長(zhǎng)強(qiáng)大的程序掌握功能。數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)存語義上的關(guān)聯(lián)性與全都性，數(shù)據(jù)庫中數(shù)據(jù)正確的必要條件。數(shù)據(jù)的并發(fā)掌握與故障恢復(fù)

即數(shù)據(jù)的完整性。數(shù)據(jù)的完整性是保證數(shù)據(jù)庫是一個(gè)集成、共享的數(shù)據(jù)集合體，它能為多個(gè)應(yīng)用程序效勞，因此，對(duì)數(shù)據(jù)庫并發(fā)操作時(shí)，要保證數(shù)據(jù)不被破壞。數(shù)據(jù)的效勞

當(dāng)多個(gè)應(yīng)用程序數(shù)據(jù)庫治理系統(tǒng)供給了對(duì)數(shù)據(jù)庫中數(shù)據(jù)的多種效勞，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。數(shù)據(jù)庫治理系統(tǒng)供給的相應(yīng)的數(shù)據(jù)語言包括如下：數(shù)據(jù)定義語言〔DataDefinitionLanguageDDL〕D用戶通過它可以便利地對(duì)數(shù)據(jù)庫中的相關(guān)內(nèi)容進(jìn)展定義。例如，對(duì)數(shù)據(jù)庫、表、索引進(jìn)展定義。2〕〔DataManipulationLanguageDML〕用戶通過它可以實(shí)現(xiàn)對(duì)數(shù)據(jù)庫的根本操作。例如，對(duì)表中數(shù)據(jù)的查詢、插入、刪除和修改。3〕〔DataControlLanguageDCL〕負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)掌握、故障恢復(fù)等功能，包括系統(tǒng)初啟程序、文件讀寫與維護(hù)程序、存取路徑治理程序、緩沖區(qū)治理程序、 安全性掌握程序、完整性檢查程序、并發(fā)掌握程序、事務(wù)治理程序、運(yùn)行日志治理程序、數(shù)據(jù)庫恢復(fù)程序等。目前流行的DBMS均為關(guān)系型數(shù)據(jù)庫系統(tǒng)，發(fā)ORACLE、Sybase的PowerBuilder及IBM的DB2、微軟件的SQLServer等。還有一些小型的數(shù)據(jù)庫，如4〕

VisualFoxPro和Access數(shù)據(jù)庫的治理員〔DataBaseAdministratorDBA〕主要工作如下：數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫維護(hù)改善系統(tǒng)性能，提高系統(tǒng)效率5〕數(shù)據(jù)庫系統(tǒng)〔DataBaseSystem，DBS〕由如下幾個(gè)局部組成：數(shù)據(jù)庫〔數(shù)據(jù)〕數(shù)據(jù)庫治理員〔人員〕系統(tǒng)平臺(tái)〔硬件平臺(tái)和軟件平臺(tái)〕硬件平臺(tái)包括：網(wǎng)絡(luò)軟件平臺(tái)包括：操作系統(tǒng)接口軟件6〕數(shù)據(jù)庫應(yīng)用系統(tǒng)數(shù)據(jù)庫應(yīng)用系統(tǒng)〔DataBaseApplicationSystemDBAS〕是數(shù)據(jù)庫系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面而構(gòu)成的。它包括：數(shù)據(jù)庫數(shù)據(jù)庫治理員硬件平臺(tái)應(yīng)用界面2?數(shù)據(jù)庫系統(tǒng)的進(jìn)展隨著計(jì)算機(jī)軟硬件技術(shù)的進(jìn)展，數(shù)據(jù)處理方法也經(jīng)受了從低級(jí)到高級(jí)的進(jìn)展過程，依據(jù)數(shù)據(jù)治理的特點(diǎn)可將其劃分為人工治理、文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)三個(gè)階段。人工治理階段在20世紀(jì)50年月，計(jì)算機(jī)主要用于數(shù)值計(jì)算。從當(dāng)時(shí)的硬件看，外存只有紙帶、卡片、磁帶，沒有直接存取設(shè)備；從軟件看〔實(shí)際上，當(dāng)時(shí)還未形成軟件的整體概念〕 ，沒有操作系統(tǒng)以及治理數(shù)據(jù)的軟件；從數(shù)據(jù)看，數(shù)據(jù)量小，數(shù)據(jù)無構(gòu)造，由用戶直接治理，且數(shù)據(jù)間缺乏規(guī)律組織，數(shù)據(jù)依靠于特定的應(yīng)用程序，缺乏獨(dú)立性。文件系統(tǒng)階段是數(shù)據(jù)庫系統(tǒng)進(jìn)展的初級(jí)階段， 它供給了簡(jiǎn)潔的數(shù)據(jù)共享和數(shù)據(jù)治理力量， 的、統(tǒng)一的、治理和數(shù)據(jù)共享的力量。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫階段20世紀(jì)60年月末期，層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫開頭進(jìn)展，它們?yōu)榻y(tǒng)一治理和數(shù)據(jù)共享供給了支撐，即標(biāo)志著數(shù)據(jù)庫系統(tǒng)的真正降臨。 但它們有很多的缺乏，如受文件的物理影響較大，對(duì)數(shù)據(jù)庫使用帶來很多不便，數(shù)據(jù)構(gòu)造簡(jiǎn)單，不變于推廣。關(guān)系數(shù)據(jù)庫系統(tǒng)階段關(guān)系數(shù)據(jù)庫系統(tǒng)消滅于2070年月，它的數(shù)據(jù)庫構(gòu)造簡(jiǎn)潔，少，使用廣泛。由于應(yīng)用的領(lǐng)域不同，它常分為：工程數(shù)據(jù)庫系統(tǒng)圖形數(shù)據(jù)庫系統(tǒng)圖像數(shù)據(jù)庫系統(tǒng)統(tǒng)計(jì)數(shù)據(jù)庫系統(tǒng)學(xué)問數(shù)據(jù)庫系統(tǒng)并行數(shù)據(jù)庫系統(tǒng)面對(duì)對(duì)象數(shù)據(jù)庫系統(tǒng)?數(shù)據(jù)庫系統(tǒng)的根本特點(diǎn)1〕數(shù)據(jù)的集成性在數(shù)據(jù)庫系統(tǒng)中承受統(tǒng)一的數(shù)據(jù)構(gòu)造方式

使用便利，規(guī)律性強(qiáng)物理性在數(shù)據(jù)庫系統(tǒng)中依據(jù)多個(gè)應(yīng)用程序的需要組織全局的統(tǒng)一的數(shù)據(jù)構(gòu)造，據(jù)構(gòu)造，也可建立數(shù)據(jù)間的語義聯(lián)系從而構(gòu)成一個(gè)內(nèi)存嚴(yán)密聯(lián)系的數(shù)據(jù)整體

數(shù)據(jù)模式是多個(gè)應(yīng)用程序共同的、的一局部

全局的數(shù)據(jù)構(gòu)造，而每個(gè)應(yīng)用的數(shù)據(jù)則是全局構(gòu)造中數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)的全都性是指系統(tǒng)中同一數(shù)據(jù)的不同消滅應(yīng)保持一樣的值， 而數(shù)據(jù)的不全都性是指同一數(shù)據(jù)在系統(tǒng)不同拷貝處有不同的值。削減數(shù)據(jù)的冗余性可以避開數(shù)據(jù)的不全都性。數(shù)據(jù)的獨(dú)立性數(shù)據(jù)的獨(dú)立性是指數(shù)據(jù)與程序間的互不依靠性。轉(zhuǎn)變不會(huì)影響應(yīng)用程序。物理獨(dú)立性

即數(shù)據(jù)的物理構(gòu)造〔包括存儲(chǔ)構(gòu)造、存取方式〕的轉(zhuǎn)變，不會(huì)影響數(shù)據(jù)庫的規(guī)律構(gòu)造，即不會(huì)引起應(yīng)用程序的變化。規(guī)律的獨(dú)立性4〕數(shù)據(jù)庫總體規(guī)律構(gòu)造的轉(zhuǎn)變，不需要相應(yīng)修改應(yīng)用程序。數(shù)據(jù)完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫訪問者以防非法訪問并發(fā)掌握：掌握多個(gè)應(yīng)用程序的并發(fā)訪問所發(fā)生的相互干擾以保證其正確性?數(shù)據(jù)庫系統(tǒng)的內(nèi)部構(gòu)造體系數(shù)據(jù)庫系統(tǒng)的內(nèi)部具有三級(jí)模式與二級(jí)映射。1〕數(shù)據(jù)模式是數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)構(gòu)造的一種表示形式，它具有不同的層次與構(gòu)造方式?！?〕概念模式概念模式是數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)規(guī)律構(gòu)造的描述， 數(shù)據(jù)視圖。概念模式主要描述數(shù)據(jù)的概念記錄類型以及它們之間的關(guān)系，還包括一些數(shù)據(jù)間的語義約束。外模式外模式又稱子模式或用戶模式，是用戶的數(shù)據(jù)視圖，即用戶見到的數(shù)據(jù)模式。概念模式給出系統(tǒng)全局的數(shù)據(jù)描述而外模式則給出每個(gè)用戶的局部數(shù)據(jù)描述。內(nèi)模式內(nèi)模式又稱物理模式，它給出數(shù)據(jù)庫物理存儲(chǔ)構(gòu)造與物理存儲(chǔ)方法， 索引、集簇及hash等存取方式與存取路徑，內(nèi)模式的物理性主要表達(dá)在操作系統(tǒng)及文件級(jí)上。內(nèi)模式對(duì)一般的用戶是透亮的，但它的設(shè)計(jì)直接影響到數(shù)據(jù)庫系統(tǒng)的性能。模式的三個(gè)級(jí)別層次反映了模式的三個(gè)不同環(huán)境以及它們的不同要求， 其中內(nèi)模式處于最底層，它反映數(shù)據(jù)在計(jì)算機(jī)物理構(gòu)造中的實(shí)際存儲(chǔ)形式， 概念模式牌中層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局規(guī)律要求，而外模式處于最外層，通過兩種映射由物理數(shù)據(jù)庫映射而成它反映用戶對(duì)數(shù)據(jù)的要求。2〕數(shù)據(jù)庫系統(tǒng)的三級(jí)模式是對(duì)數(shù)據(jù)的三個(gè)級(jí)別抽象，它把數(shù)據(jù)的具體物理實(shí)現(xiàn)留給物理模式，使得全局設(shè)計(jì)者不必關(guān)心數(shù)據(jù)庫的具體實(shí)現(xiàn)與物理背景； 通過兩級(jí)映射建立了模式間的聯(lián)系與轉(zhuǎn)換，使得概念模式與外模式雖然并不物理存在，但也能通過映射獲得實(shí)體。同時(shí)， 映射也保證了數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的獨(dú)立性。兩級(jí)模式的映射：概念模式到內(nèi)模式的映射：該映射給出概念模式中數(shù)據(jù)的全局規(guī)律構(gòu)造到數(shù)據(jù)的物理存儲(chǔ)構(gòu)造間的對(duì)應(yīng)關(guān)系外模式到概念模式的映射：該映射給出了外模式與概念模式之間的對(duì)應(yīng)關(guān)系1數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象， 而數(shù)據(jù)模型是數(shù)據(jù)特征的抽象， 它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示與操作供給了一個(gè)抽象的框架。數(shù)據(jù)模型描述的三個(gè)局部：數(shù)據(jù)構(gòu)造、數(shù)據(jù)操作與數(shù)據(jù)約束。(1描述數(shù)據(jù)的類型、內(nèi)容、性質(zhì)及數(shù)據(jù)間的聯(lián)系等。(2主要描述在相應(yīng)的數(shù)據(jù)構(gòu)造上的操作類型與操作方式。(3主要描述數(shù)據(jù)構(gòu)造內(nèi)數(shù)據(jù)間的語法、 語義聯(lián)系，它們之間的制約與依存關(guān)系， 變化的規(guī)章，以保證數(shù)據(jù)的正確、有效與相容。規(guī)律數(shù)據(jù)模型又稱數(shù)據(jù)模型，較為成熟的有：層次模型、網(wǎng)狀模型和關(guān)系模型。物理數(shù)據(jù)模型又稱物理模型，是面對(duì)計(jì)算機(jī)物理表示的模型。2.E-RE-RE-R(EntityRelationshipmodel實(shí)體在現(xiàn)實(shí)生活中客觀存在且又能相互區(qū)分的事物，稱為實(shí)體。具有共性的實(shí)體可組成一個(gè)集合稱為實(shí)體集。屬性屬性是用來描述實(shí)體的特征。一個(gè)實(shí)體有很多個(gè)屬性。每個(gè)屬性都可以有值，一個(gè)屬性的取值范圍稱為該屬性的值域或值集。聯(lián)系反映事物之間的關(guān)聯(lián)稱為聯(lián)系。實(shí)體集之間的聯(lián)系有多種，就實(shí)體集個(gè)數(shù)而言，有：兩個(gè)實(shí)體集間的聯(lián)系多個(gè)實(shí)體集之間的聯(lián)系一個(gè)實(shí)體集內(nèi)部的聯(lián)系兩個(gè)實(shí)體集間的聯(lián)系即實(shí)體集間的函數(shù)關(guān)系，有如下幾種關(guān)系：一對(duì)一的聯(lián)系一對(duì)多的聯(lián)系多對(duì)多的聯(lián)系E-R模型三個(gè)根本概念之間的聯(lián)系關(guān)系(1實(shí)體是概念世界中的根本單位，屬性附屬于實(shí)體，它本身并不構(gòu)成獨(dú)立性單位。一個(gè)實(shí)體可以有假設(shè)干個(gè)屬性，實(shí)體與它全部屬性構(gòu)成了實(shí)體的一個(gè)完整描述。有肯定的聯(lián)系。

實(shí)體與屬性間實(shí)體有型與值的區(qū)分，一個(gè)實(shí)體的全部屬性的集合，稱為實(shí)體型，而實(shí)體中屬性值的集合，即構(gòu)成該實(shí)體的值。(2)實(shí)體與聯(lián)系實(shí)體集之間通過聯(lián)系建立聯(lián)接關(guān)系。E-R用矩形表示實(shí)體集，在矩形內(nèi)部標(biāo)出實(shí)體集的名稱用橢圓形表示屬性，在橢圓上標(biāo)出屬性的名稱用菱形表示聯(lián)系，在菱形上標(biāo)出聯(lián)系名屬性依附于實(shí)體，它們之間用無向線段聯(lián)接屬性也依附于聯(lián)系，它們之?層次模型假設(shè)用圖來表示，層次模型是一棵倒立的樹。在數(shù)據(jù)庫中，滿足以下兩個(gè)條件的數(shù)據(jù)模型稱為層次模型：II在層次模型中，結(jié)點(diǎn)層次從根開頭定義，根為第一層，根的子結(jié)點(diǎn)為其次層，根為其子結(jié)點(diǎn)的父結(jié)點(diǎn)，同一父結(jié)點(diǎn)的子結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)，沒有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。層次模型表示的是一對(duì)多的關(guān)系， 即一個(gè)父節(jié)點(diǎn)可以對(duì)應(yīng)多個(gè)子節(jié)點(diǎn)。 、直觀、處理便利、算法標(biāo)準(zhǔn)；缺點(diǎn)是不能表達(dá)含有多對(duì)多關(guān)系的簡(jiǎn)單構(gòu)造。R1是根節(jié)點(diǎn)，R2、R3是R1的子結(jié)點(diǎn)，它們互為兄弟結(jié)點(diǎn)；們也互為兄弟節(jié)點(diǎn)；R3、R4、R5

R4、R5為R2的子結(jié)節(jié)點(diǎn)，它其中，每一個(gè)節(jié)點(diǎn)都代表一個(gè)實(shí)體型，各實(shí)體型由上而下是 1：n的聯(lián)系。支持層次模型的DBMS稱為層次數(shù)據(jù)庫治理系統(tǒng)，在這種數(shù)據(jù)庫系統(tǒng)中建立的數(shù)據(jù)庫是層次數(shù)據(jù)庫。層次數(shù)據(jù)模型支持的操作主要有：查詢、插入、刪除和更。?網(wǎng)狀模型假設(shè)用圖來表示，網(wǎng)狀模型是一個(gè)網(wǎng)絡(luò)。在數(shù)據(jù)庫中，滿足以下兩個(gè)條件的數(shù)據(jù)模型稱為網(wǎng)狀模型。III允許兩個(gè)結(jié)點(diǎn)間有兩種以上的聯(lián)系，即允許結(jié)點(diǎn)間有復(fù)合鏈，用網(wǎng)絡(luò)表示某種聯(lián)系由于在網(wǎng)狀模型中子結(jié)點(diǎn)與父結(jié)點(diǎn)的聯(lián)系不是唯一的，聯(lián)系有關(guān)的父結(jié)點(diǎn)和子結(jié)點(diǎn)。

網(wǎng)狀模型的優(yōu)點(diǎn)是可以表示簡(jiǎn)單的數(shù)據(jù)構(gòu)造，存取數(shù)據(jù)的效率比較高；缺點(diǎn)是構(gòu)造簡(jiǎn)單，每個(gè)問題都有其相對(duì)的特別性，實(shí)現(xiàn)的算法難以標(biāo)準(zhǔn)化。在抽象網(wǎng)狀模型中，R1與R4L1,R1與R3L2,R2與R3系被命名為L(zhǎng)3,R3與R5L4,R4與R5之間的聯(lián)系被命名為L(zhǎng)5。R1為R3和R4點(diǎn)，R2R3R1R2網(wǎng)狀模型是一個(gè)不加任何條件限制的無向圖。比照較敏捷。

它沒有層次模型那樣需要滿足嚴(yán)格的條件， 相通常的操作方式是將網(wǎng)狀模型分解成假設(shè)干個(gè)二級(jí)樹，即只有兩個(gè)層次的樹。在網(wǎng)狀模型標(biāo)準(zhǔn)中，根本構(gòu)造簡(jiǎn)潔二級(jí)樹叫做系，系的根本數(shù)據(jù)單位是記錄，它相當(dāng)于

E-R模型中的實(shí)體集；記錄又可由假設(shè)干數(shù)據(jù)項(xiàng)組成，它相當(dāng)于5?關(guān)系模型1)關(guān)系的數(shù)據(jù)構(gòu)造

E-R模型中的屬性。關(guān)系模型是利用二維表來表示，簡(jiǎn)稱表。表頭即屬性的集合，在表中每一行存放數(shù)據(jù)，稱為元組。二維表要求滿足的條件：二維表中元組的個(gè)數(shù)有限元組在二維表中的唯一性，在同一個(gè)表中不存在完全一樣的兩個(gè)元組二維表中元組的挨次無關(guān)，可以任意調(diào)換元組中的各重量不能再分解二維表中各屬性名唯一二維表中各屬性的挨次無關(guān)二維表屬性的重量具有與該屬性一樣的值域鍵：能夠唯一確定元組的屬性或?qū)傩缘慕M合。 例如，在學(xué)生根本狀況表中， 可以用學(xué)號(hào)來唯一標(biāo)識(shí)某個(gè)學(xué)生，即學(xué)號(hào)可以作為該表的鍵。鍵具有標(biāo)識(shí)元組、建立元組間聯(lián)系等重要作用。在二維表中但凡能夠唯一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼。 二維表中可能有假設(shè)干個(gè)鍵，稱為候選碼或候選健。從二維表的全部候選鍵中選取一個(gè)作為用戶使用的鍵稱為主鍵或主碼。外鍵：假設(shè)表中的一個(gè)字段不是本表的鍵或候選鍵，字段為外鍵或外碼。表中肯定有鍵。

而是另外一個(gè)表的鍵或候選鍵， 則稱該在關(guān)系中一般支持空值，空值表示未知的值或不行能消滅的值，一般用的主鍵中不允許消滅空值，由于如主鍵為空值則失去了其元組標(biāo)識(shí)的作用。

NULL表示。關(guān)系關(guān)系模式支持子模式，關(guān)系子模式是關(guān)系數(shù)據(jù)庫模式中用戶所見到的那局部數(shù)據(jù)模式描述。2〕關(guān)系模型的數(shù)據(jù)操縱是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改。〔1〕數(shù)據(jù)查詢?cè)谝粋€(gè)關(guān)系中查詢數(shù)據(jù)，操作方式是先定位，然后再操作。在多個(gè)關(guān)系中查詢數(shù)據(jù)，先將多個(gè)關(guān)系合并為一個(gè)關(guān)系，再在合并后的關(guān)系中進(jìn)展定位，然后再操作。〔2〕數(shù)據(jù)刪除數(shù)據(jù)刪除操作是在一個(gè)關(guān)系中刪除元組的操作。操作方式也是先定位，然后再刪除操作?！?〕數(shù)據(jù)插入數(shù)據(jù)插入也是僅對(duì)一個(gè)關(guān)系的操作。即在指定的關(guān)系中插入一個(gè)或多個(gè)元組?！?〕數(shù)據(jù)修改數(shù)據(jù)修改是在一個(gè)關(guān)系中修改指定的元組與屬性。刪除要修改的元組，再插入修改后的元組兩個(gè)根本操作。關(guān)系的根本操作：兩個(gè)關(guān)系合并一個(gè)或多個(gè)關(guān)系的查詢關(guān)系中元組的插入3〕

數(shù)據(jù)修改不是一個(gè)根本的操作，可分解為數(shù)據(jù)約束：實(shí)體完整性約束、參照完整性約束和用戶定義的完整性約束?！?〕實(shí)體完整性約束要求關(guān)系的主鍵中屬性值不能為空值，主鍵的惟一打算元組的惟一性?！?〕參照完整性約束關(guān)系之間相關(guān)聯(lián)的根本約束，不允許關(guān)系引用不存在的元組。(3用戶依據(jù)具體的數(shù)據(jù)環(huán)境與應(yīng)用環(huán)境具體設(shè)置約束。關(guān)系數(shù)據(jù)庫系統(tǒng)供給完整性約束語言，用戶利用該語言寫出的約束條件，運(yùn)行時(shí)由系統(tǒng)自動(dòng)檢查。關(guān)系模型的根本操作關(guān)系是由假設(shè)干個(gè)不同的元組組成的，組的集合。

因此關(guān)系可看作元組的集合。N元關(guān)系是一個(gè)n元有序設(shè)有一個(gè)n元關(guān)系R，它有n個(gè)域，分別是D1、D2、……、Dn,此時(shí)，它們的笛卡爾集是：集合可看作是域的笛卡爾積的子集，。關(guān)系模型的四種操作是：可將它們分解為六種根本操作：關(guān)系的屬性指定關(guān)系的元組選擇關(guān)系的查詢?關(guān)系模型的根本運(yùn)算插入插入操作可看作是集合的并運(yùn)算。即在原有的關(guān)系組的并運(yùn)算：刪除在關(guān)系R中刪除元組R”可看作是兩個(gè)關(guān)系的差運(yùn)算：

R中并入要插入的元組R”是這兩個(gè)元R-R”修改修改關(guān)系R中的元組