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

1、第1頁(yè)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱 q 數(shù)據(jù)結(jié)構(gòu)與算法q 程序設(shè)計(jì)基礎(chǔ)q 軟件工程基礎(chǔ)q 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)這四個(gè)方面在試卷中出現(xiàn)的情況是：選擇題10個(gè)（20分），填空題5個(gè)（10分），總分值占到了試卷卷面分的30，是一個(gè)不小的比例。 第1頁(yè)/共132頁(yè)第2頁(yè)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)試卷分析 章節(jié)章節(jié)考試時(shí)間考試時(shí)間數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法與算法程序設(shè)程序設(shè)計(jì)基礎(chǔ)計(jì)基礎(chǔ)軟件工軟件工程基礎(chǔ)程基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)計(jì)基礎(chǔ)2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年

2、9月10分2分8分10分2010年3月10分0分10分10分第2頁(yè)/共132頁(yè)第3頁(yè) 算法的基本概念 2.2.算法復(fù)雜度的概念和意義 數(shù)據(jù)結(jié)構(gòu)的概念 線性表 棧和隊(duì)列 樹與二叉樹 查找技術(shù) 排序技術(shù) 對(duì)于等級(jí)考試，這個(gè)部分的考核重點(diǎn)主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹(遍歷、結(jié)點(diǎn)），還有排序和查找考試中也經(jīng)常會(huì)涉及到。第3頁(yè)/共132頁(yè)第4頁(yè)算法的定義算法的定義算法是程序設(shè)計(jì)的核心算法是程序設(shè)計(jì)的核心 算法是在有限步驟內(nèi)求解某一問題所使用的一組算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程程( (計(jì)算的方法

3、計(jì)算的方法) )。在這個(gè)過(guò)程中，無(wú)論是形成解題。在這個(gè)過(guò)程中，無(wú)論是形成解題思路思路( (推理實(shí)現(xiàn)的算法推理實(shí)現(xiàn)的算法) )還是編寫程序還是編寫程序( (操作實(shí)現(xiàn)的算操作實(shí)現(xiàn)的算法法) )，都是在實(shí)施某種算法。，都是在實(shí)施某種算法。例： n個(gè)數(shù)從大到小進(jìn)行排序。 有多種排序方法 ，常用的有冒泡排序、選擇排序等。第4頁(yè)/共132頁(yè)第5頁(yè) 2 . 算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：n 有窮性n 確定性n 輸入n 輸出n 可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所

4、謂0個(gè)輸入是指算法本身定除了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無(wú)意義的；算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成 第5頁(yè)/共132頁(yè)第6頁(yè) 算法與計(jì)算機(jī)程序 算法_是一組邏輯步驟 程序用計(jì)算機(jī)語(yǔ)言描述的算法INPUT rS=3.14 * r*rPTINT S開始輸入R RS=3.14 * R*R輸出S S結(jié)束問題：輸入園的半徑，計(jì)算園的面積 一個(gè)算法的表示需要使用一些語(yǔ)言形式。傳統(tǒng)的算法-圖形法，如“流程圖”和N-S圖目前常用的方法-使用偽碼描述算法。第6頁(yè)/共132頁(yè)第7頁(yè)冒泡排序的方法：1.掃描整個(gè)線性表，逐次對(duì)相鄰

5、的兩個(gè)元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后 ；2.除最后一個(gè)元素，對(duì)剩余的元素重復(fù)上述過(guò)程，將次大的數(shù)排到表的倒數(shù)第二個(gè)位置；3.重復(fù)上述過(guò)程；對(duì)于長(zhǎng)度為n的線性表，冒泡排序需要對(duì)表掃描n-1遍。 算法舉例：n個(gè)數(shù)排序第7頁(yè)/共132頁(yè)第8頁(yè)4. 算法的兩個(gè)基本要素：n 算術(shù)運(yùn)算n 關(guān)系運(yùn)算n 邏輯運(yùn)算n 數(shù)據(jù)傳輸n 順序n 選擇n 循環(huán)u一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；u二是算法的控制結(jié)構(gòu)。u算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法 第8頁(yè)/共132頁(yè)第9頁(yè) 評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲(chǔ)需求： 時(shí)間復(fù)雜度：執(zhí)行這個(gè)

6、算法所需要的計(jì)算工作量一般可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量計(jì)算工作量 空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間 算法在執(zhí)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間 時(shí)間復(fù)雜度它大致等于計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作所需的平均時(shí)間與算法中進(jìn)行簡(jiǎn)單操作的次數(shù)的乘積。 一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)部分第9頁(yè)/共132頁(yè)第10頁(yè)： 時(shí)間復(fù)雜度：執(zhí)行這個(gè)算法所需要的計(jì)算工作量 空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間第10頁(yè)/共132頁(yè)第11頁(yè)(1) 在計(jì)算機(jī)中，算法是指_。 A. 查

7、詢方法 B. 加工方法 C. 解題方案的準(zhǔn)確而完整的描述 D. 排序方法(2)下列敘述中正確的是 （07年4月）A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B)算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D)算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)(3)算法的有窮性是指 (08年4月)A）算法程序的運(yùn)行時(shí)間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長(zhǎng)度是有限的 D）算法只能被有限的用戶使用(c)(B)算法習(xí)題:(A)第11頁(yè)/共132頁(yè)第12頁(yè)(4) 算法的時(shí)問復(fù)雜度是指 (2010年3月)A)算法的執(zhí)行時(shí)間B)算法所處理的數(shù)

8、據(jù)量C)算法程序中的語(yǔ)句或指令條數(shù)D)算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)(5) 算法的空間復(fù)雜度是指 (09年9月) A）算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語(yǔ)句或指令條數(shù)D）算法在執(zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù)(6) 下列敘述中正確的是 (06年9月)A）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說(shuō)法都不對(duì)(D)計(jì)算工作量(A)(D)第12頁(yè)/共132頁(yè)第13頁(yè) 計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)

