計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)

1、全國(guó)計(jì)算機(jī)等級(jí)考試全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)二級(jí)公共基礎(chǔ)知識(shí)第一章 數(shù)據(jù)結(jié)構(gòu)與算法(30%)n 考試大綱1. 算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3. 線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4. 棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6. 樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。7. 順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，

2、插入類(lèi)排序）。知識(shí)點(diǎn)歸納n算法的基本概念n所謂算法是指解題方案的準(zhǔn)確而完整的描述。嚴(yán)格來(lái)說(shuō)，一個(gè)算法必須具有以下五個(gè)主要特征：算法的基本特征算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：n 有窮性有窮性n 確定性確定性n 輸入輸入n 輸出輸出n 可行性可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；算法原則上能夠精確地運(yùn)行算法的基本概念n算法的組成要素n算

3、法中對(duì)數(shù)據(jù)的運(yùn)算和操作n算法的控制結(jié)構(gòu)n算法設(shè)計(jì)基本方法n列舉法n歸納法n遞推n遞歸n減半遞推n回溯法n 算術(shù)運(yùn)算算術(shù)運(yùn)算n 關(guān)系運(yùn)算關(guān)系運(yùn)算n 邏輯運(yùn)算邏輯運(yùn)算n 數(shù)據(jù)傳輸數(shù)據(jù)傳輸n 順序順序n 選擇選擇n 循環(huán)循環(huán)算法的復(fù)雜度n算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量算法優(yōu)劣的量度。1.算法的時(shí)間復(fù)雜度n算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)f(n)。算法的復(fù)雜度n算法的空間復(fù)雜度n算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?？臻g復(fù)雜度作為算法所需存儲(chǔ)空間的量度數(shù)據(jù)結(jié)構(gòu)n利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算

4、機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題：n數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。n在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。1.對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。n與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容是指在存儲(chǔ)空間中使用一個(gè)存儲(chǔ)結(jié)點(diǎn)來(lái)存儲(chǔ)一個(gè)數(shù)據(jù)元素，在存儲(chǔ)空間中建立各存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)，來(lái)表示數(shù)據(jù)元素之間的

5、邏輯關(guān)系。n常見(jiàn)的存儲(chǔ)結(jié)構(gòu)：n順序存儲(chǔ)結(jié)構(gòu)n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)n索引存儲(chǔ)結(jié)構(gòu)n散列存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)n在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：n存在一個(gè)唯一的被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素n存在一個(gè)唯一的被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素n除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)n除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)n非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹(shù)和圖都屬于非線性結(jié)構(gòu)。線性表n通常以下列 n 個(gè)數(shù)據(jù)元素的序列”表示線性表線性表 ：(a1,a2 ,.,ai ,.,an) n序列中數(shù)據(jù)元素的個(gè)數(shù) n 定

6、義為線性表的表長(zhǎng)表長(zhǎng)；n=0 時(shí)的線性表被稱(chēng)為空表空表。稱(chēng) i 為ai在線性表中的位序位序。線性表的順序存儲(chǔ)n線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次存放依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱(chēng)作線性表的基地址線性表的基地址。 所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址基地址 一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量 線性表的插入和刪除運(yùn)算n插入運(yùn)算是指在線性表的某個(gè)指定位置增

7、加一個(gè)新結(jié)點(diǎn)。n一般情況下，要在第i(1in)個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開(kāi)始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入到第i項(xiàng)。n刪除運(yùn)算是指撤銷(xiāo)結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)。n一般情況，要?jiǎng)h除第i(1in)個(gè)元素，要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素，共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。棧n棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。n棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進(jìn)先出后進(jìn)先出的線性表。n通常用指針top指示

8、棧頂位置，用指針bottom指示棧底位置。棧的順序存儲(chǔ)及運(yùn)算n用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。n棧的操作n入棧：在棧頂位置插入一個(gè)新元素，棧頂指針top加1。n退棧：取出棧頂元素并賦值給一個(gè)指定的變量，棧頂指針top減1。n取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。隊(duì)列n隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。n隊(duì)列是一種先進(jìn)先出先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。n向

