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

一、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)用來(lái)反映一個(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ī)定了解決某一特定類(lèi)型問(wèn)題的一系列運(yùn)算，是對(duì)解題方案的準(zhǔn)確與完整的描述。一個(gè)問(wèn)題的解決方案要以算法為基礎(chǔ)。1.1概念介紹?算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即算法的工作量其中是問(wèn)題的規(guī)模。例如，兩個(gè)階矩陣相乘所需要的基本運(yùn)算即兩個(gè)實(shí)數(shù)的乘法次數(shù)為,即計(jì)算工作量為，也就是時(shí)間復(fù)雜度為。?算法的空間復(fù)雜度:算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。?數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素相互之間的關(guān)系，稱(chēng)為結(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ǔ)空間中的存放形式。也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)。各數(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è)指針來(lái)表示結(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)本身的信息，稱(chēng)為數(shù)據(jù)域；另一部分用于存儲(chǔ)該結(jié)點(diǎn)的后繼結(jié)點(diǎn)（或前驅(qū)結(jié)點(diǎn)）的存儲(chǔ)單元地址，稱(chēng)為指針域。指針域可以包含一個(gè)或多個(gè)指針，這由結(jié)點(diǎn)之間的關(guān)系所決定。?線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)如果在一個(gè)線(xiàn)性結(jié)構(gòu)中，一個(gè)數(shù)據(jù)元素都沒(méi)有，則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu)的邏輯特征：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中，除第一個(gè)數(shù)據(jù)元素只有一個(gè)后繼沒(méi)有前驅(qū)、最后一個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)沒(méi)有后繼外，其他的每一個(gè)數(shù)據(jù)元素僅有一個(gè)前驅(qū)和一個(gè)后繼。線(xiàn)性結(jié)構(gòu)也稱(chēng)為線(xiàn)性表。注：某個(gè)元素直接相鄰的前一個(gè)元素稱(chēng)為此元素的前驅(qū)、直接相鄰的后一個(gè)元素稱(chēng)為此元素的后繼。非線(xiàn)性結(jié)構(gòu)的邏輯特征：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中，某數(shù)據(jù)元素可能有多于一個(gè)前驅(qū)或后繼。如樹(shù)型結(jié)構(gòu)等。習(xí)題：一）選擇題（單選）算法的時(shí)間復(fù)雜度是指（）算法的執(zhí)行時(shí)間算法所處理的數(shù)據(jù)量算法程序中的語(yǔ)句或指令條數(shù)）算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)線(xiàn)性表線(xiàn)性表是由同一類(lèi)型的數(shù)據(jù)元素構(gòu)成的一種線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)。是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線(xiàn)性表常用的存儲(chǔ)方式有兩種：順序存儲(chǔ)方式和鏈接存儲(chǔ)方式。線(xiàn)性表的數(shù)學(xué)定義：說(shuō)明：線(xiàn)性表是具有相同類(lèi)型的$個(gè)數(shù)據(jù)元素組成的有限序列。:為表的名稱(chēng)?！?:為表的元素，也稱(chēng)為線(xiàn)性表中的一個(gè)結(jié)點(diǎn)。它可以是一個(gè)數(shù)、一個(gè)字符、一個(gè)字符串，也可以是一條記錄，還可以是復(fù)雜的數(shù)據(jù)對(duì)象是的前驅(qū)、是的后繼，是的前驅(qū)、是的后繼，?…，依次類(lèi)推。:為線(xiàn)性表的長(zhǎng)度元素個(gè)數(shù)）當(dāng)時(shí)稱(chēng)線(xiàn)性表為空表。線(xiàn)性表的特點(diǎn)：■在非空的線(xiàn)性表中：存在唯一的一個(gè)“第一個(gè)元素”（根結(jié)點(diǎn)）。存在唯一的一個(gè)“最后一個(gè)元素”（終端結(jié)點(diǎn)）。除第一個(gè)元素外，其他的元素均有唯一的前驅(qū)。除最后一個(gè)元素外，其他的元素均有唯一的后繼。1.棧3和隊(duì)列棧和隊(duì)列本質(zhì)上也是線(xiàn)性表，只是它們的操作受到了限制。1.3棧.1棧是限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。表尾稱(chēng)為棧頂 ，表頭稱(chēng)為棧底 。棧這種數(shù)據(jù)結(jié)構(gòu)，類(lèi)似于子彈夾，底端是封閉的，最后壓入的子彈總是最先被彈出，最先壓入的子彈只能最后被彈出。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后能被刪除的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。因此，棧也被稱(chēng)為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。1.3隊(duì).列2隊(duì)列是指只允許在表的一端插入元素、在另一端刪除元素的線(xiàn)性表。允許插入的一端稱(chēng)為隊(duì)尾 ，允許刪除的一端稱(chēng)為隊(duì)頭 。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之最后插入的元素將最后才能被刪除。因此，隊(duì)列又稱(chēng)為“先進(jìn)先出”或“后進(jìn)后出”的線(xiàn)性表。