9、元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 一般來(lái)說(shuō)，人們不會(huì)同時(shí)處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對(duì)于具有不同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。第13頁(yè)/共132頁(yè)第14頁(yè)二. 數(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é)科，它包括三個(gè)方

10、面。（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。第14頁(yè)/共132頁(yè)第15頁(yè)1. 邏輯結(jié)構(gòu)邏輯結(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)系。例：1. 一年四季的數(shù)據(jù)結(jié)構(gòu) B=(D,R) D=春，夏，秋，冬 R=(春，夏) ,(夏，秋),(秋，冬)2. 家庭成員的數(shù)據(jù)結(jié)構(gòu) B=(D,R) D=父親，兒子，女兒 R=(父親，兒子) ,(父親，女兒)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示

11、父親兒子女兒第15頁(yè)/共132頁(yè)第16頁(yè) 常見的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)u 線性結(jié)構(gòu) 結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；u 樹形結(jié)構(gòu) 結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；u 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來(lái)表示。第16頁(yè)/共132頁(yè)第17頁(yè) 2. 存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)） 計(jì)算機(jī)在實(shí)際進(jìn)行數(shù)據(jù)處理時(shí)，被處理的各數(shù)據(jù)元素總是被存放在計(jì)算機(jī)的存儲(chǔ)空間中，并且，各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置與它們的邏輯關(guān)系不一定

12、是相同的，而且一般也不可能相同。如：一年四季 家庭成員 計(jì)算機(jī)存儲(chǔ)空間怎樣存放？ 存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。常見的存儲(chǔ)結(jié)構(gòu)有： 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu) 只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲(chǔ)方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲(chǔ)結(jié)構(gòu)。第17頁(yè)/共132頁(yè)第18頁(yè) 3. 數(shù)據(jù)的運(yùn)算 檢索 插入 刪除 更新 排序 通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是動(dòng)態(tài)變化的。根據(jù)需要或在處理過(guò)程中，可以在一個(gè)數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)新結(jié)點(diǎn)（插入運(yùn)算），也可以刪除某個(gè)結(jié)點(diǎn)（刪除運(yùn)算），除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分

13、解、復(fù)制和修改。 在對(duì)數(shù)據(jù)結(jié)構(gòu)的處理過(guò)程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)的個(gè)數(shù)在動(dòng)態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動(dòng)態(tài)地變化。如：無(wú)序表變有序表數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容：n 數(shù)據(jù)的邏輯結(jié)構(gòu)n 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n 數(shù)據(jù)的運(yùn)算第18頁(yè)/共132頁(yè)第19頁(yè)常見的數(shù)據(jù)結(jié)構(gòu) 1.線性表 2.棧和隊(duì)列 3.樹第19頁(yè)/共132頁(yè)第20頁(yè) 線性表是由n（n0）個(gè)數(shù)據(jù)元素 a1，a2，ai，an組成的一個(gè)有限序列。春夏秋冬記錄1 02011001 張三 男記錄2 02011003 李四 女 記錄3記錄4第20頁(yè)/共132頁(yè)第21頁(yè) 順序存儲(chǔ)結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在

14、物理上相鄰的存儲(chǔ)單元里，順序存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的值，不存儲(chǔ)結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。a1a2aian存儲(chǔ)地址200020042000+4*(i-1)2000+4*(n-1)占4個(gè)字節(jié)第i個(gè)數(shù)的地址第一個(gè)數(shù)的地址L為該類型數(shù)所占的字節(jié)線性表的存儲(chǔ)結(jié)構(gòu)有兩種：u 順序存儲(chǔ)結(jié)構(gòu)u 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第21頁(yè)/共132頁(yè)第22頁(yè) 順序表的插入運(yùn)算 順序表的刪除運(yùn)算 在線性表順序存儲(chǔ)情況下，要插入或刪除一個(gè)元素，都會(huì)由于數(shù)據(jù)元素的移動(dòng)而消耗大量的處理時(shí)間，所以這種存儲(chǔ)方式對(duì)于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動(dòng)的線性表是合適的。線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表。第22頁(yè)/共132頁(yè)第23

15、頁(yè) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲(chǔ)順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點(diǎn)的指針域指示。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅存儲(chǔ)結(jié)點(diǎn)的值，而且存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系：數(shù)據(jù)域數(shù)據(jù)域指針域指針域第23頁(yè)/共132頁(yè)第24頁(yè)設(shè)線性表為（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的物理狀態(tài)1 a12 a23 a34 a45 a567注意:1 2 3 此類編號(hào)不代表所在的地址單元的地址編碼第24頁(yè)/共132頁(yè)

16、第25頁(yè) 單鏈表的插入運(yùn)算 單鏈表的刪除運(yùn)算采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間開銷較大，但是進(jìn)行插入和刪除運(yùn)算不會(huì)造成大量元素的移動(dòng)。循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。 a1a2a5a3a4HEAD319510第25頁(yè)/共132頁(yè)第26頁(yè)雙向鏈表的存儲(chǔ)結(jié)構(gòu) 提問：?jiǎn)蜗蜴湵淼娜秉c(diǎn)是什么？ 提示：如何尋找結(jié)點(diǎn)的直接前趨。 雙向鏈表可以克服單鏈表的單向性的缺點(diǎn)。 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。 HEAD31510 a2 a3 a4 a1雙向循環(huán)鏈表 第26頁(yè)/共132頁(yè)第27頁(yè) 順序存儲(chǔ)結(jié)構(gòu)注意：注意：n 數(shù)據(jù)元素在計(jì)算機(jī)

17、數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系系與它們的邏輯關(guān)系不一定是相同的。不一定是相同的。n 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，可以有多種存儲(chǔ)結(jié)構(gòu)，且不同的存儲(chǔ)結(jié)構(gòu)影且不同的存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率響數(shù)據(jù)處理的效率 。1a2923a1145a4106789a3510a50HEAD31 a12 a23 a34 a45 a567u鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表 : a1，a2，a3，a4，a5 第27頁(yè)/共132頁(yè)第28頁(yè)棧和隊(duì)列都是特殊的線性表。第28頁(yè)/共132頁(yè)第29頁(yè)是一種特殊的線性表。其特點(diǎn)是插入和刪除運(yùn)算都只能在線性表的一端進(jìn)行。 棧是按照“”或“