9、隊(duì)尾插入一個(gè)元素的操作稱(chēng)為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱(chēng)為退隊(duì)。循環(huán)隊(duì)列n將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。n循環(huán)隊(duì)列初始狀態(tài)為空，即front=rear=m。n入隊(duì)操作時(shí)，rear加1，若rear=m+1，則置rear=1；n退隊(duì)操作時(shí)，front加1，若front=m+1，則置front=1。n在循環(huán)隊(duì)列為空或?yàn)闈M時(shí)，均有front=rear，因此需要設(shè)置標(biāo)志s進(jìn)行區(qū)分，定義s=0表示隊(duì)列為空，s=1表示隊(duì)列非空。單鏈表n線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以連續(xù)，也可以不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素

10、ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需要存儲(chǔ)其后繼元素的存儲(chǔ)位置信息(指針域)。n指針域中存儲(chǔ)的信息稱(chēng)為指針或鏈，N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于結(jié)點(diǎn)中只包含一個(gè)指針域，故稱(chēng)為單鏈表。單鏈表n通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的地址，稱(chēng)為頭指針。整個(gè)鏈表的存儲(chǔ)必須從頭指針開(kāi)始(順序存取)，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒(méi)有直接后繼，其指針域?yàn)榭?。單鏈表的插入和刪除雙向鏈表和循環(huán)鏈表n在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。n循環(huán)鏈表的特點(diǎn)是表中最后一

11、個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。HEADHEADHEADHEADHEADHEAD樹(shù)及其基本概念n樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹(shù)中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。n樹(shù)是(n0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹(shù)中： (1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。 (2)當(dāng)n1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,Tm，其中每個(gè)有限子集本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。n集合為空的樹(shù)簡(jiǎn)稱(chēng)為空樹(shù)；樹(shù)中的元素稱(chēng)為結(jié)點(diǎn)。樹(shù)的主要術(shù)

12、語(yǔ)n結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。n葉節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。n雙親、孩子和兄弟：結(jié)點(diǎn)的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱(chēng)為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱(chēng)為兄弟。n層次：結(jié)點(diǎn)的層次從根開(kāi)始定義，根為第一層，根的孩子為第二層。n深度：樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度或高度。ABDFECGHIJKMn 一個(gè)結(jié)點(diǎn)的子樹(shù)的一個(gè)結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)；個(gè)數(shù)； Q：結(jié)點(diǎn)結(jié)點(diǎn)A、G的度數(shù)？的度數(shù)？n 樹(shù)中所有結(jié)點(diǎn)度的最樹(shù)中所有結(jié)點(diǎn)度的最大值；大值；Q：右圖中樹(shù)的度？右圖中樹(shù)的度？n 度為度為0的結(jié)點(diǎn)；的結(jié)點(diǎn)； Q：圖中葉子結(jié)點(diǎn)有幾個(gè)？圖中葉子結(jié)點(diǎn)有幾個(gè)？7 度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)； Q

