全國計算機二級《公共基礎(chǔ)知識》講義.doc

《全國計算機二級《公共基礎(chǔ)知識》講義.doc》由會員分享，可在線閱讀，更多相關(guān)《全國計算機二級《公共基礎(chǔ)知識》講義.doc（86頁珍藏版）》請在裝配圖網(wǎng)上搜索。

目錄 全國二級C語言考試大綱 1 全國二級公共基礎(chǔ)知識考試大綱 3 公共基礎(chǔ)知識講義 4 第一講 數(shù)據(jù)結(jié)構(gòu)與算法 4 第二講 數(shù)據(jù)庫設(shè)計基礎(chǔ) 11 第三講 軟件工程基礎(chǔ) 18 第四講 程序設(shè)計基礎(chǔ) 25 公共基礎(chǔ)知識習(xí)題 28 數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題 28 數(shù)據(jù)庫設(shè)計基礎(chǔ)習(xí)題 33 軟件工程基礎(chǔ)習(xí)題 38 程序設(shè)計基礎(chǔ)習(xí)題 41 2009年3月二級C語言筆試真題 43 2009年3月二級C語言筆試答案 54 2008年9月二級C語言筆試真題 55 2008年9月二級C語言筆試答案 64 2008年4月二級C語言筆試真題 65 2008年4月二級C語言筆試答案 73 2007年9月二級C語言筆試真題 74 2007年9月二級C語言筆試答案 86 全國二級C語言考試大綱 ◆ 基本要求 1.熟悉 Visual C++ 6.0 集成開發(fā)環(huán)境。 2.掌握結(jié)構(gòu)化程序設(shè)計的方法，具有良好的程序設(shè)計風(fēng)格。 3.掌握程序設(shè)計中簡單的數(shù)據(jù)結(jié)構(gòu)和算法并能閱讀簡單的程序。 4.在 Visual C++ 6.0 集成環(huán)境下，能夠編寫簡單的C程序，并具有基本的糾錯和調(diào)試程序的能力 ◆ 考試內(nèi)容 一、C語言程序的結(jié)構(gòu) 1.程序的構(gòu)成，main函數(shù)和其他函數(shù)。 2.頭文件，數(shù)據(jù)說明，函數(shù)的開始和結(jié)束標(biāo)志以及程序中的注釋。 3.源程序的書寫格式。 4.C語言的風(fēng)格。 二、數(shù)據(jù)類型及其運算 1.C的數(shù)據(jù)類型（基本類型，構(gòu)造類型，指針類型，無值類型）及其定義方法。 2.C運算符的種類、運算優(yōu)先級和結(jié)合性。 3.不同類型數(shù)據(jù)間的轉(zhuǎn)換與運算。 4.C表達式類型（賦值表達式，算術(shù)表達式，關(guān)系表達式，邏輯表達式，條件表達式，逗號表達式）和求值規(guī)則。 三、基本語句 1.表達式語句，空語句，復(fù)合語句。 2.輸入輸出函數(shù)的調(diào)用，正確輸入數(shù)據(jù)并正確設(shè)計輸出格式。 四、選擇結(jié)構(gòu)程序設(shè)計 1.用if語句實現(xiàn)選擇結(jié)構(gòu)。 2.用switch語句實現(xiàn)多分支選擇結(jié)構(gòu)。 3.選擇結(jié)構(gòu)的嵌套。 五、循環(huán)結(jié)構(gòu)程序設(shè)計 1.for循環(huán)結(jié)構(gòu)。 2.while和do-while循環(huán)結(jié)構(gòu)。 3.continue語句和break語句。 4.循環(huán)的嵌套。 六、數(shù)組的定義和引用 1.一維數(shù)組和二維數(shù)組的定義、初始化和數(shù)組元素的引用。 2.字符串與字符數(shù)組。 七、函數(shù) 1.庫函數(shù)的正確調(diào)用。 2.函數(shù)的定義方法。 3.函數(shù)的類型和返回值。 4.形式參數(shù)與實在參數(shù)，參數(shù)值傳遞。 5.函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用。 6.局部變量和全局變量。 7.變量的存儲類別（自動，靜態(tài)，寄存器，外部），變量的作用域和生存期。 八、編譯預(yù)處理 1.宏定義和調(diào)用（不帶參數(shù)的宏，帶參數(shù)的宏）。 2.“文件包含”處理。 九、指針 1.地址與指針變量的概念，地址運算符與間址運算符。 2.一維、二維數(shù)組和字符串的地址以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針變量的定義。通過指針引用以上各類型數(shù)據(jù)。 3.用指針作函數(shù)參數(shù)。 4.返回地址值的函數(shù)。 5.指針數(shù)組，指向指針的指針。 十、結(jié)構(gòu)體（即“結(jié)構(gòu)”）與共同體（即“聯(lián)合”） 1.用typedef說明一個新類型。 2.結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義和成員的引用。 3.通過結(jié)構(gòu)體構(gòu)成鏈表，單向鏈表的建立，結(jié)點數(shù)據(jù)的輸出、刪除與插入。 十一、位運算 1.位運算符的含義和使用。 2.簡單的位運算。 十二、文件操作 只要求緩沖文件系統(tǒng)（即高級磁盤I/O系統(tǒng)），對非標(biāo)準(zhǔn)緩沖文件系統(tǒng)（即低級磁盤I/O系統(tǒng)）不要求。 1.文件類型指針（FILE類型指針）。 2.文件的打開與關(guān)閉（fopen，fclose）。 3.文件的讀寫（fputc，fgetc，fputs，fgets，fread，fwrite，fprintf，fscanf函數(shù)的應(yīng)用），文件的定位（rewind，fseek函數(shù)的應(yīng)用）。 ◆ 考試方式 1.筆試：90分鐘，滿分100分，其中含公共基礎(chǔ)知識部分的30分。 2.上機：90分鐘，滿分100分 3、上機操作包括： （1）填空。 （2）改錯。 （3）編程。 全國二級公共基礎(chǔ)知識考試大綱 ◆ 基本要求 　　1.掌握算法的基本概念。 　　2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 　　3.掌握基本排序和查找算法。 　　4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。 　　5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)的能力。 　　6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。 ◆ 考試內(nèi)容 一、 基本數(shù)據(jù)結(jié)構(gòu)與算法 1. 算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。 2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3. 線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。 4. 棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。 6. 樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 二、 程序設(shè)計基礎(chǔ) 1. 程序設(shè)計方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計。 3. 面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。 三、 軟件工程基礎(chǔ) 1. 軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。 2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。 3. 結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細設(shè)計。 4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。 5. 程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。 四、 數(shù)據(jù)庫設(shè)計基礎(chǔ) 1. 數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。 2. 數(shù)據(jù)模型，實體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3. 關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。 4. 數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。 ◆ 考試方式 公共基礎(chǔ)知識有10道選擇題和5道填空題共三十分 公共基礎(chǔ)知識講義 第一講 數(shù)據(jù)結(jié)構(gòu)與算法 1.1 算法 1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。 *：算法不等于程序，也不等于計算方法。程序的編制不可能優(yōu)于算法的設(shè)計。 2、算法的基本特征 （1）可行性。針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。 （2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。 （3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。 （4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情報時，此算法才是有效的；而當(dāng)提供的情報不夠時，算法可能無效。 *：綜上所述，所謂算法，是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。 （1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。 （2）算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 1）順序存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。 2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。 3）索引存儲：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。 *：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。 （3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 3、數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。 4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點；2）每一個結(jié)點最多有一個前件，也最多有一個后件。 *：常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。 （2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 *：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。 1.3 線性表及其順序存儲結(jié)構(gòu) 1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。 *：線性表是一種存儲結(jié)構(gòu)，它的存儲方式：順序和鏈?zhǔn)健? 2、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 *：由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結(jié)點的存儲地址。 3、順序表的插入、刪除運算 （1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。 *：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。 （2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。 *：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。 1.4 棧和隊列 1、棧及其基本運算 棧是限定在一端進行插入與刪除運算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。 棧具有記憶作用。 棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。 棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！? 2、隊列及其基本運算 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。 隊列是“先進先出”或“后進后出”的線性表。 隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。 循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。 *：循環(huán)隊列中元素的個數(shù)=rear-front。 1.5 線性鏈表 1、線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充；（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。 2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。因此，在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件），如下圖所示： 線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。 在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。因此，在某些應(yīng)用中，對于線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，指向其前件結(jié)點；另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示： 3、線性鏈表的基本運算 （1）在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。 *：在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可，也不會出現(xiàn)“上溢”現(xiàn)象。 （2）在線性鏈表中刪除包含指定元素的結(jié)點。 *：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。 （3）將兩個線性鏈表按要求合并成一個線性鏈表。 （4）將一個線性鏈表按要求進行分解。 （5）逆轉(zhuǎn)線性鏈表。 （6）復(fù)制線性鏈表。 （7）線性鏈表的排序。 （8）線性鏈表的查找。 *：線性鏈表不能隨機存取。 4、循環(huán)鏈表及其基本運算 在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環(huán)鏈表。 與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點，而循環(huán)鏈表的頭指針指向表頭結(jié)點；2）循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。 下圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表： 循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。 *：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點出發(fā)來訪問表中其他所有結(jié)點，并實現(xiàn)空表與非空表的運算的統(tǒng)一。 1.6 樹與二叉樹 1、樹的基本概念 樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。 2、二叉樹及其基本性質(zhì) （1）什么是二叉樹 二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1）非空二叉樹只有一個根結(jié)點；2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。 *：根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子樹）或2（有2棵子樹）。 （2）二叉樹的基本性質(zhì) 性質(zhì)1 在二叉樹的第k層上，最多有 個結(jié)點。 性質(zhì)2 深度為m的二叉樹最多有個 個結(jié)點。 性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點總比度為2的結(jié)點多一個。 性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為 ，其中 表示取 的整數(shù)部分。 3、滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。 完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。 *：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點的個數(shù)為0或1。 下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹： 完全二叉樹還具有如下兩個特性： 性質(zhì)5 具有n個結(jié)點的完全二叉樹深度為 。 性質(zhì)6 設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點進行編號，則對于編號為k（k=1，2，…，n）的結(jié)點有以下結(jié)論： ①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。 ②若2k≤n，則編號為k的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。 ③若2k+1≤n，則編號為k的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。 4、二叉樹的存儲結(jié)構(gòu) 在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為左指針域；另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為右指針域。 *：一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。 5、二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種： （1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 （2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 （3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 1.7 查找技術(shù) 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查找結(jié)果：（查找成功：找到；查找不成功：沒找到。） 平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。 1、順序查找 基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。 在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。 順序查找一個具有n個元素的線性表，其平均復(fù)雜度為O（n）。 下列兩種情況下只能采用順序查找： 1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。 2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。 2、二分法查找 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。 查找過程： 1）若中間項（中間項mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到； 2）若x小于中間項的值，則在線性表的前半部分查找； 3）若x大于中間項的值，則在線性表的后半部分查找。 特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。 *：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復(fù)雜度為O（log2n）。 1.8 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。 1、交換類排序法（方法：冒泡排序，快速排序）。 2、插入類排序法（方法：簡單插入排序，希爾排序）。 3、選擇類排序法（方法：簡單選擇排序，堆排序）。 總結(jié)：各種排序法比較： 第二講 數(shù)據(jù)庫設(shè)計基礎(chǔ) 2.1 數(shù)據(jù)庫系統(tǒng)的基本概念 1、數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng) （1）數(shù)據(jù)：實際上就是描述事物的符號記錄。 數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如整型、實型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。 （2）數(shù)據(jù)庫（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點，亦即是數(shù)據(jù)庫集中了各種應(yīng)用的數(shù)據(jù)，進行統(tǒng)一的構(gòu)造和存儲，而使它們可被不同應(yīng)用程序所使用。 （3）數(shù)據(jù)庫管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。 數(shù)據(jù)庫管理系統(tǒng)功能： 1）數(shù)據(jù)模式定義。數(shù)據(jù)庫管理系統(tǒng)負責(zé)為數(shù)據(jù)庫構(gòu)建模式，也就是為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架。 2）數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫管理系統(tǒng)負責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。 3）數(shù)據(jù)操縱。數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)提供方便，它一般提供如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡單的算術(shù)運算及統(tǒng)計的能力，而且還可以與某些過程性語言結(jié)合，使其具有強大的過程性操作能力。 4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)在語義上的關(guān)聯(lián)性與一致性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫中數(shù)據(jù)正確的必要條件，因此必須經(jīng)常檢查以維護數(shù)據(jù)正確。數(shù)據(jù)庫中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會引發(fā)數(shù)據(jù)的非法使用，因此必須要對數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時做檢查，這就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性與安全性的維護是數(shù)據(jù)庫系統(tǒng)的基本功能。 5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體，它能為多個應(yīng)用程序服務(wù)，所以就存在著多個應(yīng)用程序?qū)?shù)據(jù)庫的并發(fā)操作。在并發(fā)操作中如果不加控制和管理，多個應(yīng)用程序間就會相互干擾，從而對數(shù)據(jù)庫中的數(shù)據(jù)造成破壞。因此，數(shù)據(jù)庫管理系統(tǒng)必須對多個應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞，這就是數(shù)據(jù)庫的并發(fā)控制。數(shù)據(jù)庫中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫管理系統(tǒng)必須有能力及時進行恢復(fù)，這就是數(shù)據(jù)庫的故障恢復(fù)。 6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫管理系統(tǒng)提供對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。 （4）數(shù)據(jù)庫管理員（DBA）：對數(shù)據(jù)庫進行規(guī)劃、設(shè)計、維護、監(jiān)視等的專業(yè)管理人員。 （5）數(shù)據(jù)庫系統(tǒng)（DBS）：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。 （6）數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。 *：數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。 2、數(shù)據(jù)庫系統(tǒng)的發(fā)展 數(shù)據(jù)庫管理發(fā)展至今已經(jīng)歷了三個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。 下表是數(shù)據(jù)管理三個階段的比較： 人工管理階段 文件系統(tǒng)階段 數(shù)據(jù)庫系統(tǒng)階段 背 景 應(yīng)用背景 科學(xué)計算 科學(xué)計算、管理 大規(guī)模管理 硬件背景 無直接存取存儲設(shè)備 磁盤、磁鼓 大容量磁備盤 軟件背景 沒有操作系統(tǒng) 有文件系統(tǒng) 有數(shù)據(jù)庫管理系統(tǒng) 處理方式 批處理 聯(lián)機實時處理、批處理 聯(lián)機實時處理、分布處理、批處理 特 點 數(shù)據(jù)的管理者 用戶（程序員） 文件系統(tǒng) 數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)面向的對象 某一應(yīng)用程序 某一應(yīng)用 現(xiàn)實世界 數(shù)據(jù)的共享程度 無共享，冗余度極大 共享性差，冗余度大 共享性高，冗余度小 數(shù)據(jù)的獨立性 不獨立，完全依賴于程序 獨立性差 具有高度的物理獨立性和一定的邏輯獨立性 數(shù)據(jù)的結(jié)構(gòu)化 無結(jié)構(gòu) 記錄內(nèi)有結(jié)構(gòu)，整體無結(jié)構(gòu) 整體結(jié)構(gòu)化，用數(shù)據(jù)模型描述 數(shù)據(jù)控制能力 應(yīng)用程序自己控制 應(yīng)用程序自己控制 由數(shù)據(jù)庫管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)能力 3、數(shù)據(jù)庫系統(tǒng)的基本特點 （1）數(shù)據(jù)的高集成性。 （2）數(shù)據(jù)的高共享性與低冗余性。 *：數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余，但無法避免一切冗余。 （3）數(shù)據(jù)獨立性：數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中數(shù)據(jù)獨立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與存取方式的改變不會影響應(yīng)用程序。 數(shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性兩級。 1）物理獨立性：物理獨立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲結(jié)構(gòu)，存取方式等）的改變，如存儲設(shè)備的更換、物理存儲的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化。 2）邏輯獨立性：數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨立性。 （4）數(shù)據(jù)統(tǒng)一管理與控制。 數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個方面： 1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。 2）數(shù)據(jù)的安全性保護：檢查數(shù)據(jù)庫訪問者以防止非法訪問。 3）并發(fā)控制：控制多個應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。 4、數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 （1）數(shù)據(jù)庫系統(tǒng)的三級模式： 1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。 2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。 3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級上，它還未深入到設(shè)備級上（如磁盤及磁盤操作）。內(nèi)模式對一般用戶是透明的，但它的設(shè)計直接影響數(shù)據(jù)庫的性能。 （2）數(shù)據(jù)庫系統(tǒng)的兩級映射： 1）概念模式/內(nèi)模式的映射：實現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)庫的存儲結(jié)構(gòu)發(fā)生變化時，通過修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨立性。 2）外模式/概念模式的映射：實現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式發(fā)生變化時，通過修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨立性。 2.2 數(shù)據(jù)模型 1、數(shù)據(jù)模型 （1）數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示與操作提供一個抽象的框架。 （2）數(shù)據(jù)模型所描述的內(nèi)容有三個部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。 1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是所研究的對象類型的集合，包括與數(shù)據(jù)類型、內(nèi)容、性質(zhì)有關(guān)的對象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對象。它用于描述系統(tǒng)的靜態(tài)特性。 2）數(shù)據(jù)操作：數(shù)據(jù)操作是對數(shù)據(jù)庫中各種對象（型）的實例（值）允許執(zhí)行的操作的集合，包括操作的含義、符號、操作規(guī)則及實現(xiàn)操作的語句等。它用于描述系統(tǒng)的動態(tài)特性。 3）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號數(shù)據(jù)模型的數(shù)據(jù)庫狀態(tài)及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。 （3）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類： 1）概念數(shù)據(jù)模型：簡稱概念模型，是對客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫。概念模型主要有：E-R模型(實體聯(lián)系模型)、擴充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。 2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn)。邏輯數(shù)據(jù)模型主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取? 3）物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計算機物理表示的模型，此模型給出了數(shù)據(jù)模型在計算機上物理結(jié)構(gòu)的表示。 2、實體聯(lián)系模型及E-R圖 （1）E-R模型的基本概念： 1）實體：現(xiàn)實世界中的事物。 2）屬性：事物的特性。 3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。 E-R模型三個基本概念之間的聯(lián)接關(guān)系：1）實體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）實體（集）與聯(lián)系。 *：E-R模型的基本成分是實體和聯(lián)系。 （2）E-R模型的圖示法： 1）實體集：用矩形表示。 2）屬性：用橢圓形表示。 3）聯(lián)系：用菱形表示。 4）實體集與屬性間的聯(lián)接關(guān)系：用無向線段表示。 5）實體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。 （3）數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。 1）層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點：A、每棵樹有且僅有一個無雙親結(jié)點，稱為根；B、樹中除根外所有結(jié)點有且僅有一個雙親。 2）網(wǎng)狀模型是層次模型的一個特例，從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。 3）關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關(guān)系。 二維表的表框架由n個命名的屬性組成，n稱為屬性元數(shù)。每個屬性有一個取值范圍稱為值域。表框架對應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實際上，一個元組是由n個元組分量所組成，每個元組分量是表框架中每個屬性的 投影值。 學(xué)號 姓名 性別 出生年月 班級 籍貫 2007102 張潔然 男 07-07-88 07動畫1班 天津 2007203 李一明 男 05-01-87 07播音5班 廣西南寧 2007305 王 麗 女 04-09-88 07管理4班 遼寧沈陽 2007406 劉 宏 男 10-11-88 07新聞3班 江蘇南京 *：同一個關(guān)系模型的任兩個元組值不能完全相同。 主碼：或稱為關(guān)鍵字、主鍵，簡稱碼、鍵，表中的一個屬性或幾個屬性的組合、其值能唯一地標(biāo)識表中一個元組的，稱為關(guān)系的主碼或關(guān)鍵字。例如，學(xué)生的學(xué)號。主碼屬性不能取空值。 外部關(guān)鍵字：或稱為外鍵，在一個關(guān)系中含有與另一個關(guān)系的關(guān)鍵字相對應(yīng)的屬性組稱為該關(guān)系的外部關(guān)鍵字。外部關(guān)鍵字取空值或為外部表中對應(yīng)的關(guān)鍵字值。例如，在學(xué)生表中含有的所屬班級名字，是班級表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。 （4）關(guān)系中的數(shù)據(jù)約束： 1）實體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因為主鍵是唯一決定元組的，如為空值則其唯一性就成為不可能的了。 2）參照完整性約束：關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，即在關(guān)系中的外鍵要么是所關(guān)聯(lián)關(guān)系中實際存在的元組，要么為空值。 3）用戶定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。例如某個屬性的取值范圍在0—100之間等。 3、從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型 數(shù)據(jù)庫的邏輯設(shè)計的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫管理系統(tǒng)）中的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實體與聯(lián)系都可以表示成關(guān)系，E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實體集也可以轉(zhuǎn)換成關(guān)系。 2.3 關(guān)系代數(shù) 1、關(guān)系的數(shù)據(jù)結(jié)構(gòu) 關(guān)系是由若干個不同的元組所組成，因此關(guān)系可視為元組的集合。n元關(guān)系是一個n元有序組的集合。 關(guān)系模型的基本運算：1）插入；2）刪除；3)修改；4）查詢（包括投影、選擇、笛卡爾積運算）。 2、關(guān)系操縱 關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四種操作。 3、集合運算及選擇、投影、連接運算 （1）并（∪）：關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合。 （2）差（－）：關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合。 （3）交（∩）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S的元組構(gòu)成的集合。 （4）廣義笛卡爾積（）：設(shè)關(guān)系R和S的屬性個數(shù)分別為n、m，則R和S的廣義笛卡爾 積是一個有（n+m）列的元組的集合。每個元組的前n列來自R的一個元組，后m列來自S 的一個元組，記為RS。 *：根據(jù)笛卡爾積的定義：有n元關(guān)系R及m元關(guān)系S，它們分別有p、q個元組，則關(guān)系R與S經(jīng)笛卡爾積記為RS，該關(guān)系是一個n+m元關(guān)系，元組個數(shù)是pq，由R與S的有序組組合而成。 例：有兩個關(guān)系R和S，分別進行并、差、交和廣義笛卡爾積運算。 （5）在關(guān)系型數(shù)據(jù)庫管理系統(tǒng)中，基本的關(guān)系運算有選擇、投影與聯(lián)接三種操作： 1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那些符合指定條件的記錄挑出來。 2）投影：投影是從所有字段中選取一部分字段及其值進行操作，它是一種縱向操作。 3）聯(lián)接：聯(lián)接將兩個關(guān)系模式拼接成一個更寬的關(guān)系模式，生成的新關(guān)系中包含滿足聯(lián)接條件的元組。 2.4 數(shù)據(jù)庫設(shè)計方法和步驟 （1）數(shù)據(jù)庫設(shè)計階段包括：需求分析、概念分析、邏輯設(shè)計、物理設(shè)計。 （2）數(shù)據(jù)庫設(shè)計的每個階段都有各自的任務(wù)： 1）需求分析階段：這是數(shù)據(jù)庫設(shè)計的第一個階段，任務(wù)主要是收集和分析數(shù)據(jù)，這一階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計概念結(jié)構(gòu)的基礎(chǔ)。 2）概念設(shè)計階段：分析數(shù)據(jù)間內(nèi)在語義關(guān)聯(lián)，在此基礎(chǔ)上建立一個數(shù)據(jù)的抽象模型，即形成E-R圖。 *：數(shù)據(jù)庫概念設(shè)計的過程包括選擇局部應(yīng)用、視圖設(shè)計和視圖集成。 3）邏輯設(shè)計階段：將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。 4）物理設(shè)計階段：對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度及有效利用存儲空間。 第三講 軟件工程基礎(chǔ) 3.1 軟件工程基本概念 1、軟件的相關(guān)概念 計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 軟件的特點包括：1）軟件是一種邏輯實體，而不是物理實體，具有抽象性；2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；3）軟件在運行、使用期間不存在磨損、老化問題；4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會因素。 2、軟件危機與軟件工程 軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。具體的說，在軟件開發(fā)和維護過程中，軟件危機主要表現(xiàn)在： 1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生。 2）軟件開發(fā)成本和進度無法控制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生。 3）軟件質(zhì)量難以保證。 4）軟件不可維護或維護程度非常低。 5）軟件的成本不斷提高。 6）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長。 總之，可以將軟件危機可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。 軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。軟件工程的目的就是要建造一個優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點： 1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。 2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟學(xué)。 軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程，它包括3個要素：方法、工具和過程。方法是完成軟件工程項目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。 軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。 3、軟件生命周期 軟件生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。 軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護三個階段： 1）軟件定義階段：包括制定計劃和需求分析。 制定計劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計劃。 需求分析：對待開發(fā)軟件提出的需求進行分析并給出詳細的定義。 2）軟件開發(fā)階段： 軟件設(shè)計：分為概要設(shè)計和詳細設(shè)計兩個部分。 軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。 軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分。 3）軟件運行維護階段：軟件投入運行，并在使用中不斷地維護，進行必要的擴充和刪改。 *：軟件生命周期中所花費最多的階段是軟件運行維護階段。 4、軟件工程的目標(biāo)和與原則 （1）軟件工程目標(biāo)：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、 可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 （2）軟件工程需要達到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用。 （3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 1)抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細節(jié)，采用分層次抽象，自頂向下，逐層細化的辦法控制軟件開發(fā)過程的復(fù)雜性。 2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實現(xiàn)細節(jié)隱蔽起來，使模塊接口盡量簡單。 3）模塊化：模塊是程序中相對獨立的成分，一個獨立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過大會使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會導(dǎo)致整個系統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。 4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強的內(nèi)聚性。 5）確定性：軟件開發(fā)過程中所有概念的表達應(yīng)是確定、無歧義且規(guī)范的。 6）一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。 7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實現(xiàn)系統(tǒng)所需的功能。 8）可驗證性：應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性。 5、軟件開發(fā)工具與軟件開發(fā)環(huán)境 (1)軟件開發(fā)工具 軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進步和完善，促進軟件開發(fā)的高速度和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟件工程方法提供了自動的或半自動的軟件支撐環(huán)境。同時，軟件開發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難以有效的實施。 （2）軟件開發(fā)環(huán)境 軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合。 計算機輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開發(fā)機器和一個存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。 3.2 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。 1、需求分析 需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）面向?qū)ο蟮姆治龇椒ā? *：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題。 *：需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個步驟進行。 2、結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用。 結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判定表。 數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。 上圖是數(shù)據(jù)流圖的基本圖形元素： 加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。 數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。 存儲文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。 源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。 畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細化，完善求精。 下圖是一個數(shù)據(jù)流圖的示例： 數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。 *：數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。 *：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。 3、軟件需求規(guī)格說明書（SRS） 軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細的功能和行為描述、性能需求和設(shè)計約束的說明、合適的驗收標(biāo)準(zhǔn)，給出對目標(biāo)軟件的各種需求。 3.3 結(jié)構(gòu)化設(shè)計方法 1、軟件設(shè)計的基礎(chǔ) *：需求分析主要解決“做什么”的問題，而軟件設(shè)計主要解決“怎么做”的問題。 從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。 結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。 數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。 接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。 過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。 從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計和詳細設(shè)計。 概要設(shè)計：又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式。 詳細設(shè)計：確定每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。 軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性。 1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他細節(jié)。 2）模塊化。解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對獨立但又不相互關(guān)聯(lián)的模塊的過程。 3）信息隱蔽。每個模塊的實施細節(jié)對于其他模塊來說是隱蔽的。 4）模塊獨立性。軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其他的模塊的接口是簡單的。 *：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨立性。 模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨立性的兩個定性指標(biāo)。 內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。 *：按內(nèi)聚性由弱到強排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。 耦合性：是模塊間互相連接的緊密程度的度量。 *：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。 一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。 在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。 2、總體設(shè)計（概要設(shè)計）和詳細設(shè)計 （1）總體設(shè)計（概要設(shè)計） 軟件概要設(shè)計的基本任務(wù)是：1）設(shè)計軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計；3）編寫概要設(shè)計文檔；4）概要設(shè)計文檔評審。 常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符： 模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。 經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖： 它們的含義分別是： 傳入模塊：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級模塊。 傳出模塊：從上級模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。 變換模塊：從上級模塊取得數(shù)據(jù)，進行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級模塊。 協(xié)調(diào)模塊：對所有下屬模塊進行協(xié)調(diào)和管理的模塊。 程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語列舉如下： 深度：表示控制的層數(shù)。 上級模塊、從屬模塊：上、下兩層模塊a和b，且有a調(diào)用b，則a是上級模塊，b是從屬模塊。 寬度：整體控制跨度（最大模塊數(shù)的層）的表示。 扇入：調(diào)用一個給定模塊的模塊個數(shù)。 扇出：一個模塊直接調(diào)用的其他模塊數(shù)。 原子模塊：樹中位于葉子結(jié)點的模塊。 面向數(shù)據(jù)流的設(shè)計方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。 數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。 A、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。 B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問題的工作機理是接受一項事務(wù)，根據(jù)事務(wù)處理的特點和性質(zhì)，選擇分派一個適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。 （2）詳細設(shè)計 詳細設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。 *：詳細設(shè)計的任務(wù)是確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。 常用的過程設(shè)計（即詳細設(shè)計）工具有以下幾種： 圖形工具：程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。 表格工具：判定表。 語言工具：PDL（偽碼） 3.4 軟件測試 1、軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。 *：軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯誤，不能也不可能證明程序沒有錯誤。軟件測試的關(guān)鍵是設(shè)計測試用例，一個好的測試用例能找到迄今為止尚未發(fā)現(xiàn)的錯誤。 2、軟件測試方法：靜態(tài)測試和動態(tài)測試。 靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進行。 動態(tài)測試：是基于計算機的測試，主要包括白盒測試方法和黑盒測試方法。 （1）白盒測試 白盒測試方法也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設(shè)計規(guī)格要求。 白盒測試的基本原則：保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊所有判斷的每一分支至少執(zhí)行一次；保證所測模塊每一循環(huán)都在邊界條件和一般條件