18、”的原則組織數(shù)據(jù)的線性表。 棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。 下面討論順序存儲(chǔ)結(jié)構(gòu)中棧元素的插入和刪除運(yùn)算。 順序棧的進(jìn)棧和出棧運(yùn)算 棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素 在順序棧中插入和刪除運(yùn)算不需要在順序棧中插入和刪除運(yùn)算不需要移動(dòng)表中其他數(shù)據(jù)元素移動(dòng)表中其他數(shù)據(jù)元素。第29頁(yè)/共132頁(yè)第30頁(yè)是一種特殊的線性表。其特點(diǎn)是所有的插入都在表的一端進(jìn)行，所有的刪除運(yùn)算都在表的另一端進(jìn)行。 隊(duì)列是按照“”或“”的原則組織數(shù)據(jù)的線性表。 隊(duì)列的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。 順序隊(duì)列的運(yùn)算 棧有三種操作： 入棧出棧讀棧頂元素隊(duì)列有三種操作：入隊(duì)出隊(duì)讀隊(duì)首元

19、素例：有入棧元素序列：ABCD，求可能的出棧序列如是隊(duì)列又是什么情況呢？第30頁(yè)/共132頁(yè)第31頁(yè) 把隊(duì)列的存儲(chǔ)空間在邏輯上看作一個(gè)環(huán)，當(dāng)R指向存儲(chǔ)空間的末端后，就把它重新置于始端。 循環(huán)隊(duì)列的運(yùn)算隊(duì)列中進(jìn)行插入的一端稱做隊(duì)尾(rear),進(jìn)行刪除的一端稱做隊(duì)首(front)。 習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于【 】結(jié)構(gòu)。（2005年9月）答案：存儲(chǔ)結(jié)構(gòu)。第31頁(yè)/共132頁(yè)第32頁(yè)常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)線性表 線性結(jié)構(gòu)棧 是特殊的線性表 隊(duì)列 也是一種操作受限的特殊的線性表樹 （樹型結(jié)構(gòu)） 是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)第32頁(yè)/共132頁(yè)第33頁(yè)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)方面的考題 1：

20、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 （2005年4月）A) 存儲(chǔ)在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲(chǔ)空間量C) 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示2. 下列敘述中正確的是 （2009年3月） A）棧是“先進(jìn)先出”的線性表 B）隊(duì)列是“先進(jìn)后出”的線性表 C）循環(huán)隊(duì)列是非線性結(jié)構(gòu) D）有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于 。4. 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是A）循環(huán)隊(duì)列 B) 帶鏈隊(duì)列C) 二叉樹 D）帶鏈棧答案：D。答案：D。答案：線性結(jié)構(gòu)。答案：c第33頁(yè)/共132頁(yè)第34頁(yè)5。下列敘述中正確的

21、是（ ）。 （2008年9月） A）順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的 B）順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu) C）順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表 D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間答案：A。6 6。下列關(guān)于棧的敘述正確的是 （2008年4月） A A）棧按“先進(jìn)先出”組織數(shù)據(jù) B)B)棧按“先進(jìn)后出”組織數(shù)據(jù) C C）只能在棧底插入數(shù)據(jù) D D）不能刪除數(shù)據(jù) 答案：B。7. 一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊(duì)，然后再依次退隊(duì)，則元素退隊(duì)的順序?yàn)?【1】 。（2

22、010年3月） 答案：A，B，C，D，E，F(xiàn)，5，4，3，2，1第34頁(yè)/共132頁(yè)第35頁(yè)9. 設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針front=45(指向隊(duì)頭元素的前一位置)，尾指針rear=10(指向隊(duì)尾元素)，則該循環(huán)隊(duì)列中共有 【2】 個(gè)元素。 （2010年3月） 8。假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組（數(shù)組元索的下標(biāo)從0到49）作為棧的存儲(chǔ)空間，棧底指針bottom指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有【 】個(gè)元素。 （2009年3月） 答案：19答案：15第35頁(yè)/共132頁(yè)第36頁(yè)一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這

23、種數(shù)據(jù)結(jié)構(gòu)即為。 有且僅有一個(gè)根結(jié)點(diǎn)； 除第一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)結(jié)點(diǎn)； 除最后一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接后繼結(jié)點(diǎn)。 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性表、棧和隊(duì)列都是線性結(jié)構(gòu)線性表、棧和隊(duì)列都是線性結(jié)構(gòu) 一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱其為。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)第36頁(yè)/共132頁(yè)第37頁(yè)樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。 樹的概念 二叉樹的概念 二叉樹的存儲(chǔ) 二叉樹的遍歷第37頁(yè)/共132頁(yè)第38頁(yè) 樹的定義：n個(gè)結(jié)點(diǎn)的有限集。（n=0） ABDFECGHIJKMn 根：only onen 若n=0，則稱為空樹；n 否則，當(dāng)n1時(shí)，其余結(jié)

24、點(diǎn)被分成m（m0）個(gè)互不相交的子集T1，T2，.，Tm，每個(gè)子集又是一棵樹。由此可以看出，樹的定義是遞歸的。n Question：如何辨別根？A只有一個(gè)只有一個(gè)結(jié)點(diǎn)的樹結(jié)點(diǎn)的樹第38頁(yè)/共132頁(yè)第39頁(yè)ABDFECGHIJKMn 一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)； Q：結(jié)點(diǎn)結(jié)點(diǎn)A、G的度數(shù)？的度數(shù)？n 樹中所有結(jié)點(diǎn)度的最大值；Q：右圖中樹的度？右圖中樹的度？n 度為0的結(jié)點(diǎn)； Q：圖中葉子結(jié)點(diǎn)有幾個(gè)？圖中葉子結(jié)點(diǎn)有幾個(gè)？7 度不為0的結(jié)點(diǎn)； Q：圖中非終端結(jié)點(diǎn)有幾個(gè)？圖中非終端結(jié)點(diǎn)有幾個(gè)？ 5第39頁(yè)/共132頁(yè)第40頁(yè)ABDFECGHIJKMn 樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推；

