2011計算機(jī)2級公共基礎(chǔ)知識考前沖刺培訓(xùn)(張健).ppt

1、計算機(jī)等級考試公共基礎(chǔ)知識,張健,第2頁,計算機(jī)二級考試公共基礎(chǔ)知識大綱,數(shù)據(jù)結(jié)構(gòu)與算法 程序設(shè)計基礎(chǔ) 軟件工程基礎(chǔ) 數(shù)據(jù)庫設(shè)計基礎(chǔ),這四個方面在試卷中出現(xiàn)的情況是：選擇題10個（20分），填空題5個（10分），總分值占到了試卷卷面分的30，是一個不小的比例。,第3頁,計算機(jī)二級考試公共基礎(chǔ)知識試卷分析,第4頁,數(shù)據(jù)結(jié)構(gòu)：本部分內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。 程序設(shè)計基礎(chǔ)：本部分在考試中會出現(xiàn)約1個題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡單，掌握住基本的概念就可以輕松應(yīng)對考試了。 軟件工程：本部分在

2、筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章。從出題的深度來看，本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此考生在復(fù)習(xí)本章時，重點應(yīng)放在基本概念的記憶和基本原理的理解上。 數(shù)據(jù)庫：本部分在考試中一般出現(xiàn)2-4個小題。本章內(nèi)容概括性強(qiáng)，比較抽象，難于理解，因此建議考生在復(fù)習(xí)的時候，首先熟讀講義，其次對數(shù)據(jù)庫系統(tǒng)的基本概念及原理等知識要注意理解、加強(qiáng)記憶。,第5頁,算法 算法的基本概念 2.算法復(fù)雜度的概念和意義,一、基本數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的概念 線性表 棧和隊列 樹與二叉樹 查找技術(shù) 排序技術(shù),對于等級考試，這個部分的考

3、核重點主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹(遍歷、結(jié)點），還有排序和查找考試中也經(jīng)常會涉及到。,第6頁,算法的定義 對解題方案準(zhǔn)確而完整的描述稱為算法。,算法是程序設(shè)計的核心, 算法的基本概念,算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機(jī)解題的過程(計算的方法)。在這個過程中，無論是形成解題思路(推理實現(xiàn)的算法)還是編寫程序(操作實現(xiàn)的算法)，都是在實施某種算法。,例： n個數(shù)從大到小進(jìn)行排序。 有多種排序方法 ，常用的有冒泡排序、選擇排序等。,算法可以簡單地理解為對實際問題的求解過程。,第7頁,2 . 算法的基本特征 一個算法應(yīng)該具有以下五個重要的特征：,

4、有窮性 確定性 輸入 輸出 可行性,第8頁,算法與計算機(jī)程序 算法_是一組邏輯步驟 程序用計算機(jī)語言描述的算法,3. 算法的表示,INPUT r S=3.14 * r*r PTINT S,問題： 輸入園的半徑，計算園的面積,一個算法的表示需要使用一些語言形式。 傳統(tǒng)的算法-圖形法，如“流程圖”和N-S圖 目前常用的方法-使用偽碼描述算法。,第9頁,冒泡排序的方法： 1.掃描整個線性表，逐次對相鄰的兩個元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后 ； 2.除最后一個元素，對剩余的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置； 3.重復(fù)上述過程； 對于長度為n的線

5、性表，冒泡排序需要對表掃描n-1遍。,算法舉例：n個數(shù)排序,第10頁,4. 算法的兩個基本要素：,基本運算和操作 算術(shù)運算 關(guān)系運算 邏輯運算 數(shù)據(jù)傳輸,控制結(jié)構(gòu) 順序 選擇 循環(huán),一是對數(shù)據(jù)對象的運算和操作； 二是算法的控制結(jié)構(gòu)。,算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法,第11頁,5. 算法評價 評價一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲需求： 時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量 一般可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量計算工作量 空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間 時間復(fù)雜度它大致等于計算機(jī)執(zhí)行一種簡單操作所需的平均時間與算法中

6、進(jìn)行簡單操作的次數(shù)的乘積。 一個算法在計算機(jī)存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個部分,第12頁,一、算法,對解題方案準(zhǔn)確而完整的描述稱為算法。 算法不等于程序，也不等計算機(jī)方法，程序的編制不可能優(yōu)于算法的設(shè)計。 算法評價： 時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量 空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間,第13頁,(1) 在計算機(jī)中，算法是指_。（2011年9月） A. 查詢方法 B. 加工方法 C. 解題方案的準(zhǔn)確而完整的描述 D. 排序方法 (2)下列敘述中正確的是 （07年4月） A

7、)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B)算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量 C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的 D)算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān) (3)算法的有窮性是指 (08年4月) A）算法程序的運行時間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的用戶使用,(c),(B),算法習(xí)題:,(A),第14頁,(4) 算法的時間復(fù)雜度是指 (2010年3月) A)算法的執(zhí)行時間 B)算法所處理的數(shù)據(jù)量 C)算法程序中的語句或指令條數(shù) D)算法在執(zhí)行過程中所需要的基本運算次數(shù) (5) 算法的空間復(fù)雜度是指

