全國(guó)計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)--復(fù)習(xí)(20210308212517)

1、全國(guó)計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí) 一、數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu) 指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。 數(shù)據(jù)結(jié)構(gòu)用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成， 即一個(gè)數(shù)據(jù)由哪些成分構(gòu)成、 以什 么方式構(gòu)成、呈現(xiàn)什么樣的結(jié)構(gòu) 。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu) 和物理上的數(shù)據(jù)結(jié)構(gòu)之分 。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)之間的邏輯 關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù) 存在的形式。 算法是解題的步驟，是指令的有限序列。 它們規(guī)定了解決某一特定類型 問題的一系列運(yùn)算， 是對(duì)解題方案的準(zhǔn)確與完整的描述。 一個(gè)問題的解決方案要 以算法為基礎(chǔ)。 1.1 概念介紹 算法的時(shí)間復(fù)雜度: 算法的時(shí)間復(fù)雜度

2、是指執(zhí)行算法所需要的計(jì)算工作量。 算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量， 而算法所執(zhí)行的基本運(yùn) 算次數(shù)是問題規(guī)模的函數(shù)，即 算法的工作量 =f(n) 其中 n 是問題的規(guī)模。 例如， 兩個(gè) n 階矩陣相乘所需要的基本運(yùn)算 （即兩個(gè)實(shí)數(shù)的乘法 ）次數(shù)為 n3，即計(jì)算工作量為n3，也就是時(shí)間復(fù)雜度為n3。 算法的空間復(fù)雜度： 算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素相互之間的關(guān)系，稱為結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。 也稱 數(shù)據(jù)的物理結(jié)構(gòu)

3、。 各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相 同的。同一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示成任意一種或幾種不同的存儲(chǔ)結(jié) 構(gòu)。 數(shù)據(jù)的順序存儲(chǔ)方式 ：是將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上亦 相鄰的存儲(chǔ)單元里。也就是將所有存儲(chǔ)結(jié)點(diǎn)相繼存入在一個(gè)連續(xù)相鄰的存儲(chǔ)區(qū) 里。 數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)方式 ：是在存儲(chǔ)每個(gè)結(jié)點(diǎn)信息的同時(shí)，增加一個(gè)指 針來表示結(jié)點(diǎn)間的邏輯關(guān)系。該方式不要求邏輯上相鄰結(jié)點(diǎn)在物理位置上亦相 鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。因此， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的每 個(gè)結(jié)點(diǎn)都由兩部分組成： 一部分用于存儲(chǔ)結(jié)點(diǎn)本身的信息，稱為 數(shù)據(jù)域 ；另一 部分用于存儲(chǔ)該結(jié)點(diǎn)的后繼結(jié)點(diǎn) （

4、或前驅(qū)結(jié)點(diǎn) ）的存儲(chǔ)單元地址，稱為 指針域 。 指針域可以包含一個(gè)或多個(gè)指針，這由結(jié)點(diǎn)之間的關(guān)系所決定。 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 如果在一個(gè)線性結(jié)構(gòu)中， 一個(gè)數(shù)據(jù)元素都沒有， 則稱該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)結(jié) 構(gòu)。 線性結(jié)構(gòu)的邏輯特征 ：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中，除第一個(gè)數(shù)據(jù)元 素只有一個(gè)后繼沒有前驅(qū)、 最后一個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)沒有后繼外， 其他的 每一個(gè)數(shù)據(jù)元素僅有一個(gè)前驅(qū)和一個(gè)后繼。線性結(jié)構(gòu)也稱為 線性表 。 注：某個(gè)元素直接相鄰的前一個(gè)元素稱為此元素的 前驅(qū) 、直接相鄰的后一 個(gè)元素稱為此元素的 后繼 。 非線性結(jié)構(gòu)的邏輯特征 ：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中， 某數(shù)據(jù)元素可 能有多于一個(gè)前驅(qū)或后繼。如

5、樹型結(jié)構(gòu)等。 習(xí)題： （一）選擇題 （單選 ） 1. 算法的時(shí)間復(fù)雜度是指（ D ） A）算法的執(zhí)行時(shí)間 B）算法所處理的數(shù)據(jù)量 C）算法程序中的語句或指令條數(shù) D）算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù) 1.2 線性表 線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的一種線性的數(shù)據(jù)結(jié)構(gòu)。是一種最基 本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表常用的存儲(chǔ)方式有兩種： 順序存儲(chǔ)方式和鏈接存 儲(chǔ)方式。 線性表的數(shù)學(xué)定義： L=（a i,a2,a3,na 說明： 線性表是具有相同類型的n（n X）個(gè)數(shù)據(jù)元素組成的有限序列。 L:為表的名稱。 ai（i=1,2,為表的元素，也稱為線性表中的一個(gè)結(jié)點(diǎn)。它可以是一個(gè)數(shù)、 一個(gè)字符、一個(gè)字