樹(shù)4和二叉樹(shù)樹(shù).樹(shù)形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中一種很重要的非線(xiàn)性結(jié)構(gòu)。在樹(shù)形結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。樹(shù)形結(jié)構(gòu)很像自然界中的樹(shù)，像一棵倒長(zhǎng)的樹(shù)。在現(xiàn)實(shí)生活中，能用樹(shù)形結(jié)構(gòu)表示的例子很多。參見(jiàn)下面的圖形：第一章第一章第二章第三章第四章/\/\\/\'/'\丄1節(jié)1.2節(jié)N節(jié)'22節(jié)2.3節(jié)3J節(jié)3.2節(jié)Ni節(jié)4.2節(jié)樹(shù)形結(jié)構(gòu)的基本特征及基本術(shù)語(yǔ)以下圖為例：在樹(shù)形結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)（除了樹(shù)的根結(jié)點(diǎn)）只有一個(gè)前驅(qū)，稱(chēng)為父結(jié)點(diǎn)。如：上圖中的“”是、、、的父結(jié)點(diǎn)；“”是、的父結(jié)點(diǎn)。子結(jié)點(diǎn)：在樹(shù)形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼，稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。如：上圖中的、、、是“”的子結(jié)點(diǎn)；、是“”的子結(jié)點(diǎn)。葉子結(jié)點(diǎn)：在樹(shù)形結(jié)構(gòu)中，沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)，也稱(chēng)終端結(jié)點(diǎn)。如：上圖中的、、、、、、、、、均為葉子結(jié)點(diǎn)。結(jié)點(diǎn)的度：在樹(shù)形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后繼個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。如：上圖中根結(jié)點(diǎn)的度是；結(jié)點(diǎn)的度是；結(jié)點(diǎn)、、、、、的度都為。葉子結(jié)點(diǎn)的度為。樹(shù)的度：在樹(shù)形結(jié)構(gòu)中，所有結(jié)點(diǎn)中的最大的度稱(chēng)為樹(shù)的度。如：上圖中樹(shù)的度為4，因?yàn)榻Y(jié)點(diǎn)的度最大，是。樹(shù)的深度：在樹(shù)形結(jié)構(gòu)中，樹(shù)的最大層數(shù)稱(chēng)為樹(shù)的深度（或高度）。如：上圖中樹(shù)的深度是5。說(shuō)明：樹(shù)形結(jié)構(gòu)具有明顯的層次關(guān)系，即樹(shù)是一種層次結(jié)構(gòu)。在樹(shù)形結(jié)構(gòu)中一般按如下原則分層：1） 根結(jié)點(diǎn)在第1層。2） 其余結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)的層數(shù)加1。子樹(shù)：在樹(shù)形結(jié)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱(chēng)為該結(jié)點(diǎn)的一棵子樹(shù)。如：上圖中，結(jié)點(diǎn)有棵子樹(shù)，它們分別以、、、為根結(jié)點(diǎn)；結(jié)點(diǎn)有棵子樹(shù)，其根結(jié)點(diǎn)為；結(jié)點(diǎn)有棵子樹(shù)，它們分別以、、為根結(jié)點(diǎn)。在樹(shù)形結(jié)構(gòu)中，子樹(shù)間互不相交，葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。森林：森林是$棵互不相交的樹(shù)的集合。刪去一棵樹(shù)的根，就得到一個(gè)森林;反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。二叉樹(shù)（1二）叉樹(shù)的特點(diǎn)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，最多有兩棵子樹(shù)，分另稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。當(dāng)一個(gè)結(jié)點(diǎn)即沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí)，該結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。在下面的圖中，左面是只有根結(jié)點(diǎn)的二叉樹(shù)，右面是深度為4的二叉樹(shù)：