8、 (09年9月) A）算法在執(zhí)行過程中所需要的計算機(jī)存儲空間 B）算法所處理的數(shù)據(jù)量 C）算法程序中的語句或指令條數(shù) D）算法在執(zhí)行過程中所需要的臨時工作單元數(shù) (6) 下列敘述中正確的是 (06年9月) A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大 B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小 C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說法都不對,(D) 計算工作量,(A),(D),第15頁,（7）將長度為n的順序存儲在線性表中刪除一個元素，最壞情況下需要移動表中的元素個數(shù)為（ ）。,答案：n-1,第16頁,計算機(jī)在進(jìn)行數(shù)據(jù)處理時，實際需要處理的數(shù)據(jù)元素一般有很

9、多，而這些大量的數(shù)據(jù)元素都需要存放在計算機(jī)中，因此，大量的數(shù)據(jù)元素在計算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機(jī)的存儲空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。,二、數(shù)據(jù)結(jié)構(gòu),程序=算法+數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。,第17頁,二. 數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，它包括三個方面。（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； （2）在對數(shù)據(jù)進(jìn)行處理

10、時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； （3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。,第18頁,1. 邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （1）表示數(shù)據(jù)元素的信息； （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。,第19頁,常見的邏輯結(jié)構(gòu)有： 線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。, 線性結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對一個的關(guān)系； 樹形結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系； 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。 其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示。

11、,第20頁,2. 存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)存儲空間中的具體實現(xiàn)。 常見的存儲結(jié)構(gòu)有： 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 索引存儲結(jié)構(gòu),只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲結(jié)構(gòu)。,第21|92頁,常見的數(shù)據(jù)結(jié)構(gòu),1.線性表 2.棧和隊列 3.樹,第22|92頁,復(fù)習(xí)： 指針 結(jié)構(gòu)體,第23頁, 線性表（Linear List）,線性表是由n（n0）個數(shù)據(jù)元素 a1，a2，ai，an組成的一個有限序列。,簡單的線性表,復(fù)雜的線性表,記錄1 02011001 張三 男,記錄2 02011003

12、李四 女 ,記錄3,記錄4,第24頁,線性表的順序存儲結(jié)構(gòu),順序存儲結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，順序存儲結(jié)構(gòu)只存儲結(jié)點的值，不存儲結(jié)點間的關(guān)系，結(jié)點間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。,存儲地址,2000,2004,2000+4*(i-1),2000+4*(n-1),占4個字節(jié),Loa（ai）=Loa（a1）+L*（i-1）,第i個數(shù)的地址,第一個數(shù)的地址,L為該類型數(shù)所占的字節(jié),線性表的存儲結(jié)構(gòu),線性表的存儲結(jié)構(gòu)有兩種： 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu),第25頁,順序表的插入運算 順序表的刪除運算,順序表的插入和刪除運算,在線性表順序存儲情況下，要插入或刪除一個元素，

13、都會由于數(shù)據(jù)元素的移動而消耗大量的處理時間，所以這種存儲方式對于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動的線性表是合適的。,線性表的順序存儲結(jié)構(gòu)稱為順序表。,第26頁,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu),線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點的指針域指示。 鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個存儲結(jié)點不僅存儲結(jié)點的值，而且存儲結(jié)點之間的關(guān)系：,第27頁,應(yīng)用舉例線性鏈表的存儲結(jié)構(gòu),設(shè)線性表為（a1，a2，a3，a4，a5）,HEAD,3,線性鏈表的物理狀態(tài),線性表的順序存儲結(jié)構(gòu),注意:1 2 3 此類編號不代表所在

14、的地址單元的地址編碼,第28頁,單鏈表的插入運算 單鏈表的刪除運算,線性鏈表的插入和刪除運算,采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲空間開銷較大，但是進(jìn)行插入和刪除運算不會造成大量元素的移動。,循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點。,第29頁,雙向鏈表的存儲結(jié)構(gòu),提問：單向鏈表的缺點是什么？ 提示：如何尋找結(jié)點的直接前趨。 雙向鏈表可以克服單鏈表的單向性的缺點。 在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。,HEAD,3,1,5,10,雙向循環(huán)鏈表,第30頁,線性表的存儲結(jié)構(gòu)有兩種,順序存儲結(jié)構(gòu),注意： 數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系與

15、它們的邏輯關(guān)系不一定是相同的。 一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且不同的存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率 。,HEAD,3,鏈?zhǔn)酱鎯Y(jié)構(gòu),線性表 : a1，a2，a3，a4，a5 ,第31頁,2. 棧和隊列,棧和隊列都是特殊的線性表。 棧（Stack）及其基本運算 隊列（Queue）及其基本運算 循環(huán)隊列及其基本運算,第32頁,棧（Stack）是一種特殊的線性表。其特點是插入和刪除運算都只能在線性表的一端進(jìn)行。 棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的線性表。 棧的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。 下面討論順序存儲結(jié)構(gòu)中棧元素的插入和刪除運算。 順序棧的進(jìn)棧和出棧運算 棧

