【正文】 M:N或 m:n。如，教師與學(xué)生的關(guān)系。 2022/2/9 102 ER模型 ? 實(shí)體集與屬性集間的聯(lián)系 ?一個(gè)實(shí)體的所有屬性取值組成了一個(gè)值叫元組。 ? 實(shí)體（集）與聯(lián)系 ?實(shí)體集間可通過(guò)聯(lián)系建立聯(lián)接關(guān)系，一般而言，實(shí)體集無(wú)法建立直接關(guān)系，它只能通過(guò)聯(lián)系才能建立起聯(lián)接關(guān)系。 2022/2/9 103 ER模型的圖示法 ? 實(shí)體集表示法 ? 屬性表示法 ? 聯(lián)系表示法 ? 實(shí)體集與屬性間的聯(lián)接關(guān)系 student course SC S Sn Sa G C Cn P n m 2022/2/9 104 層次模型 ? 基本結(jié)構(gòu)是樹(shù)型結(jié)構(gòu)，如家族結(jié)構(gòu)、行政結(jié)構(gòu)，它們自頂向下、層次分明。 學(xué)校 領(lǐng)導(dǎo) 領(lǐng)導(dǎo) 領(lǐng)導(dǎo) 院系 研究所 部處 教研室 班 領(lǐng)導(dǎo) 領(lǐng)導(dǎo) 2022/2/9 105 層次模型 ? 層次模型的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，操作簡(jiǎn)單 ? 對(duì)于實(shí)體聯(lián)系是固定的，且預(yù)先定義好的應(yīng)用系統(tǒng)，有較高的性能。 ? 但該模型物理成分復(fù)雜，操作與使用均不理想。 ? 不適用于表示非層次性的聯(lián)系。 2022/2/9 106 網(wǎng)狀模型 ? 略晚于層次模型。 ? 在數(shù)據(jù)表示和數(shù)據(jù)操縱比層次模型更高效。 ? 在使用時(shí)，涉及到系統(tǒng)內(nèi)部物理因素較多，用戶操作使用不方便。 2022/2/9 107 關(guān)系模型 ? 采用二維表來(lái)表示，簡(jiǎn)稱表。 ? 二維表由表框架和表的元組組成。 學(xué)號(hào) 姓名 語(yǔ)文 數(shù)學(xué) 物理 化學(xué) 2022001 柳迪 91 93 89 98 2022022 李曉 89 85 84 89 2022022 石磊 87 81 88 71 2022022 杜鵬 71 89 72 85 2022/2/9 108 關(guān)系模型 ? 鍵（碼）：二維表中能惟一標(biāo)識(shí)元組的最小屬性集。 ? 候選鍵（碼）：二維表中可能有若干個(gè)鍵。 ? 主鍵（碼）：從二維表的所有候選鍵中選取一個(gè)作為用戶使用的鍵。 ? 外鍵（碼）：表 A中的某屬性集是表 B的鍵，稱該屬性集為 A的外鍵。 ? 表中一定要有鍵，若表中所有屬性的子集均不是鍵，則表中屬性的全集必為鍵。 ? 在關(guān)系元組的分量中允許出現(xiàn)空值表示信息的空缺。 ? 主鍵中不允許出現(xiàn)空值。 ? 關(guān)系數(shù)據(jù)庫(kù)：一個(gè)語(yǔ)義相關(guān)的關(guān)系集合。 ? 關(guān)系支持子模式，子模式也是二維表結(jié)構(gòu)，對(duì)應(yīng)用戶數(shù)據(jù)庫(kù)，稱為視圖。 2022/2/9 109 關(guān)系模型 ? 關(guān)系的操縱 一般有查詢、增加、刪除、修改四種。 ? 關(guān)系中的數(shù)據(jù)約束 ? 實(shí)體完整性：關(guān)系的主鍵中屬性值不能為空。 ? 參照完整性：關(guān)系之間相關(guān)的基本約束，在關(guān)系中的外鍵要么是所關(guān)聯(lián)關(guān)系中實(shí)際存在的元組，要么就為空值。 ? 用戶完整性：針對(duì)具體環(huán)境由用戶具體設(shè)置的約束。 2022/2/9 110 關(guān)系代數(shù) ? 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)是建立在數(shù)學(xué)理論基礎(chǔ)上的，使用關(guān)系代數(shù)可以表示關(guān)系模型的數(shù)據(jù)操作。 ? 關(guān)系可以看成有序組的集合，可以將操作看成是集合的運(yùn)算。 ? 關(guān)系模型的基本運(yùn)算 ?插入。設(shè)有關(guān)系 R需插入若干元組，要插入的元組組成關(guān)系 R’，插入可用集合表示為 R∪ R’ ?刪除。 RR’ ?修改。設(shè)需修改的元組構(gòu)成關(guān)系 R’，修改后的元組構(gòu)成關(guān)系 R’’，修改可用集合表示為 (RR’) ∪ R’’ 2022/2/9 111 關(guān)系代數(shù) ? 關(guān)系模型的基本運(yùn)算 ? 查詢。無(wú)法用傳統(tǒng)的集合運(yùn)算表示，需要引入一些新的運(yùn)算。 ?投影：在給定關(guān)系的某些域上進(jìn)行。從一個(gè)關(guān)系中選擇出所需要的屬性成分，按要求排列成一個(gè)新關(guān)系。是一元運(yùn)算。 設(shè) R有 n個(gè)域： A1， A2， … ， An，在 R上對(duì)域 A1， A2， … ， An的投影可表示成 πAi1,Ai2,…,Aim (R） ?選擇。由原關(guān)系中滿足條件的元組組成。 設(shè)關(guān)系的邏輯條件為 F，則 R滿足 F的選擇運(yùn)算可表示為 σF(R) ?笛卡爾積。對(duì)兩個(gè)關(guān)系的合并運(yùn)算。 設(shè)有 n元關(guān)系 R及 m元關(guān)系 S，它們分別有 p、 q個(gè)元組，則 R與 S的笛卡爾積記 R S，新關(guān)系是一個(gè) n+m元關(guān)系，元組的個(gè)數(shù)為 p q 2022/2/9 112 關(guān)系代數(shù)中的擴(kuò)充運(yùn)算 ? 交。記為 R∩S ? 除。 設(shè)有關(guān)系 T、 R， T能被除的充要條件是： T中的域包含 R中的所有屬性，T中有一些域不出現(xiàn)在 R中。 除運(yùn)算中 S的域由 T中那些不出現(xiàn)在 R中的域組成。 A B C D 1 2 3 4 7 8 5 6 7 8 3 4 1 2 5 6 1 2 4 2 C D 3 4 5 6 C D 3 4 A B 1 2 7 8 A B 1 2 7 8 T R R S S 2022/2/9 113 關(guān)系代數(shù)中的擴(kuò)充運(yùn)算 ? 連接。 是一種二元運(yùn)算，記為 R| |S=σ(R S) ? 自然連接。 兩關(guān)系間有公共域。 通過(guò)公共域的相等值進(jìn)行連接。 記為 R| |S iθj iθj 2022/2/9 114 數(shù)據(jù)庫(kù)設(shè)計(jì) ? 設(shè)計(jì)，一般采用生命周期法。 ? 需求分析通常采用結(jié)構(gòu)化分析方法和面向?qū)ο蟮姆治龇椒ā? ? 數(shù)據(jù)庫(kù)概念設(shè)計(jì)。 目的是分析數(shù)據(jù)間內(nèi)在語(yǔ)義聯(lián)系，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)的抽象模型。 有兩種方法：集中式法。適合小型并不復(fù)雜的單位或部門。 視圖集成法。 2022/2/9 115 數(shù)據(jù)庫(kù)邏輯設(shè)計(jì) ? 從 ER圖向關(guān)系模式轉(zhuǎn)換的方法 ? 一個(gè)實(shí)體轉(zhuǎn)換成一個(gè)關(guān)系模式。 ? 一個(gè) 1:1聯(lián)系可轉(zhuǎn)換成一個(gè)獨(dú)立的關(guān)系模式，也可與任一端對(duì)應(yīng)的關(guān)系模式合并。 ? 一個(gè) 1:n聯(lián)系可轉(zhuǎn)換成一個(gè)獨(dú)立的關(guān)系模式，也可與 n端對(duì)應(yīng)的關(guān)系模式合并。 ? 一個(gè) m:n聯(lián)系轉(zhuǎn)換為一個(gè)關(guān)系模式。 ? 3個(gè)或 3個(gè)以上實(shí)體間的多元聯(lián)系轉(zhuǎn)換為一個(gè)關(guān)系模式。 2022/2/9 116 數(shù)據(jù)庫(kù)邏輯設(shè)計(jì) ? 邏輯模式規(guī)范化 在關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)中經(jīng)常出現(xiàn)數(shù)據(jù)冗余、插入異常、刪除異常、更新異常等問(wèn)題，數(shù)據(jù)庫(kù)規(guī)范化在于消除這些問(wèn)題。 ? 第一范式。 每個(gè)屬性值是不可再分的最小數(shù)據(jù)單位。 ? 第二范式。 R中的每一個(gè)非主屬性完全函數(shù)依賴于 R的任一候選碼。 該關(guān)系中的非主屬性 SNAME,CLASS,TNAME,TAGE,ADDRESS都不是完全函數(shù)依賴候選碼 (S,C),而是部分依賴 (S,C)。 可以采用投影，把關(guān)系分解為三個(gè)關(guān)系。 2022/2/9 117 ? 第三范式。關(guān)系 R的任何一個(gè)非主屬性都不傳遞函數(shù)據(jù)依賴于它的任何一個(gè)候選碼。 CTA（ C,TNAME,TAGE,ADDRESS)中， C→TNAME,TNAME →TAGE, 所以 C →TAGE, 可采用投影的辦法，將 CTA分解為： CT（ C， TNAME） TA（ TNAME， TAGE， ADDRESS） ? 第四范式。消除多值依賴，可采用投影的辦法將關(guān)系分解。 2022/2/9 118 S SNAME CLASS C TNAME TAGE ADDRESS SCORE S1 劉力 202201 C1 周文軍 38 A1 78 S1 劉力 202201 C2 曹立新 27 A1 64 S2 李軍 202201 C1 周文軍 38 A1 85 S2 李軍 202201 C2 曹立新 27 A1 62 S2 李軍 202201 C3 羅曉 52 A2 85 S3 王林 202202 C1 周文軍 38 A1 72 S3 王林 202202 C3 羅曉 52 A2 93 S4 沈國(guó)立 202202 C2 曹立新 27 A1 72 S4 沈國(guó)立 202202 C3 羅曉 52 A1 66 S4 沈國(guó)立 202202 C4 周文軍 38 A1 73 2022/2/9 119 ? 關(guān)系視圖設(shè)計(jì)，即外模式設(shè)計(jì)。 ? 物理設(shè)計(jì)。 2022/2/9 120 ? 例題詳解 一、選擇題 【 例 1】 算法的時(shí)間復(fù)雜度取決于 _______。（考點(diǎn) 2） A）問(wèn)題的規(guī)模 B）待處理的數(shù)據(jù)的初態(tài) C）問(wèn)題的難度 D） A）和 B） 解析：算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，在同一個(gè)問(wèn)題規(guī)模下，而且與輸入數(shù)據(jù)有關(guān)。即與輸入數(shù)據(jù)所有的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。 答案： D） 【 例 2】 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 _______。（考點(diǎn) 3） A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B）線性結(jié)構(gòu)和非線性結(jié)構(gòu) C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D）動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 解析：邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)一的關(guān)系，非線性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)多或者多對(duì)一的關(guān)系，所以答案為B）。 答案： B） 【 例 3】 以下 _______不是棧的基本運(yùn)算。（考點(diǎn) 5） A）判斷棧是否為素空 B）將棧置為空棧 C）刪除棧頂元素 D）刪除棧底元素 解析：棧的基本運(yùn)算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對(duì)棧的操作都是在棧頂進(jìn)行的。 答案： D） 【 例 4】 鏈表不具備的特點(diǎn)是 _______。（考點(diǎn) 6） A）可隨機(jī)訪問(wèn)任意一個(gè)結(jié)點(diǎn) B）插入和刪除不需要移動(dòng)任何元素 C）不必事先估計(jì)存儲(chǔ)空間 D）所需空間與其長(zhǎng)度成正比 解析：順序表可以隨機(jī)訪問(wèn)任意一個(gè)結(jié)點(diǎn)，而鏈表必須從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)出發(fā)，逐一查找每個(gè)結(jié)點(diǎn)。所以答案為 A）。 答案： A） 2022/2/9 121 ? 【 例 5】 已知某二叉樹(shù)的后序遍歷序列是 DACBE，中序遍歷序列是 DEBAC，則它的前序遍歷序列是 _______。（考點(diǎn) 8） A） ACBED B） DEABC C） DECAB D） EDBAC 解析：后序遍歷的順序是 左子樹(shù)－右子樹(shù)－根結(jié)點(diǎn) ；中序遍歷順序是 左子樹(shù)－根結(jié)點(diǎn)－右子樹(shù) ；前序遍歷順序是 根結(jié)點(diǎn)－左子樹(shù)－右子樹(shù) 。根據(jù)各種遍歷算法，不難得出前序遍歷序列是 EDBAC。所以答案為 D）。 答案： D） 【 例 6】 設(shè)有一個(gè)已按各元素的值排好序的線性表（長(zhǎng)度大于 2），對(duì)給定的值 k，分別用順序查找法和二分查找法查找一個(gè)與 k相等的元素，比較的次數(shù)分別是 s和 b，在查找不成功的情況下， s和 b的關(guān)系是 _______。（考點(diǎn) 9） A） s=b B） sb C） sb D） s≥b 解析：對(duì)于順序查找，查找不成功時(shí)和給定關(guān)鍵字比較的次數(shù)為 n+1。二分查找查找不成功的關(guān)鍵字比較次數(shù)為 〔 log2n〕 +1。當(dāng) n≥2時(shí)，顯然 n+1〔 log2n〕+1。 答案： B） 【 例 7】 在快速排序過(guò)程中，每次劃分，將被劃分的表（或子表）分成左、右兩個(gè)子表，考慮這兩個(gè)子表，下列結(jié)論一定正確的是 _______。（考點(diǎn) 11） A）左、右兩個(gè)子表都已各自排好序 B）左邊子表中的元素都不大于右邊子表中的元素 C） 左邊子表的長(zhǎng)度小于右邊子表的長(zhǎng)度 D）左、右兩個(gè)子表中元素的平均值相等 解析：快速排序基本思想是：任取待排序表中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過(guò)一趟排序，將待排元素分為左右兩個(gè)子表，左子表元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子表的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子表繼續(xù)進(jìn)行排序，直至整個(gè)表有序。 答案： B） 2022/2/9 122 ? 二、填空題 【 例 1】 問(wèn)題處理方案的正確而完整的描述稱為 _______。（考點(diǎn) 1） 解析：計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。 答案：算法 【 例 2】 一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是按線性結(jié)構(gòu)處理的，則屬于 _______。（考點(diǎn) 4） 解析：一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)或是非線性結(jié)構(gòu)，要根據(jù)具體情況而定。如果對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)來(lái)處理的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。 答案：線性結(jié)構(gòu) 【 例 3】 設(shè)樹(shù) T的度為 4，其中度為 3和 4的結(jié)點(diǎn)的個(gè)數(shù)分別為 1，則 T中葉子結(jié)點(diǎn)的個(gè)數(shù)為 _______。（考點(diǎn) 7） 解析：根據(jù)樹(shù)的性質(zhì)：樹(shù)的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度與對(duì)應(yīng)的結(jié)點(diǎn)個(gè)數(shù)乘積之和加 1。 因此樹(shù)的結(jié)點(diǎn)數(shù)為 1 4＋ 2 2＋ 3 1＋ 4 1＋ 1＝ 16。葉子結(jié)點(diǎn)數(shù)目等于樹(shù)結(jié)點(diǎn)總數(shù)減去度不為 0的結(jié)點(diǎn)數(shù)之和，即 16－（ 4＋ 2＋ 1＋ 1）＝ 8。 答案： 8 【 例 4】 二分法查找的存儲(chǔ)結(jié)構(gòu)僅限于 _______且是有序的。（考點(diǎn) 10） 解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序 (升序或降序均可）。 答案：順序存儲(chǔ)結(jié)構(gòu) 2022/2/9 12