13、：圖中非終端結(jié)點(diǎn)有幾個(gè)？圖中非終端結(jié)點(diǎn)有幾個(gè)？ 5ABDFECGHIJKMn 樹(shù)中根結(jié)點(diǎn)的層樹(shù)中根結(jié)點(diǎn)的層次為次為1，根結(jié)點(diǎn)子樹(shù)的根為第，根結(jié)點(diǎn)子樹(shù)的根為第2層，層，以此類(lèi)推；以此類(lèi)推；樹(shù)中所有結(jié)點(diǎn)層次的樹(shù)中所有結(jié)點(diǎn)層次的最大值；最大值； Q：圖中樹(shù)的深度？圖中樹(shù)的深度？二叉樹(shù)n二叉樹(shù)是n(n0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱(chēng)為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹(shù)，分別稱(chēng)為根的左子樹(shù)和右子樹(shù)。n二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，并且二叉樹(shù)的子樹(shù)有左右之分，其順序不能任意顛倒。二叉樹(shù)的基本性質(zhì)n性質(zhì)性質(zhì)1 1 在二叉樹(shù)的第

14、i層上至多有2i-1個(gè)結(jié)點(diǎn)（i1）n性質(zhì)性質(zhì)2 2 深度為k的二叉樹(shù)至多有2k -1個(gè)結(jié)點(diǎn)（k1）n性質(zhì)性質(zhì)3 3 對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2 ，則：n0 =n2+1n性質(zhì)性質(zhì)4 4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n +1滿二叉樹(shù)和完全二叉樹(shù)n滿二叉樹(shù)滿二叉樹(shù)除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也就是說(shuō)每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹(shù)的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。n完全二叉樹(shù)完全二叉樹(shù)除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，

15、其深度為log2n +1。n從以上定義可知，滿二叉樹(shù)也是完全二叉樹(shù)，反之則不然。滿二叉樹(shù)滿二叉樹(shù) 最大層的結(jié)點(diǎn)最大層的結(jié)點(diǎn)均向左靠齊均向左靠齊 完全二叉樹(shù)完全二叉樹(shù) ADCBEF二叉樹(shù)的基本性質(zhì)性質(zhì)性質(zhì)5 5 如果對(duì)一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為log2n +1）的結(jié)點(diǎn)按層序（從第1層到第log2n +1 層，每層從左到右）從1起開(kāi)始編號(hào)，則對(duì)任一編號(hào)為 i 的結(jié)點(diǎn)(1in)，則:(1) 如果 i=1，則編號(hào)為 i 的結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親；如果 i1，則其雙親結(jié)點(diǎn) parent(i)的編號(hào)是i/2。(2) 如果 2in，則編號(hào)為 i 的結(jié)點(diǎn)無(wú)左孩子（編號(hào)為 i 的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）

16、；否則其左孩子結(jié)點(diǎn) lChild(i) 的編號(hào)是 2i 。(3) 如果 2i+1n，則編號(hào)為 i 的結(jié)點(diǎn)無(wú)右孩子；否則其右孩子結(jié)點(diǎn) rChild(i) 的編號(hào)是結(jié)點(diǎn) 2i+1。 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)n在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲(chǔ)左右子樹(shù)根節(jié)點(diǎn)的存儲(chǔ)位置，即指針。L(i)V(i)R(i)LchildvalueRchild二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷n二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。從二叉樹(shù)的結(jié)構(gòu)定義得知，二叉樹(shù)是由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)三部分構(gòu)成，則遍歷二叉樹(shù)的操作可分解為訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)和遍歷右子樹(shù)三個(gè)子操

17、作，并且由二叉樹(shù)的遞歸定義可知，遍歷左子樹(shù)和遍歷右子樹(shù)可如同遍歷二叉樹(shù)一樣遞歸進(jìn)行。 先序遍歷二叉樹(shù)先序遍歷二叉樹(shù)中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；否則(1) 訪問(wèn)根結(jié)點(diǎn)；(2) 先序遍歷左子樹(shù)；(3) 先序遍歷右子樹(shù)。 若二叉樹(shù)為空，則空操作；否則(1) 中序遍歷左子樹(shù)；(2) 訪問(wèn)根結(jié)點(diǎn)；(3) 中序遍歷右子樹(shù)。 若二叉樹(shù)為空，則空操作；否則(1) 后序遍歷左子樹(shù)；(2) 后序遍歷右子樹(shù)；(3) 訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA查找n查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中

18、查找某個(gè)指定的元素。n順序查找n順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。n順序查找：最好情況比較1次，最壞情況比較n次n如果線性表為無(wú)序表，即表中元素的排列是無(wú)序的，則不管線性表采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都必須使用順序查找。n如果線性表有序，但采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則也必須使用順序查找。查找n二分查找(折半查找)n二分查找法只適用于順序存儲(chǔ)的有序表。先確定待查目標(biāo)元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當(dāng)查找區(qū)間縮小