16、的基本運算有三種：入棧、退棧和讀棧頂元素,在順序棧中插入和刪除運算不需要移動表中其他數(shù)據(jù)元素。,第33頁,隊列（Queue）是一種特殊的線性表。其特點是所有的插入都在表的一端進(jìn)行，所有的刪除運算都在表的另一端進(jìn)行。 隊列是按照“先進(jìn)先出”或“后進(jìn)后出”的原則組織數(shù)據(jù)的線性表。 隊列的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。 順序隊列的運算,棧有三種操作： 入棧出棧讀棧頂元素 隊列有三種操作：入隊出隊讀隊首元素,例：有入棧元素序列：ABCD，求可能的出棧序列 如是隊列又是什么情況呢？,第34頁,循環(huán)隊列 把隊列的存儲空間在邏輯上看作一個環(huán)，當(dāng)R指向存儲空間的末端后，就把它重新置于始端。 循

17、環(huán)隊列的運算,隊列中進(jìn)行插入的一端稱做隊尾(rear),進(jìn)行刪除的一端稱做隊首(front)。,習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于【 】結(jié)構(gòu)。（2005年9月）,答案：存儲結(jié)構(gòu)。,第35頁,常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu),線性表 線性結(jié)構(gòu) 棧 是特殊的線性表 隊列 也是一種操作受限的特殊的線性表 樹 （樹型結(jié)構(gòu)） 是一種重要的非線形數(shù)據(jù)結(jié)構(gòu),第36頁,1：數(shù)據(jù)的存儲結(jié)構(gòu)是指 （2005年4月） A) 存儲在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲空間量 C) 數(shù)據(jù)在計算機(jī)中的順序存儲方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 2. 下列敘述中正確的是 （2009年3月） A）棧是“先進(jìn)先出”

18、的線性表 B）隊列是“先進(jìn)后出”的線性表 C）循環(huán)隊列是非線性結(jié)構(gòu) D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于 。 4. 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是 A）循環(huán)隊列 B) 帶鏈隊列 C) 二叉樹 D）帶鏈棧,答案：D。,答案：D。,答案：線性結(jié)構(gòu)。,答案：c,第37頁,5。下列敘述中正確的是（ ）。 （2008年9月） A）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的 B）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu) C）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表 D）

19、鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間,答案：A。,6。下列關(guān)于棧的敘述正確的是 （2008年4月） A）棧按“先進(jìn)先出”組織數(shù)據(jù) B)棧按“先進(jìn)后出”組織數(shù)據(jù) C）只能在棧底插入數(shù)據(jù) D）不能刪除數(shù)據(jù),答案：B。,第38頁,9. 設(shè)某循環(huán)隊列的容量為50，如果頭指針front=45(指向隊頭元素的前一位置)，尾指針rear=10(指向隊尾元素)，則該循環(huán)隊列中共有 【2】 個元素。 （2010年3月）,8。假設(shè)用一個長度為50的數(shù)組（數(shù)組元索的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧

20、中具有【 】個元素。 （2009年3月）,答案：19,答案：15,7. 一個隊列的初始狀態(tài)為空?，F(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊，然后再依次退隊，則元素退隊的順序為 【1】 。（2010年3月）,答案：A，B，C，D，E，F(xiàn)，5，4，3，2，1,第39頁,10、下列敘述中正確的是：（2012年3月） A、循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu) B、循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu) C、循環(huán)隊列是非線性結(jié)構(gòu) D、循環(huán)隊列是一直邏輯結(jié)構(gòu),答案：A,11、下列敘述中正確的是：（2012年3月） A、棧是一種先進(jìn)先出的線性表 B、隊列是一種后進(jìn)先出的線性表 C、棧和隊列都是非線性結(jié)

21、構(gòu) D、以上三種說法都不對,答案：D,12、設(shè)循環(huán)隊列的存儲空間為Q(1:3),初始狀態(tài)為front=rear=30。現(xiàn)經(jīng)過一系列入隊與退隊運算后，front=16，rear=15，則循環(huán)隊列中有（ ）個元素。（2012年3月）,答案：29,第40頁,一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(jié)構(gòu)。 有且僅有一個根結(jié)點； 除第一個結(jié)點外，每一個結(jié)點最多有一個直接前驅(qū)結(jié)點； 除最后一個結(jié)點外，每一個結(jié)點最多有一個直接后繼結(jié)點。,線性結(jié)構(gòu)與非線性結(jié)構(gòu) 線性表、棧和隊列都是線性結(jié)構(gòu) 一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱其為非線性結(jié)構(gòu)。,第41頁,樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。 樹的概

22、念 二叉樹的概念 二叉樹的存儲 二叉樹的遍歷,3. 樹與二叉樹,第42頁,樹的概念,樹的定義：n個結(jié)點的有限集。（n=0）,A,B,D,F,E,C,G,H,I,J,K,M,根：only one 若n=0，則稱為空樹； 否則，當(dāng)n1時，其余結(jié)點被分成m（m0）個互不相交的子集T1，T2，.，Tm，每個子集又是一棵樹。由此可以看出，樹的定義是遞歸的。 Question：如何辨別根？,A,只有一個結(jié)點的樹,第43頁,樹型結(jié)構(gòu)的常用術(shù)語,A,B,D,F,E,C,G,H,I,J,K,M,結(jié)點的度 一個結(jié)點的子樹的個數(shù)； Q：結(jié)點A、G的度數(shù)？ 樹的度 樹中所有結(jié)點度的最大值；Q：右圖中樹的度？ 終端結(jié)點