25、 Q：圖中結(jié)點(diǎn)圖中結(jié)點(diǎn)F的層次？的層次？n 樹中所有結(jié)點(diǎn)層次的最大值； Q：圖中樹的深度？圖中樹的深度？n 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無(wú)序樹。第40頁(yè)/共132頁(yè)第41頁(yè) 二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是： 每個(gè)結(jié)點(diǎn)最多有兩棵子樹； 子樹有左右之分，次序不能任意顛倒。 二叉樹的5種基本形態(tài)第41頁(yè)/共132頁(yè)第42頁(yè)【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i1）ABCDFEHG第42頁(yè)/共132頁(yè)第43頁(yè)【性質(zhì)2】深度為h的二叉樹最多有2h -1個(gè)結(jié)點(diǎn)（h 1）如果一個(gè)深度為h的二叉樹擁有2h-1個(gè)結(jié)點(diǎn)，則將它

26、稱為滿二叉樹滿二叉樹。有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹完全二叉樹。第43頁(yè)/共132頁(yè)第44頁(yè)121314158910114567123滿二叉樹完全二叉樹12138910114567123 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹第44頁(yè)/共132頁(yè)第45頁(yè)1213891011456123非完全二叉樹深度為4的完全二叉樹84567123第45頁(yè)/共132頁(yè)第46頁(yè)【性質(zhì)3】二叉樹上葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1A

27、BCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)第46頁(yè)/共132頁(yè)第47頁(yè)【性質(zhì)4】具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2 (n+1) 其中， log2n 的結(jié)果是不大于log2n的最大整數(shù)121314158910114567123深度為4的滿二叉樹深度為4的完全二叉樹84567123深度為3的完全二叉樹具有47深度為4的完全二叉樹具有815深度為5的完全二叉樹具有1531 log2(8+1) = ln9/In2=4 log2 (15+ 1) =In16/In2=4深度為6的完全二叉樹 具有3263深度為7的完全二叉樹 具有64127深度為8的完全二叉樹 具有128255深度為9的完全二叉樹 具有25

28、6511深度為10的完全二叉樹具有5121023深度為11的完全二叉樹具有10242047第47頁(yè)/共132頁(yè)第48頁(yè)1 1：在深度為7 7的滿二叉樹中, ,葉子結(jié)點(diǎn)的個(gè)數(shù)為（20062006年4 4月） A)32A)32 B)31 B)31 C)64C)64 D)63D)632 2：在深度為7 7的滿二叉樹中，度為2 2的結(jié)點(diǎn)個(gè)數(shù)為【 】 。(07(07年4 4月）3 3：一棵二叉樹中共有7070個(gè)葉子結(jié)點(diǎn)與8080個(gè)度為1 1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為 （0707年9 9月） A A）219 B219 B）221 C221 C）229 D229 D）2312314 4： 某二叉樹中度

29、為2 2的結(jié)點(diǎn)有1818個(gè)，則該二叉樹中有 【 】個(gè)葉子結(jié)點(diǎn)。（20052005年4 4月）5 5：一棵二叉樹第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為【 】個(gè)。（20052005年9 9月） 樹型結(jié)構(gòu)方面的考題 1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。第48頁(yè)/共132頁(yè)第49頁(yè) 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。LlinkinfoRlink二叉樹的存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)ABDCFGE A G E F B C Dt第49頁(yè)/共132頁(yè)第50頁(yè) 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運(yùn)算有聯(lián)系。（1）先（前）序遍歷（DLR）（2）中序

30、遍歷（LDR）（3）后序遍歷（LRD）ABCDFEHG第50頁(yè)/共132頁(yè)第51頁(yè) 遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。（1）先（前）序遍歷（DLR） 若二叉樹為空，則結(jié)束遍歷操作；否則 訪問根結(jié)點(diǎn)；遍歷左子樹；遍歷右子樹。ABCDFEHG先序遍歷的結(jié)果： A A B E C F G H D B E C F G H D第51頁(yè)/共132頁(yè)第52頁(yè)（2）中序遍歷（LDR） 若二叉樹為空，則結(jié)束遍歷操作；否則 中序遍歷左子樹； 訪問根結(jié)點(diǎn)； 中序遍歷右子樹。中序遍歷的結(jié)果： E B A F H G C D（3）后序遍歷（LRD） 若二叉樹為空，則結(jié)束遍歷操作；否則 后序遍歷左子樹； 后序遍歷右子

31、樹； 訪問根結(jié)點(diǎn)。后序遍歷的結(jié)果： E B H G F D C AABCDFEHG第52頁(yè)/共132頁(yè)第53頁(yè) 先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過(guò)三種遍歷得到的順序分別為？練習(xí)：練習(xí)：根據(jù)先序遍歷序列，建立二叉樹第53頁(yè)/共132頁(yè)第54頁(yè)1:設(shè)二叉樹如下： （2010年3月）對(duì)該二叉樹進(jìn)行后序遍歷的結(jié)果為 【3】 樹型結(jié)構(gòu)方面的考題 22: 對(duì)如下二叉樹（2006年4月）進(jìn)行后序遍歷的結(jié)果為A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA EDBGHFCA DABCFHDGE第5

32、4頁(yè)/共132頁(yè)第55頁(yè) 查找是數(shù)據(jù)處理的重要內(nèi)容。 查找指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。 若找到了滿足條件的結(jié)點(diǎn)，稱查找成功；否則稱查找失敗。 衡量一個(gè)查找算法的主要標(biāo)準(zhǔn)是查找過(guò)程中對(duì)關(guān)鍵字進(jìn)行的平均比較次數(shù)。 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法： 順序查找 二分查找第55頁(yè)/共132頁(yè)第56頁(yè) 線性表中最簡(jiǎn)單的查找方法。 方法：從線性表的第一個(gè)元素開始，依次將線性表中的元素與關(guān)鍵字進(jìn)行比較，若相等，則查找成功；若將所有元素都與關(guān)鍵字進(jìn)行了比較但不相等，則查找失敗。 順序查找法的適用場(chǎng)合： 對(duì)線性表中元素的排列次序沒有要求； 對(duì)線性表的存儲(chǔ)結(jié)構(gòu)沒有要求，鏈?zhǔn)?/p>