19、到0也沒(méi)有找到目標(biāo)元素為止。n查找過(guò)程中，給定值首先和處于待查區(qū)間中間位置的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到前半個(gè)區(qū)間 或 后半個(gè)區(qū)間 之后繼續(xù)進(jìn)行查找。折半查找二分查找查找 二分查找(折半查找)：由于每次都可以減少一半的元素，所以最壞時(shí)間復(fù)雜度為log(2n)排序n排序是指將一個(gè)無(wú)序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。n排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲(chǔ)的線性表為排序?qū)ο螅诔绦蛟O(shè)計(jì)語(yǔ)言中就是一維數(shù)組。n排序的算法種類(lèi)很多，主要包括交換類(lèi)排序、插入類(lèi)排序、選擇類(lèi)排序等。交換類(lèi)排序法交換類(lèi)排序法 n冒泡排序冒泡排序n快速

20、排序快速排序 插入類(lèi)排序法插入類(lèi)排序法n簡(jiǎn)單插入排序簡(jiǎn)單插入排序n希爾排序希爾排序選擇類(lèi)排序法選擇類(lèi)排序法n簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序n堆排序堆排序最壞時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：n冒泡排序法、快速排序、簡(jiǎn)單選擇排序法、簡(jiǎn)單插冒泡排序法、快速排序、簡(jiǎn)單選擇排序法、簡(jiǎn)單插入排序：入排序： 最壞情況需要最壞情況需要n(n-1)/2次比較；次比較；n希爾排序法：希爾排序法： 最壞情況需要最壞情況需要O(n1.5)次比較；次比較；n堆排序法堆排序法, 最壞情況需要最壞情況需要O(nlog2n)次比較；次比較； 平均速度最快排序：平均速度最快排序：快速排序快速排序最好、最壞、平均三種復(fù)雜度都相同的排序方法

21、：最好、最壞、平均三種復(fù)雜度都相同的排序方法：堆排序堆排序第二章 程序設(shè)計(jì)基礎(chǔ)(15%)n考試大綱n1. 程序設(shè)計(jì)方法與風(fēng)格。2. 結(jié)構(gòu)化程序設(shè)計(jì)。3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。 知識(shí)點(diǎn)歸納n程序設(shè)計(jì)方法n程序設(shè)計(jì)是一門(mén)技術(shù)，需要相應(yīng)的理論、方法和工具來(lái)支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。n在程序設(shè)計(jì)中，通常采用“自頂向下，逐步求精”的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語(yǔ)言編寫(xiě)的程序。程序設(shè)計(jì)風(fēng)格n除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良

22、好的程序設(shè)計(jì)風(fēng)格概括起來(lái)包括以下及格方面：n源程序文檔化n數(shù)據(jù)說(shuō)明的方法n語(yǔ)句的結(jié)構(gòu)n輸入和輸出程序設(shè)計(jì)風(fēng)格n源程序文檔化n標(biāo)識(shí)符的命名n程序的注釋n序言性注釋n功能性注釋n程序的視覺(jué)組織n數(shù)據(jù)的說(shuō)明n數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化n說(shuō)明語(yǔ)句中變量的安排有序化n使用注釋說(shuō)明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)風(fēng)格n語(yǔ)句結(jié)構(gòu)語(yǔ)句結(jié)構(gòu)n在一行內(nèi)只寫(xiě)一條語(yǔ)句n程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性n除非對(duì)效率有特殊要求，程序編寫(xiě)要做到清晰第一，效率第二n首先要保證程序正確，然后才要求提高速度n避免使用臨時(shí)變量而使程序的可讀性下降n避免不必要的轉(zhuǎn)移n盡可能使用庫(kù)函數(shù)n避免使用復(fù)雜的條件語(yǔ)句n盡量減少使用“否定”條件的條件語(yǔ)句n數(shù)據(jù)結(jié)構(gòu)