23、 度為0的結(jié)點； Q：圖中葉子結(jié)點有幾個？7 非終端結(jié)點 度不為0的結(jié)點； Q：圖中非終端結(jié)點有幾個？ 5,孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、結(jié)點的子孫、結(jié)點的祖先,第44頁,樹型結(jié)構(gòu)的常用術(shù)語,A,B,D,F,E,C,G,H,I,J,K,M,結(jié)點的層次 樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推； Q：圖中結(jié)點F的層次？ 樹的深度 樹中所有結(jié)點層次的最大值； Q：圖中樹的深度？ 有序樹、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。,第45頁,二叉樹的概念,定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是： 每個結(jié)點最多有兩棵

24、子樹； 子樹有左右之分，次序不能任意顛倒。,二叉樹的5種基本形態(tài),第46頁,二叉樹的性質(zhì),【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個結(jié)點（i1）,第47頁,【性質(zhì)2】深度為h的二叉樹最多有2h -1個結(jié)點（h 1） 滿二叉樹：如果一個深度為h的二叉樹擁有2h-1個結(jié)點，則將它稱為滿二叉樹。 完全二叉樹：有一棵深度為h，具有n個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進(jìn)行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1n的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。,第48頁,滿二叉樹,完全二叉樹,12,13,8,9,10,11,4,5,6,

25、7,1,2,3,完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹,第49頁,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉樹,深度為4的完全二叉樹,8,4,5,6,7,1,2,3,第50頁,【性質(zhì)3】二叉樹上葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1,度為2的結(jié)點,葉子結(jié)點,第51頁,【性質(zhì)4】具有n個結(jié)點的完全二叉樹的深度為 log2 (n+1) 其中，log2n 的結(jié)果是不大于log2n的最大整數(shù),深度為4的滿二叉樹,深度為4的完全二叉樹,深度為3的完全二叉樹具有47 深度為4的完全二叉樹具有815 深度為5的完全二叉樹具有1531,log2(8+1) = ln9/In2=4 log2

26、 (15+ 1) =In16/In2=4,深度為6的完全二叉樹 具有3263 深度為7的完全二叉樹 具有64127 深度為8的完全二叉樹 具有128255 深度為9的完全二叉樹 具有256511 深度為10的完全二叉樹具有5121023 深度為11的完全二叉樹具有10242047,第52頁,1：在深度為7的滿二叉樹中,葉子結(jié)點的個數(shù)為（2006年4月） A)32 B)31 C)64 D)63 2：在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為【 】 。(07年4月） 3：一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為 （07年9月） A）219 B）221 C）229

27、 D）231 4： 某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有 【 】個葉子結(jié)點。（2005年4月）,樹型結(jié)構(gòu)方面的考題,1答案：C。,3答案：A。,2答案：63。,4答案：19。,第53頁,5：一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為【 】個。（2005年9月） 6、一棵二叉樹共有25個節(jié)點，其中5個時子節(jié)點，那么度為1的節(jié)點數(shù)為 A、4 B、6 C、10 D、16,5答案：32。,6答案：C。,第54頁,二叉樹的存儲,在計算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。,二叉樹的存儲結(jié)點的結(jié)構(gòu),A,B,D,C,F,G,E,t,第55頁,二叉樹的遍歷,遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。

28、二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運算有聯(lián)系。 遍歷的方式有三種 （1）先（前）序遍歷（DLR） （2）中序遍歷（LDR） （3）后序遍歷（LRD）,第56頁,二叉樹的遍歷,遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。 （1）先（前）序遍歷（DLR） 若二叉樹為空，則結(jié)束遍歷操作；否則 訪問根結(jié)點； 先序遍歷左子樹； 先序遍歷右子樹。,先序遍歷的結(jié)果： A B E C F G H D,第57頁,（2）中序遍歷（LDR） 若二叉樹為空，則結(jié)束遍歷操作；否則 中序遍歷左子樹； 訪問根結(jié)點； 中序遍歷右子樹。 中序遍歷的結(jié)果： E B A F H G C D （3）后序遍歷（LRD） 若二叉樹為空，則

29、結(jié)束遍歷操作；否則 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點。 后序遍歷的結(jié)果： E B H G F D C A,第58頁,先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCA,A,B,C,F,H,D,E,G,下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？,練習(xí)：,根據(jù)先序遍歷序列，建立二叉樹,第59頁,1:設(shè)二叉樹如下： （2010年3月）對該二叉樹進(jìn)行后序遍歷的結(jié)果為 【3】,樹型結(jié)構(gòu)方面的考題 2,2: 對如下二叉樹（2006年4月） 進(jìn)行后序遍歷的結(jié)果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,EDBGHFCA

30、,D,A,B,C,F,H,D,G,E,第60頁, 查找技術(shù),查找是數(shù)據(jù)處理的重要內(nèi)容。 查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。 若找到了滿足條件的結(jié)點，稱查找成功；否則稱查找失敗。 衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵字進(jìn)行的平均比較次數(shù)。 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： 順序查找 二分查找,第61頁,順序查找,線性表中最簡單的查找方法。 方法：從線性表的第一個元素開始，依次將線性表中的元素與關(guān)鍵字進(jìn)行比較，若相等，則查找成功；若將所有元素都與關(guān)鍵字進(jìn)行了比較但不相等，則查找失敗。 順序查找法的適用場合： 對線性表中元素的排列次序沒有要求； 對線性

31、表的存儲結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序結(jié)構(gòu)均可。,第62頁,二分查找(折半查找),是一種效率較高的查找方法，但是只適合順序存儲的有序表。 二分查找的方法：首先將關(guān)鍵字與線性表中間位置的結(jié)點比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個子表中進(jìn)行；重復(fù)上述過程，直至查找成功或子表長度為0。 二分查找法的適用場合： 線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列； 線性表采用順序存儲結(jié)構(gòu)。,第63|92頁,折半查找算法舉例,對給定數(shù)列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。 a1 a2 a3 a4 a5 a6 a

32、7 a8 a9 a10 第1次： 3，5，11，17，21，23，28，30，32，50 K=30 mid1=（1+10）/2 = 5 ka(mid1)=a(5)=21 第2次： 23，28，30，32，50 mid2 = （6+10） /2 = 8 K=a(mid2)=a(8)=30,low,high,mid,low,high,mid,第64頁,練習(xí) 假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關(guān)鍵字值為27的數(shù)據(jù)元素.,對于長度為n的有序線性表，最壞情況只需比較log2n次。,第65頁, 排序技術(shù),排

33、序指將一個無序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。 排序方法中其排序?qū)ο笠话闶琼樞虼鎯Φ木€性表。 根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法： 交換類排序法 冒泡排序 快速排序 插入類排序法 簡單插入排序 希爾排序 選擇類排序法 簡單選擇排序 堆排序,第66頁,冒泡排序,冒泡排序的方法： 掃描整個線性表，逐次對相鄰的兩個元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最小)的元素排到表的最后(或最前) ； 除最后(或最前)一個元素，對剩余的元素重復(fù)上述過程，將次大(或次小)的數(shù)排到表的倒數(shù)(或正數(shù))第二個位置； 重復(fù)上述過程； 對于長度為n的線性表，冒泡排