33、結(jié)構(gòu)和順序結(jié)構(gòu)均可。第56頁(yè)/共132頁(yè)第57頁(yè)折半查找折半查找) ) 是一種效率較高的查找方法，但是只適合順序存儲(chǔ)的有序表。 二分查找的方法：首先將關(guān)鍵字與線性表中間位置的結(jié)點(diǎn)比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個(gè)子表中進(jìn)行；重復(fù)上述過(guò)程，直至查找成功或子表長(zhǎng)度為0。 二分查找法的適用場(chǎng)合： 線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列； 線性表采用順序存儲(chǔ)結(jié)構(gòu)。第57頁(yè)/共132頁(yè)第58頁(yè)練習(xí)假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關(guān)鍵字值為27的數(shù)據(jù)元素.對(duì)于長(zhǎng)度為對(duì)于

34、長(zhǎng)度為n n的有序線性表，最壞情況只需比較的有序線性表，最壞情況只需比較log2nlog2n次。次。 第58頁(yè)/共132頁(yè)第59頁(yè) 排序指將一個(gè)無(wú)序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。 排序方法中其排序?qū)ο笠话闶琼樞虼鎯?chǔ)的線性表。 根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：交換類排序法 冒泡排序 快速排序 插入類排序法 簡(jiǎn)單插入排序 希爾排序選擇類排序法 簡(jiǎn)單選擇排序 堆排序第59頁(yè)/共132頁(yè)第60頁(yè) 冒泡排序的方法： 掃描整個(gè)線性表，逐次對(duì)相鄰的兩個(gè)元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最小)的元素排到表的最后(或最前) ； 除最后(或最前

35、)一個(gè)元素，對(duì)剩余的元素重復(fù)上述過(guò)程，將次大(或次小)的數(shù)排到表的倒數(shù)(或正數(shù))第二個(gè)位置； 重復(fù)上述過(guò)程； 對(duì)于長(zhǎng)度為n的線性表，冒泡排序需要對(duì)表掃描n-1遍。 第60頁(yè)/共132頁(yè)第61頁(yè)冒泡排序的方法u 設(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ù)u第二趟冒泡排序第61頁(yè)/共132頁(yè)第62|92頁(yè)Q：第二趟冒泡排序后的結(jié)果是什么樣的

36、？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？Q：你覺得冒泡排序的效率如何？如果是你，你會(huì)用什么方法來(lái)排序？ 冒泡排序比較簡(jiǎn)單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效率較低。 冒泡排序終止條件: 本趟排序未發(fā)生交換，終止排序算法 第62頁(yè)/共132頁(yè)第63|92頁(yè)初始 第一趟 第二趟 第三趟 第四趟 第五趟序列 排序后 排序后 排序后 排序后 排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（26,18,32,54,47

37、,9,15 )冒泡排序法，需要比較的次數(shù)為冒泡排序法，需要比較的次數(shù)為n(n-1)/2n(n-1)/2； 第63頁(yè)/共132頁(yè)第64頁(yè) 選擇排序的方法： 掃描整個(gè)線性表，從中找出最小的元素，與第一個(gè)元素交換； 除第一個(gè)元素，對(duì)剩下的子表采用相同的方法找出次小的數(shù)，與第二個(gè)數(shù)交換； 重復(fù)上述過(guò)程； 對(duì)于長(zhǎng)度為n的線性表，選擇排序需要對(duì)表掃描n-1遍。 簡(jiǎn)單選擇排序法簡(jiǎn)單選擇排序法, , 最壞情況需要最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較； 第64頁(yè)/共132頁(yè)第65|92頁(yè)u初態(tài)： 15，14，22，30，37，15，11u第一趟： 11 14，22，30，37，15，15u

38、第二趟： 11，14 22，30，37，15，15u第三趟： 11，14，15 30，37，22，15u第四趟： 11，14，15，15 37，22，30u第五趟： 11，14，15，15，22 37，30u第六趟： 11，14，15，15，22，30 37 有序序列例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：第65頁(yè)/共132頁(yè)第66頁(yè) 簡(jiǎn)單選擇排序法, 最壞情況需要n(n-1)/2次比較； 冒泡排序法, 最壞情況需要n(n-1)/2次比較； 希爾排序法, 最壞情況需要O(n1.5)次比較； 堆排序法, 最壞情況需要O(nlog2n)次

39、比較； 第66頁(yè)/共132頁(yè)第67頁(yè)(1) 對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是（2005年4月）A) 冒泡排序?yàn)閚/2 B) 冒泡排序?yàn)閚C) 快速排序?yàn)閚 D) 快速排序?yàn)閚(n-1)/2(2)在長(zhǎng)為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為_。（06年9月） A）、63 B）、64 C）、6 D）、7(3) 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是（2005年9月） A）順序存儲(chǔ)的有序線性表 B）線性鏈表 C）二叉鏈表 D）有序線性鏈表(4) 下列排序方法中，最壞情況下比較次數(shù)最少的是（09年3月） A）冒泡排序 B）簡(jiǎn)單選擇排序 C）

40、直接插入排序 D）堆排序DBAD第67頁(yè)/共132頁(yè)第68頁(yè) 1. 程序設(shè)計(jì)方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計(jì)。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。第68頁(yè)/共132頁(yè)第69頁(yè) 結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：1. 自頂向下；2. 逐步求精；3. 模塊化；4. 限制使用goto語(yǔ)句。 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：（1）順序結(jié)構(gòu)： 簡(jiǎn)單的程序設(shè)計(jì)，最基本、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)（分支結(jié)構(gòu)）： 包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，（3）重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）： 可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。第69頁(yè)/共132頁(yè)第70頁(yè) 對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母?/p>