6、符串，也可以是一條記錄，還可以是復(fù)雜的數(shù)據(jù)對(duì)象。a1 是 a2的前驅(qū)、a2是ai的后繼，a2是a3的前驅(qū)、a3是a2的后繼，依次類推。 n ：為線性表的長(zhǎng)度（元素個(gè)數(shù)），當(dāng)n=0時(shí)稱線性表為空表。 線性表的特點(diǎn) : 在非空的線性表中：存在唯一的一個(gè)“第一個(gè)元素” （根結(jié)點(diǎn) ）。存在唯一的 一個(gè)“最后一個(gè)元素” （終端結(jié)點(diǎn) ）。除第一個(gè)元素外，其他的元素均有唯一的前 驅(qū)。除最后一個(gè)元素外，其他的元素均有唯一的后繼。 1.3 棧和隊(duì)列 棧和隊(duì)列本質(zhì)上也是線性表， 只是它們的操作受到了限制。 1.3.1 棧 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。表尾稱為棧頂 (top) ，表 頭稱為棧底 (b

7、ottom) 。 棧這種數(shù)據(jù)結(jié)構(gòu)，類似于子彈夾， 底端是封閉的， 最后壓入的子彈總是最先被彈 出，最先壓入的子彈只能最后被彈出。 棧頂元素總是最后被插入的元素， 從而也是最先能被刪除的元素； 棧底元素 總是最先被插入的元素， 從而也是最后能被刪除的元素。 即棧是按照“先進(jìn)后出” 或“后進(jìn)先出”的原則組織數(shù)據(jù)的。因此， 棧也被稱為 “先進(jìn)后出” 表 或“后進(jìn)先出”表。 由此可以看出，棧具有記憶作用。 1.3.2 隊(duì)列 隊(duì)列是指只允許在表的一端插入元素、 在另一端刪除元素的線性表。 允許插入的 一端稱為隊(duì)尾 (rear) ，允許刪除的一端稱為隊(duì)頭 (front) 。 在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中， 最先插

8、入的元素將最先能夠被刪除， 反之最后插入的元 素將最后才能被刪除。因此， 隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后 出”的線性表。 1.4樹和二叉樹 1.4.1 樹 樹形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中一種很重要的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，所有數(shù)據(jù) 元素之間的關(guān)系具有明顯的層次特性。 樹形結(jié)構(gòu)很像自然界中的樹，像一棵倒長(zhǎng) 的樹。在現(xiàn)實(shí)生活中，能用樹形結(jié)構(gòu)表示的例子很多。參見下面的圖形： 轡桶*塞學(xué)蔭 樹形結(jié)構(gòu)的基本特征及基本術(shù)語: 以下圖為例： 樹的根： 在樹形結(jié)構(gòu)中，沒有前驅(qū)的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根 如：上圖中的“ R”。 父結(jié)點(diǎn)： 在樹形結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)（除了樹的根結(jié)點(diǎn)）只有一個(gè)前驅(qū)，稱為父

9、結(jié)點(diǎn)。 女如:上圖中的“ R”是K、P、Q、D的父結(jié)點(diǎn)；“N ”是X、Y的父結(jié)點(diǎn)。 子結(jié)點(diǎn)： 在樹形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 女如:上圖中的K、P、Q、D是“R”的子結(jié)點(diǎn)；X、Y是“ N”的子結(jié)點(diǎn)。 葉子結(jié)點(diǎn)： 在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，也稱終端結(jié)點(diǎn)。 女如:上圖中的C、M、F、E、X、G、S、L、Z、A均為葉子結(jié)點(diǎn)。 結(jié)點(diǎn)的度: 在樹形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后繼個(gè)數(shù)稱為該結(jié)點(diǎn)的度。 如如:上圖中根結(jié)點(diǎn)R的度是4;結(jié)點(diǎn)T的度是3;結(jié)點(diǎn)P、Q、D、0、丫、 W 的度都為 1。葉子結(jié)點(diǎn)的度為 0。 樹的度： 在樹形結(jié)構(gòu)中， 所有結(jié)點(diǎn)中的最大的度稱為樹的

10、度。 如：上圖中樹的度為 4， 因?yàn)榻Y(jié)點(diǎn) R 的度最大，是 4。 樹的深度： 在樹形結(jié)構(gòu)中，樹的最大層數(shù)稱為樹的深度 (或高度)。如：上圖中樹的深度 是 5。說明：樹形結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)。在樹形 結(jié)構(gòu)中一般按如下原則分層： 1) 根結(jié)點(diǎn)在第 1 層。 2) 其余結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)的層數(shù)加 1。 子樹： 在樹形結(jié)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一棵子樹。 如：上圖中，結(jié)點(diǎn)R有4棵子樹，它們分別以K、P、Q、D為根結(jié)點(diǎn)；結(jié)點(diǎn)P 有1棵子樹，其根結(jié)點(diǎn)為N ;結(jié)點(diǎn)T有3棵子樹，它們分別以 W、Z、A為根 結(jié)點(diǎn)。 在樹形結(jié)構(gòu)中，子樹間互不相交，葉子結(jié)點(diǎn)沒有子樹

11、。 森林： 森林是M(M 0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個(gè)森 林;反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴洹?1.4.2二叉樹 (1)二叉樹的特點(diǎn) 非空二叉樹只有一個(gè)根結(jié)點(diǎn)。 二叉樹中的每個(gè)結(jié)點(diǎn)，最多有兩棵子樹，分另稱為該結(jié)點(diǎn)的左子樹與右 子樹。當(dāng)一個(gè)結(jié)點(diǎn)即沒有左子樹也沒有右子樹時(shí)，該結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。在下面 的圖中，左面是只有根結(jié)點(diǎn)的二叉樹，右面是深度為4的二叉樹： (2)滿二叉樹與完全二叉樹 1)滿二叉樹： 滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn) 就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的 第k層上有2i-1 (k 1)個(gè)結(jié)

12、點(diǎn)，且深度為k的滿二叉樹有2k-1(k 1)個(gè)結(jié)點(diǎn)。 在下圖中分別是深度為2、3、4的滿二叉樹： A 2）裸度為2的甫二叉樹（h）深度為3的灌二貝撕 （c）深度為4的摘二叉樹 S 1.32 #|-XW 滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵深度相同的子樹， 且 葉子結(jié)點(diǎn)都在最下一層 2）完全二叉樹： 若一棵二叉樹最多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于 2，并且最下一 層上的所有結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉 樹。 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹仍然 是一棵完全二叉樹。 在完全二叉樹中， 若某個(gè)結(jié)點(diǎn)沒有左子結(jié)點(diǎn)，則它