34、序需要對表掃描n-1遍。,第67|92頁,冒泡排序的方法,設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（18，20，15，32，4，25），第一趟冒泡排序后的序列狀態(tài)如圖所示： 18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25 18 15 20 4 25 32 最大數(shù),第二趟冒泡排序,第68|92頁,Q：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？ Q：你覺得冒泡排序的效率如何？如果是你，你會用什么方法來排序？ 冒泡排序比較簡單，當(dāng)初始序列基本有

35、序時，冒泡排序有較高的效率，反之效率較低。 冒泡排序終止條件: 本趟排序未發(fā)生交換，終止排序算法,第69|92頁,初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54,設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（26,18,32,54,47,9,15 ),冒泡排序法，需要比較的次數(shù)為n(n-1)/2；,第70頁,選擇排序,選擇排序的方法： 掃描整個線性表，從中找出最小的元素，與第一個元素交換； 除

36、第一個元素，對剩下的子表采用相同的方法找出次小的數(shù)，與第二個數(shù)交換； 重復(fù)上述過程； 對于長度為n的線性表，選擇排序需要對表掃描n-1遍。,簡單選擇排序法,最壞情況需要n(n-1)/2次比較；,第71|92頁,初態(tài)： 15，14，22，30，37，15，11 第一趟： 11 14，22，30，37，15，15 第二趟： 11，14 22，30，37，15，15 第三趟： 11，14，15 30，37，22，15 第四趟： 11，14，15，15 37，22，30 第五趟： 11，14，15，15，22 37，30 第六趟： 11，14，15，15，22，30 37 有序序列,例：設(shè)待排數(shù)據(jù)元素

37、的關(guān)鍵字為（15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：,第72頁,排序法小結(jié)：,簡單選擇排序法,最壞情況需要n(n-1)/2次比較； 冒泡排序法, 最壞情況需要n(n-1)/2次比較； 希爾排序法, 最壞情況需要O(n1.5)次比較； 堆排序法, 最壞情況需要O(nlog2n)次比較；,第73頁,排序查找方面的考題：,(1) 對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是（2005年4月） A) 冒泡排序為n/2 B) 冒泡排序為n C) 快速排序為n D) 快速排序為n(n-1)/2 (2)在長為64的有序線性表中進(jìn)行順序查找，最壞情況

38、下需要比較的次數(shù)為_。（06年9月） A）、63 B）、64 C）、6 D）、7 (3) 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是（2005年9月） A）順序存儲的有序線性表 B）線性鏈表 C）二叉鏈表 D）有序線性鏈表 (4) 下列排序方法中，最壞情況下比較次數(shù)最少的是（09年3月） A）冒泡排序 B）簡單選擇排序 C）直接插入排序 D）堆排序,D,B,A,D,第74頁,第二章 程序設(shè)計基礎(chǔ),內(nèi)容： 1. 程序設(shè)計方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計。 3. 面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。,第75頁,1結(jié)構(gòu)化程序設(shè)計,結(jié)構(gòu)化程序設(shè)計方法的四條原則是： 1. 自頂向下；