41、念。 對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 屬性即對(duì)象所包含的信息 操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。第70頁(yè)/共132頁(yè)第71頁(yè) 類是指具有共同屬性、共同方法的對(duì)象的集合。 所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。 消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括 （1）接收消息的對(duì)象的名稱； （2）消息標(biāo)識(shí)符，也稱消息名； （3）零個(gè)或多個(gè)參數(shù)。 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。 單繼承指一個(gè)類只允許有一個(gè)父類 多重繼承指一個(gè)類允許有多個(gè)父類。 多態(tài)性是指同

42、樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。第71頁(yè)/共132頁(yè)第72頁(yè)程序設(shè)計(jì)基礎(chǔ)方面的考題1.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和【 】 . (2009年3月)2. 下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的是（2009年9月）A) 可封裝 D) 自頂向下 C) 模塊化 D) 逐步求精3. 以下敘述中正確的是。（2010年3月） A）程序設(shè)計(jì)的任務(wù)就是編寫程序代碼并上機(jī)調(diào)試 B）程序設(shè)計(jì)的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu) C）程序設(shè)計(jì)的任務(wù)就是確定所用算法 D）以上三種說(shuō)法都不完整4.在面向?qū)ο蠓椒ㄖ?，類的?shí)例稱為 【_】 。（2005年4月）5.在面向?qū)ο蠓椒ㄖ? 【_】

43、 描述的是具有相似屬性與操作的一組對(duì)象。（2006年4月）（順序結(jié)構(gòu)）A D對(duì)象類第72頁(yè)/共132頁(yè)第73頁(yè)第三章 軟件工程基礎(chǔ)計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。第73頁(yè)/共132頁(yè)第74頁(yè)1.軟件工程概念 軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程包括3個(gè)要素：方法、工具和過(guò)程。 軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。軟件生命周期三個(gè)階段:軟件定義、軟件開發(fā)、運(yùn)行維護(hù)，主要活動(dòng)階段是：（1）可行性研究與計(jì)劃制定；（2）需求分析；（3）軟件設(shè)計(jì)；

44、（4）軟件實(shí)現(xiàn)；（5）軟件測(cè)試；（6）運(yùn)行和維護(hù)。第74頁(yè)/共132頁(yè)第75頁(yè)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具 （1）數(shù)據(jù)流圖； （2）數(shù)據(jù)字典； （3）判定樹； 判定表。 （4）軟件需求規(guī)格說(shuō)明書第75頁(yè)/共132頁(yè)第76頁(yè) 軟件設(shè)計(jì)包括：總體設(shè)計(jì)與詳細(xì)設(shè)計(jì) 在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。 常見的過(guò)程設(shè)計(jì)工具有：圖形工具（程序流程圖,N-S,PAD）表格工具（判定表）語(yǔ)言工具（PDL偽碼）第76頁(yè)/共132頁(yè)第77頁(yè) 程序流程圖N-S圖PAD圖第77頁(yè)/

45、共132頁(yè)第78頁(yè) 軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。 軟件測(cè)試方法：靜態(tài)測(cè)試： 包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。動(dòng)態(tài)測(cè)試： 是基本計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒測(cè)試方法 軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試。第78頁(yè)/共132頁(yè)第79頁(yè) 程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開發(fā)階段進(jìn)行。 軟件調(diào)試 靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的設(shè)計(jì)手段。 動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：（1）強(qiáng)行排錯(cuò)法；（2）回溯法；（3）原因排除法。第79頁(yè)/共132

46、頁(yè)第80頁(yè)(1) 下面敘述中錯(cuò)誤的是 (2009年3月） A）軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤并改正錯(cuò)誤 B）對(duì)被調(diào)試的程序進(jìn)行“錯(cuò)誤定位”是程序調(diào)試的必要步驟 C）程序調(diào)試通常也稱為Debug D）軟件測(cè)試應(yīng)嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性 (2) 軟件測(cè)試可分為白盒測(cè)試和黑盒測(cè)試?；韭窂綔y(cè)試屬于【 】測(cè)試。(2009年3月）(3) 按照軟件測(cè)試的一般步驟，集成測(cè)試應(yīng)在_測(cè)試之后進(jìn)行。(4) 軟件工程三要素包括方法、工具和過(guò)程，其中，_支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制和管理。(2008年9月)(5)軟件設(shè)計(jì)中劃分模塊的一個(gè)準(zhǔn)則是(2009年9月）A) 低內(nèi)聚低耦合 B) 高內(nèi)聚低耦合C) 低內(nèi)聚高耦

47、合 D) 高內(nèi)聚高耦合A 軟件工程方面的考題：白盒 單元過(guò)程 B第80頁(yè)/共132頁(yè)第81頁(yè)(6) 下列敘述中正確的是（2005年9月）AA）軟件交付使用后還需要進(jìn)行維護(hù)B）軟件一旦交付使用就不需要再進(jìn)行維護(hù)C）軟件交付使用后其生命周期就結(jié)束D）軟件維護(hù)是指修復(fù)程序中被破壞的指令(7) 程序流程圖中的菱形框表示的是 【2】(2009年9月) 。(8)軟件開發(fā)過(guò)程主要分為需求分析、設(shè)計(jì)、編碼與測(cè)試四個(gè)階段，其中 【3】 階段產(chǎn)生“軟件需求規(guī)格說(shuō)明書。（2009年9月） (9)下列敘述中正確的是（2006年4月） A)軟件測(cè)試應(yīng)該由程序開發(fā)者來(lái)完成 B)程序經(jīng)調(diào)試后一般不需要再測(cè)試 C)軟件維護(hù)只