13、一定沒有右子結(jié)點(diǎn)， 即該 結(jié)點(diǎn)必是葉子結(jié)點(diǎn)。 (3) 二叉樹的性質(zhì) 假設(shè)定義根結(jié)點(diǎn)的層數(shù)為 1(注意：有些資料中規(guī)定根結(jié)點(diǎn)的層數(shù)為 0) 。 性質(zhì)1：在二叉樹的第i層上，最多有2i- 1(i 1)個(gè)結(jié)點(diǎn)。 性質(zhì)2:深度為k的二叉樹最多有2k-1(k 1)個(gè)結(jié)點(diǎn)。 性質(zhì)3:在任意二叉樹中，若度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))的個(gè)數(shù)為no，度為 2的結(jié)點(diǎn)的個(gè)數(shù)為n2,貝U： n0= n2+1 (對(duì)于完全二叉樹還有如下屬性 ) 性質(zhì) 4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹， 其深度為 log2n+1 。注： log 2n 表示取 log 2n 的整數(shù)部分。性質(zhì) 5：如果將一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹自 頂向下、

14、同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào) 1、2、3、n,則對(duì)于任意結(jié) 點(diǎn)i(1 i 1 ，貝該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 Int(i/2) 。也可表示成 i/2 ，都 表示取整數(shù)。 2) 如果 2in ，貝結(jié)點(diǎn) i 無左子結(jié)點(diǎn)，顯然也沒有右子結(jié)點(diǎn)，是葉子結(jié)點(diǎn)。 如果2i n ，貝結(jié)點(diǎn) i 無右子結(jié)點(diǎn)。 如果2i+1 n，則結(jié)點(diǎn)i的右子結(jié)點(diǎn)的編號(hào)為2i+1。 (4) 二叉樹的遍歷 二叉樹的遍歷就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn) 僅被訪問一次 一棵非空二叉樹是由根結(jié)點(diǎn)、 左子樹和右子樹三部分組成。因此遍歷一棵非 空二叉樹的問題就可以分解為三項(xiàng)“子任條”： 訪問根結(jié)點(diǎn)（假設(shè)用D表示）。 遍歷左子樹

15、（假設(shè)用L表示）。 遍歷右子樹（假設(shè)用R表示）。 在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后 右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可分為三種：前序遍歷（DLR）、 中序遍歷（LDR）、后序遍歷（LRD）。 以下圖中的二叉樹為例: 前序遍歷（DLR）: 首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí), 仍然先訪問子樹的根結(jié)點(diǎn)，然后遍歷其左子樹，最后遍歷其右子樹。即，前序遍 歷是指訪問所有的根結(jié)點(diǎn)（包括子樹的根結(jié)點(diǎn)）都在遍歷其左、右子樹之前。 前序遍歷的操作: 若二叉樹為空，則結(jié)束反返回。否則： 訪問根結(jié)點(diǎn) 前序遍歷左子樹 前序遍歷右子樹 如，

16、對(duì)上圖中的二叉樹進(jìn)行前序遍歷的結(jié)果是： F C A D B E G H P 中序遍歷 (LDR) ： 首先遍歷左子樹，然后訪問根結(jié)點(diǎn) ，最后遍歷右子樹。在遍歷 左、右子樹時(shí)，仍然先遍歷其左子樹，然后訪問子樹的根結(jié)點(diǎn)，最后遍歷其右子 樹。即，中序遍歷是指訪問所有的根結(jié)點(diǎn) (包括子樹的根結(jié)點(diǎn) )都在遍歷其左子樹 之后、在遍歷其右子樹之前。 中序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： 中序遍歷左子樹 訪問根結(jié)點(diǎn) 中序遍歷右子樹 如，對(duì)上圖中的二叉樹進(jìn)行中序遍歷的結(jié)果是： A C B D F E H G P 后序遍歷 (LRD) ： 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。 在遍歷左

17、、右子樹時(shí)，仍然先遍歷其左子樹，然后遍歷其右子樹，最后訪問子樹 的根結(jié)點(diǎn)。即，后序遍歷是指訪問所有的根結(jié)點(diǎn) (包括子樹的根結(jié)點(diǎn) )都在遍歷其 左、右子樹之后。 后序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： 后序遍歷左子樹 后序遍歷右子樹 訪問根結(jié)點(diǎn) 如，對(duì)上圖中的二叉樹進(jìn)行后序遍歷的結(jié)果是： A B D C H P G E F 1.5 查找 查找又稱檢索。 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。 通 常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。 1.5.1 順序查找 順序查找又稱順序搜索或線性查找。 順序查找一般是指在線性表中查找指定 的元素。 順序查找的基本思想： 在

18、n 個(gè)結(jié)點(diǎn)組成的線性表中， 從線性表的一端開始， 依次將線性表中的元素 與被查元素進(jìn)行比較，若相等則表示找到， 即查找成功； 若線性表中所有的元素 都與被查元素進(jìn)行了比較但都不相等， 則表示線性表中沒有要找的元素， 即查找 失敗。 在順序查找中，查找成功時(shí)最多需要比較 n 次、最少比 較 1 次、平均比較次數(shù)約為表長(zhǎng)的一半。 查找失敗時(shí)比較 n+1 次。 順序查找的時(shí)間復(fù)雜度為 O(n) 。 對(duì)于無序表 (即表中的元素的排列是無序的 ) 和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表 (有序 的和無序的 )，只能用順序查找。 順序查找的優(yōu)點(diǎn)： 算法簡(jiǎn)單而適用范圍廣。 對(duì)表中元素的排列次序無要求， 既可以是按關(guān)鍵字 排