39、2. 逐步求精； 3. 模塊化； 4. 限制使用goto語句。 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：（1）順序結(jié)構(gòu)： 簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)（分支結(jié)構(gòu)）： 包括簡單選擇和多分支選擇結(jié)構(gòu)，（3）重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）： 可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。,第76頁,2面向?qū)ο蟮某绦蛟O(shè)計,對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢?對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 屬性即對象所包含的信息 操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。,第77頁,類是指具有共同屬性、共同方法的對象的

40、集合。 所以類是對象的抽象，對象是對應(yīng)類的一個實例。 消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括 （1）接收消息的對象的名稱； （2）消息標(biāo)識符，也稱消息名； （3）零個或多個參數(shù)。 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。 單繼承指一個類只允許有一個父類 多重繼承指一個類允許有多個父類。 多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。,第78頁,程序設(shè)計基礎(chǔ)方面的考題,1.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和【 】 . (2009年3月) 2. 下列選項中不屬于結(jié)構(gòu)化程序設(shè)計原則的是（2009年9月） A) 可封裝 D)

41、 自頂向下 C) 模塊化 D) 逐步求精 3. 以下敘述中正確的是。（2010年3月） A）程序設(shè)計的任務(wù)就是編寫程序代碼并上機(jī)調(diào)試 B）程序設(shè)計的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu) C）程序設(shè)計的任務(wù)就是確定所用算法 D）以上三種說法都不完整 4.在面向?qū)ο蠓椒ㄖ?，類的實例稱為 【_】 。（2005年4月） 5.在面向?qū)ο蠓椒ㄖ? 【_】 描述的是具有相似屬性與操作的一組對象。（2006年4月）,（順序結(jié)構(gòu)）,A,D,對象,類,第79頁,第三章 軟件工程基礎(chǔ),計算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。,第80頁,1.軟件工程概念,軟件工

42、程是應(yīng)用于計算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。軟件工程包括3個要素：方法、工具和過程。 軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的過程。軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行維護(hù)，主要活動階段是：（1）可行性研究與計劃制定；（2）需求分析；（3）軟件設(shè)計；（4）軟件實現(xiàn)；（5）軟件測試；（6）運行和維護(hù)。,第81頁,2結(jié)構(gòu)化分析方法,結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具 （1）數(shù)據(jù)流圖； （2）數(shù)據(jù)字典； （3）判定樹；判定表。 （

43、4）軟件需求規(guī)格說明書,第82頁,3結(jié)構(gòu)化設(shè)計方法,軟件設(shè)計包括：總體設(shè)計與詳細(xì)設(shè)計 在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。 常見的過程設(shè)計工具有： 圖形工具（程序流程圖,N-S,PAD） 表格工具（判定表） 語言工具（PDL偽碼）,第83頁,程序流程圖,N-S圖,PAD圖,第84頁,4軟件測試,軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。 軟件測試方法：靜態(tài)測試： 包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進(jìn)行。動態(tài)測試： 是基本計算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法 軟件測試過程一般按4個步驟進(jìn)行：單元測試、集成測試、驗

44、收測試（確認(rèn)測試）和系統(tǒng)測試。,第85頁,5 程序的調(diào)試,程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進(jìn)行。 軟件調(diào)試 靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段。 動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：（1）強(qiáng)行排錯法；（2）回溯法；（3）原因排除法。,第86頁,(1) 下面敘述中錯誤的是 (2009年3月） A）軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤 B）對被調(diào)試的程序進(jìn)行“錯誤定位”是程序調(diào)試的必要步驟 C）程序調(diào)試通常也稱為Debug D）軟件測試應(yīng)嚴(yán)格執(zhí)行測試計劃，排除測試的隨意性 (2) 軟件測試可分為白盒測試和黑盒測試?；韭窂綔y試屬于【 】測試

45、。(2009年3月） (3) 按照軟件測試的一般步驟，集成測試應(yīng)在_測試之后進(jìn)行。 (4) 軟件工程三要素包括方法、工具和過程，其中，_支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。(2008年9月) (5)軟件設(shè)計中劃分模塊的一個準(zhǔn)則是(2009年9月） A) 低內(nèi)聚低耦合 B) 高內(nèi)聚低耦合 C) 低內(nèi)聚高耦合 D) 高內(nèi)聚高耦合,A,軟件工程方面的考題：,白盒,單元,過程,B,第87頁,(6) 下列敘述中正確的是（2005年9月）A A）軟件交付使用后還需要進(jìn)行維護(hù) B）軟件一旦交付使用就不需要再進(jìn)行維護(hù) C）軟件交付使用后其生命周期就結(jié)束 D）軟件維護(hù)是指修復(fù)程序中被破壞的指令 (7) 程序流程

46、圖中的菱形框表示的是 【2】(2009年9月) 。 (8)軟件開發(fā)過程主要分為需求分析、設(shè)計、編碼與測試四個階段，其中 【3】 階段產(chǎn)生“軟件需求規(guī)格說明書。 （2009年9月） (9)下列敘述中正確的是（2006年4月） A)軟件測試應(yīng)該由程序開發(fā)者來完成 B)程序經(jīng)調(diào)試后一般不需要再測試 C)軟件維護(hù)只包括對程序代碼的維護(hù) D)以上三種說法都不對,A,邏輯條件,需求分析,D,第88頁,(3)軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件(或工具軟件)。下面屬于系統(tǒng)軟件的是 A)編輯軟件 B)操作系統(tǒng) C)教務(wù)管理系統(tǒng)D)瀏覽器 (4)軟件(程序)調(diào)試的任務(wù)是 A)診斷和改正程序中的錯誤B

