【重点】计算机二级公共基础重点
第一章數據結構與算法
1.1算法
1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟，方法的一種描述。
*：算法不等于程序，也不等于計算方法。程序的編制不可能優于算法的設計。
2、算法的基本特征
（1）可行性。針對實際問題而設計的算法，執行后能夠得到滿意的結果。
1015+1-1015=0
1015-1015+1=1
（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。算法必須在有限的時間內完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。
（4）擁有足夠的情報（信息）。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這就是算法執行的起點或依據。因此，一個算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯誤時，算法將無法執行或執行有錯。一般說來，當算法擁有足夠的情報時，此算法才是有效的；而當提供的情報不夠時，算法可能無效。
*：綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。
3、算法復雜度主要包括時間復雜度和空間復雜度。（讀熟）
（1）算法時間復雜度是指執行算法所需要的計算工作量，可以用執行算法的過程中所需基本運算的執行次數來度量。
（2）算法空間復雜度是指執行這個算法所需要的內存空間。
1.2數據結構的基本概念
1、數據結構是指相互有關聯的數據元素的集合。
2、數據結構主要研究和討論以下三個方面的問題：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。
數據的邏輯結構包含：1）表示數據元素的信息；2）表示各數據元素之間的前后件關系。
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。
數據的存儲結構有順序、鏈接、索引等。
1）順序存儲。（數組最大）它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
2）鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構。
3）索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
*：數據的邏輯結構反映數據元素之間的邏輯關系，數據的存儲結構（也稱數據的物理結構）是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以采用不同的存儲結構，但影響數據處理效率。
（3）對各種數據結構進行的運算。
3、數據結構的圖形表示
一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。在數據結構的圖形表示中，對于數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，并簡稱為結點；為了進一步表示各數據元素之間的前后件關系，對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。
4、數據結構分為兩大類型：線性結構和非線性結構。
（1）線性結構（非空的數據結構）條件：1）有且只有一個根結點；2）每一個結點最多有一個前件，也最多有一個后件。
*：常見的線性結構有線性表、棧、隊列和線性鏈表等。
（2）非線性結構：不滿足線性結構條件的數據結構。
*：常見的非線性結構有樹、二叉樹和圖等。
1.3線性表及其順序存儲結構（讀熟）
1、線性表由一組數據元素構成，數據元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。
2、線性表（數組）的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
*：由此可以看出，在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結點的存儲地址。
3、順序表的插入、刪除運算
（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結束后，第i個位置就被空出，然后將新元素插入到第i項。插入結束后，線性表的長度就增加了1。
*：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。在最壞情況下，需要移動表中的n個元素。
（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束后，線性表的長度就減小了1。
*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。在最壞情況下，需要移動表中的n-1個元素。
1.4棧和隊列
1、棧及其基本運算
棧是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數據的。棧具有記憶作用。
棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）（查找）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。
棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。
棧內的元素個數計算：TOP-BOTTOM+1，其中BOTTOM>=1，如果棧當中TOP=BOTTOM=0說明棧是空的。
2、隊列及其基本運算（類：火車）
隊列是指允許在一端（隊尾）進行插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。隊列是“先進先出”或“后進后出”的線性表。
隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。
循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。
循環隊列元素個數計算：循環隊列中元素的個數=rear（尾）-front（頭）。Rear-front為正數時，便是循環隊列的元素個數，為負數時，需要再加上循環隊列的容量。為零時，可以取以上兩種情況。
1.5線性鏈表
1、線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素；（2）線性表的順序存儲結構下，線性表的存儲空間不便于擴充；（3）線性表的順序存儲結構不便于對存儲空間的動態分配。
2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用于存放數據元素的值，稱為數據域；另一部分用于存放指針，稱為指針域，用于指向該結點的前一個或后一個結點（即前件或后件），如下圖所示：
?
線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。
在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其后件結點，而不能找到其前件結點。因此，在某些應用中，對于線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其后件結點，這種鏈表稱為雙向鏈表，如下圖所示：
?
3、線性鏈表的基本運算
（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。
*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現“上溢”現象。
（2）在線性鏈表中刪除包含指定元素的結點。
*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。
（3）將兩個線性鏈表按要求合并成一個線性鏈表。
（4）將一個線性鏈表按要求進行分解。
（5）逆轉線性鏈表。
（6）復制線性鏈表。
（7）線性鏈表的排序。
（8）線性鏈表的查找。
*：線性鏈表不能隨機存取。`?
4、循環鏈表及其基本運算
在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環鏈表。
與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭
結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。
下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：
循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由于在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。
*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，并實現空表與非空表的運算的統一。
1.6樹與二叉樹
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
（1）什么是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
?*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。
（2）二叉樹的基本性質
性質1在二叉樹的第k層上，最多有個結點。
例：一棵二叉樹第六層（根結點為第一層）的結點數最多為個。
性質2深度為m的二叉樹最多有個結點。
例：深度為5的二叉樹至多有個結點。
性質3在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。
例：某二叉樹中度數為2的結點有18個，則該二叉樹中有個葉子結點。
性質4具有n個結點的二叉樹，其深度至少為，其中表示取的整數部分。
例：具有88個結點的二叉樹，其深度至少為。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。
例：在深度為7的滿二叉樹中，葉子結點的個數為個。
完全二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。
*：根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：
?
完全二叉樹還具有如下兩個特性：
?性質5具有n個結點的完全二叉樹深度為。
例：具有90個結點的完全二叉樹的深度為。
性質6設完全二叉樹共有n個結點，如果從根結點開始，按層序（每一層從左到右）用自然數1，2，…，n給結點進行編號，則對于編號為k（k=1，2，…，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為INT(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的右子結點編號為2k+1；否則該結點無右子結點。
例：設一棵n個結點的完全二叉樹從根結點這一層開始，每一層上的結點按從左到右的順序存儲在數組A中，設某個結點在數組中的位置為i，則其父結點的位置是。
4、二叉樹的存儲結構
在計算機中，二叉樹通常采用鏈式存儲結構。
與線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結點），因此，用于存儲二叉樹的存儲結點的指針域有兩個：一個用于指向該結點的左子結點的存儲地址，稱為左指針域；另一個用于指向該結點的右子結點的存儲地址，稱為右指針域。
*：一般二叉樹通常采用鏈式存儲結構，對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。
5、二叉樹的遍歷
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
（1）前序遍歷（DLR）：若二叉樹為空，則結束返回。否則：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。
（2）中序遍歷（LDR）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。
（3）后序遍歷（LRD）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。
1.7查找技術
（讀）查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。
查找結果：（查找成功：找到；查找不成功：沒找到。）
平均查找長度：查找過程中關鍵字和給定值比較的平均次數。
1、順序查找
基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。
順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。
下列兩種情況下只能采用順序查找：
1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。
2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。
前提：必須在具有順序存儲結構的有序表中進行。
查找過程：
1）若中間項的值等于x，則說明已查到；
2）若x小于中間項的值，則在線性表的前半部分查找；
3）若x大于中間項的值，則在線性表的后半部分查找。
特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
*：二分法查找只適用于順序存儲的線性表，且表中元素必須按關鍵字有序（升序，但允許相鄰元素值相等）排列。對于無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）。
1.8排序技術
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調整為有序記錄序列的一種操作。
1、交換類排序法（方法：冒泡排序，快速排序）。
2、插入類排序法（方法：簡單插入排序，希爾排序）。
3、選擇類排序法（方法：簡單選擇排序，堆排序）。
總結：各種排序法比較：（會做題）
?
本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所占分值也比較大，約10分。
?
第二章程序設計基礎? ??背
2.1程序設計風格
程序設計的風格主要強調：“清晰第一，效率第二”。主要應注重和考慮下述一些因素：
（1）源程序文檔化。
1）符號名的命名。符號名能反映它所代表的實際東西，應有一定的實際含義。
2）程序的注釋。分為序言性注釋和功能性注釋。
序言性注釋：位于程序開頭部分，包括程序標題、程序功能說明、主要算法、接口說明、程序位置、開發簡歷、程序設計者、復審者、復審日期及修改日期等。
功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。
3）視覺組織。利用空格、空行、縮進等技巧使程序層次清晰。
（2）數據說明。1）數據說明的次序規范化；2）說明語句中變量安排有序化；3）使用注釋來說明復雜數據的結構。
（3）語句的結構。1）在一行內只寫一條語句；2）程序編寫應優先考慮清晰性；3）程序編寫要做到清晰第一，效率第二；4）在保證程序正確的基礎上再要求提高效率；5）避免使用臨時變量而使程序的可讀性下降；6）避免不必要的轉移；7）盡量使用庫函數；8）避免采用復雜的條件語句；9）盡量減少使用“否定”條件語句；10）數據結構要有利于程序的簡化；11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱蔽，確保每一個模塊的獨立性；13）從數據出發去構造程序；14）不要修補不好的程序，要重新編寫。
（4）輸入和輸出。1）對輸入數據檢驗數據的合法性；2）檢查輸入項的各種重要組合的合法性；3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單；4）輸入數據時，應允許使用自由格式；5）應允許缺省值；6）輸入一批數據時，最好使用輸入結束標志；7）在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數據輸入過程中和輸入結束時，應在屏幕上給出狀態信息；8）當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。
2.2結構化程序設計（面向過程的程序設計方法）
1、結構化程序設計方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語句。
（1）自頂向下。程序設計時，應先考慮總體，后考慮細節；先考慮全局目標，后考慮局部目標。不要一開始就過多追求眾多的細節，先從最上層總目標開始設計，逐步使問題具體化。
（2）逐步求精。對復雜問題，應設計一些子目標作過渡，逐步細化。
（3）模塊化。一個復雜問題，肯定是由若干稍簡單的問題構成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。
（4）限制使用goto語句。
2、結構化程序的基本結構：順序結構，選擇結構，重復結構。
1）順序結構。一種簡單的程序設計，即按照程序語句行的自然順序，一條語句一條語句地執行程序，它是最基本、最常用的結構。
2）選擇結構。又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列。
3）重復結構。又稱循環結構，可根據給定的條件，判斷是否需要重復執行某一相同的或類似的程序段。
僅僅使用順序、選擇和循環三種基本控制結構就足以表達各種其他形式結構，從而實現任何單入口/單出口的程序。
2.3面向對象的程序設計
客觀世界中任何一個事物都可以被看成是一個對象，面向對象方法的本質就是主張從客觀世界固有的事物出發來構造系統，提倡人們在現實生活中常用的思維來認識、理解和描述客觀事物，強調最終建立的系統能夠映射問題域。也就是說，系統中的對象及對象之間的關系能夠如實地反映問題域中固有的事物及其關系。
面向對象方法的主要優點：（1）與人類習慣的思維方法一致；（2）穩定性好；（3）可重用性好；（4）易于開發大型軟件產品；（5）可維護性好。
*：面向對象的程序設計主要考慮的是提高軟件的可重用性。
對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向對象的程序設計方法中的對象是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，由一組表示其靜態特征的屬性和它可執行的一組操作組成。
*：對象是屬性和方法的封裝體。
屬性即對象所包含的信息，它在設計對象時確定，一般只能通過執行對象的操作來改變。
操作描述了對象執行的功能，操作也稱為方法或服務。
*：操作是對象的動態屬性。
*：一個對象由對象名、屬性和操作三部分組成。
對象的基本特點：標識惟一性，分類性，多態性，封裝性，模塊獨立性好。
（1）標識惟一性。指對象是可區分的，并且由對象的內在本質來區分，而不是通過描述來區分。
（2）分類性。指可以將具有相同屬性的操作的對象抽象成類。
（3）多態性。指同一個操作可以是不同對象的行為。
（4）封裝性。從外面看只能看到對象的外部特性，即只需知道數據的取值范圍和可以對該數據施加的操作，根本無需知道數據的具體結構以及實現操作的算法。對象的內部，即處理能力的實行和內部狀態，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內部狀態，對象的內部狀態只能由其自身改變。
*：信息隱蔽是通過對象的封裝性來實現的。
（5）模塊獨立性好。對象是面向對象的軟件的基本模塊，它是由數據及可以對這些數據施加的操作所組成的統一體，而且對象是以數據為中心的，操作圍繞對其數據所需做的處理來設置，沒有無關的操作。從模塊的獨立性考慮，對象內部各種元素彼此結合得很緊密，內聚性強。
類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。
消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括：（1）接收消息的對象的名稱；（2）消息標識符，也稱消息名；（3）零個或多個參數。
*：在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發送消息。
繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。
*：類的繼承性是類之間共享屬性和操作的機制，它提高了軟件的可重用性。
多態性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現象。
本章應考點撥：本章在考試中會出現約1個題目，所占分值大約占2分，是出題量較小的一章。本章內容比較少，也很簡單，掌握住基本的概念就可以輕松應對考試了，所以在這部分丟分，比較可惜。
?
第三章軟件工程基礎
3.1軟件工程基本概念
1、軟件的相關概念
計算機軟件是包括程序、數據及相關文檔的完整集合。
軟件的特點包括：1）軟件是一種邏輯實體，而不是物理實體，具有抽象性；2）軟件的生產與硬件不同，它沒有明顯的制作過程；3）軟件在運行、使用期間不存在磨損、老化問題；4）軟件的開發、運行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟件移植的問題；5）軟件復雜性高，成本昂貴；6）軟件開發涉及諸多的社會因素。
2、軟件危機與軟件工程
軟件工程概念的出現源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發和維護過程中所遇到的一系列嚴重問題。具體的說，在軟件開發和維護過程中，軟件危機主要表現在：
1）軟件需求的增長得不到滿足。用戶對系統不滿意的情況經常發生。
2）軟件開發成本和進度無法控制。開發成本超出預算，開發周期大大超過規定日期的情況經常發生。
3）軟件質量難以保證。
4）軟件不可維護或維護程度非常低。
5）軟件的成本不斷提高。
6）軟件開發生產率的提高跟不上硬件的發展和應用需求的增長。
總之，可以將軟件危機可以歸結為成本、質量、生產率等問題。
軟件工程是應用于計算機軟件的定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程的目的就是要建造一個優良的軟件系統，它所包含的內容概括為以下兩點：
1）軟件開發技術，主要有軟件開發方法學、軟件工具、軟件工程環境。
2）軟件工程管理，主要有軟件管理、軟件工程經濟學。
軟件工程的主要思想是將工程化原則運用到軟件開發過程，它包括3個要素：方法、工具和過程。方法是完成軟件工程項目的技術手段；工具是支持軟件的開發、管理、文檔生成；過程支持軟件開發的各個環節的控制、管理。
軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。
3、軟件生命周期
軟件生命周期：軟件產品從提出、實現、使用維護到停止使用退役的過程。
軟件生命周期分為軟件定義、軟件開發及軟件運行維護三個階段：
1）軟件定義階段：包括制定計劃和需求分析。
制定計劃：確定總目標；可行性研究；探討解決方案；制定開發計劃。
需求分析：對待開發軟件提出的需求進行分析并給出詳細的定義。
2）軟件開發階段：
軟件設計：分為概要設計和詳細設計兩個部分。
軟件實現：把軟件設計轉換成計算機可以接受的程序代碼。
軟件測試：在設計測試用例的基礎上檢驗軟件的各個組成部分。
3）軟件運行維護階段：軟件投入運行，并在使用中不斷地維護，進行必要的擴充和刪改。
*：軟件生命周期中所花費最多的階段是軟件運行維護階段。
4、軟件工程的目標與原則
（1）軟件工程目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、
可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產品。
（2）軟件工程需要達到的基本目標應是：付出較低的開發成本；達到要求的軟件功能；取得較好的軟件性能；開發的軟件易于移植；需要較低的維護費用；能按時完成開發，及時交付使用。
（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。
1)抽象：抽象是事物最基本的特性和行為，忽略非本質細節，采用分層次抽象，自頂向下，逐層細化的辦法控制軟件開發過程的復雜性。
2）信息隱蔽：采用封裝技術，將程序模塊的實現細節隱蔽起來，使模塊接口盡量簡單。
3）模塊化：模塊是程序中相對獨立的成分，一個獨立的編程單位，應有良好的接口定義。模塊的大小要適中，模塊過大會使模塊內部的復雜性增加，不利于模塊的理解和修改，也不利于模塊的調試和重用；模塊太小會導致整個系統表示過于復雜，不利于控制系統的復雜性。
4）局部化：保證模塊間具有松散的耦合關系，模塊內部有較強的內聚性。
5）確定性：軟件開發過程中所有概念的表達應是確定、無歧義且規范的。
6）一致性：程序內外部接口應保持一致，系統規格說明與系統行為應保持一致。
7）完備性：軟件系統不丟失任何重要成分，完全實現系統所需的功能。
8）可驗證性：應遵循容易檢查、測評、評審的原則，以確保系統的正確性。
5、軟件開發工具與軟件開發環境
(1)軟件開發工具
軟件開發工具的完善和發展將促使軟件開發方法的進步和完善，促進軟件開發的高速度和高
質量。軟件開發工具的發展是從單項工具的開發逐步向集成工具發展的，軟件開發工具為軟件工程方法提供了自動的或半自動的軟件支撐環境。同時，軟件開發方法的有效應用也必須得到相應工具的支持，否則方法將難以有效的實施。
(2)軟件開發環境
軟件開發環境（或稱軟件工程環境）是全面支持軟件開發全過程的軟件工具集合。
計算機輔助軟件工程（CASE，ComputerAidedSoftwareEngineering）將各種軟件工具、開發機器和一個存放開發過程信息的中心數據庫組合起來，形成軟件工程環境。它將極大降低軟件開發的技術難度并保證軟件開發的質量。
3.2結構化分析方法
結構化方法的核心和基礎是結構化程序設計理論。
1、需求分析
需求分析方法有：1）結構化需求分析方法；2）面向對象的分析方法。
*：需求分析的任務就是導出目標系統的邏輯模型，解決“做什么”的問題。
*：需求分析一般分為需求獲取、需求分析、編寫需求規格說明書和需求評審四個步驟進行。
2、結構化分析方法
結構化分析方法是結構化程序設計理論在軟件需求分析階段的應用。
結構化分析方法的實質：著眼于數據流，自頂向下，逐層分解，建立系統的處理流程，以數據流圖和數據字典為主要工具，建立系統的邏輯模型。
結構化分析的常用工具：1）數據流圖（DFD）；2）數據字典（DD）；3）判定樹；4）判定表。
數據流圖以圖形的方式描繪數據在系統中流動和處理的過程，它反映了系統必須完成的邏輯功能，是結構化分析方法中用于表示系統邏輯模型的一種工具。
下圖是數據流圖的基本圖形元素：
加工（轉換）：輸入數據經加工變換產生輸出。
數據流：沿箭頭方向傳送數據的通道，一般在旁邊標注數據流名。
存儲文件（數據源）：表示處理過程中存放各種數據的文件。
源，潭：表示系統和環境的接口，屬系統之外的實體。
畫數據流圖的基本步驟：自外向內，自頂向下，逐層細化，完善求精。
下圖是一個數據流圖的示例：
數據字典：對所有與系統相關的數據元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統分析員對于輸入、輸出、存儲成分和中間計算結果有共同的理解。
*：數據字典的作用是對數據流圖中出現的被命名的圖形元素的確切解釋。
*：數據字典是結構化分析方法的核心。
3、軟件需求規格說明書（SRS）
軟件需求規格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細的功能和行為描述、性能需求和設計約束的說明、合適的驗收標準，給出對目標軟件的各種需求。
軟件需求規格說明書應具有以下特點：1）正確性；2）無歧義性；3）完整性；4）可驗證性；5）一致性；6）可理解性；7）可修改性；8）可追蹤性，其中最重要的特點是無歧義性。
3.3結構化設計方法
1、軟件設計的基礎
*：需求分析主要解決“做什么”的問題，而軟件設計主要解決“怎么做”的問題。
從技術觀點來看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計。
結構設計：定義軟件系統各主要部件之間的關系。
數據設計：將分析時創建的模型轉化為數據結構的定義。
接口設計：描述軟件內部、軟件和協作系統之間以及軟件與人之間如何通信。
過程設計：把系統結構部件轉換成軟件的過程性描述。
從工程角度來看，軟件設計分兩步完成，即概要設計和詳細設計。
概要設計：又稱結構設計，將軟件需求轉化為軟件體系結構，確定系統級接口、全局數據結構或數據庫模式。
詳細設計：確定每個模塊的實現算法和局部數據結構，用適當方法表示算法和數據結構的細節。
軟件設計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性。
1）抽象。抽象是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節。
2）模塊化。解決一個復雜問題時自頂向下逐步把軟件系統劃分成一個個較小的、相對獨立但又不相互關聯的模塊的過程。
3）信息隱蔽。每個模塊的實施細節對于其他模塊來說是隱蔽的。
4）模塊獨立性。軟件系統中每個模塊只涉及軟件要求的具體的子功能，而和軟件系統中其他的模塊的接口是簡單的。
*：模塊分解的主要指導思想是信息隱蔽和模塊獨立性。
模塊的耦合性和內聚性是衡量軟件的模塊獨立性的兩個定性指標。在結構化程序設計中，模塊劃分的原則是：模塊內具有高內聚度，模塊間具有低耦合度。
內聚性：是一個模塊內部各個元素間彼此結合的緊密程度的度量。
*：按內聚性由弱到強排列，內聚可以分為以下幾種：偶然內聚、邏輯內聚、時間內聚、過程內聚、通信內聚、順序內聚及功能內聚。
耦合性：是模塊間互相連接的緊密程度的度量。
*：按耦合性由高到低排列，耦合可以分為以下幾種：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合以及非直接耦合。
一個設計良好的軟件系統應具有高內聚、低耦合的特征。
2、總體設計（概要設計）和詳細設計
（1）總體設計（概要設計）
軟件概要設計的基本任務是：1）設計軟件系統結構；2）數據結構及數據庫設計；3）編寫概要設計文檔；4）概要設計文檔評審。
常用的軟件結構設計工具是結構圖，也稱程序結構圖。程序結構圖的基本圖符：
?模塊用一個矩形表示，箭頭表示模塊間的調用關系。在結構圖中還可以用帶注釋的箭頭表示模塊調用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數據信息。
經常使用的結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協調模塊。其表示形式如下圖：
它們的含義分別是：
傳入模塊：從下屬模塊取得數據，經處理再將其傳送給上級模塊。
傳出模塊：從上級模塊取得數據，經處理再將其傳送給下屬模塊。
變換模塊：從上級模塊取得數據，進行特定的處理，轉換成其他形式，再傳送給上級模塊。
協調模塊：對所有下屬模塊進行協調和管理的模塊。
程序結構圖的有關術語列舉如下：
深度：表示控制的層數。
上級模塊、從屬模塊：上、下兩層模塊a和b，且有a調用b，則a是上級模塊，b是從屬模塊。
寬度：整體控制跨度（最大模塊數的層）的表示。
扇入：調用一個給定模塊的模塊個數。
扇出：一個模塊直接調用的其他模塊數。
原子模塊：樹中位于葉子結點的模塊。
下圖是一個程序結構圖的示例：
面向數據流的設計方法定義了一些不同的映射方法，利用這些方法可以把數據流圖變換成結構圖表示軟件的結構。
數據流的類型：大體可以分為兩種類型，變換型和事務型。
A、變換型：變換型數據處理問題的工作過程大致分為三步，即取得數據、變換數據和輸出數據。變換型系統結構圖由輸入、中心變換、輸出三部分組成。
B、事務型：事務型數據處理問題的工作機理是接受一項事務，根據事務處理的特點和性質，選擇分派一個適當的處理單元，然后給出結果。
（2）詳細設計
詳細設計是為軟件結構圖中的每一個模塊確定實現算法和局部數據結構，用某種選定的表達工具表示算法和數據結構的細節。
*：詳細設計的任務是確定實現算法和局部數據結構，不同于編碼或編程。
常用的過程設計（即詳細設計）工具有以下幾種：
圖形工具：程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。
表格工具：判定表。
語言工具：PDL（偽碼）
3.4軟件測試
1、軟件測試定義：使用人工或自動手段來運行或測定某個系統的過程，其目的在于檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。
*：軟件測試的目的：盡可能地多發現程序中的錯誤，不能也不可能證明程序沒有錯誤。軟件測試的關鍵是設計測試用例，一個好的測試用例能找到迄今為止尚未發現的錯誤。
2、軟件測試方法：靜態測試和動態測試。
靜態測試：包括代碼檢查、靜態結構分析、代碼質量度量。不實際運行軟件，主要通過人工進行。
動態測試：是基于計算機的測試，主要包括白盒測試方法和黑盒測試方法。
（1）白盒測試（看得見程序內部，因此是測試內部結構和流程）
白盒測試方法也稱為結構測試或邏輯驅動測試。它是根據軟件產品的內部工作過程，檢查內部成分，以確認每種內部操作符合設計規格要求。
白盒測試的基本原則：保證所測模塊中每一獨立路徑至少執行一次；保證所測模塊所有判斷的每一分支至少執行一次；保證所測模塊每一循環都在邊界條件和一般條件下至少各執行一次；驗證所有內部數據結構的有效性。
*：白盒測試法的測試用例是根據程序的內部邏輯來設計的，主要用軟件的單元測試，主要方法有邏輯覆蓋、基本路徑測試等。
A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內部的邏輯結構為基礎的測試用例設計技術。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。
語句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執行一次。
路徑覆蓋：執行足夠的測試用例，使程序中所有的可能的路徑都至少經歷一次。
判定覆蓋：使設計的測試用例保證程序中每個判斷的每個取值分支（T或F）至少經歷一次。
條件覆蓋：設計的測試用例保證程序中每個判斷的每個條件的可能取值至少執行一次。
判斷-條件覆蓋：設計足夠的測試用例，使判斷中每個條件的所有可能取值至少執行一次，同時每個判斷的所有可能取值分支至少執行一次。
*：邏輯覆蓋的強度依次是：語句覆蓋<路徑覆蓋<判定覆蓋<條件覆蓋<判斷-條件覆蓋。
B、基本路徑測試。其思想和步驟是，根據軟件過程性描述中的控制流程確定程序的環路復雜性度量，用此度量定義基本路徑集合，并由此導出一組測試用例，對每一條獨立執行路徑進行測試。
（2）黑盒測試（看得見程序外部，因此是測試外部功能與特性）
黑盒測試方法也稱為功能測試或數據驅動測試。黑盒測試是對軟件已經實現的功能是否滿足需求進行測試和驗證。
黑盒測試主要診斷功能不對或遺漏、接口錯誤、數據結構或外部數據庫訪問錯誤、性能錯誤、初始化和終止條件錯誤。
黑盒測試不關心程序內部的邏輯，只是根據程序的功能說明來設計測試用例，主要方法有等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟件的確認測試。
A、等價類劃分法。這是一種典型的黑盒測試方法，它是將程序的所有可能的輸入數據劃分成若干部分（及若干等價類），然后從每個等價類中選取數據作為測試用例。
B、邊界值分析法。它是對各種輸入、輸出范圍的邊界情況設計測試用例的方法。
C、錯誤推測法。人們可以靠經驗和直覺推測程序中可能存在的各種錯誤，從而有針對性地編寫檢查這些錯誤的用例。
3、軟件測試過程一般按4個步驟進行：單元測試、集成測試、確認測試和系統測試。
（1）單元測試
單元測試是對軟件設計的最小單位——模塊（程序單元）進行正確性檢測的測試，目的是發現各模塊內部可能存在的各種錯誤。
單元測試根據程序的內部結構來設計測試用例，其依據是詳細設計說明書和源程序。單元測試的技術可以采用靜態分析和動態測試。對動態測試通常以白盒測試為主，輔之以黑盒測試。
單元測試的內容包括：模塊接口測試、局部數據結構測試、錯誤處理測試和邊界測試。
*：在進行單元測試時，要用一些輔助模塊去模擬與被測模塊相聯系的其他模塊，即為被測模塊設計和搭建驅動模塊和樁模塊。其中，驅動模塊相當于被測模塊的主程序，它接收測試數據，并傳給被測模塊，輸出實際測試結果；而樁模塊是模擬其他被調用模塊，不必將子模塊的所有功能帶入。
（2）集成測試
集成測試是測試和組裝軟件的過程，它是把模塊在按照設計要求組裝起來的同時進行測試，主要目的是發現與接口有關的錯誤。
集成測試的依據是概要設計說明書。
集成測試所涉及的內容包括：軟件單元的接口測試、全局數據結構測試、邊界條件和非法輸入的測試等。
集成測試通常采用兩種方式：非增量方式組裝與增量方式組裝。
非增量方式組裝：也稱為一次性組裝方式。首先對每個模塊分別進行模塊測試，然后再把所有模塊組裝在一起進行測試，最終得到要求的軟件系統。
增量方式組裝：又稱漸增式集成方式。首先對一個個模塊進行模塊測試，然后將這些模塊逐步組裝成較大的系統，在組裝的過程中邊連接邊測試，以發現連接過程中產生的問題。最后通過增殖逐步組裝成要求的軟件系統。增量方式組裝又包括自頂向下、自底向上、自頂向下與自底向上相結合等三種方式。
（3）確認測試
確認測試的任務是驗證軟件的有效性，即驗證軟件的功能和性能及其他特性是否與用戶的要求一致。
確認測試的主要依據是軟件需求規格說明書。
確認測試主要運用黑盒測試法。
（4）系統測試
系統測試的目的在于通過與系統的需求定義進行比較，發現軟件與系統定義不符合或與之矛盾的地方。
系統測試的測試用例應根據需求分析規格說明來設計，并在實際使用環境下來運行。
系統測試的具體實施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口測試、安全性測試等。
3.5程序的調試
程序調試的任務是診斷和改正程序中的錯誤，主要在開發階段進行，調試程序應該由編制源程序的程序員來完成。
程序調試的基本步驟：（1）錯誤定位；（2）糾正錯誤；（3）回歸測試。
*：軟件的調試后要進行回歸測試，防止引進新的錯誤。
軟件調試可分為靜態調試和動態調試。靜態調試主要是指通過人的思維來分析源程序代碼和排錯，是主要的調試手段，而動態調試是輔助靜態調試。
對軟件主要的調試方法可以采用：
（1）強行排錯法。主要方法有：通過內存全部打印來排錯；在程序特定部位設置打印語句；自動調試工具。
（2）回溯法。發現了錯誤，分析錯誤征兆，確定發現“癥狀”的位置。一般用于小程序。
（3）原因排除法。是通過演繹、歸納和二分法來實現的。
1）演繹法。根據已有的測試用例，設想及枚舉出所有可能出錯的原因作為假設；然后再用原始測試數據或新的測試，從中逐個排除不可能正確的假設；最后，再用測試數據驗證余下的假設確定出錯的原因。
2）歸納法。從錯誤征兆著手，通過分析它們之間的關系來找出錯誤。大致分四步：收集有關的數據；組織數據；提出假設；證明假設。
3）二分法。在程序的關鍵點給變量賦正確值，然后運行程序并檢查程序的輸出。如果輸出結果正確，則錯誤原因在程序的前半部分；反之，錯誤原因在程序的后半部分。
本章應考點撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎部分比較重要的一章。從出題的深度來看，本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此大家在復習本章時，重點應放在基本概念的記憶和基本原理的理解上。
?
第四章數據庫設計基礎
4.1數據庫系統的基本概念
1、數據、數據庫、數據管理系統
（1）數據：實際上就是描述事物的符號記錄。數據的特點：有一定的結構，有型與值之分。數據的型給出了數據表示的類型，如整型、實型、字符型等。而數據的值給出了符合給定型的值，如整型（INT）值15。
（2）數據庫（DB）：是數據的集合，具有統一的結構形式并存放于統一的存儲介質內，是多種應用數據的集成，并可被各個應用程序所共享。數據庫存放數據是按數據所提供的數據模式存放的，具有集成與共享的特點，亦即是數據庫集中了各種應用的數據，進行統一的構造和存儲，而使它們可被不同應用程序所使用。
（3）數據庫管理系統（DBMS）：一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等，是數據庫系統的核心。
數據庫管理系統功能：
1）數據模式定義。數據庫管理系統負責為數據庫構建模式，也就是為數據庫構建其數據框架。
2）數據存取的物理構建。數據庫管理系統負責為數據模式的物理存取與構建提供有效的存取方法與手段。
3）數據操縱。數據庫管理系統為用戶使用數據庫中的數據提供方便，它一般提供如查詢、插入、修改以及刪除數據的功能。此外，它自身還具有做簡單的算術運算及統計的能力，而且還可以與某些過程性語言結合，使其具有強大的過程性操作能力。
4）數據的完整性、安生性定義與檢查。數據庫中的數據具有內在語義上的關聯性與一致性，它們構成了數據的完整性，數據的完整性是保證數據庫中數據正確的必要條件，因此必須經常檢查以維護數據正確。數據庫中的數據具有共享性，而數據共享可能會引發數據的非法使用，因此必須要對數據正確使用做出必要的規定，并在使用時做檢查，這就是數據的安全性。數據完整性與安全性的維護是數據庫系統的基本功能。
5）數據庫的并發控制與故障恢復。數據庫是一個集成、共享的數據集合體，它能為多個應用程序服務，所以就存在著多個應用程序對數據庫的并發操作。在并發操作中如果不加控制和管理，多個應用程序間就會相互干擾，從而對數據庫中的數據造成破壞。因此，數據庫管理系統必須對多個應用程序的并發操作做必要的控制以保證數據不受破壞，這就是數據庫的并發控制。數據庫中的數據一旦遭到破壞，數據庫管理系統必須有能力及時進行恢復，這就是數據庫的故障恢復。
6）數據的服務。數據庫管理系統提供對數據庫中數據的多種服務功能，如數據拷貝、轉存、重組、性能監測、分析等。
（4）數據庫管理員（DBA）：對數據庫進行規劃、設計、維護、監視等的專業管理人員。
（5）數據庫系統（DBS）：由數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構成的運行實體。
（6）數據庫應用系統：由數據庫系統、應用軟件及應用界面三者組成。
*：數據庫技術的根本目標是解決數據的共享問題。
2、數據庫系統的發展
數據庫管理發展至今已經歷了三個階段：人工管理階段、文件系統階段和數據庫系統階段。
下表是數據管理三個階段的比較（此表只要有印象，不要求記憶）：
| ? | 人工管理階段 | 文件系統階段 | 數據庫系統階段 | |
| 背 景 | 應用背景 | 科學計算 | 科學計算、管理 | 大規模管理 |
| 硬件背景 | 無直接存取存儲設備 | 磁盤、磁鼓 | 大容量磁備盤 | |
| 軟件背景 | 沒有操作系統 | 有文件系統 | 有數據庫管理系統 | |
| 處理方式 | 批處理 | 聯機實時處理、批處理 | 聯機實時處理、分布處理、批處理 | |
| 特 點 | 數據的管理者 | 用戶（程序員） | 文件系統 | 數據庫管理系統 |
| 數據面向的對象 | 某一應用程序 | 某一應用 | 現實世界 | |
| 數據的共享程度 | 無共享，冗余度極大 | 共享性差，冗余度大 | 共享性高，冗余度小 | |
| 數據的獨立性 | 不獨立，完全依賴于程序 | 獨立性差 | 具有高度的物理獨立性和一定的邏輯獨立性 | |
| 數據的結構化 | 無結構 | 記錄內有結構，整體無結構 | 整體結構化，用數據模型描述 | |
| 數據控制能力 | 應用程序自己控制 | 應用程序自己控制 | 由數據庫管理系統提供數據安全性、完整性、并發控制和恢復能力 | |
3、數據庫系統的基本特點
（1）數據的高集成性。
（2）數據的高共享性與低冗余性。
*：數據庫系統可以減少數據冗余，但無法避免一切冗余。
（3）數據獨立性。
數據獨立性是數據與程序間的互不依賴性，即數據庫中數據獨立于應用程序而不依賴于應用程序。也就是說，數據的邏輯結構、存儲結構與存取方式的改變不會影響應用程序。
數據獨立性一般分為物理獨立性與邏輯獨立性兩級。
1）物理獨立性：物理獨立性即是數據的物理結構（包括存儲結構，存取方式等）的改變，如存儲設備的更換、物理存儲的更換、存取方式改變等都不影響數據庫的邏輯結構，從而不致引起應用程序的變化。
舉例：假設數據“母親”和數據“女兒”，這兩個數據無論存放在哪她們都是母女關系，不影響她們之間的邏輯關系，這叫物理獨立性。
2）邏輯獨立性：數據庫總體邏輯結構的改變，如修改數據模式、增加新的數據類型、改變數據間聯系等，不需要相應修改應用程序，這就是數據的邏輯獨立性。
（4）數據統一管理與控制。
數據統一管理與控制主要包含以下三個方面：
1）數據的完整性檢查：檢查數據庫中數據的正確性以保證數據的正確。
2）數據的安全性保護：檢查數據庫訪問者以防止非法訪問。
3）并發控制：控制多個應用的并發訪問所產生的相互干擾以保證其正確性。
4、數據庫系統的內部結構體系
（1）數據庫系統的三級模式：
1）概念模式：數據庫系統中全局數據邏輯結構的描述，是全體用戶（應用）公共數據視圖。
2）外模式：也稱子模式或用戶模式，它是用戶的數據視圖，也就是用戶所見到的數據模式，它由概念模式推導而出。
3）內模式：又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。內模式的物理性主要體現在操作系統及文件級上，它還未深入到設備級上（如磁盤及磁盤操作）。內模式對一般用戶是透明的，但它的設計直接影響數據庫的性能。
（2）數據庫系統的兩級映射：
1）概念模式/內模式的映射：實現了概念模式到內模式之間的相互轉換。當數據庫的存儲結構發生變化時，通過修改相應的概念模式/內模式的映射，使得數據庫的邏輯模式不變，其外模式不變，應用程序不用修改，從而保證數據具有很高的物理獨立性。
2）外模式/概念模式的映射：實現了外模式到概念模式之間的相互轉換。當邏輯模式發生變化時，通過修改相應的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應用程序不必修改，保證數據具有較高的邏輯獨立性。
4.2數據模型
1、數據模型
（1）數據模型的概念：是數據特征的抽象，它從抽象層次上描述了系統的靜態特征、動態行為和約束條件，為數據庫系統的信息表示與操作提供一個抽象的框架。
（2）數據模型所描述的內容有三個部分，它們是數據結構、數據操作與數據約束。
1）數據結構：數據結構是所研究的對象類型的集合，包括與數據類型、內容、性質有關的對象，以及與數據之間聯系有關的對象。它用于描述系統的靜態特性。
2）數據操作：數據操作是對數據庫中各種對象（型）的實例（值）允許執行的操作的集合，包括操作的含義、符號、操作規則及實現操作的語句等。它用于描述系統的動態特性。
3）數據的約束條件：數據的約束條件是一組完整性規則的集合。完整性規則是給定的數據模型中數據及其聯系所具有的制約和依存規則，用以限定符號數據模型的數據庫狀態及狀態的變化，以保證數據的正確、有效和相容。
（3）數據模型分為概念模型、邏輯數據模型和物理模型三類：
1）概念數據模型：簡稱概念模型，是對客觀世界復雜事物的結構描述及它們之間的內在聯系的刻畫。概念模型主要有：E-R模型(實體聯系模型)、擴充的E-R模型、面向對象模型及謂詞模型等。
2）邏輯數據模型：又稱數據模型，是一種面向數據庫系統的模型，該模型著重于在數據庫系統一級的實現。邏輯數據模型主要有：層次模型、網狀模型、關系模型、面向對象模型等。
3）物理數據模型：又稱物理模型，它是一種面向計算機物理表示的模型，此模型給出了數據模型在計算機上物理結構的表示。
2、實體聯系模型及E-R圖
（1）E-R模型的基本概念：
1）實體：現實世界中的事物。
2）屬性：事物的特性。
3）聯系：現實世界中事物間的關系。實體集的關系有一對一、一對多、多對多的聯系。
E-R模型三個基本概念之間的聯接關系：1）實體集（聯系）與屬性間的聯接關系；2）實體（集）與聯系。
*：E-R模型的基本成分是實體和聯系。
（2）E-R模型的圖示法：
1）實體集：用矩形表示。
2）屬性：用橢圓形表示。
3）聯系：用菱形表示。
4）實體集與屬性間的聯接關系：用無向線段表示。
5）實體集與聯系間的聯接關系：用無向線段表示。
下圖是一個E-R模型的圖示例：
（3）數據庫管理系統常見的數據模型有層次模型、網狀模型和關系模型三種。
?1）層次模型的基本結構是樹形結構，具有以下特點：A、每棵樹有且僅有一個無雙親結點，稱為根；B、樹中除根外所有結點有且僅有一個雙親。
?2）網狀模型是層次模型的一個特例，從圖論上看，網狀模型是一個不加任何條件限制的無向圖。
3）關系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關系。對關系的描述稱為關系模式，一個關系模式對應一個關系的結構。
二維表的表框架由n個命名的屬性組成，n稱為屬性元數。每個屬性有一個取值范圍稱為值域。表框架對應了關系的模式，在表框架中按行可以存放數據，每行數據稱為元組，實際上，一個元組是由n個元組分量所組成，每個元組分量是表框架中每個屬性的投影值，但元組中的每一個分量不能在進行分割。
| 學號 | 姓名 | 性別 | 出生年月 | 班級 | 籍貫 |
| 2007102 | 張潔然 | 男 | 07-07-88 | 07動畫1班 | 天津 |
| 2007203 | 李一明 | 男 | 05-01-87 | 07播音5班 | 廣西南寧 |
| 2007305 | 王麗 | 女 | 04-09-88 | 07通信4班 | 遼寧沈陽 |
*：同一個關系模型的任兩個元組值不能完全相同。
主碼：或稱為關鍵字、主鍵，簡稱碼、鍵。表中的一個屬性或幾個屬性的組合、其值能唯一地標識表中一個元組，稱為關系的主碼或關鍵字。例如，學生的學號。主碼屬性不能取空值。
外部關鍵字：或稱為外鍵，在一個關系中含有與另一個關系的關鍵字相對應的屬性組稱為該關系的外部關鍵字。外部關鍵字取空值或為外部表中對應的關鍵字值。例如，在學生表中含有的所屬班級名字，是班級表中的關鍵字屬性，它是學生表中的外部關鍵字。
（4）關系中的數據約束：
1）實體完整性約束：要求關系的主鍵中屬性值不能為空值，因為主鍵是唯一決定元組的，如為空值則其唯一性就成為不可能的了。
2）參照完整性約束：關系之間相互關聯的基本約束，不允許關系引用不存在的元組，即在關系中的外鍵要么是所關聯關系中實際存在的元組，要么為空值。
3）用戶定義的完整性約束：反映某一具體應用所涉及的數據必須滿足的語義要求。例如某個屬性的取值范圍在0—100之間等。
3、從E-R圖導出關系數據模型
數據庫的邏輯設計的主要工作是將E-R圖轉換成指定RDBMS（關系數據庫管理系統）中的關系模式。首先，從E-R圖到關系模式的轉換是比較直接的，實體與聯系都可以表示成關系，E-R圖中屬性也可以轉換成關系的屬性。實體集也可以轉換成關系。
4.3關系代數
1、關系的數據結構
關系是由若干個不同的元組所組成，因此關系可視為元組的集合。n元關系是一個n元有序組的集合。
關系模型的基本運算：1）插入；2）刪除；3)修改；4）查詢（包括投影、選擇、笛卡爾積運算）。
2、關系操縱
關系模型的數據操縱即是建立在關系上的數據操縱，一般有查詢、增加、刪除和修改四種操作。
3、集合運算及選擇、投影、連接運算
（1）并（∪）：將兩個以上表的行并到一起，去除相同的行。
（2）差（－）：在關系R中減去S有的行，保留的是S中沒有的行。運算的時候依次將兩個表的一行一行相減。
（3）交（∩）：求兩個以上表的公共行，前提是參與運算的表的結構必須相同。
（4）廣義笛卡爾積（×）：行與行的重新組合。
*：根據笛卡爾積的定義：有n元關系R及m元關系S，它們分別有p、q個元組，則關系R與S經笛卡爾積記為R×S，該關系是一個n+m元關系，元組個數是p×q，由R與S的有序組組合而成。
例：有兩個關系R和S，分別進行并、差、交和廣義笛卡爾積運算。
（5）在關系型數據庫管理系統中，基本的關系運算有選擇、投影與聯接三種操作：
1）選擇：選擇指的是從二維關系表的全部記錄中，把那些符合指定條件的記錄挑出來（選行）。
2）投影：投影是從所有字段中選取一部分字段及其值進行操作，它是一種縱向操作（投列）。
3）聯接：聯接將兩個關系模式拼接成一個更寬的關系模式，生成的新關系中包含滿足聯接條件的元組。
4.4數據庫設計方法和步驟
（1）數據庫設計階段包括：需求分析、概念分析、邏輯設計、物理設計。
（2）數據庫設計的每個階段都有各自的任務：
1）需求分析階段：這是數據庫設計的第一個階段，任務主要是收集和分析數據，這一階段收集到的基礎數據和數據流圖是下一步設計概念結構的基礎。
2）概念設計階段：分析數據間內在語義關聯，在此基礎上建立一個數據的抽象模型，即形成E-R圖。
*：數據庫概念設計的過程包括選擇局部應用、視圖設計和視圖集成。
3）邏輯設計階段：將E-R圖轉換成指定RDBMS中的關系模式。
4）物理設計階段：對數據庫內部物理結構作調整并選擇合理的存取路徑，以提高數據庫訪問速度及有效利用存儲空間。
本章應考點撥：本章在考試中一般出現2-4個小題。本章內容概括性強，比較抽象，難于理解，因此建議考生在復習的時候，首先熟讀講義，其次對數據庫系統的基本概念及原理等知識要注意理解、加強記憶。
?
另有本人整理的【真題21套】計算機二級公共基礎知識選擇題真題【含解析】來幫助大家提高自己，最后祝大家都取得好成績?~
?
資料整理不易，覺得有用的話請一鍵三連~?~建議收藏啊~
?
總結
以上是生活随笔為你收集整理的【重点】计算机二级公共基础重点的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端学习（932）：mouseenter
- 下一篇： 前端学习（1293）:系统模块path路