19、列的有序表，也可以是無序表； 對(duì)表的存儲(chǔ)結(jié)構(gòu)也無任何要求， 既適用于順序 存儲(chǔ)的順序表，也適用于鏈接存儲(chǔ)的鏈表。 順序查找的缺點(diǎn)： 查找效率低，平均查找長(zhǎng)度較大。當(dāng) n 很大時(shí)不宜采用順序查找。 1.5.2 二分查找 二分查找又稱折半查找。 它是一種查找效率較高的查找方法。 該方法只適用 于順序存儲(chǔ)結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列(非遞減有序 排列)。二分查找不能用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。 二分查找的基本思想：參見“ C 語言程序設(shè)計(jì)”或“ VB 程序設(shè)計(jì)”課件的 相應(yīng)內(nèi)容動(dòng)畫。 對(duì)于長(zhǎng)度為 n 的有序線性表，查找成功時(shí)最多需 要比較 log2(n+1) 次、最少比較 1 次、

20、平均查找長(zhǎng)度 近似 log2n 。當(dāng)查找失敗時(shí)，比較 log2n 或 log2(n+1) 次。 不管二分查找成功與否，其時(shí)間復(fù)雜度均為 O(log2n) 。 二分查找的最壞性能和平均性能相當(dāng)接近。 1.6 排序 排序就是將文件中的記錄進(jìn)行整理， 使之按照關(guān)鍵字進(jìn)行遞增或遞減的順序 排列起來，成為一個(gè)有序序列的過程。在本節(jié)所介紹的排序方法中， 其排序的對(duì) 象一般認(rèn)為是順序存儲(chǔ)的線性表，在程序設(shè)計(jì)語言中就是一維數(shù)組。 這里的排序算法，都是針對(duì)升序排序。 1.6.1 交換排序 交換排序是兩兩比較待排序記錄的關(guān)鍵字， 若發(fā)現(xiàn)兩個(gè)記錄關(guān)鍵字的次序相 反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。下面介紹兩種常

21、用的交換排序。 (1) 冒泡排序 冒泡排序的基本思想：參見“ C 語言程序設(shè)計(jì)”或“ VB 程序設(shè)計(jì)”課件的 相應(yīng)內(nèi)容動(dòng)畫。 對(duì)于長(zhǎng)度為 n 的線性表，在最壞情況下，冒泡排 序需要經(jīng)過 n/2 遍的掃描，比較次數(shù)為 n(n-1)/2 。 冒泡排序算法的平均時(shí)間復(fù)雜度為 O(n2) ，空間 復(fù)雜度為 O(1) 。 (2) 快速排序 快速排序的基本思想： 參見下圖： 可編輯 無序線件表 分割 WT 分割 分割 快速排序示竟 從線性表中選取一個(gè)元素，設(shè)為 T,將線性表后面小于T的元素移到前面， 將線性表前面大于T的元素移到后面，結(jié)果就把線性表分成了兩部分(稱為兩個(gè) 子表)，T插入到其分界線的位置處，

22、這個(gè)過程稱為線性表的分割。通過對(duì)線性 表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中 的所有元素均不大于T,后面子表中的所有元素均不小于 To 如果對(duì)分割后的各子表再按上述原則進(jìn)行分割， 并且這種分割過程可以一直 做下去，隨著對(duì)各子表不斷地進(jìn)行分割，劃分出的子表會(huì)越來越多(一次只能對(duì) 一個(gè)子表進(jìn)行再分割處理)，直到所有子表中的元素都排好序?yàn)橹?，則此時(shí)的線 性表就變成了有序表。 對(duì)于長(zhǎng)度為n的線性表： 在最壞情況下，快速排序比較次數(shù)為n(n-1)/2。算法 的時(shí)間復(fù)雜度為0(n2)，空間復(fù)雜度為0(n)。 在最好情況下，快速排序算法的時(shí)間復(fù)雜度為 0(nlog2n)，空間

23、復(fù)雜度為 O(log2n)。 快速排序算法的平均時(shí)間復(fù)雜度是 0(nlog2n)，平均 比較次數(shù)不大于(n+1)log2n 1.6.2 插入排序 插入排序是每次將一個(gè)待排序的記錄按其關(guān)鍵字大小， 插入到前面已排好的 序列中的適當(dāng)位置，直到全部記錄插入為止。 (1) 直接插入排序 快速排序的基本思想：請(qǐng)查看相關(guān)資料。 對(duì)于長(zhǎng)度為 n 的線性表： 在最壞情況下，直接插入排序比較次數(shù)為 n(n-1)/2 。 算法的時(shí)間復(fù)雜度為 O(n2) 。 (2) 希爾排序 希爾排序的基本思想：請(qǐng)查看相關(guān)資料。 對(duì)于長(zhǎng)度為 n 的線性表： 在最壞情況下希爾排序比較次數(shù)為 O(n1.5) 。 1.6.3 選擇排序

24、選擇排序的基本思想是：每一遍在n-i+1(i=1,2,n-1)個(gè)待排序記錄中選取 關(guān)鍵字最小的記錄作為有序序列中第 i 個(gè)記錄，直到全部記錄排完為止。 (1) 直接選擇排序 選擇排序的基本思想：參見“ C 語言程序設(shè)計(jì)”或“ VB 程序設(shè)計(jì)”課件的 相應(yīng)內(nèi)容動(dòng)畫。 在最壞情況下，直接選擇排序比較次數(shù)為 n(n-1)/2 。 (2) 堆排序 希爾排序的基本思想：請(qǐng)查看相關(guān)資料。 O(nlog2n) 。 在最壞情況下，堆排序比較次數(shù)為 習(xí)題： (一)選擇題 (單選 ) 1. 下列敘述中正確的是 ( D ) A )棧是“先進(jìn)先出”的線性表 B )隊(duì)列是“先進(jìn)后出”的線性表 C) 循環(huán)隊(duì)列是非線性結(jié)構(gòu)