23、要有利于程序的簡(jiǎn)化n要模塊化，使模塊功能盡可能單一化n利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性n從數(shù)據(jù)出發(fā)構(gòu)造程序n不要修補(bǔ)不好的程序，要重寫(xiě)編寫(xiě)程序設(shè)計(jì)風(fēng)格n輸入和輸出n對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性n檢查輸入項(xiàng)的各種重要組合的合法性n輸入格式要簡(jiǎn)單，以使輸入的步驟和操作盡可能簡(jiǎn)單n輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式n應(yīng)允許缺省值n輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志n在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息n當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋?zhuān)⒃O(shè)計(jì)輸出報(bào)表格式。結(jié)構(gòu)化

24、程序設(shè)計(jì)n結(jié)構(gòu)化程序設(shè)計(jì)的原則n自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開(kāi)始就過(guò)多追求細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。n逐步求精。對(duì)復(fù)雜的問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)過(guò)渡，逐步細(xì)化。n模塊化。一個(gè)復(fù)雜問(wèn)題肯定是有若干簡(jiǎn)單問(wèn)題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。n嚴(yán)格限制GOTO語(yǔ)句的使用。結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)n程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，并且具有如下特點(diǎn)：?jiǎn)稳肟?、單出口、結(jié)構(gòu)中無(wú)死循環(huán)，程序中三種

25、基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。n一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。n在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。面向?qū)ο蟪绦蛟O(shè)計(jì)n 面向?qū)ο蠓椒ǖ幕靖拍?.對(duì)象、類(lèi)和屬性 在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問(wèn)題域中某個(gè)實(shí)體的抽象。每個(gè)對(duì)象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來(lái)定義。類(lèi)是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，描述了屬于該類(lèi)的所有對(duì)象的性質(zhì)。2.方法 方法有稱(chēng)為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過(guò)消息傳遞，還可為其他對(duì)象使用。面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方

26、法的一個(gè)重要特征。指一個(gè)類(lèi)(子類(lèi))直接使用另一個(gè)類(lèi)(父類(lèi))的所有屬性和方法。它可以減少相似類(lèi)的重復(fù)說(shuō)明，從而體現(xiàn)一般性和特殊性的原則。4.多態(tài)性：多態(tài)性可以用“一個(gè)對(duì)外界面，多個(gè)內(nèi)部實(shí)現(xiàn)”來(lái)表示?？梢酝ㄟ^(guò)方法重載和方法重寫(xiě)來(lái)實(shí)現(xiàn)多態(tài)。重載指一個(gè)類(lèi)中可以有多個(gè)具有相同名稱(chēng)的方法，由傳遞給它們的不同個(gè)數(shù)和類(lèi)型的參數(shù)來(lái)決定執(zhí)行那個(gè)方法。重寫(xiě)指子類(lèi)可以重新實(shí)現(xiàn)父類(lèi)的某些方法，使其具有自己的特征。多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，提高了軟件的可重用性和可擴(kuò)充性。5.消息：面向?qū)ο笙到y(tǒng)中的對(duì)象之間是通過(guò)消息機(jī)制彼此相互合作的，消息是一個(gè)對(duì)象與另一個(gè)對(duì)象之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某

27、一要求的信息。面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)n按照人的思維方式對(duì)客觀世界進(jìn)行抽象n穩(wěn)定性好n可重用性好n易于開(kāi)發(fā)大型軟件n可維護(hù)性好第三章 軟件工程基礎(chǔ)n考試大綱n1. 軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。3. 結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4. 軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。5. 程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。 知識(shí)點(diǎn)歸納n軟件定義和特點(diǎn)n計(jì)算機(jī)軟件式計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。計(jì)算機(jī)軟件具有

28、如下特點(diǎn)：n軟件是一種邏輯實(shí)體，具有抽象性n軟件生產(chǎn)沒(méi)有明顯的制造過(guò)程n軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題n軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性n軟件復(fù)雜性高，成本昂貴n軟件開(kāi)發(fā)涉及諸多社會(huì)因素軟件危機(jī)n所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題，包括：n軟件需求的增長(zhǎng)得不到滿足n軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制n軟件質(zhì)量難以保證n軟件不可維護(hù)或可維護(hù)性低n軟件成本不斷提高n軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。軟件工程n為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于計(jì)算機(jī)軟件定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。n軟件工程的

