公共基礎(chǔ)部分

全國計算機等級考試——二級公共基礎(chǔ)知識部分目錄PAGE目錄第1章數(shù)據(jù)結(jié)構(gòu)與算法 11、算法 12、數(shù)據(jù)結(jié)構(gòu)的基本概念 23、線性表及其存儲結(jié)構(gòu) 24、棧和隊列 35、線性鏈表 36、樹與二叉樹 47、查找技術(shù) 58、排序技術(shù) 5第2章程序設(shè)計基礎(chǔ) 61、程序設(shè)計方法與風(fēng)格 62、結(jié)構(gòu)化程序設(shè)計 63、面向?qū)ο蟮某绦蛟O(shè)計 7第3章軟件工程基礎(chǔ) 71、軟件工程基礎(chǔ)概念 72、結(jié)構(gòu)化分析方法 83、結(jié)構(gòu)化設(shè)計方法 94、軟件測試 95、程序的調(diào)試 9第4章數(shù)據(jù)庫設(shè)計基礎(chǔ) 101、數(shù)據(jù)庫系統(tǒng)的基本概念 102、數(shù)據(jù)模型 113、關(guān)系代數(shù) 124、數(shù)據(jù)設(shè)計與管理 12 第1章數(shù)據(jù)結(jié)構(gòu)與算法PAGE5數(shù)據(jù)結(jié)構(gòu)與算法算法算法的概念：是指解題方案的準確而完整的描述。算法的基本特征：可行性確定性有窮性擁有足夠的情報算法的基本要素算法中對數(shù)據(jù)的運算和操作算術(shù)運算邏輯運算關(guān)系運算數(shù)據(jù)傳輸算法的控制結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）循環(huán)結(jié)構(gòu)算法設(shè)計基本方法列舉法：根據(jù)提出的問題列舉所有可能的情況，并用問題中給定的條件進行檢驗，找出答案。學(xué)用于解決“是否存在”或“有多少種可能”等類型的問題。歸納法：通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。遞推：指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。（本質(zhì)上也屬于歸納法）遞歸：將問題逐層分解，最后歸結(jié)為一些最簡單的問題。直接遞歸：一個算法P顯式調(diào)用自己間接遞歸：算法P調(diào)用另一算法Q，而算法Q又調(diào)用算法P。減半遞推技術(shù)：指將問題的規(guī)模減半，而問題的性質(zhì)不變（即減半）并重復(fù)進行（即遞推）?；厮莘ǎ和ㄟ^對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，每步試探成功則繼續(xù)，直至問題解決，否則換路線再試探。算法的復(fù)雜度算法的時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量。計算方法（P4）：用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)：算法的工作量＝f(n)其中n是問題的規(guī)模。同一問題規(guī)模下分析算法的工作量方法：平均性態(tài)（P5）：指用各種特定輸入下的基本運算次數(shù)的加權(quán)平均值來度量算法的工作量。最壞情況復(fù)雜性（P5）：指在規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。算法的空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)學(xué)科討論的三個問題：數(shù)據(jù)集合中各數(shù)據(jù)之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。研究數(shù)據(jù)結(jié)構(gòu)的目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量減少數(shù)據(jù)處理過程中占用的計算機存儲空間。什么是數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的概念：反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示（或指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合），至少應(yīng)包含以下信息：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，它有兩個要素：（P9）B=(D,R)D={1,2,3,4}R={(1,2),(2,3),(3,4)}數(shù)據(jù)元素的集合，通常記為D；數(shù)據(jù)元素集合上的關(guān)系（即反映D中各數(shù)據(jù)元素之間前后件的關(guān)系），通常記為R數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式（即數(shù)據(jù)的物理結(jié)構(gòu)）。常見的存儲結(jié)構(gòu)有4種：順序存儲、鏈式存儲、索引存儲和散列存儲。數(shù)據(jù)結(jié)構(gòu)的圖形表示(P11例1.8)線性結(jié)構(gòu)與非線性結(jié)構(gòu)：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度可分為兩大類型，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)：一個非空的數(shù)據(jù)結(jié)構(gòu)滿足以下兩個條件即為線性結(jié)構(gòu)，或稱線性表。線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還是線性結(jié)構(gòu)。常見的線性表如：線性表、線性鏈表、棧、隊列等。有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：不符合線性結(jié)構(gòu)規(guī)則的數(shù)據(jù)結(jié)構(gòu)稱非線性結(jié)構(gòu)。如樹、二叉樹和圖等。線性表及其順序存儲結(jié)構(gòu)線性表的基本概念線性表：由n(n>=0)個數(shù)據(jù)元素組成的一個有限序列，表中每一個數(shù)據(jù)元素除第一個外，有且只有一個前件，除最后一個外，有且只有一個后件。線性表也可以是一個空表，即n=0。線性表順序存儲兩個基本特點：線性表中所有元素所占的存儲空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。順序表：用順序存儲方式形成的線性表稱順序表，順序表的結(jié)構(gòu)簡單，適合存放元素不經(jīng)常變動的線性表。順序存儲方式：把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元中，可以實現(xiàn)隨機存取。順序表的插入運算：在順序表中插入元素，會使插入位置后的其它元素依次后移，如插入時系統(tǒng)為線性表開辟的存儲空間已滿，則會造成“上溢”錯誤。順序表較長時，插入運算的效率很低。順序表的刪除運算：刪除順序表的一個元素，會使刪除位置后的其它元素依次前移。順序表較長時，刪除運算的效率也很低。棧和隊列棧：只允許在一端進行插入與刪除元素操作的線性表稱“?！币卜Q“堆?！?。允許插入與刪除的一端稱“棧頂”，不允許進行插入與刪除的一端稱“棧底”。棧按照“先進后出、后進先出”的原則組織數(shù)據(jù)。棧的順序存儲：可以用一維數(shù)組作為棧的順序存儲空間，另需用一個變量作棧頂指針，記錄棧頂位置。棧的運算：入棧運算：往棧中插入一個元素。首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置。如棧頂指針已經(jīng)指向存儲空間的最后一個位置則棧滿，再進行入棧操作就會造成“上溢”錯誤。退棧（出棧）：從棧中刪除一個元素。首先將棧頂元素的值賦給一個指定的變量，然后將棧頂指針退一。如棧頂指針為0則?？?，如再進行退棧操作則會造成“下溢”錯誤。讀棧頂元素：將棧頂元素賦給一個指定的變量。讀棧操作不會改變棧頂指針，即不刪除棧頂元素。如棧頂指針為0則因?？斩x不到棧頂元素。隊列：允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為排頭（也稱隊頭）。隊列按照“先進先出、后進后出”的原則組織數(shù)據(jù)。隊列的順序存儲：隊列也可以用一維數(shù)組作為隊列的順序存儲空間。另需一個變量記錄隊尾位置（rear），另一個變量記錄排頭前一個位置(front)，還有一個變量記錄隊中元素個數(shù)。循環(huán)隊列：將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。循環(huán)隊列的初始狀態(tài)為空，即隊尾、排頭都指向數(shù)組的最后一個單元，隊列元素個數(shù)為0。循環(huán)隊列的運算：入隊運算：首先將隊尾加1（如超過最后一個單元位置時變?yōu)?），隊列元素記錄變量也加1，然后將新元素插入到隊尾指向的位置，當隊列非空，而隊尾等于排頭時則隊列已滿，再入隊就會“上溢”錯誤；退隊（出隊）運算：首先將排頭加1（如排頭超過最后一個單元位置時就變?yōu)?），隊列元素記錄變量減1，然后將排頭指向的元素值賦給指定的變量，當隊列為空時再進行退隊操作就會“下溢”錯誤。線性鏈表基本概念：指針：用來存放存儲位置的存儲單元（變量）稱指針。結(jié)點：假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每個數(shù)據(jù)結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。鏈式存儲方式：由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放指針的指針域兩部分構(gòu)成結(jié)點，指針域記錄前后結(jié)點的位置，形成像鏈條一樣的存儲方式稱為鏈式存儲方式。鏈式存儲方式中存儲單元可以是不連續(xù)的，但訪問必須順序進行。線性鏈表：用鏈式存儲結(jié)構(gòu)存儲線性表稱為線性鏈表。在鏈表中有一個頭結(jié)點（HEAD），它是為方便運算的實現(xiàn)而增加的。線性單鏈表：即指針域只記錄前結(jié)點位置或后結(jié)點位置形成的線性鏈表。線性雙向鏈表：即指針域同時記錄前后結(jié)點位置形成的線性鏈表。其中一個稱為左指針用于指向前件結(jié)點，另一個稱右指針，用于指向后件結(jié)點。帶鏈的棧和隊列：使用鏈式存儲結(jié)構(gòu)存儲棧和隊列。線性鏈表的基本運算：在線性鏈表中查找指定元素線性鏈表的插入線性鏈表的刪除循環(huán)鏈表循環(huán)鏈表：在鏈表中增加頭結(jié)點，并讓最后一個結(jié)點的指針批向頭結(jié)點，形成一個環(huán)狀鏈；基本運算：插入與刪除結(jié)點。樹與二叉樹樹：概念：每個結(jié)點只有一個前件（父結(jié)點），而后件（子結(jié)點）可以有多個。沒有前件的結(jié)點稱樹根，沒有后件的結(jié)點稱葉子。度：一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度，所有結(jié)點中的最大的度稱為樹的度。層：樹的結(jié)構(gòu)是分層的，樹的最大層次稱為樹的深度。子樹：以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。二叉樹：概念：只有一個根結(jié)點，每個結(jié)點最多只有兩棵子樹（左子樹與右子樹），這樣的樹稱二叉樹。基本性質(zhì)：性質(zhì)1：第k層上最多有2k-1(k>=1)個結(jié)點。性質(zhì)2：深度為m的二叉樹最多有2m-1個結(jié)點。性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。性質(zhì)4：具有n個結(jié)點的二叉樹中，其深度到少為(Log2N)+1的整數(shù)值。性質(zhì)5：具有n個結(jié)點的完全二叉樹的深度為[log2n]+1性質(zhì)6：設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每層從左到右）用自然數(shù)列給結(jié)點進行編號，則對于編號為k的結(jié)點有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點；若k>1則該結(jié)點的父結(jié)點編號為Int(k/2)。若2k<=n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點。若2k+1<=n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點，則該二叉樹稱滿二叉樹。滿二叉樹每層上的結(jié)點數(shù)都達到最大值，即第k層上有2k-1個結(jié)點，且深度為m的滿二叉樹有2m-1個結(jié)點。完全二叉樹：除最后一層外，每個層上的結(jié)點數(shù)均達到最大值，而最后一層上只缺少右邊的若干結(jié)點。完全二叉樹的葉子結(jié)點數(shù)為：總結(jié)點數(shù)－int(總結(jié)點數(shù)/2)二叉樹的存儲結(jié)構(gòu)：二叉樹通常用鏈式結(jié)構(gòu)存儲。二叉樹的遍歷：不重復(fù)地訪問二叉樹中所有結(jié)點稱遍歷。遍歷二叉樹的過程是一個遞歸的過程。前序遍歷：先訪問根結(jié)點，然后訪問左子樹，最好訪問右子樹。中序遍歷：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。后序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。查找技術(shù)順序查找：又稱順序搜索，指從第一個元素開始在線性表中查找指定的元素。對大的線性表順序查找的效率很低，但在下列兩種情況下只能采用順序查找：如果線性表為無序表；采用鏈式結(jié)構(gòu)的有序線性表。二分查找：從有序表的中間開始查找，如比中間小則在前半部分的中間再找，否則從后半部分的中間再找，重復(fù)上面的過程，直至找到指定的元素。二分查找只能查找順序存儲的有序表，查找效率比順序查找高得多，長度為n的有序線性線最壞情況下二分查找只要比較log2n次，而順序查找需比較n次。排序技術(shù)：指將一個無序序列整理成按值非遞減順序排列的有序序列。交換類排序法：指通過互相交換數(shù)據(jù)元素值方法進行排序。常見有以下兩種：冒泡排序法：依次掃描線性表，把表相阾兩個元素中較大的元素往后移（每次移動稱消去一個逆序），直到把最大的元素移到表尾，然后再重復(fù)上面過程，在剩下的線性表中進行排序，直到剩下的線性表為空。所以冒泡排序又稱下沉排序。假設(shè)線性表長度為n，冒泡排序的最壞情況需要經(jīng)過n(n-1)/2遍比較?？焖倥判蚍ǎ簭木€性表中選取一個元素T作為標準，把比T小的元素移到前面，比T大的元素移到后面，結(jié)果就將線性表分成了兩個子表，然后對子表分別重復(fù)上面的過程，直至各子表為空。具體實現(xiàn)如下：首先在表的第一、中間一個和最后一個元素中選取一個中項（設(shè)為p(k)元素），并用變量T記住P(k)的值，再將第一個元素移動到p(k)位置上，然后設(shè)置兩個指針I(yè)和j，I記錄表的起始位置，j記錄表的結(jié)束位置；將j逐漸減小，并不斷比較p(j)與T，如發(fā)現(xiàn)p(j)<T則P(j)移到p(i)位置上；將I逐漸增大，并不斷比較p(i)與T，如發(fā)現(xiàn)p(i)>T，將p(i)移動到p(j)位置上。不斷重復(fù)b)中的操作，直至指針I(yè)與j相等（即指向同一位置），將T移到p(i)位置上。插入類排序法：指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中而完成的排序操作。簡單插入排序法：把第一個元素看作一個有序子表。用T記住剩下線性表的第一個元素值。從有序子表最后一個元素開始掃描，把比T大的元素依次后移一個位置，直至發(fā)現(xiàn)不大于T的元素或沒有發(fā)現(xiàn)不大于T的元素為止，把T插入到有序子表中空出來的位置上，使有序子表長度加1。重復(fù)上面的操作，直至有序子表長度與線性表相同。排序效率與冒泡排序一樣，最壞情況下，長度為n的線性表使用簡單插入排序需要n(n-1)/2次比較。希爾排序法：將整個無序序列分割成若干個小的子序列，然后分別進行插入排序。具體實現(xiàn)時一般會先以序列的一半長度作為分割子序列單位，然后再逐次減小分割單位，直至分割單位為1。本排序的效率與所選取的增量序列有關(guān)，按上述增量最壞情況下希爾排序所需要的比較次數(shù)為O(n1.5)。選擇類排序法：掃描整個線性表，選出最小的元素將它交換到表的最前面；然后在剩下的子表中重復(fù)使用這個操作，直至子表為空。簡單選擇排序法：最壞情況下需要比較n(n-1)/2次堆排序法P38：最壞情況下，堆排序需要比較的次數(shù)為O(nlog2n)。*歸并排序：指將兩個或兩個以上的有序表組合成一個新的有序表。它的內(nèi)存量較前面幾種都要大。幾個補充算法分析：是指對一個算法的運行時間和占用空間做定量分析，目的是要降低算法的時間復(fù)雜度和空間復(fù)雜度，提高算法的執(zhí)行效率。*強連通圖：在有向圖中若任意兩個頂點都連通，則該圖為強連通圖。有n個頂點的強連通圖到少有n條邊。鏈表與順序表比較：順序表訪問方便，可以隨機訪問；鏈表插入刪除結(jié)點比順序方便。第2章程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)程序設(shè)計方法與風(fēng)格當今主導(dǎo)的程序設(shè)計風(fēng)格：清晰第一，效率第二。形成良好程序設(shè)計風(fēng)格：源程序文檔化數(shù)據(jù)說明的次序規(guī)范，變量安排有序，使用注釋。語句的結(jié)構(gòu)輸入和輸出盡可能方便用戶使用。結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計的原則自頂向下：程序設(shè)計時從總體到細節(jié)，從全局目標到局部目標。逐步求精：對復(fù)雜問題應(yīng)設(shè)計一些子目標作過渡，逐步細化。模塊化：總目標分解為人目標，再進一步分解為具體的小目標，每個小目標稱為一個模塊。限制使用goto語句。結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點順序結(jié)構(gòu)：是最基本、最常用的結(jié)構(gòu)，按程序語句的自然順序一條一條地執(zhí)行。選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)。根據(jù)設(shè)定的條件選擇其中一條分支來執(zhí)行相應(yīng)的語句序列。重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)。根據(jù)給定的條件，重復(fù)執(zhí)行同一相同或類似的程序段，直到允許循環(huán)的條件被破壞為止?？傊?，遵循結(jié)構(gòu)化程序的設(shè)計原則可以有以下優(yōu)點：易于理解使用和維護；提高編程工作的效率，降低開發(fā)成本。結(jié)構(gòu)化程序設(shè)計原則和方法的應(yīng)用使用順序、選擇和循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；選用的控制結(jié)構(gòu)只許有一個入口和一個出口；程序塊組成要容易識別，每塊只有一個入口和一個出口；使用基本控制結(jié)構(gòu)進行嵌套與組合來實現(xiàn)復(fù)雜結(jié)構(gòu)；用前后一致的方法來模擬三種基本結(jié)構(gòu)以外的控制結(jié)構(gòu)；嚴格控制GOTO語句的使用。面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蠓椒ǖ谋举|(zhì)：系統(tǒng)中的對象以及對象之間的關(guān)系能夠如實地反映問題域中固有事物及關(guān)系。面向?qū)ο竽Ｐ妥罨镜母拍顬閷ο蠛皖悺；驹恚菏褂矛F(xiàn)實世界的抽象地思考問題從而自然地解決問題。它強調(diào)模擬現(xiàn)實世界中的概念而不強調(diào)算法，鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用應(yīng)用領(lǐng)域的概念去思考。面向?qū)ο蠓椒ǖ膬?yōu)點：與人類習(xí)慣的思維方法一致，面向?qū)ο蟮暮诵氖菍ο?。穩(wěn)定性好可重用性好：可繼承父類的所有屬性和方法。易于開發(fā)大型軟件產(chǎn)品可維護性好穩(wěn)定性好容易修改容易理解易于測試和調(diào)試面向?qū)ο蠓椒ǖ幕靖拍顚ο螅╫bject）：應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何事物都可以作為對象，它既可以是具體的物理實體的抽象，也可以是人為的概念。對象的基本特點：標識惟一性分類性多態(tài)性封裝性模塊獨立性好類和實例類：指具有共同屬性、方法的對象的集合。實例：類的其中一個具體應(yīng)用就是一個實例。消息：實例之間相互傳遞的信息叫消息，傳送的消息實質(zhì)上是接受對象所具有的操作/方法名稱，有時還包括相應(yīng)參數(shù)。繼承：使用已有的類定義作基礎(chǔ)建立新類的定義技術(shù)。它是面向?qū)ο蠓椒ǖ囊粋€主要特征。繼續(xù)分為單繼承與多重繼承。單繼承：指一個類只允許有一個父類。多重繼承：指一個類允許有多個父類。多態(tài)性：指同樣的消息被不同的對象接受時可導(dǎo)致完全不同行動的現(xiàn)象。第3章軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件工程的基本概念軟件：是計算機系統(tǒng)中與硬件相互儲存的程序、數(shù)據(jù)及相關(guān)文檔的完整集合。所以軟件由機器可以執(zhí)行的程序和數(shù)據(jù)，及是機器不可執(zhí)行的相關(guān)文檔兩部分構(gòu)成。程序：是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計語言描述的、適合計算機執(zhí)行的指令（語句）序列。數(shù)據(jù)：是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔：是與程序開發(fā)、維護和使用有關(guān)的圖文資料。軟件的特點軟件是一種邏輯實體，不是物理實體，具有抽象性。軟件的生產(chǎn)與硬件不同，沒有明顯的制作過程。軟件的運行與使用不存在磨損與老化問題。軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制。軟件復(fù)雜性高，成本昂貴。軟件開發(fā)涉及諸多的社會因素。軟件的分類：按功能分可為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（工具軟件）。軟件危機與軟件工程軟件危機：泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。歸結(jié)起來為成本、質(zhì)量、生產(chǎn)率等問題。軟件工程：是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔實踐標準和工序。軟件工程三要素：方法、工具和過程。軟件工程的核心思想：把軟件產(chǎn)品看作是一個工程產(chǎn)品來處理。軟件工程過程：是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具運行下由軟件工程師完成的一系列軟件工程活動。包括4種基本活動：軟件規(guī)格說明、軟件開發(fā)、軟件確認、軟件演進。從軟件開發(fā)的觀點看，它是使用適當?shù)馁Y源為開發(fā)軟件進行的一組開發(fā)活動，在過程結(jié)束時將輸入轉(zhuǎn)化為輸出。軟件生命周期：通常將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期?？梢源致詣澐譃檐浖x、軟件開發(fā)、和軟件運行維護三個階段。軟件生命周期的主要活動階段是：可行性研究與計劃制定：確定開發(fā)目標和總的要求，給出可行方案，制定開發(fā)計劃。需求分析：根據(jù)用戶的需求進行分析并給出詳細定義，即確定軟件系統(tǒng)的功能。軟件設(shè)計：在反復(fù)理解軟件需求的基礎(chǔ)上給出軟件結(jié)構(gòu)、模塊劃分、功能分配及處理流程。軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼，即完成源程序的編碼和相關(guān)用戶文檔，編寫單元測試計劃。軟件測試：檢驗軟件的各個組成部分，編寫測試分析報告。運行和維護：交付使用，并不斷進行維護，根據(jù)新需求進行擴充和刪改。本階段所花的費用遠遠大于開發(fā)階段。軟件的維護分改正性維護、適應(yīng)性維護、完善性維護和預(yù)防性維護4種。軟件工程的目標與原則軟件工程的目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程的理論和技術(shù)研究的主要包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。這也是軟件設(shè)計所必須遵循的原則。P54軟件開發(fā)環(huán)境：是全面支持軟件開發(fā)全過程的軟件工具集合。計算機輔助軟件工程縮寫CASE結(jié)構(gòu)化分析方法軟件開發(fā)方法：是軟件開發(fā)過程所遵循的方法和步驟。包括分析方法、設(shè)計方法和程序設(shè)計方法。結(jié)構(gòu)化分析方法：其核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論，包括結(jié)構(gòu)化分析方法、結(jié)構(gòu)化設(shè)計方法和結(jié)構(gòu)化編程方法。需求分析與其方法需求分析：指用戶對目標軟件系統(tǒng)在功能、行為、性能、設(shè)計約束等方面的期望。有四個方面的工作：需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審。需求分析方法：結(jié)構(gòu)分析方法：包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法。面向?qū)ο蟮姆治龇椒ò葱枨蠓治鼋⒌哪Ｐ吞匦苑挚煞譃殪o態(tài)分析方法和動態(tài)分析方法。結(jié)構(gòu)化分析方法：是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的運用。數(shù)據(jù)流圖P56：是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)字典：是結(jié)構(gòu)化分析方法的核心，是對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表。判定樹、判定表軟件需求規(guī)格說明書：是需求分析階段的最后成果，是軟件開發(fā)中的重要文檔之一。其作用為便于理解與交流作為軟件開發(fā)的基礎(chǔ)和依據(jù)作為確認測試和驗收的依據(jù)結(jié)構(gòu)需求分析的常用工具：數(shù)據(jù)流圖（DFD）：用于描述數(shù)據(jù)處理過程。主要的描述圖符有加工（轉(zhuǎn)換）“○”、數(shù)據(jù)流“→”、存儲文件（數(shù)據(jù)源）“〓”、源和潭“□”。數(shù)據(jù)字典（DD）：是各類數(shù)據(jù)描述的集合，通常包括數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲和處理過程5個部分。判定樹判定表結(jié)構(gòu)化設(shè)計方法軟件設(shè)計的基本概念軟件設(shè)計的構(gòu)成：軟件結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計：描述軟件內(nèi)部、軟件和操作系統(tǒng)之間及軟件與人之間如何通信；過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。軟件設(shè)計的步驟：從工程管理角度，軟件設(shè)計分兩步完成：概要設(shè)計和詳細設(shè)計。概要設(shè)計：即總體設(shè)計或結(jié)構(gòu)設(shè)計基本任務(wù)：設(shè)計軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計、編寫概要設(shè)計文檔和概要設(shè)計文檔評審等，在需求分析基礎(chǔ)上把復(fù)雜的系統(tǒng)功能分解成一系列比較簡單的功能。數(shù)據(jù)流類型：變換型和事務(wù)型常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖（由四種模塊構(gòu)成：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊）。詳細設(shè)計：其任務(wù)是為軟件結(jié)構(gòu)圖的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。常用的表達工具有：程序流程圖（PFD）、N－S、PAD、HIPO、判定表和PDL（偽碼）等。程序流程圖：也稱程序框圖，其中箭頭表示控制流，方塊表示加工步驟，菱形表示邏輯條件。N－S圖：用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖。軟件設(shè)計的一般過程：軟件設(shè)計是一個迭代的過程，先進行高層次的結(jié)構(gòu)設(shè)計，后進行低層次的過程設(shè)計，中間穿插進行數(shù)據(jù)設(shè)計和接口設(shè)計。軟件設(shè)計的基本原理P61結(jié)構(gòu)化設(shè)計方法：采用最佳的可能方法設(shè)計系統(tǒng)的各個組成部分以及各成分之間的內(nèi)部聯(lián)系的技術(shù)。軟件測試：是保證軟件質(zhì)量的重要手段，包括需求定義階段的需求測試、編碼階段的單元測試、集成階段以及后期的確認測試、系統(tǒng)測試，以驗證軟件是否合格、能否交付用戶使用等。測試的目的：發(fā)現(xiàn)錯誤。測試的準則：所有測試都應(yīng)追溯到需求嚴格執(zhí)行測試計劃，排隊測試的隨意性充分注意測試中的群集現(xiàn)象程序員應(yīng)避免檢查自己的程序窮舉測試不可能妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告，為維護提供方便。測試技術(shù)與方法P72按是否需要執(zhí)行被測試軟件分為靜態(tài)測試和動態(tài)測試。按功能劃分可分為白盒和黑盒測試。白盒測試：用于測試程序內(nèi)部結(jié)構(gòu)，此方法將程序看作邏輯路徑的集合。有邏輯覆蓋、基本路徑測試等，其中邏輯覆蓋分語句覆蓋、路徑覆蓋、判定覆蓋、條件覆蓋、判斷－條件覆蓋；黑盒測試：是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試和驗證。分等價劃分法、邊界值分析法、錯誤推測法。軟件測試的過程：單元測試、集成測試、驗收測試（確認測試）和系統(tǒng)測試。單元測試：對軟件的最小設(shè)計單元－模塊進行正確性檢驗的測試。集成測試：是測試和組裝軟件的測試，目的是發(fā)現(xiàn)與接口有關(guān)的錯誤。驗收測試：即確認測試，是驗證軟件的功能和性能及其他特性是否滿足需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測試：是將通過測試確認的軟件加入的整個計算機系統(tǒng)中進行測試，目的是在真實的系統(tǒng)工作環(huán)境下檢驗軟件是否能與系統(tǒng)正確連接，發(fā)現(xiàn)軟件與系統(tǒng)需求不一致地方。程序的調(diào)試基本概念程序調(diào)試活動的組成：根據(jù)錯誤的跡象確定程序中錯誤的確切性質(zhì)、原因和位置，對程序進行修改排隊這個錯誤。其目的是診斷和改正程序中的錯誤。程序調(diào)試的基本步驟錯誤定位修改設(shè)計和代碼，以排除錯誤進行回歸測試，防止引進新的錯誤程序調(diào)試的原則P81軟件調(diào)試方法強行排錯法回溯法原因排除法第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)（Date）：描述事物的符號記錄。數(shù)據(jù)一般分臨時性數(shù)據(jù)與持久性數(shù)據(jù)兩類。處理數(shù)據(jù)的最小單位是數(shù)據(jù)項，若干數(shù)據(jù)項組成數(shù)據(jù)元素。數(shù)據(jù)庫（DataBase）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。也就是說它是一個結(jié)構(gòu)化的數(shù)據(jù)集合，具有集成、共享之特點。數(shù)據(jù)庫管理系統(tǒng)(DBMS)：是一種系統(tǒng)軟件，是數(shù)據(jù)庫的機構(gòu)，是數(shù)據(jù)庫系統(tǒng)的核心，負責(zé)數(shù)據(jù)庫的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等。主要有以下六方面功能：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)數(shù)據(jù)的服務(wù)幾個相關(guān)縮寫：數(shù)據(jù)定義語言（DDL）、數(shù)據(jù)操縱語言（DML）、數(shù)據(jù)控制語言（DCL）數(shù)據(jù)庫管理員（DBA）：主要工作為數(shù)據(jù)庫設(shè)計數(shù)據(jù)庫維護改善系統(tǒng)性能，提高系統(tǒng)效率。數(shù)據(jù)庫系統(tǒng)（DBS）：以數(shù)據(jù)庫為核心的由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理員系統(tǒng)軟、硬件平臺五部分構(gòu)成的完整的運行實體。數(shù)據(jù)庫應(yīng)用系統(tǒng)（DBAS）：在數(shù)據(jù)庫系統(tǒng)基礎(chǔ)上加上應(yīng)用軟件及應(yīng)用界面，包括數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、系統(tǒng)軟、硬件平臺、應(yīng)用軟件、應(yīng)用界面七部分構(gòu)成的有機整體。數(shù)據(jù)庫管理的發(fā)展三個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。數(shù)據(jù)庫系統(tǒng)的發(fā)展三個階段：文件系統(tǒng)階段、層次數(shù)據(jù)庫和網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段和關(guān)系數(shù)據(jù)庫系統(tǒng)階段。目前三種比較重要的數(shù)據(jù)庫技術(shù)：面向?qū)ο髷?shù)據(jù)庫系統(tǒng)、知識庫系統(tǒng)、關(guān)系數(shù)據(jù)庫系統(tǒng)的擴充。數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)高獨立性數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系三級模式：數(shù)據(jù)模式是數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式。概念模式：是數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）數(shù)據(jù)視圖。以概念模式為框架所組成的數(shù)據(jù)為叫概念數(shù)據(jù)庫。外模式：也稱子模式或用戶模式，是用戶的數(shù)據(jù)視圖。以外模式為框架所組成數(shù)據(jù)庫叫用戶數(shù)據(jù)庫。內(nèi)模式：又稱物理模式，是數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法，如數(shù)據(jù)存儲的文件結(jié)構(gòu)、索引、集簇及hash等。是數(shù)據(jù)的物理結(jié)構(gòu)在計算機存儲空間中的存放形式。它的設(shè)計直接影響數(shù)據(jù)庫的性能。以內(nèi)模式為框架所組成的數(shù)據(jù)庫叫物理數(shù)據(jù)庫。二級映射：概念模式到內(nèi)模式的映射外模式到概念模式的映射數(shù)據(jù)模型數(shù)據(jù)模型的基本概念數(shù)據(jù)模式的內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型的應(yīng)用層次概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型E－R模型（實體聯(lián)系模型）：由實體、聯(lián)系和屬性三者結(jié)合起來表示現(xiàn)實世界?；靖拍顚嶓w：是概念世界的基本單位，是客觀存在的且又能被相互區(qū)別的事物。屬性：實體的特征聯(lián)系：事物之間的關(guān)聯(lián)，也就是實體間的函數(shù)關(guān)系，常見的函數(shù)關(guān)系有一對一（實體間一一對應(yīng)）、一對多（實體A對應(yīng)多個其它實體，而其他實體只對應(yīng)實體A）、多對多（多個實體間相互有多個關(guān)系）。E－R圖示法實體集表示法屬性表示法聯(lián)系表示法實體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系實體集與聯(lián)系間的聯(lián)接關(guān)系層次模型：以樹形結(jié)構(gòu)表示現(xiàn)實世界，具有以下特性：每棵樹有且僅有一個無雙親結(jié)點，稱為根樹中除根外所有結(jié)點有且僅有一個雙親。網(wǎng)狀模型P95關(guān)系模型：關(guān)系的數(shù)據(jù)結(jié)構(gòu)：用二維表表示，簡稱表。二維表由表框架和表的元組組成。表框架上按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，一個元組由n個元組分量組成，每個元組分量是表框架上每個屬性的投影值。滿足下列7個性質(zhì)的二維表稱關(guān)系：元組個數(shù)有限性元組的惟一性元組的次序無關(guān)性元組分量的原子性屬性名惟一性屬性的次序無關(guān)性分量值域的同一性關(guān)系的操縱：是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