(2)滿(mǎn)二叉樹(shù)與完全二叉樹(shù)1)滿(mǎn)二叉樹(shù)：滿(mǎn)二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。就是說(shuō)，在滿(mǎn)二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿(mǎn)二叉樹(shù)的第層上有$個(gè)結(jié)點(diǎn)，且深度為的滿(mǎn)二叉樹(shù)有 鼻個(gè)纟吉點(diǎn)。在下圖中分別是深度為、3的滿(mǎn)二叉樹(shù)：滿(mǎn)二叉樹(shù)中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵深度相同的子樹(shù)，且葉子結(jié)點(diǎn)都在最下一層。2)完全二叉樹(shù)：若一棵二叉樹(shù)最多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的所有結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱(chēng)為完全二叉樹(shù)。在下圖的4棵二叉樹(shù)中，分別是深度為3和4的完全二叉樹(shù)：滿(mǎn)二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。在滿(mǎn)二叉樹(shù)的最下一層上，從最右邊開(kāi)始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹(shù)仍然是一棵完全二叉樹(shù)。在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)，則它一定沒(méi)有右子結(jié)點(diǎn)，即該結(jié)點(diǎn)必是葉子結(jié)點(diǎn)。(3)二叉樹(shù)的性質(zhì)假設(shè)定義根結(jié)點(diǎn)的層數(shù)為1(注意：有些資料中規(guī)定根結(jié)點(diǎn)的層數(shù)為0。)性質(zhì)：在二叉樹(shù)的第層上，最多有 鼻個(gè)結(jié)點(diǎn)。性質(zhì)：深度為的二叉樹(shù)最多有 鼻個(gè)結(jié)點(diǎn)。性質(zhì)3在任意二叉樹(shù)中，若度為的結(jié)點(diǎn)即葉子結(jié)點(diǎn)的個(gè)數(shù)為，度為的結(jié)點(diǎn)的個(gè)數(shù)為，貝J：(對(duì)于完全二叉樹(shù)還有如下屬性)性質(zhì)：具有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為 。注:表示取 的整數(shù)部分。性質(zhì)：如果將一棵有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下、同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)\ \ \…、，則對(duì)于任意結(jié)點(diǎn)WW有如下結(jié)論：如果=此結(jié)點(diǎn)為根結(jié)點(diǎn)，無(wú)前驅(qū)即無(wú)父結(jié)點(diǎn)）如果>則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 。也可表示成 /都表示取整數(shù)。如果，則結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)，顯然也沒(méi)有右子結(jié)點(diǎn)，是葉子結(jié)點(diǎn)。如果W,則結(jié)點(diǎn)的左子結(jié)點(diǎn)是編號(hào)為的結(jié)點(diǎn)。如果 ，則結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。如果Wi則結(jié)點(diǎn)的右子結(jié)點(diǎn)的編號(hào)為 。二叉樹(shù)的遍歷二叉樹(shù)的遍歷就是遵從某種次序，訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪(fǎng)問(wèn)一次。一棵非空二叉樹(shù)是由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)三部分組成。因此遍歷一棵非空二叉樹(shù)的問(wèn)題就可以分解為三項(xiàng)“子任條”：訪(fǎng)問(wèn)根結(jié)點(diǎn)假設(shè)用表示。遍歷左子樹(shù)假設(shè)用表示。遍歷右子樹(shù)假設(shè)用表示。在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后右的原則下，根據(jù)訪(fǎng)問(wèn)根結(jié)點(diǎn)的次序，二叉樹(shù)的遍歷可分為三種：前序遍歷、中序遍歷、后序遍歷。以下圖中的二叉樹(shù)為例:前序遍歷：首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪(fǎng)問(wèn)子樹(shù)的根結(jié)點(diǎn)，然后遍歷其左子樹(shù)，最后遍歷其右子樹(shù)。即，前序遍歷是指訪(fǎng)問(wèn)所有的根結(jié)點(diǎn)（包括子樹(shù)的根結(jié)點(diǎn)）都在遍歷其左、右子樹(shù)之前。前序遍歷的操作：若二叉樹(shù)為空，則結(jié)束反返回。否則：訪(fǎng)問(wèn)根結(jié)點(diǎn)前序遍歷左子樹(shù)前序遍歷右子樹(shù)如，對(duì)上圖中的二叉樹(shù)進(jìn)行前序遍歷的結(jié)果是：FCADBEG中序遍歷 ：首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷其左子樹(shù)，然后訪(fǎng)問(wèn)子樹(shù)的根結(jié)點(diǎn)，最后遍歷其右子樹(shù)。即，中序遍歷是指訪(fǎng)問(wèn)所有的根結(jié)點(diǎn)（包括子樹(shù)的根結(jié)點(diǎn)）都在遍歷其左子樹(shù)之后、在遍歷其右子樹(shù)之前。中序遍歷的操作：若二叉樹(shù)為空，則結(jié)束反返回。否則：中序遍歷左子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)中序遍歷右子樹(shù)如，對(duì)上圖中的二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是：ACBDFEH后序遍歷：首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷其左子樹(shù)，然后遍歷其右子樹(shù)，最后訪(fǎng)問(wèn)子樹(shù)的根結(jié)點(diǎn)。即，后序遍歷是指訪(fǎng)問(wèn)所有的根結(jié)點(diǎn)（包括子樹(shù)的根結(jié)點(diǎn)）都在遍歷其左、右子樹(shù)之后。后序遍歷的操作：若二叉樹(shù)為空，則結(jié)束反返回。否則：①后序遍歷左子樹(shù)②后序遍歷右子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)如，對(duì)上圖中的二叉樹(shù)進(jìn)行后序遍歷的結(jié)果是：查找查找又稱(chēng)檢索。查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。順1序查找順序查找又稱(chēng)順序搜索或線(xiàn)性查找。順序查找一般是指在線(xiàn)性表中查找指定的元素。順序查找的基本思想：在個(gè)結(jié)點(diǎn)組成的線(xiàn)性表中，從線(xiàn)性表的一端開(kāi)始，依次將線(xiàn)性表中的元素與被查元素進(jìn)行比較，若相等則表示找到，即查找成功；若線(xiàn)性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線(xiàn)性表中沒(méi)有要找的元素，即查找失敗。在順序查找中，查找成功時(shí)最多需要比較次、最少比較次、平均比較次數(shù)約為表長(zhǎng)的一半。查找失敗時(shí)比較次。順序查找的時(shí)間復(fù)雜度為 。對(duì)于無(wú)序表（即表中的元素的排列是無(wú)序的）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表（有序的和無(wú)序的，只能用順序查找。順序查找的優(yōu)點(diǎn)：算法簡(jiǎn)單而適用范圍廣。對(duì)表中元素的排列次序無(wú)要求，既可以是按關(guān)鍵字排列的有序表，也可以是無(wú)序表；對(duì)表的存儲(chǔ)結(jié)構(gòu)也無(wú)任何要求，既適用于順序存儲(chǔ)的順序表，也適用于鏈接存儲(chǔ)的鏈表。順序查找的缺點(diǎn)：查找效率低，平均查找長(zhǎng)度較大。當(dāng)很大時(shí)不宜采用順序查找。二2分查找二分查找又稱(chēng)折半查找。它是一種查找效率較高的查找方法。該方法只適用于順序存儲(chǔ)結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列（非遞減有序排列）。二分查找不能用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表。二分查找的基本思想：參見(jiàn)“語(yǔ)言程序設(shè)計(jì)”或“程序設(shè)計(jì)”課件的相應(yīng)內(nèi)容動(dòng)畫(huà)。對(duì)于長(zhǎng)度為的有序線(xiàn)性表，查找成功時(shí)最多需要比較 次'最少比較次、平均查找長(zhǎng)度近似g當(dāng)查找失敗時(shí)，比較 或次。不管二分查找成功與否，其時(shí)間復(fù)雜度均為。二分查找的最壞性能和平均性能相當(dāng)接近。1.6排序排序就是將文件中的記錄進(jìn)行整理，使之按照關(guān)鍵字進(jìn)行遞增或遞減的順序排列起來(lái)，成為一個(gè)有序序列的過(guò)程。在本節(jié)所介紹的排序方法中，其排序的對(duì)象一般認(rèn)為是順序存儲(chǔ)的線(xiàn)性表，在程序設(shè)計(jì)語(yǔ)言中就是一維數(shù)組。這里的排序算法，都是針對(duì)升序排序。交1換排序交換排序是兩兩比較待排序記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個(gè)記錄關(guān)鍵字的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。下面介紹兩種常用的交換排序。