29、三要素n方法n工具n過(guò)程軟件工程過(guò)程n軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。它包括兩方面含義：n1. 軟件工程過(guò)程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動(dòng)。通常包括四種基本活動(dòng)：nP(Plan)：軟件規(guī)格說(shuō)明nD(Do)：軟件開(kāi)發(fā)nC(Check)：軟件確認(rèn)nA(Action)：軟件演進(jìn)n2.從軟件開(kāi)發(fā)的觀點(diǎn)看，軟件工程過(guò)程是使用適當(dāng)?shù)馁Y源，為開(kāi)發(fā)軟件進(jìn)行的一組開(kāi)發(fā)活動(dòng)，在活動(dòng)結(jié)束時(shí)將輸入(用戶需求)轉(zhuǎn)化為輸出(軟件產(chǎn)品)。軟件生命周期n軟件從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用的過(guò)程稱(chēng)為軟件的生命周期。一般包括以下幾個(gè)階段：n可行性研究與計(jì)劃制定n

30、需求分析n軟件設(shè)計(jì)n軟件實(shí)現(xiàn)n軟件測(cè)試n運(yùn)行和維護(hù)軟件工程目標(biāo)與原則n軟件工程的目標(biāo)是在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產(chǎn)品。n為達(dá)到上述目標(biāo)，在軟件開(kāi)發(fā)的過(guò)程中，必須遵循軟件工程的基本原則：n抽象n信息隱蔽n模塊化n局部化n確定性n一致性n完備性n可驗(yàn)證性軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境n軟件開(kāi)發(fā)工具對(duì)過(guò)程和方法提供自動(dòng)或半自動(dòng)的支持。當(dāng)這些工具被集成起來(lái)使得一個(gè)工具產(chǎn)生的信息可以被另外一個(gè)工具使用時(shí)，一個(gè)支持軟件開(kāi)發(fā)的系統(tǒng)就建立起來(lái)了，稱(chēng)為計(jì)算機(jī)輔助軟件工程(CASE)。CASE集成了軟件

31、、硬件和一個(gè)軟件工程數(shù)據(jù)庫(kù)(包含了有關(guān)分析、設(shè)計(jì)、程序構(gòu)造和測(cè)試的重要信息)從而創(chuàng)建了一個(gè)軟件開(kāi)發(fā)環(huán)境。結(jié)構(gòu)化分析方法n結(jié)構(gòu)化分析方法大多使用自頂向下、逐層分解的系統(tǒng)分析方法來(lái)定義系統(tǒng)需求。在結(jié)構(gòu)化分析的基礎(chǔ)上，完成系統(tǒng)的規(guī)格說(shuō)明，建立系統(tǒng)的一個(gè)自頂向下的任務(wù)分析模型。結(jié)構(gòu)化分析方法是一種建模技術(shù)，模型的核心是數(shù)據(jù)辭典，它描述了所有在目標(biāo)系統(tǒng)中使用和生成的數(shù)據(jù)對(duì)象。結(jié)構(gòu)化分析常用的工具：n數(shù)據(jù)流圖(DFD):描述數(shù)據(jù)在系統(tǒng)中如何被傳送或變換以及描述如何對(duì)數(shù)據(jù)流進(jìn)行變換的功能，用于功能建模。n數(shù)據(jù)字典n判定樹(shù)n判定表數(shù)據(jù)流圖n數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，它從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫(huà)數(shù)據(jù)

32、流從輸入系統(tǒng)到從系統(tǒng)輸入的移動(dòng)變換過(guò)程。n數(shù)據(jù)流圖的基本元素n外部實(shí)體n數(shù)據(jù)流n處理(加工)n數(shù)據(jù)存儲(chǔ)數(shù)據(jù)字典n數(shù)據(jù)字典是關(guān)于數(shù)據(jù)的信息的集合，對(duì)數(shù)據(jù)流圖中的各個(gè)元素進(jìn)行完整的定義和說(shuō)明。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構(gòu)成系統(tǒng)的邏輯模型。n數(shù)據(jù)字典通常包含的信息有：名稱(chēng)、別名、何處使用、如何使用、內(nèi)容描述以及補(bǔ)充信息等。軟件需求n軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開(kāi)發(fā)進(jìn)度需求等。n需求分析應(yīng)交付的主要文檔是軟件需求規(guī)格說(shuō)明書(shū)(SRS)。結(jié)構(gòu)化設(shè)計(jì)n結(jié)構(gòu)化設(shè)計(jì)就是采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分以及個(gè)成分之間的內(nèi)部聯(lián)系