47、)盡可能多地發(fā)現(xiàn)程序中的錯誤 C)發(fā)現(xiàn)并改正程序中的所有錯誤D)確定程序中錯誤的性質(zhì) (5)數(shù)據(jù)流程圖(DFD圖)是 A)軟件概要設(shè)計的工具 B)軟件詳細(xì)設(shè)計的工具 C)結(jié)構(gòu)化方法的需求分析工具D)面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?(6)軟件生命周期可分為定義階段，開發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計屬于 A)定義階段 B)開發(fā)階段 C)維護(hù)階段 D)上述三個階段,2010年3月計算機(jī)等級考試,B,A,C,B,第89頁,數(shù)據(jù)庫設(shè)計基礎(chǔ)知識點得分表,時間,知識點,第90頁,第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ),數(shù)據(jù)：實際上就是描述事物的符號記錄。 數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用

48、數(shù)據(jù)的集成，并可被各個應(yīng)用程序共享。 數(shù)據(jù)庫管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。 數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。 數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。,第91頁,數(shù)據(jù)庫系統(tǒng),92,常見的關(guān)系數(shù)據(jù)庫管理系統(tǒng),小型數(shù)據(jù)庫： Visual FoxPro （以后簡稱為VFP） Access (office套件中的一個) Paradox 大型數(shù)據(jù)庫： Oracle Informix SYBASE SQL se

49、rver 等,第93頁,數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：（1）數(shù)據(jù)定義語言： 負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建； （2）數(shù)據(jù)操縱語言： 負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等；（3）數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。 數(shù)據(jù)庫管理系統(tǒng)的發(fā)展 (1)文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。 (2)層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段 ：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。 (3)關(guān)系數(shù)據(jù)庫系統(tǒng)階段,1.數(shù)據(jù)庫系統(tǒng)的基本概念,第94頁,關(guān)系數(shù)據(jù)庫系統(tǒng)的基本特點： 數(shù)據(jù)的集成性 數(shù)據(jù)的高共享性與低冗余性 數(shù)據(jù)

50、獨立性（物理獨立性與邏輯獨立性） 數(shù)據(jù)統(tǒng)一管理與控制。 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。 數(shù)據(jù)庫系統(tǒng)的三級模式：（1）概念模式（2）外模式（3）內(nèi)模式 數(shù)據(jù)庫系統(tǒng)的兩級映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。,1.數(shù)據(jù)庫系統(tǒng)的基本概念,95,應(yīng)用,外模式 (用戶數(shù)據(jù)庫),應(yīng)用,外模式 (用戶數(shù)據(jù)庫),應(yīng)用,外模式 (用戶數(shù)據(jù)庫),概念模式 (概念數(shù)據(jù)庫),內(nèi)模式 (物理數(shù)據(jù)庫),數(shù)據(jù)庫,外模式概念模式映射,概念模式內(nèi)模式映射模式,96,2. 數(shù)據(jù)模型,數(shù)據(jù)模型（Data Model）是對客觀事物及其關(guān)系的數(shù)據(jù)描述。 數(shù)據(jù)庫中的數(shù)據(jù)模

51、型可以將復(fù)雜的現(xiàn)實世界要求反映到計算機(jī)數(shù)據(jù)庫中的物理世界。 現(xiàn)實世界 信息世界 計算機(jī)世界 數(shù)據(jù)模型是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件。 數(shù)據(jù)模型所描述的內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。,第97頁,2. 數(shù)據(jù)模型,E-R模型的基本概念（1）實體：現(xiàn)實世界中的事物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。 一個班級的學(xué)生，學(xué)生與學(xué)生之間是一對一的關(guān)系。 在一所學(xué)校，一門課程與學(xué)生之間是一對多的關(guān)系。 在一所學(xué)校，多門課程與多個學(xué)生之間是多對多的關(guān)系。,98,E-R模型的圖示法 用簡單的幾何