）冒泡排序冒泡排序的基本思想：參見(jiàn)“語(yǔ)言程序設(shè)計(jì)”或“程序設(shè)計(jì)”課件的相應(yīng)內(nèi)容動(dòng)畫(huà)。對(duì)于長(zhǎng)度為的線(xiàn)性表，在最壞情況下，冒泡排序需要經(jīng)過(guò)遍的掃描，比較次數(shù)為 1冒泡排序算法的平均時(shí)間復(fù)雜度為 ，空間復(fù)雜度為。快速排序快速排序的基本思想：參見(jiàn)下圖：從線(xiàn)性表中選取一個(gè)元素，設(shè)為，將線(xiàn)性表后面小于的元素移到前面，將線(xiàn)性表前面大于的元素移到后面，結(jié)果就把線(xiàn)性表分成了兩部分稱(chēng)為兩個(gè)子表），，插入到其分界線(xiàn)的位置處，這個(gè)過(guò)程稱(chēng)為線(xiàn)性表的分割。通過(guò)對(duì)線(xiàn)性表的一次分割，就以，為分界線(xiàn)，將線(xiàn)性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于，后面子表中的所有元素均不小于。如果對(duì)分割后的各子表再按上述原則進(jìn)行分割，并且這種分割過(guò)程可以一直做下去，隨著對(duì)各子表不斷地進(jìn)行分割，劃分出的子表會(huì)越來(lái)越多（一次只能對(duì)一個(gè)子表進(jìn)行再分割處理），直到所有子表中的元素都排好序?yàn)橹?，則此時(shí)的線(xiàn)性表就變成了有序表。對(duì)于長(zhǎng)度為的線(xiàn)性表：在最壞情況下，快速排序比較次數(shù)為 1算法的時(shí)間復(fù)雜度為，空間復(fù)雜度為 。在最好情況下，快速排序算法的時(shí)間復(fù)雜度為o空間復(fù)雜度為 ?？焖倥判蛩惴ǖ钠骄鶗r(shí)間復(fù)雜度是 0平均比較次數(shù)不大于插2入排序插入排序是每次將一個(gè)待排序的記錄按其關(guān)鍵字大小，插入到前面已排好的序列中的適當(dāng)位置，直到全部記錄插入為止。(1算直接插入排序快速排序的基本思想：請(qǐng)查看相關(guān)資料。對(duì)于長(zhǎng)度為的線(xiàn)性表：TOC\o"1-5"\h\z\o"CurrentDocument"在最壞情況下，直接插入排序比較次數(shù)為 。算法的時(shí)間復(fù)雜度為 。(2算希爾排序希爾排序的基本思想：請(qǐng)查看相關(guān)資料。對(duì)于長(zhǎng)度為的線(xiàn)性表：\o"CurrentDocument"在最壞情況下希爾排序比較次數(shù)為 1選擇3排序選擇排序的基本思想是：每一遍在 … 個(gè)待排序記錄中選取關(guān)鍵字最小的記錄作為有序序列中第個(gè)記錄，直到全部記錄排完為止。算直接選擇排序選擇排序的基本思想：參見(jiàn)“語(yǔ)言程序設(shè)計(jì)”或“程序設(shè)計(jì)”課件的相應(yīng)內(nèi)容動(dòng)畫(huà)。在最壞情況下，直接選擇排序比較次數(shù)為1(2)堆在排序在在在希在爾在排序的基本思想：請(qǐng)查看相關(guān)資料。在在最壞情況下，堆排序比較次數(shù)為 。習(xí)題：(一)選擇題(單選.下列敘述中正確的是(D))棧是“先進(jìn)先出”的線(xiàn)性表)隊(duì)列是“先進(jìn)后出”的線(xiàn)性表)循環(huán)隊(duì)列是非線(xiàn)性結(jié)構(gòu))有序線(xiàn)性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).下列關(guān)于棧的敘述中正確的是(A)棧頂兀素最先被刪除 棧頂兀素最后才能被刪除棧底元素永遠(yuǎn)不能被刪除 以上三種說(shuō)法都不對(duì)下列敘述中正確的是有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線(xiàn)性結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線(xiàn)性結(jié)構(gòu)循環(huán)鏈表是非線(xiàn)性結(jié)構(gòu)雙向鏈表是非線(xiàn)性結(jié)構(gòu)支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是棧 樹(shù) 隊(duì)列二叉樹(shù)5.某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是(C)A)10)8B)6C)4二提示：在任意二叉樹(shù)中，若度為的結(jié)點(diǎn)即葉子結(jié)點(diǎn)的個(gè)數(shù)為0度為的結(jié)點(diǎn)的個(gè)數(shù)為，則： 即 葉子結(jié)點(diǎn)數(shù)6.某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹(shù)的深度為（假設(shè)根結(jié)點(diǎn)在第一層）（D）.下列排序方法中，最壞情況下比較次數(shù)最少的是（D））冒泡排序 ）簡(jiǎn)單選擇排序）直接插入排序 ）堆排序.下列敘述中正確的是（A）對(duì)長(zhǎng)度為的有序鏈表進(jìn)行查找，最壞的情況下需要的比較次數(shù)為對(duì)長(zhǎng)度為的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為（/對(duì)長(zhǎng)度為的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為對(duì)長(zhǎng)度為的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為二填空題1.假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到4）9作為棧的存儲(chǔ)空間，棧底指針 指向棧底元素，棧頂指針指向棧頂元素，如果 數(shù)組下標(biāo)，則棧中具有 個(gè)元素。答案：20一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素、、、、、、、、、、一次入隊(duì)，然后再一次退隊(duì)，則元素退隊(duì)的順序?yàn)?。答案：、'、、、'、、、、設(shè)某循環(huán)隊(duì)列的容量為，如果頭指針 指向隊(duì)頭元素的前一個(gè)位置）尾指針（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有 個(gè)元素。答案：設(shè)二叉樹(shù)如下：對(duì)該二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為答案：一棵二叉樹(shù)的中序遍歷結(jié)果為 ，前序遍歷結(jié)果為 ，則后序遍歷結(jié)果為 。 答案：6.有序線(xiàn)性表能進(jìn)行二分查找的前提是該線(xiàn)性表必須是 存_儲(chǔ)_。__答案：順序二、軟件工程基礎(chǔ)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。軟件的分類(lèi)軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應(yīng)用軟件：是為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件。系統(tǒng)軟件：是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶(hù)提供各種服務(wù)的軟件。支撐軟件：是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶(hù)開(kāi)發(fā)軟件的工具性軟件。軟件生命周期通常將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱(chēng)為軟件生