48、包括對(duì)程序代碼的維護(hù) D)以上三種說(shuō)法都不對(duì)A 邏輯條件需求分析D第81頁(yè)/共132頁(yè)第82頁(yè)(3)軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件(或工具軟件)。下面屬于系統(tǒng)軟件的是 A)編輯軟件 B)操作系統(tǒng)C)教務(wù)管理系統(tǒng)D)瀏覽器(4)軟件(程序)調(diào)試的任務(wù)是 A)診斷和改正程序中的錯(cuò)誤B)盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤C)發(fā)現(xiàn)并改正程序中的所有錯(cuò)誤D)確定程序中錯(cuò)誤的性質(zhì)(5)數(shù)據(jù)流程圖(DFD圖)是 A)軟件概要設(shè)計(jì)的工具 B)軟件詳細(xì)設(shè)計(jì)的工具C)結(jié)構(gòu)化方法的需求分析工具D)面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?6)軟件生命周期可分為定義階段，開發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計(jì)屬于 A)定義階段 B

49、)開發(fā)階段C)維護(hù)階段 D)上述三個(gè)階段2010年3月計(jì)算機(jī)等級(jí)考試 BA C B 第82頁(yè)/共132頁(yè)第83頁(yè)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)知識(shí)點(diǎn)得分表數(shù)據(jù)庫(kù)的數(shù)據(jù)庫(kù)的基本概念基本概念數(shù)據(jù)數(shù)據(jù)模型模型關(guān)系關(guān)系代數(shù)代數(shù)數(shù)據(jù)庫(kù)設(shè)數(shù)據(jù)庫(kù)設(shè)計(jì)與管理計(jì)與管理小計(jì)08年年4月月2分6分2分10分08年年9月月2分4分2分2分10分09年年3月月2分2分2分4分10分09年年9月月2分2分2分4分10分10年年3月月2分4分2分2分10分時(shí)間知識(shí)點(diǎn)第83頁(yè)/共132頁(yè)第84頁(yè)實(shí)際上就是描述事物的符號(hào)記錄。：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序共享。：一種系統(tǒng)軟

50、件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。第84頁(yè)/共132頁(yè)第85頁(yè)數(shù)據(jù)庫(kù)系統(tǒng)第85頁(yè)/共132頁(yè)86常見的關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng) 小型數(shù)據(jù)庫(kù)： Visual FoxPro （以后簡(jiǎn)稱為VFP） Access (office套件中的一個(gè)) Paradox 大型數(shù)據(jù)庫(kù)： Oracle Informix SYBASE SQL server 等 第86頁(yè)/共132頁(yè)第87頁(yè)數(shù)據(jù)庫(kù)管理系統(tǒng)提供

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

52、統(tǒng)一管理與控制。 數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)。 數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：（1）概念模式（2）外模式（3）內(nèi)模式 數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。 1.數(shù)據(jù)庫(kù)系統(tǒng)的基本概念第88頁(yè)/共132頁(yè)89應(yīng)用外模式(用戶數(shù)據(jù)庫(kù))應(yīng)用外模式(用戶數(shù)據(jù)庫(kù))應(yīng)用外模式(用戶數(shù)據(jù)庫(kù))概念模式(概念數(shù)據(jù)庫(kù))內(nèi)模式(物理數(shù)據(jù)庫(kù))數(shù)據(jù)庫(kù)外模式概念模式映射概念模式內(nèi)模式映射模式第89頁(yè)/共132頁(yè)902. 數(shù)據(jù)模型數(shù)據(jù)模型（Data Model）是對(duì)客觀事物及其關(guān)系的數(shù)據(jù)描述。 數(shù)據(jù)庫(kù)中的數(shù)據(jù)模型可以將復(fù)雜的現(xiàn)實(shí)世界要求反映到計(jì)算機(jī)

53、數(shù)據(jù)庫(kù)中的物理世界?，F(xiàn)實(shí)世界信息世界計(jì)算機(jī)世界 數(shù)據(jù)模型是數(shù)據(jù)特征的抽象，靜態(tài)特征、動(dòng)態(tài)行為和約束條件。數(shù)據(jù)模型所描述的內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。第90頁(yè)/共132頁(yè)第91頁(yè)（1）實(shí)體：現(xiàn)實(shí)世界中的事物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。 一個(gè)班級(jí)的學(xué)生，學(xué)生與學(xué)生之間是一對(duì)一的關(guān)系。 在一所學(xué)校，一門課程與學(xué)生之間是一對(duì)多的關(guān)系。 在一所學(xué)校，多門課程與多個(gè)學(xué)生之間是多對(duì)多的關(guān)系。第91頁(yè)/共132頁(yè)92E-R模型的圖示法用簡(jiǎn)單的幾何圖形表示實(shí)體集、屬性與聯(lián)系。(1)實(shí)體集表示法在E-R圖中用矩形表表示實(shí)體集