25、 D) 有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2. 下列關(guān)于棧的敘述中正確的是 ( A ) A) 棧頂元素最先被刪除 B) 棧頂元素最后才能被刪除 C) 棧底元素永遠(yuǎn)不能被刪除 D) 以上三種說法都不對(duì) 3. 下列敘述中正確的是 ( B ) A) 有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu) B) 只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu) C) 循環(huán)鏈表是非線性結(jié)構(gòu) D) 雙向鏈表是非線性結(jié)構(gòu) 4. 支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是 ( A ) A) 棧 B) 樹 C) 隊(duì)列 D) 二叉樹 5. 某二叉樹有 5 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是( C ) A )10

26、 B)8C)6D )4 提示：在任意二叉樹中，若度為 0 的結(jié)點(diǎn) (即葉子結(jié)點(diǎn) )的個(gè)數(shù)為 n0 ，度為 2 的結(jié)點(diǎn)的個(gè)數(shù) 為 n2 ，則： n0= n2+1即 n0( 葉子結(jié)點(diǎn)數(shù) )=5+1=6 6. 某二叉樹共有 7 個(gè)結(jié)點(diǎn)， 其中葉子結(jié)點(diǎn)只有 1 個(gè)，則該二叉樹的深度為 (假設(shè)根結(jié)點(diǎn)在第 一層 )( D ) A) 3 B) 4C) 6D)7 7. 下列排序方法中，最壞情況下比較次數(shù)最少的是( D ) A )冒泡排序B)簡(jiǎn)單選擇排序C)直接插入排序D)堆排序 8. 下列敘述中正確的是 ( A ) A) 對(duì)長(zhǎng)度為 n 的有序鏈表進(jìn)行查找，最壞的情況下需要的比較次數(shù)為 n B) 對(duì)長(zhǎng)度為 n

27、的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為( n/2 ) C) 對(duì)長(zhǎng)度為 n 的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為(log 2n) D) 對(duì)長(zhǎng)度為 n 的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為 (nlog 2n) ( 二) 填空題 1. 假設(shè)用一個(gè)長(zhǎng)度為 50 的數(shù)組(數(shù)組元素的下標(biāo)從 0 到 49 )作為棧的存儲(chǔ)空間，棧底指 針 bottom 指向棧底元素，棧頂指針 top 指向棧頂元素，如果 bottom=49,top=30( 數(shù)組 下標(biāo) )，則棧中具有 個(gè)元素。 答案：20 2. 一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A、B、C、D、E、F、5、4、3、2

28、、1 一次入隊(duì)， 然后再一次退隊(duì)，則元素退隊(duì)的順序?yàn)?答案：A、B、C、D、E、F、5、4、3、2、1 3設(shè)某循環(huán)隊(duì)列的容量為50,如果頭指針front=45（指向隊(duì)頭元素的前一個(gè)位置 ），尾指針 rear=10 （指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有 元素。 答案：15 4.設(shè)二叉樹如下： 對(duì)該二叉樹進(jìn)行后序遍歷的結(jié)果為 答案：E、D、B、G、H、F、C、A 5. 一棵二叉樹的中序遍歷結(jié)果為 DBEAFC，前序遍歷結(jié)果為 ABDECF，則后序 遍歷結(jié)果為 答案：DEBFCA 存儲(chǔ)。 6. 有序線性表能進(jìn)行二分查找的前提是該線性表必須是 答案：順序 二、軟件工程基礎(chǔ) 計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬

29、件相互依存的另一部分， 是包括 程序、數(shù)據(jù) 及相關(guān) 文檔的完整集合。 軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的， 與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。 軟件的分類 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件 （或工具軟件 ）。 應(yīng)用軟件：是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。 系統(tǒng)軟件： 是計(jì)算機(jī)管理自身資源， 提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提 供各種服務(wù)的軟件。 支撐軟件： 是介于系統(tǒng)軟件和應(yīng)用軟件之間， 協(xié)助用戶開發(fā)軟件的工具性軟 件。 軟件生命周期 通常將軟件產(chǎn)品從提出、 實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生 命周期。參見下圖： 結(jié)構(gòu)化分析方法

30、 結(jié)構(gòu)化分析的常用工具： 數(shù)據(jù)流圖(DFD):是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖 形表示，它直接支持系統(tǒng)的功能建模。 數(shù)據(jù)字典(DD):是結(jié)構(gòu)化分析方法的核心。 判定樹 判定表 結(jié)構(gòu)化設(shè)計(jì)方法 常見的過程設(shè)計(jì)工具： 圖形工具：程序流程圖，N-S圖，PAD圖（問題分析圖）,HIPO 表格工具：判定表。 語言工具：PDL（偽碼） 軟件設(shè)計(jì)的基本原理 1）抽象：是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮 其他細(xì)節(jié)。 2）模塊化：是指把一個(gè)待開發(fā)的軟件分解成若干小的簡(jiǎn)單的部分。如高級(jí) 語言中的過程、函數(shù)、子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模 塊可以按一定的方

31、法組裝起來成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。 3）信息隱蔽：是指在一個(gè)模塊內(nèi)包含的信息 （過程或數(shù)據(jù) ），對(duì)于不需要這些 信息的其他模塊來說是不能訪問的。 4）模塊獨(dú)立性：是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模 塊的聯(lián)系最少且接口簡(jiǎn)單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。 衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性 的度量標(biāo)準(zhǔn) 。 內(nèi)聚性： 是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。 內(nèi)聚是從 功能角度來度量模塊內(nèi)的聯(lián)系 內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展。 一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模 塊的模塊獨(dú)立性越強(qiáng)。 作為軟件結(jié)構(gòu)設(shè)計(jì)的設(shè)計(jì)原則， 要求每一個(gè)模