命周期。參見(jiàn)下圖：結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖 ：是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)字典 ：是結(jié)構(gòu)化分析方法的核心。判定樹(shù)判定表結(jié)構(gòu)化設(shè)計(jì)方法常見(jiàn)的過(guò)程設(shè)計(jì)工具：圖形工具：程序流程圖，圖，圖問(wèn)題分析圖）表格工具：判定表。語(yǔ)言工具：偽碼軟件設(shè)計(jì)的基本原理抽1象）：是一種思維工具，就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。模2塊）化：是指把一個(gè)待開(kāi)發(fā)的軟件分解成若干小的簡(jiǎn)單的部分。如高級(jí)語(yǔ)言中的過(guò)程、函數(shù)、子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模塊可以按一定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。信3息）隱蔽：是指在一個(gè)模塊內(nèi)包含的信息（過(guò)程或數(shù)據(jù)），對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪(fǎng)問(wèn)的。4）模塊獨(dú)立性：是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性?xún)蓚€(gè)定性的度量標(biāo)準(zhǔn)。內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。內(nèi)聚是從功能角度來(lái)度量模塊內(nèi)的聯(lián)系。內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。作為軟件結(jié)構(gòu)設(shè)計(jì)的設(shè)計(jì)原則，要求每一個(gè)模塊的內(nèi)部都具有很強(qiáng)的內(nèi)聚性，它的各個(gè)組成部分彼此都密切相關(guān)。耦合性：耦合性是模塊間相互連接的緊密程度的度量。一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。原則上講，模塊化設(shè)計(jì)總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。但是，由于問(wè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)行前對(duì)軟件需求、設(shè)計(jì)、編碼的最后審核。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。軟件測(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)行軟件，主要通過(guò)人工進(jìn)行。動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。需要精心設(shè)計(jì)一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程。測(cè)試用例的格式為：輸入值集）,［輸（出值集）］白盒測(cè)試：也稱(chēng)結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。白盒測(cè)試把測(cè)試對(duì)象看作一個(gè)打開(kāi)的盒子，允許測(cè)試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息來(lái)設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序所有的邏輯路徑進(jìn)行測(cè)試。通過(guò)在不同點(diǎn)檢查程序的狀態(tài)來(lái)了解實(shí)際的運(yùn)行狀態(tài)是否與預(yù)期的一致。所以，白盒測(cè)試是在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。白盒測(cè)試的主要方法有邏輯覆蓋、基本路徑測(cè)試等。黑盒測(cè)試：也稱(chēng)功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿(mǎn)足需求進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說(shuō)明，檢查程序的功能是否符合它的功能說(shuō)明。所以，黑盒測(cè)試是在軟件接口處進(jìn)行，完成功能驗(yàn)證。黑盒測(cè)試只檢查程序功能是否按照需求規(guī)格說(shuō)明書(shū)的規(guī)定正常使用，程序是否能適當(dāng)?shù)亟邮蛰斎霐?shù)據(jù)而產(chǎn)生正確的輸出信息，并且保持外部信息（如數(shù)據(jù)庫(kù)或文件）的完整性。黑盒測(cè)試主要診斷功能不對(duì)或遺漏、界面錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。黑盒測(cè)試方法主要有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等，主要用于軟件確認(rèn)測(cè)試。程序調(diào)試在對(duì)程序進(jìn)行了成功的測(cè)試之后，將進(jìn)入程序調(diào)試通常稱(chēng) ，即排錯(cuò)）程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。它與軟件測(cè)試不同，軟件測(cè)試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤，并找出軟件錯(cuò)誤的具體位置。軟件測(cè)試貫穿整個(gè)軟件生命期，調(diào)試主要在開(kāi)發(fā)階段。習(xí)題：（一）選擇題（單選）軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應(yīng)用軟件的是（C）編譯程序操作系統(tǒng) 教務(wù)管理系統(tǒng) 匯編程序軟件按功能可分為：應(yīng)用軟件、系統(tǒng)軟件、和支撐軟件（或工具軟件）。下面屬于系統(tǒng)軟件的是（B）編輯軟件操作系統(tǒng)教務(wù)管理系統(tǒng)瀏覽器、軟件（程序）調(diào)試的任務(wù)是（A）診斷和改正程序中的錯(cuò)誤 盡可能多的發(fā)現(xiàn)程序中的錯(cuò)誤發(fā)現(xiàn)并改正程序中的所有錯(cuò)誤 確定程序中錯(cuò)誤的性質(zhì)