54、，在矩形內(nèi)寫上實(shí)體集名稱。如實(shí)體集學(xué)生(student)、實(shí)體集課程(course)(2)屬性表示法在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性名稱。如學(xué)生有屬性：學(xué)號(hào)(S#)、姓名(Sn)及年齡(Sa)可用如下表示。studentcourseS#SnSa第92頁(yè)/共132頁(yè)93(3)聯(lián)系表示法在E-R圖中用菱形(內(nèi)寫上聯(lián)系名)表示聯(lián)系。如學(xué)生與課程的聯(lián)系SC,如下圖所示：(4)實(shí)體集與屬性間的聯(lián)系關(guān)系屬性依附于實(shí)體集，它們之間有聯(lián)系關(guān)系用無(wú)向線段表示。SCstudentS#SnSa第93頁(yè)/共132頁(yè)94屬性也依附于聯(lián)系，它們之間也有聯(lián)系關(guān)系，因此也可用無(wú)向線段，如聯(lián)系SC可與學(xué)生的課

55、程成績(jī)屬性G建立聯(lián)系并用下圖表示。(5)實(shí)體集與聯(lián)系間的連接關(guān)系(也可用無(wú)向線段)SCGstudentcourseSC第94頁(yè)/共132頁(yè)第95頁(yè)E-R模型之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的基本單位，屬性有屬性域，每個(gè)實(shí)體可取屬性域內(nèi)的值。一個(gè)實(shí)體的所有屬性值叫元組。E-R模型的圖示法：（1）實(shí)體集表示法；用長(zhǎng)方形（2）屬性表法；用橢圓形（3）聯(lián)系表示法。用菱形，(m:n)第95頁(yè)/共132頁(yè)第96頁(yè)層次模型（采用樹型結(jié)構(gòu)）圖圖1-4 層次模型示例層次模型示例第96頁(yè)/共132頁(yè)第97頁(yè)網(wǎng)絡(luò)模型（采用無(wú)向圖型結(jié)構(gòu)）第97頁(yè)/共132頁(yè)第98頁(yè)關(guān)系模型（采用二維表結(jié)構(gòu)）第98頁(yè)/共132頁(yè)第99

56、頁(yè) 關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生日期出生日期入學(xué)成績(jī)?nèi)雽W(xué)成績(jī)四級(jí)通過(guò)否四級(jí)通過(guò)否計(jì)算機(jī)等級(jí)考試計(jì)算機(jī)等級(jí)考試備注備注04001001尚杰尚杰男男86-11-20520.5T一級(jí)一級(jí)04001002余習(xí)芳余習(xí)芳女女86-12-26513.5F二級(jí)二級(jí)04001057張軼一張軼一男男86-01-09612.0T04002023陶紅莉陶紅莉女女85-02-14535.0F二級(jí)二級(jí)第99頁(yè)

57、/共132頁(yè)1001.關(guān)系的數(shù)據(jù)結(jié)構(gòu)二維表由表框架與表元組組成。表框架由n個(gè)命名的屬性組成(n稱為屬性元素)。每個(gè)屬性有一個(gè)取值范圍稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。每行數(shù)據(jù)稱為元組，一個(gè)元組由n個(gè)元組分量所組成，每個(gè)元組分量是表結(jié)構(gòu)中每個(gè)屬性的投影值。學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生日期出生日期入學(xué)成績(jī)?nèi)雽W(xué)成績(jī)四級(jí)通過(guò)否四級(jí)通過(guò)否計(jì)算機(jī)等級(jí)考試計(jì)算機(jī)等級(jí)考試備注備注04001001尚杰尚杰男男86-11-20520.5T一級(jí)一級(jí)04001002余習(xí)芳余習(xí)芳女女86-12-26513.5F二級(jí)二級(jí)04001057張軼一張軼一男男86-01-09612.0T04002023陶紅莉陶紅莉

58、女女85-02-14535.0F二級(jí)二級(jí)第100頁(yè)/共132頁(yè)101一個(gè)二維表要滿足下面7個(gè)性質(zhì)就可稱為一個(gè)關(guān)系。二維表中元組個(gè)數(shù)是有限的二維表中元組均不相同 二維表中元組的次序可任意交換 二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)二維表中屬性名各不相同二維表中屬性與次序無(wú)關(guān)，可任意交換二維表屬性中的分量具有與該屬性相同的值域二維表二維表關(guān)系模型關(guān)系模型VFP表文件表文件二維表框架二維表框架關(guān)系模式關(guān)系模式數(shù)據(jù)表結(jié)構(gòu)數(shù)據(jù)表結(jié)構(gòu)行行元組元組記錄記錄 元組分量元組分量數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)列列屬性屬性字段字段 屬性值域?qū)傩灾涤蜃侄沃涤蜃侄沃涤蛭┮粯?biāo)識(shí)元組的最小屬性集稱為該表的鍵(或碼)，在VFP表中稱為主關(guān)鍵

59、字第101頁(yè)/共132頁(yè)102關(guān)系模型的基本運(yùn)算： 1. 數(shù)據(jù)查詢 查詢關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)，一個(gè)關(guān)系內(nèi)的查詢以及多個(gè)關(guān)系間的查詢。 查詢的基本單位為元組分量，先定位后操作。 縱向定位（列指定） 橫向定位（行選擇） 2. 數(shù)據(jù)插入 插入一個(gè)元組（不定位） 3. 數(shù)據(jù)刪除 刪除一個(gè)元組（定位、操作） 4. 數(shù)據(jù)修改 刪除需修改的元組再插入修改后的元組關(guān)系操作第102頁(yè)/共132頁(yè)103關(guān)系模型的基本運(yùn)算： 1. 插入 集合的并運(yùn)算 2. 刪除 集合的差(交) 運(yùn)算 3. 修改 集合的差|并(除)運(yùn)算。 4. 查詢 （投影、選擇、笛卡爾積運(yùn)算）3.關(guān)系代數(shù)集合的并運(yùn)算第103頁(yè)/共132頁(yè)104 由

60、關(guān)系R和S通過(guò)交運(yùn)算得到關(guān)系T，第104頁(yè)/共132頁(yè)105用于查詢的集合運(yùn)算：（1）投影對(duì)于關(guān)系R內(nèi)的域指定稱為投影運(yùn)算。S關(guān)系就是對(duì)R關(guān)系指定A和B兩個(gè)域的結(jié)果ABCa32b01c21ABa3b0c2RS3.關(guān)系代數(shù)第105頁(yè)/共132頁(yè)106關(guān)系代數(shù)（2）選擇選擇運(yùn)算的關(guān)系是由關(guān)系R中那些滿足邏輯條件的元組所組成。S關(guān)系就是R關(guān)系中滿足A=a的結(jié)果ABCa32b01a69c21RSABCa32a69有了投影和選擇運(yùn)算，我們對(duì)一個(gè)關(guān)系內(nèi)的任意行、列的數(shù)據(jù)都可以方便的找到。第106頁(yè)/共132頁(yè)107 笛卡爾積是對(duì)兩個(gè)關(guān)系的合并操作。有三個(gè)關(guān)系R、S和T R關(guān)系 n1行, m1列 S關(guān)系 n