32、塊的內(nèi)部都 具有很強(qiáng)的內(nèi)聚性，它的各個(gè)組成部分彼此都密切相關(guān)。 耦合性：耦合性是模塊間相互連接的緊密程度的度量。 一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。原則上講， 模塊化設(shè)計(jì)總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。 但是，由于問題所固 有的復(fù)雜性和結(jié)構(gòu)化設(shè)計(jì)的原則，非直接耦合往往是不存在的。 耦合性與內(nèi)聚性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)， 耦合性與內(nèi)聚性是相互聯(lián)系 的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)， 則耦合性越弱。 一般優(yōu)秀的軟件設(shè)計(jì)， 應(yīng)盡量做到高內(nèi)聚， 低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的的內(nèi)聚性， 有利于提高模塊的獨(dú)立性。 軟件測(cè)試 軟件測(cè)試是在軟件投入運(yùn)行前

33、對(duì)軟件需求、設(shè)計(jì)、編碼的最后審核。軟件測(cè) 試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。 軟件測(cè)試應(yīng)當(dāng)制定明確的測(cè)試計(jì)劃并按計(jì) 劃執(zhí)行。 軟件測(cè)試的目的：是發(fā)現(xiàn)錯(cuò)誤。 軟件測(cè)試方法和技術(shù)： 若從是否需要執(zhí)行被測(cè)軟件的角度， 可以分為靜態(tài)測(cè) 試和動(dòng)態(tài)測(cè)試方法。若按照功能劃分可以分為白盒測(cè)試和黑盒測(cè)試方法。 靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。靜態(tài)測(cè)試不實(shí) 際運(yùn)行軟件，主要通過人工進(jìn)行。 動(dòng)態(tài)測(cè)試： 是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。需要 精心設(shè)計(jì)一批測(cè)試用例， 并利用這些測(cè)試用例去運(yùn)行程序， 以發(fā)現(xiàn)程序錯(cuò)誤的過 程。測(cè)試用例的格式為： （輸入值集 ）,（輸出值集 ） 白盒

34、測(cè)試： 也稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。 它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過 程，檢查內(nèi)部成分， 以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。 白盒測(cè)試把測(cè)試對(duì) 象看作一個(gè)打開的盒子， 允許測(cè)試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息來設(shè) 計(jì)或選擇測(cè)試用例， 對(duì)程序所有的邏輯路徑進(jìn)行測(cè)試。 通過在不同點(diǎn)檢查程序的 狀態(tài)來了解實(shí)際的運(yùn)行狀態(tài)是否與預(yù)期的一致。 所以，白盒測(cè)試是在程序內(nèi)部進(jìn) 行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。 白盒測(cè)試的主要方法有邏輯覆蓋、基本路徑測(cè)試等。 黑盒測(cè)試： 也稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。 黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功 能是否滿足需求進(jìn)行測(cè)試和驗(yàn)證。 黑盒測(cè)試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)

35、部特征，只依據(jù)程序的需求和功能規(guī)格說明， 檢查程序的功能是否符合它的功能 說明。所以，黑盒測(cè)試是在軟件接口處進(jìn)行，完成功能驗(yàn)證。黑盒測(cè)試只檢查程 序功能是否按照需求規(guī)格說明書的規(guī)定正常使用， 程序是否能適當(dāng)?shù)亟邮蛰斎霐?shù) 據(jù)而產(chǎn)生正確的輸出信息，并且保持外部信息 （如數(shù)據(jù)庫或文件 ）的完整性。 黑盒測(cè)試主要診斷功能不對(duì)或遺漏、 界面錯(cuò)誤、 數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問 錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。黑盒測(cè)試方法主要有等價(jià)類劃分法、 邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等，主要用于軟件確認(rèn)測(cè)試。 程序調(diào)試 在對(duì)程序進(jìn)行了成功的測(cè)試之后， 將進(jìn)入程序調(diào)試 (通常稱 Debug ，即排錯(cuò) ) 程序調(diào)試

36、的任務(wù)是診斷和改正程序中的錯(cuò)誤。 它與軟件測(cè)試不同， 軟件測(cè)試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò) 誤，并找出軟件錯(cuò)誤的具體位置。軟件測(cè)試貫穿整個(gè) 軟件生命期，調(diào)試主要在開發(fā)階段。 習(xí)題： (一)選擇題 ( 單選) 1. 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件(或工具軟件) 。下面屬于應(yīng)用軟 件的是 ( C ) A) 編譯程序 B) 操作系統(tǒng) C) 教務(wù)管理系統(tǒng) D) 匯編程序 2. 軟件按功能可分為：應(yīng)用軟件、系統(tǒng)軟件、和支撐軟件(或工具軟件) 。下面屬于系統(tǒng)軟 件的是 ( B ) A) 編輯軟件B)操作系統(tǒng)C)教務(wù)管理系統(tǒng)D)瀏覽器、 3. 軟件 (程序)調(diào)試的任務(wù)是 ( A ) A) 診

37、斷和改正程序中的錯(cuò)誤 C) 發(fā)現(xiàn)并改正程序中的所有錯(cuò)誤 4. 下面敘述中錯(cuò)誤的是 ( A ) B) 盡可能多的發(fā)現(xiàn)程序中的錯(cuò)誤 D) 確定程序中錯(cuò)誤的性質(zhì) 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è)試的隨意性 5. 耦合性和內(nèi)聚性是對(duì)模塊獨(dú)立性度量的兩個(gè)標(biāo)準(zhǔn)。下列敘述中正確的是( B ) A) 提高耦合性、降低內(nèi)聚性有利于提高模塊的獨(dú)立性 B) 降低耦合性、提高內(nèi)聚性有利于提高模塊的獨(dú)立性 C) 耦合性是指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度 D) 內(nèi)聚性