下面敘述中錯(cuò)誤的是（A）軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤并改正錯(cuò)誤對(duì)被調(diào)試的程序進(jìn)行“錯(cuò)誤定位”是程序調(diào)試的必要步驟程序調(diào)試通常也稱(chēng)為軟件測(cè)試應(yīng)嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性耦合性和內(nèi)聚性是對(duì)模塊獨(dú)立性度量的兩個(gè)標(biāo)準(zhǔn)。下列敘述中正確的是提高耦合性、降低內(nèi)聚性有利于提高模塊的獨(dú)立性降低耦合性、提高內(nèi)聚性有利于提高模塊的獨(dú)立性耦合性是指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度內(nèi)聚性是指模塊間互相連接的緊密程度數(shù)據(jù)流圖 圖是軟件概要設(shè)計(jì)的工具 軟件詳細(xì)設(shè)計(jì)的工具結(jié)構(gòu)化方法的需求分析工具 面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ哕浖芷诳煞譃槎x階段，開(kāi)發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計(jì)屬于（定義階段 開(kāi)發(fā)階段 維護(hù)階段 上述三個(gè)階段軟向件件需求規(guī)格說(shuō)8.在軟件開(kāi)發(fā)中，需求分析階段產(chǎn)生的主要文檔是（向）軟件集成測(cè)試計(jì)劃 軟件詳細(xì)設(shè)計(jì)說(shuō)明書(shū) 用戶(hù)手冊(cè)軟向件件需求規(guī)格說(shuō)明書(shū)重向復(fù)件（循環(huán)件結(jié)構(gòu)結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括（軟件順序結(jié)構(gòu) 跳轉(zhuǎn) 選擇分支結(jié)構(gòu)重向復(fù)件（循環(huán)件結(jié)構(gòu).下面描述中錯(cuò)誤的是（A件系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細(xì)設(shè)計(jì)軟件設(shè)計(jì)是將軟件需求轉(zhuǎn)換為軟件表示的過(guò)程數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)設(shè)計(jì)是軟件設(shè)計(jì)的任務(wù)之一圖是軟件詳細(xì)設(shè)計(jì)的表示工具二件填空題軟件測(cè)試可分為白盒測(cè)試和黑盒測(cè)試。基本路徑測(cè)試屬于 測(cè)_試_。_答案：白盒符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和 答案：順序結(jié)構(gòu)軟件是 、_數(shù)_據(jù)_和_文檔的集合。答案：程序?qū)浖O(shè)計(jì)的最小單位（模塊或程序單元）進(jìn)行的測(cè)試通常為 測(cè)_試_。答案：?jiǎn)卧蚰K三、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)應(yīng)用的三大領(lǐng)域：科學(xué)計(jì)算、數(shù)據(jù)處理、過(guò)程控制。數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)：就是描述事物的符號(hào)記錄。數(shù)據(jù)庫(kù)：是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有“集成''、“共享”的特點(diǎn)。數(shù)據(jù)庫(kù)管理系統(tǒng)：是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫(kù)管理系統(tǒng)是數(shù)據(jù)庫(kù)系統(tǒng)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)一般提供相應(yīng)的數(shù)據(jù)語(yǔ)言來(lái)完成相應(yīng)的功數(shù)據(jù)定義語(yǔ)言（數(shù)據(jù)操縱語(yǔ)言（數(shù)據(jù)控制語(yǔ)言（:負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。:負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢(xún)及增、刪、改等操作。:負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等功能，包括系統(tǒng)初啟程序、文件讀寫(xiě)與維護(hù)程序、存取路徑管理程序、緩沖區(qū)管理程序、安全性控制程序、完整性檢查程序、并發(fā)控制程序、事務(wù)管理程序、運(yùn)行日志管理程序、數(shù)據(jù)庫(kù)恢復(fù)程序等。數(shù)據(jù)庫(kù)管理員 ：由于數(shù)據(jù)庫(kù)的共享性，因此對(duì)數(shù)據(jù)庫(kù)的規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等需要有專(zhuān)人管理，稱(chēng)他們?yōu)閿?shù)據(jù)庫(kù)管理員。數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)數(shù)據(jù)、數(shù)據(jù)庫(kù)管理系統(tǒng)軟件、數(shù)據(jù)庫(kù)管理員（人員）、系統(tǒng)硬件平臺(tái)（硬件）、系統(tǒng)軟件平臺(tái)（軟件）這五部分組成，稱(chēng)為數(shù)據(jù)庫(kù)系統(tǒng)。數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng) ：是數(shù)據(jù)庫(kù)系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面這三者所組成。模型該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化成實(shí)體、聯(lián)系、屬性等幾個(gè)基本概念，以及它們間的兩種基本聯(lián)接關(guān)系，并且可以用一種圖非常直觀(guān)地表示出來(lái)。下面是模型的基本概念。目前較為有名的概念模型有模型、擴(kuò)充的 模型、面向?qū)ο竽Ｐ图爸^詞模型等。實(shí)體：現(xiàn)實(shí)世界中的事物可以抽象成為實(shí)體。實(shí)體是概念世界中的基本單位，它們是客觀(guān)存在的且又相互區(qū)別的事物。凡是有共性的實(shí)體可組成一個(gè)集合稱(chēng)實(shí)體集。如學(xué)生和學(xué)生，他們都是實(shí)體，他們又都是學(xué)生，從而組成一個(gè)學(xué)生實(shí)體集。屬性：現(xiàn)實(shí)世界中的事物均有一些特性，這些特性可以用屬性來(lái)表示。屬性刻畫(huà)了實(shí)體的特征。一個(gè)實(shí)體往往可以有若干個(gè)屬性。聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)聯(lián)稱(chēng)為聯(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)記為 或 其中也可以小寫(xiě)多對(duì)多的聯(lián)系，簡(jiǎn)記為 或模型由上面三個(gè)基本概念組成。由實(shí)體、聯(lián)系、屬性三者結(jié)合起來(lái)才能表示現(xiàn)實(shí)世界。圖：模型可以用一種非常直觀(guān)的圖的形式表示，這種圖稱(chēng)為圖。在圖中我們分別用下面不同的幾何圖形表示模型中的三個(gè)概念與兩個(gè)聯(lián)接關(guān)系。實(shí)體集表示法用矩形表示實(shí)體集，在矩形內(nèi)寫(xiě)上該實(shí)體集的名字。如實(shí)體集學(xué)生d課程 可表示為：實(shí)體集表示法屬2性）表示法用橢圓形表示屬性，在橢圓形內(nèi)寫(xiě)上該屬性的名稱(chēng)。如學(xué)生有屬性：學(xué)號(hào)、姓名及年齡，可表示為：聯(lián)系表示法用菱形表示聯(lián)系，在菱形內(nèi)寫(xiě)上聯(lián)系名。如學(xué)生與課程間的聯(lián)系，可表示為：上面是三個(gè)基本概念分別用三種幾何圖形表示。下面是它們之間的聯(lián)接關(guān)系的圖形表示。實(shí)4體）集或聯(lián)系與屬性間的聯(lián)接關(guān)系屬性依附于實(shí)體集，屬性也依附于聯(lián)系，因此它們之間分別有聯(lián)接關(guān)系。參見(jiàn)下圖：