33、的技術(shù)。也就是說(shuō)，結(jié)構(gòu)化設(shè)計(jì)是這樣一個(gè)過(guò)程：它決定用哪些方法把哪些部分聯(lián)系起來(lái)，才能解決好某個(gè)具體的有清楚定義的問(wèn)題。從工程管理的角度看，軟件設(shè)計(jì)分兩步完成：n1.概要設(shè)計(jì)，即總體設(shè)計(jì)。將軟件需求轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)和軟件的系統(tǒng)結(jié)構(gòu)。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖(Structure Chart)。n2.詳細(xì)設(shè)計(jì)：即過(guò)程設(shè)計(jì)。通過(guò)對(duì)結(jié)構(gòu)表示進(jìn)行細(xì)化，得到軟件詳細(xì)的數(shù)據(jù)結(jié)構(gòu)和算法。過(guò)程設(shè)計(jì)常用的工具有：程序流程圖、N-S圖、PAD圖、過(guò)程設(shè)計(jì)語(yǔ)言PDL(偽碼)。軟件測(cè)試n定義：n使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。n軟件測(cè)

34、試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。n一個(gè)好的測(cè)試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例。n一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。n測(cè)試不能表明軟件中不存在錯(cuò)誤，它只能說(shuō)明軟件中存在錯(cuò)誤。測(cè)試技術(shù)與方法綜述n從是否需要執(zhí)行被測(cè)試軟件的角度，可將測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。n靜態(tài)測(cè)試主要包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。n動(dòng)態(tài)測(cè)試是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程，或者說(shuō)，是根據(jù)軟件開(kāi)發(fā)的各個(gè)階段的規(guī)格說(shuō)明和程序的內(nèi)部結(jié)構(gòu)而精心設(shè)計(jì)的一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程。測(cè)試技術(shù)與方法綜述n按照功能劃分，可將軟件測(cè)試分為黑盒測(cè)試

35、和白盒測(cè)試。n黑盒測(cè)試將測(cè)試對(duì)象看作一個(gè)黑盒，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求規(guī)格說(shuō)明，檢查程序的功能是否符合它的功能說(shuō)明。這種測(cè)試又稱(chēng)為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。n白盒測(cè)試把測(cè)試對(duì)象看作一個(gè)透明的盒子，利用程序內(nèi)部的邏輯機(jī)構(gòu)及有關(guān)信息，設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序的所有邏輯路徑進(jìn)行測(cè)試。通過(guò)在不同點(diǎn)檢查程序的狀態(tài)，確定實(shí)際的狀態(tài)是否與預(yù)期的一致。這種測(cè)試又稱(chēng)為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。軟件測(cè)試的實(shí)施n軟件測(cè)試按四個(gè)步驟進(jìn)行：n單元測(cè)試：對(duì)軟件設(shè)計(jì)的最小單位模塊進(jìn)行正確性的測(cè)試，其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。n集成測(cè)試：是測(cè)試和組裝軟件的過(guò)程，它是在把模塊按照設(shè)計(jì)要求

36、組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。n確認(rèn)測(cè)試：任務(wù)是驗(yàn)證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說(shuō)明中確定的各種需求，以及軟件配置是否完全、正確。n系統(tǒng)測(cè)試：將通過(guò)確認(rèn)測(cè)試的軟件，作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支持軟件、數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)境中對(duì)其進(jìn)行一系列的集成測(cè)試和確認(rèn)測(cè)試。程序調(diào)試n程序調(diào)試的任務(wù)是診斷和修正程序中的錯(cuò)誤。n調(diào)試的方法：n強(qiáng)行排錯(cuò)法n回溯法n原因排除法第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)n考試大綱n1. 數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。2. 數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)