38、是指模塊間互相連接的緊密程度 6. 數(shù)據(jù)流圖 (DFD 圖)是( C ) A) 軟件概要設(shè)計(jì)的工具 C) 結(jié)構(gòu)化方法的需求分析工具 B) 軟件詳細(xì)設(shè)計(jì)的工具 D) 面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?7. 軟件生命周期可分為定義階段，開發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計(jì)屬于 ( B ) A) 定義階段 B) 開發(fā)階段 C) 維護(hù)階段 D) 上述三個(gè)階段 8. 在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是( D ) A) 軟件集成測(cè)試計(jì)劃 B) 軟件詳細(xì)設(shè)計(jì)說明書 C) 用戶手冊(cè) D) 軟件需求規(guī)格 說明書 9. 結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括 ( B ) A) 順序結(jié)構(gòu) B) GOTO 跳轉(zhuǎn) C) 選擇(分支

39、 )結(jié)構(gòu)D) 重復(fù) (循環(huán))結(jié)構(gòu) 10. 下面描述中錯(cuò)誤的是 ( A ) A) 系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細(xì)設(shè)計(jì) B) 軟件設(shè)計(jì)是將軟件需求轉(zhuǎn)換為軟件表示的過程 C) 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫設(shè)計(jì)是軟件設(shè)計(jì)的任務(wù)之一 D) PAD 圖是軟件詳細(xì)設(shè)計(jì)的表示工具 ( 二) 填空題 1. 軟件測(cè)試可分為白盒測(cè)試和黑盒測(cè)試。基本路徑測(cè)試屬于 測(cè)_ 試。 答案：白盒 2. 符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和 答案：順序結(jié)構(gòu) 3. 軟件是 、數(shù)據(jù)和文檔的集合。 答案：程序 4. 對(duì)軟件設(shè)計(jì)的最小單位 (模塊或程序單元 )進(jìn)行的測(cè)試通常為 測(cè)試。 答案：?jiǎn)卧?或 模塊 三、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)

40、計(jì)算機(jī)應(yīng)用的三大領(lǐng)域：科學(xué)計(jì)算、數(shù)據(jù)處理、過程控制 數(shù)據(jù)庫系統(tǒng)的基本概念 數(shù)據(jù) (Data) ：就是描述事物的符號(hào)記錄。 數(shù)據(jù)庫(DB):是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ) 介質(zhì)內(nèi)， 是多種應(yīng)用數(shù)據(jù)的集成， 并可被各個(gè)應(yīng)用程序所共享。 數(shù)據(jù)庫中的數(shù)據(jù) 具有“集成”、“共享”的特點(diǎn)。 數(shù)據(jù)庫管理系統(tǒng) (DBMS) :是數(shù)據(jù)庫的機(jī)構(gòu)，是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫 中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管理系 統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。 數(shù)據(jù)庫管理系統(tǒng)一般提供相應(yīng)的數(shù)據(jù)語言 (Data Language) 來完成相應(yīng)的 功能: 數(shù)據(jù)定義語言(DDL):負(fù)責(zé)數(shù)據(jù)的

41、模式定義與數(shù)據(jù)的物理存取構(gòu)建。 數(shù)據(jù)操縱語言 (DML) :負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。 數(shù)據(jù)控制語言(DCL):負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、 故障恢復(fù)等功能， 包括系統(tǒng)初啟程序、 文件讀寫與維護(hù)程序、 存取路徑管理程序、 緩沖區(qū)管理程序、安全性控制程序、完整性檢查程序、并發(fā)控制程序、事務(wù)管理 程序、運(yùn)行日志管理程序、數(shù)據(jù)庫恢復(fù)程序等。 數(shù)據(jù)庫管理員 (DBA) ：由于數(shù)據(jù)庫的共享性，因此對(duì)數(shù)據(jù)庫的規(guī)劃、設(shè)計(jì)、 維護(hù)、監(jiān)視等需要有專人管理，稱他們?yōu)閿?shù)據(jù)庫管理員。 數(shù)據(jù)庫系統(tǒng) (DBS) ：由數(shù)據(jù)庫 (數(shù)據(jù))、數(shù)據(jù)庫管理系統(tǒng) (軟件)、數(shù)據(jù)庫管理 員(人員 )

42、、系統(tǒng)硬件平臺(tái) (硬件)、系統(tǒng)軟件平臺(tái) (軟件)這五部分組成， 稱為數(shù)據(jù)庫 系統(tǒng)。 數(shù)據(jù)庫應(yīng)用系統(tǒng) (DBAS) ：是數(shù)據(jù)庫系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面這三者 所組成 E-R 模型 該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化成實(shí)體、 聯(lián)系、屬性等幾個(gè)基本概念，以及它 們間的兩種基本聯(lián)接關(guān)系，并且可以用一種圖非常直觀地表示出來。下面是 E-R 模型的基本概念。 目前較為有名的概念模型有 E-R 模型、擴(kuò)充的 E-R 模型、面向?qū)ο竽Ｐ图?謂詞模型等。 實(shí)體：現(xiàn)實(shí)世界中的事物可以抽象成為實(shí)體。 實(shí)體是概念世界中的基本單位， 它們是客觀存在的且又相互區(qū)別的事物。 凡是有共性的實(shí)體可組成一個(gè)集合稱實(shí) 體集。如學(xué)生A和

43、學(xué)生B,他們都是實(shí)體，他們又都是學(xué)生，從而組成一個(gè)學(xué)生 實(shí)體集。 屬性：現(xiàn)實(shí)世界中的事物均有一些特性，這些特性可以用屬性來表示。屬性 刻畫了實(shí)體的特征。一個(gè)實(shí)體往往可以有若干個(gè)屬性。 聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)聯(lián)稱為聯(lián)系。 在概念世界中聯(lián)系反映了實(shí)體集 間的一定關(guān)系。如工人與設(shè)備間的操作關(guān)系，上、下級(jí)間的領(lǐng)導(dǎo)關(guān)系等。 實(shí)體集間的聯(lián)系有多種，就實(shí)體集的個(gè)數(shù)而言有： 1) 兩個(gè)實(shí)體集間的聯(lián)系。 2) 多個(gè)實(shí)體集間的聯(lián)系。 3) 一個(gè)實(shí)體集內(nèi)部的聯(lián)系：是一個(gè)實(shí)體集內(nèi)的不同實(shí)體間的聯(lián)系。 實(shí)體集間聯(lián)系的個(gè)數(shù)可以是單個(gè)也可以是多個(gè)，包括： 一對(duì)一的聯(lián)系，簡(jiǎn)記為1:1 一對(duì)多或多對(duì)一的聯(lián)系，簡(jiǎn)記為 1：M