52、圖形表示實體集、屬性與聯(lián)系。 (1)實體集表示法 在E-R圖中用矩形表表示實體集，在矩形內(nèi)寫上實體集名稱。如實體集學(xué)生(student)、實體集課程(course) (2)屬性表示法 在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性名稱。如學(xué)生有屬性：學(xué)號(S#)、姓名(Sn)及年齡(Sa)可用如下表示。,student,course,S#,Sn,Sa,99,(3)聯(lián)系表示法 在E-R圖中用菱形(內(nèi)寫上聯(lián)系名)表示聯(lián)系。如學(xué)生與課程的聯(lián)系SC,如下圖所示： (4)實體集與屬性間的聯(lián)系關(guān)系 屬性依附于實體集，它們之間有聯(lián)系關(guān)系用無向線段表示。,SC,student,S#,Sn,Sa,100,屬

53、性也依附于聯(lián)系，它們之間也有聯(lián)系關(guān)系，因此也可用無向線段，如聯(lián)系SC可與學(xué)生的課程成績屬性G建立聯(lián)系并用下圖表示。 (5)實體集與聯(lián)系間的連接關(guān)系(也可用無向線段),SC,G,student,course,SC,第101頁,E-R模型之間的聯(lián)接關(guān)系： 實體是概念世界中的基本單位， 屬性有屬性域，每個實體可取屬性域內(nèi)的值。 一個實體的所有屬性值叫元組。 E-R模型的圖示法： （1）實體集表示法；用長方形 （2）屬性表法；用橢圓形 （3）聯(lián)系表示法。用菱形，(m:n),第102頁,層次模型（采用樹型結(jié)構(gòu)）,圖1-4 層次模型示例,第103頁,網(wǎng)絡(luò)模型（采用無向圖型結(jié)構(gòu)）,第104頁,關(guān)系模型（采用

54、二維表結(jié)構(gòu)）,第105頁,關(guān)系數(shù)據(jù)模型,關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關(guān)系。 關(guān)系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。,106,1.關(guān)系的數(shù)據(jù)結(jié)構(gòu) 二維表由表框架與表元組組成。 表框架由n個命名的屬性組成(n稱為屬性元素)。 每個屬性有一個取值范圍稱為值域。 表框架對應(yīng)了關(guān)系的模式，即類型的概念。 每行數(shù)據(jù)稱為元組，一個元組由n個元組分量所組成，每個元組分量是表結(jié)構(gòu)中每個屬性的投影值。,107,一個二維表要滿足下面7個性質(zhì)就可稱為一個關(guān)系。 二維表中元組個數(shù)

55、是有限的 二維表中元組均不相同 二維表中元組的次序可任意交換 二維表中元組的分量是不可分割的基本數(shù)據(jù)項 二維表中屬性名各不相同 二維表中屬性與次序無關(guān)，可任意交換 二維表屬性中的分量具有與該屬性相同的值域,惟一標(biāo)識元組的最小屬性集稱為該表的鍵(或碼)，在VFP表中稱為主關(guān)鍵字,108,關(guān)系模型的基本運算： 1. 數(shù)據(jù)查詢 查詢關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)，一個關(guān)系內(nèi)的查詢以及多個關(guān)系間的查詢。 查詢的基本單位為元組分量，先定位后操作。 縱向定位（列指定） 橫向定位（行選擇） 2. 數(shù)據(jù)插入 插入一個元組（不定位） 3. 數(shù)據(jù)刪除 刪除一個元組（定位、操作） 4. 數(shù)據(jù)修改 刪除需修改的元組再插入修改后的

56、元組,關(guān)系操作,109,關(guān)系模型的基本運算： 1. 插入 集合的并運算 2. 刪除 集合的差(交) 運算 3. 修改 集合的差|并(除)運算。 4. 查詢 （投影、選擇、笛卡爾積運算）,3.關(guān)系代數(shù),集合的并運算,110,由關(guān)系R和S通過交運算得到關(guān)系T，,111,用于查詢的集合運算： （1）投影 對于關(guān)系R內(nèi)的域指定稱為投影運算。 S關(guān)系就是對R關(guān)系指定A和B兩個域的結(jié)果,R,S,3.關(guān)系代數(shù),112,關(guān)系代數(shù),（2）選擇 選擇運算的關(guān)系是由關(guān)系R中那些滿足邏輯條件的元組所組成。 S關(guān)系就是R關(guān)系中滿足A=a的結(jié)果,R,S,有了投影和選擇運算，我們對一個關(guān)系內(nèi)的任意行、列的數(shù)據(jù)都可以方便的找

57、到。,113,笛卡爾積是對兩個關(guān)系的合并操作。 有三個關(guān)系R、S和T R關(guān)系 n1行, m1列 S關(guān)系 n2行， m2列 T關(guān)系 行數(shù)= n1*n2 列數(shù)= m1+m2,R,S,T,（3）笛卡爾積運算,114,笛卡爾積建立兩個關(guān)系的連接，但得到的關(guān)系龐大且數(shù)據(jù)大量冗余。在實際應(yīng)用中一般相互連接的關(guān)系往往須滿足一些條件，所得到的結(jié)果也較為簡單。 自然連接滿足兩個關(guān)系中有公共域，通過公共域的相等值進(jìn)行連接。 有三個關(guān)系R、S和T R關(guān)系 n1行, m1列 S關(guān)系 n2行， m2列 T關(guān)系 行數(shù)(n1或n2中行數(shù)多的一個) 列數(shù)m1+m2,（4）自然連接運算,115,有三個關(guān)系R、S和T，由關(guān)系R和S通過運算得到關(guān)系T，則使用的運算為,笛卡爾積,R,S,T,自然連接,R,S,T,116,在三個關(guān)系R ， S和T如下： 由關(guān)系R和S通過自然連接運算得到關(guān)系T。,R,S,T,第117頁,數(shù)據(jù)庫設(shè)計與管理,數(shù)據(jù)庫設(shè)計的兩種方法：（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；（2）面向過程：以處理需求為主，兼顧信息需求。 數(shù)據(jù)庫的生命周期： 需求分析階段 結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒?數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個部分：數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲、處理過程。 概念設(shè)計階段 分析數(shù)據(jù)內(nèi)在語義關(guān)系。E-R模型 邏輯設(shè)計階段 物理設(shè)計階段 編碼階段 測試階段 運行階段 進(jìn)一步修