其中：課程號(hào)、課程名、預(yù)修課號(hào)實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系如下圖表示實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系：還可以在線(xiàn)段邊上注明其對(duì)應(yīng)的函數(shù)關(guān)系，如、、 等。下圖表示兩個(gè)實(shí)體集間聯(lián)系叫二元聯(lián)系，多個(gè)實(shí)體集間聯(lián)系叫多元聯(lián)系。下圖聯(lián)系是一種三元聯(lián)系工廠(chǎng)、產(chǎn)品與用戶(hù)間的聯(lián)系：

下面是實(shí)體間多種聯(lián)系圖：圖：公司職工 間上、下級(jí)管理 的聯(lián)系。即一個(gè)實(shí)體集內(nèi)部可以有多種聯(lián)系。圖：教師與學(xué)生之間可以有教學(xué)聯(lián)系也可以有管理聯(lián)系。即實(shí)體集間可以有多種聯(lián)系。關(guān)系模型關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱(chēng)表。二維表由表框架 及表的元組 組成。表框架由個(gè)命名的屬性組成，稱(chēng)為屬性元數(shù) i每個(gè)屬性有一個(gè)取值范圍，稱(chēng)為值域 。表框架對(duì)應(yīng)了關(guān)系的模式，即類(lèi)型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱(chēng)為元組，實(shí)際上，一個(gè)元組是由個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值。一個(gè)表框架可以存放個(gè)元組，稱(chēng)為表的基數(shù) 。一個(gè)元表框架及框架內(nèi)個(gè)元組構(gòu)成了一個(gè)完整的二維表。關(guān)系框架與關(guān)系元組構(gòu)成了一個(gè)關(guān)系。一個(gè)語(yǔ)義相關(guān)的關(guān)系集合構(gòu)成一個(gè)關(guān)系數(shù)據(jù)庫(kù)。關(guān)系的框架稱(chēng)為關(guān)系模式，而語(yǔ)義相關(guān)的關(guān)系模式集合構(gòu)成了關(guān)系數(shù)據(jù)庫(kù)模式。滿(mǎn)足下面?zhèn)€性質(zhì)的二維表稱(chēng)為關(guān)系 ：元1組）個(gè)數(shù)有限性：二維表中元組個(gè)數(shù)是有限的。2） 元組的惟一性：二維表中元組均不相同。3） 元組的次序無(wú)關(guān)性：二維表中元組的次序可以任意交換。4） 元組分量的原子性：二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)。5） 屬性名惟一性：二維表中屬性名各不相同。6） 屬性的次序無(wú)