44、或M:1(其中M也可以小寫) 多對(duì)多的聯(lián)系，簡(jiǎn)記為 M:N或m:n E-R模型由上面三個(gè)基本概念組成。由實(shí)體、聯(lián)系、屬性三者結(jié)合起來才能 表示現(xiàn)實(shí)世界。 E-R圖：E-R模型可以用一種非常直觀的圖的形式表示，這種圖稱為E-R圖 在E-R圖中我們分別用下面不同的幾何圖形表示E-R模型中的三個(gè)概念與兩個(gè) 聯(lián)接關(guān)系 1) 實(shí)體集表示法 用矩形表示實(shí)體集，在矩形內(nèi)寫上該實(shí)體集的名字。如實(shí)體集學(xué)生 (student)、課程(course)可表示為： stvdeai course 實(shí)體集表示法 2) 屬性表示法 用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱。如學(xué)生有屬性：學(xué)號(hào) (S#)、姓名(Sn)及年齡

45、(Sa)，可表示為: 屬性表示陡 SC，可表 3) 聯(lián)系表示法 用菱形表示聯(lián)系，在菱形內(nèi)寫上聯(lián)系名。如學(xué)生與課程間的聯(lián)系 示為: 上面是三個(gè)基本概念分別用三種幾何圖形表示。 下面是它們之間的聯(lián)接關(guān)系的圖 形表示。 4）實(shí)體集或聯(lián)系與屬性間的聯(lián)接關(guān)系 屬性依附于實(shí)體集，屬性也依附于聯(lián)系，因此它們之間分別有聯(lián)接關(guān)系。參 見下圖: 其中：C#（課程號(hào)）、Cn（課程名）、P#（預(yù)修課號(hào)） 5）實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系 如下圖表示實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系： 還可以在線段邊上注明其對(duì)應(yīng)的函數(shù)關(guān)系，如1:1、1:n、n:m等。下圖表 示student與course間有多對(duì)多聯(lián)系： 兩個(gè)實(shí)體集間聯(lián)系叫二元聯(lián)系

46、，多個(gè)實(shí)體集間聯(lián)系叫多元聯(lián)系。下圖聯(lián)系 FPU是一種三元聯(lián)系(工廠、產(chǎn)品與用戶間的聯(lián)系)： 下面是實(shí)體間多種聯(lián)系圖： (a)圖：公司職工(enployee)間上、下級(jí)管理(manage)的聯(lián)系。即一個(gè)實(shí)體 集內(nèi)部可以有多種聯(lián)系。 (b)圖：教師(T)與學(xué)生(S)之間可以有教學(xué)(E)聯(lián)系也可以有管理(M)聯(lián)系。即 實(shí)體集間可以有多種聯(lián)系 F面是E-R圖的一個(gè)實(shí)例圖 關(guān)系模型 關(guān)系模型采用二維表來表示，簡(jiǎn)稱表。 二維表由表框架(Frame)及表的元組(Tuple)組成。表框架由n個(gè)命名的屬性 (Attribute)組成，n稱為屬性元數(shù)(Arity)。每個(gè)屬性有一個(gè)取值范圍，稱為值域 (Domain

47、) 。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。 在表框架中按行可以存放數(shù)據(jù)， 每行數(shù)據(jù)稱為元組，實(shí)際上，一個(gè)元組是由 n 個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值。一個(gè)表框架 可以存放 m 個(gè)元組， m 稱為表的基數(shù) (Cardinality) 。 一個(gè) n 元表框架及框架內(nèi) m 個(gè)元組構(gòu)成了一個(gè)完整的二維表。 關(guān)系框架與關(guān)系元組構(gòu)成了一個(gè) 關(guān)系 。一個(gè)語義相關(guān)的關(guān)系集合構(gòu)成一個(gè) 關(guān)系數(shù)據(jù)庫。 關(guān)系的框架稱為關(guān)系模式， 而語義相關(guān)的關(guān)系模式集合構(gòu)成了關(guān)系 數(shù)據(jù)庫模式。 滿足下面 7 個(gè)性質(zhì)的二維表稱為關(guān)系 (Relation) ： 1) 元組個(gè)數(shù)有限性：二維表中元組個(gè)數(shù)是有限的。

48、 2) 元組的惟一性：二維表中元組均不相同。 3) 元組的次序無關(guān)性：二維表中元組的次序可以任意交換。 4) 元組分量的原子性：二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)。 5) 屬性名惟一性：二維表中屬性名各不相同。 6) 屬性的次序無關(guān)性：二維表中屬性與次序無關(guān)，可任意交換。 7) 分量值域的同一性：二維表屬性的分量具有與該屬性相同的值域。 以二維表 (關(guān)系)為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型。 在關(guān)系模型中的一個(gè)重要概念是鍵 (Key) 或碼。鍵具有標(biāo)識(shí)元組、建立元組 間聯(lián)系等重要作用。 鍵或碼： 在二維表中凡能惟一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼。 候選鍵或候選碼： 二維表中可能有若干個(gè)鍵，它們稱為該表的候選鍵 (Candidata Key) 或候選碼。 主鍵或主碼： 從二維表的所有候選鍵中選取一個(gè)作為用戶使用的鍵， 稱為主 鍵 (Primary Key) 或主碼。一般主鍵也簡(jiǎn)稱為鍵或碼。 外鍵或外碼： 表