37、出關(guān)系數(shù)據(jù)模型。3. 關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。4. 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。知識(shí)點(diǎn)歸納n數(shù)據(jù)庫(kù)的定義n1.長(zhǎng)期存放在計(jì)算機(jī)內(nèi)，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫(kù)中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲(chǔ)，具有較小的冗余度、較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性。n2.數(shù)據(jù)庫(kù)是由一個(gè)互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問(wèn)這些數(shù)據(jù)的程序組成的。數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)n數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫(kù)的應(yīng)用程序的集合。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫(kù)等處理目的的通用軟件系統(tǒng)。其主

38、要功能如下：n數(shù)據(jù)模式定義n數(shù)據(jù)存取的物理構(gòu)建n數(shù)據(jù)操縱n數(shù)據(jù)的完整性、安全性定義和檢查n數(shù)據(jù)庫(kù)的并發(fā)控制和故障恢復(fù)n數(shù)據(jù)的服務(wù)n為完成上述功能，DBMS提供了相應(yīng)的語(yǔ)言：n數(shù)據(jù)定義語(yǔ)言(DDL)n數(shù)據(jù)操縱語(yǔ)言(DML)n數(shù)據(jù)控制語(yǔ)言(DCL)數(shù)據(jù)庫(kù)系統(tǒng)n數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。n數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)n數(shù)據(jù)的集成性n數(shù)據(jù)的高共享性和低冗余性n數(shù)據(jù)的獨(dú)立性n數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部體系結(jié)構(gòu)n三級(jí)模式n概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶的數(shù)據(jù)視圖n外模式：又稱(chēng)為用戶模式，是每個(gè)用戶的局部數(shù)據(jù)描述

39、，用戶的數(shù)據(jù)視圖n內(nèi)模式：又稱(chēng)為物理模式，是數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)和物理存取方法的描述n二級(jí)映射n概念模式到內(nèi)模式的映射n外模式到概念模式的映射數(shù)據(jù)模型n數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示和操作提供一個(gè)抽象的框架。數(shù)據(jù)模型描述的內(nèi)容包括三部分：n數(shù)據(jù)結(jié)構(gòu)n數(shù)據(jù)操作n數(shù)據(jù)約束n數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類(lèi)型：n概念數(shù)據(jù)模型n邏輯數(shù)據(jù)模型n物理數(shù)據(jù)模型實(shí)體聯(lián)系(ER)模型n概念模型是面向現(xiàn)實(shí)世界的，其出發(fā)點(diǎn)是有效地模擬顯示世界，給出數(shù)據(jù)的概念化結(jié)構(gòu)。實(shí)體聯(lián)系模型是一種廣泛使用的概念模型，該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化為實(shí)體實(shí)體、聯(lián)系聯(lián)系和屬性屬性等幾個(gè)基本概念，并用ER圖直觀地表示出來(lái)。ER模型的基本概念n實(shí)體：概念世界中的基本單位，它們是客觀存在且能相互區(qū)別的事物。凡具有共性的實(shí)體可以組成一個(gè)集合稱(chēng)為實(shí)體集實(shí)體集。n屬性：屬性用來(lái)描述實(shí)體的特征。一個(gè)實(shí)體可以有多個(gè)屬性，每個(gè)屬性可以有值，一個(gè)屬性的取值范圍稱(chēng)為該屬性的值域值域。n聯(lián)系：聯(lián)系反映概念世界中的實(shí)體集之間存在的一定關(guān)系。n一對(duì)一聯(lián)系(1:1)n一對(duì)多聯(lián)系(1:M)n多對(duì)多聯(lián)系(M:N)ER圖nER圖是實(shí)體聯(lián)系模型的直觀圖形表示。n實(shí)體用矩形表示，并在矩形中標(biāo)明實(shí)體的名稱(chēng)。n屬性用標(biāo)有屬性名稱(chēng)的橢