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

計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱

數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)不單獨(dú)考試，與其他二級(jí)科目組合在一起，作為二級(jí)科目考核內(nèi)容的一部分。考試方式:上機(jī)考試題型：選擇題（

注：10道選擇題，占總分值的10%）計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱數(shù)據(jù)結(jié)構(gòu)與算法全國(guó)計(jì)算機(jī)等1第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)

考試大綱

1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序）。第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱2算法的定義對(duì)解題方案準(zhǔn)確而完整的描述稱(chēng)為算法。算法是程序設(shè)計(jì)的核心

算法的基本概念

算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程(計(jì)算的方法)。在這個(gè)過(guò)程中，無(wú)論是形成解題思路(推理實(shí)現(xiàn)的算法)還是編寫(xiě)程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。例：n個(gè)數(shù)從大到小進(jìn)行排序。

有多種排序方法，常用的有冒泡排序、選擇排序等。算法的定義算法是程序設(shè)計(jì)的核心算法的基本概念算法3

算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性確定性輸入輸出可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成算法的基本特征有窮性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)4

算法的兩個(gè)基本要素：基本運(yùn)算和操作算術(shù)運(yùn)算關(guān)系運(yùn)算邏輯運(yùn)算數(shù)據(jù)傳輸控制結(jié)構(gòu)

順序選擇循環(huán)

一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；

二是算法的控制結(jié)構(gòu)。算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法

算法的兩個(gè)基本要素：基本運(yùn)算和操作控制結(jié)構(gòu)5

算法的復(fù)雜度

評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲(chǔ)需求：時(shí)間復(fù)雜度：執(zhí)行這個(gè)算法所需要的計(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è)部分算法的復(fù)雜度6

計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問(wèn)題。數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

一般來(lái)說(shuō)，人們不會(huì)同時(shí)處理特征完全不同且互相之間沒(méi)有任何關(guān)系的各類(lèi)數(shù)據(jù)元素，對(duì)于具有不同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(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)系的一門(mén)學(xué)科，它包括三個(gè)方面。

（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)算。計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元7

1.數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

1.數(shù)據(jù)的邏輯結(jié)構(gòu)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖8常見(jiàn)的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)。①線性結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；②樹(shù)形結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；③圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。其中，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱(chēng)為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來(lái)表示。常見(jiàn)的邏輯結(jié)構(gòu)有：①線性結(jié)構(gòu)9

數(shù)據(jù)的存儲(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)系不一定是相同的，而且一般也不可能相同。存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。常見(jià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)稱(chēng)為邏輯結(jié)構(gòu)。一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲(chǔ)結(jié)構(gòu)。常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)：1.線性表

2.棧和隊(duì)列

3.樹(shù)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）只抽象地反映數(shù)10線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹(shù)和圖都屬于非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)11１．線性表

線性表是由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個(gè)有限序列。簡(jiǎn)單的線性表春夏秋冬復(fù)雜的線性表記錄102011001張三男…記錄202011003李四女…記錄3記錄4線性表的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)１．線性表線性表是由n（n≥0）12線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱(chēng)作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元13順序表的插入和刪除運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為順序表。順序表的插入運(yùn)算順序表的刪除運(yùn)算

在線性表順序存儲(chǔ)情況下，要插入或刪除一個(gè)元素，都會(huì)由于數(shù)據(jù)元素的移動(dòng)而消耗大量的處理時(shí)間，所以這種存儲(chǔ)方式對(duì)于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動(dòng)的線性表是合適的。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的數(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)系：順序表的插入和刪除運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為順序表。順序14單鏈表的插入運(yùn)算

單鏈表的刪除運(yùn)算線性鏈表的插入和刪除運(yùn)算采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間開(kāi)銷(xiāo)較大，但是進(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單鏈表的插入運(yùn)算線性鏈表的插入和刪除運(yùn)算15雙向鏈表的存儲(chǔ)結(jié)構(gòu)HEAD31510a2a3a4a1

雙向鏈表可以克服單鏈表的單向性的缺點(diǎn)。

在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。線性表的存儲(chǔ)結(jié)構(gòu)有兩種

順序存儲(chǔ)結(jié)構(gòu)注意：數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的。一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且不同的存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表:{a1，a2，a3，a4，a5}雙向鏈表的存儲(chǔ)結(jié)構(gòu)HEAD31510a216棧和隊(duì)列棧和隊(duì)列都是特殊的線性表。

棧（Stack）及其基本運(yùn)算

隊(duì)列（Queue）及其基本運(yùn)算

循環(huán)隊(duì)列及其基本運(yùn)算棧和隊(duì)列棧和隊(duì)列都是特殊的線性表。17棧順序棧的進(jìn)棧和出棧運(yùn)算：棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種先進(jìn)后出（后進(jìn)先出）的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素棧順序棧的進(jìn)棧和出棧運(yùn)算：棧是限定僅在表的一端進(jìn)行插入和18隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱(chēng)為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱(chēng)為退隊(duì)。棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有三種：入隊(duì)＼出隊(duì)＼讀隊(duì)首元素隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(19

循環(huán)隊(duì)列

將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，當(dāng)R指向存儲(chǔ)空間的末端后，就把它重新置于始端。

循環(huán)隊(duì)列的運(yùn)算隊(duì)列中進(jìn)行插入的一端稱(chēng)做隊(duì)尾(rear),進(jìn)行刪除的一端稱(chēng)做隊(duì)首(front)。

線性表線性結(jié)構(gòu)棧

是特殊的線性表隊(duì)列也是一種操作受限的特殊的線性表樹(shù)（樹(shù)型結(jié)構(gòu)）是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)循環(huán)隊(duì)列隊(duì)列中進(jìn)行插入的一端稱(chēng)做隊(duì)20一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(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)

一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)其為非線性結(jié)構(gòu)。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線21樹(shù)型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。

樹(shù)的概念

二叉樹(shù)的概念

二叉樹(shù)的存儲(chǔ)

二叉樹(shù)的遍歷樹(shù)與二叉樹(shù)樹(shù)型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹(shù)與二叉樹(shù)22樹(shù)及其基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹(shù)中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹(shù)是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹(shù)中：

(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。

(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。集合為空的樹(shù)簡(jiǎn)稱(chēng)為空樹(shù)；樹(shù)中的元素稱(chēng)為結(jié)點(diǎn)。樹(shù)及其基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹(shù)中，所有的數(shù)據(jù)元23樹(shù)型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM1)度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。2)葉子節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。3)層次：結(jié)點(diǎn)的層次從根開(kāi)始定義，根為第一層，根的孩子為第二層。4)深度：樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度或高度。5)結(jié)點(diǎn)的層次樹(shù)中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹(shù)的根為第2層，以此類(lèi)推；6)樹(shù)的深度

樹(shù)中所有結(jié)點(diǎn)層次的最大值；①②③④樹(shù)型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM1)度：結(jié)點(diǎn)擁有的24二叉樹(shù)二叉樹(shù)是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱(chēng)為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹(shù)，分別稱(chēng)為根的左子樹(shù)和右子樹(shù)。二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，并且二叉樹(shù)的子樹(shù)有左右之分，其順序不能任意顛倒。定義：二叉樹(shù)是一種有序的樹(shù)形結(jié)構(gòu)。它與一般樹(shù)形結(jié)構(gòu)的區(qū)別是：

1)每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；

2)子樹(shù)有左右之分，次序不能任意顛倒。二叉樹(shù)二叉樹(shù)是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或25二叉樹(shù)的基本性質(zhì)【性質(zhì)1】

在二叉樹(shù)的第K層上最多有2k-1個(gè)結(jié)點(diǎn)（k≥1）【性質(zhì)2】深度為h的二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn)（h≥1）【性質(zhì)3】二叉樹(shù)上葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1ABCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)二叉樹(shù)的基本性質(zhì)【性質(zhì)1】在二叉樹(shù)的第K26滿二叉樹(shù)

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹(shù)

ADCBEF滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)：如果一個(gè)深度為h的二叉樹(shù)擁有2h-1個(gè)結(jié)點(diǎn)，則將它稱(chēng)為滿二叉樹(shù)。完全二叉樹(shù)：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若將它與一棵同深度的滿二叉樹(shù)中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹(shù)中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹(shù)中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱(chēng)這棵二叉樹(shù)為完全二叉樹(shù)。滿二叉樹(shù)最大層的結(jié)點(diǎn)均向左靠齊完全二叉樹(shù)ADCBEF滿27二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。LlinkinfoRlink二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)ABDCFGEA∧G∧∧E∧∧F∧B∧C∧

Dt二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采28二叉樹(shù)的遍歷二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。從二叉樹(shù)的結(jié)構(gòu)定義得知，二叉樹(shù)是由"根結(jié)點(diǎn)"、"左子樹(shù)"和"右子樹(shù)"三部分構(gòu)成，則遍歷二叉樹(shù)的操作可分解為"訪問(wèn)根結(jié)點(diǎn)"、"遍歷左子樹(shù)"和"遍歷右子樹(shù)"三個(gè)子操作，并且由二叉樹(shù)的遞歸定義可知，遍歷左子樹(shù)和遍歷右子樹(shù)可如同遍歷二叉樹(shù)一樣"遞歸"進(jìn)行。

前序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹(shù)；

(3)先序遍歷右子樹(shù)。若二叉樹(shù)為空，則空操作；

否則

(1)中序遍歷左子樹(shù)；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹(shù)。若二叉樹(shù)為空，則空操作；

否則

(1)后序遍歷左子樹(shù)；

(2)后序遍歷右子樹(shù)；

(3)訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)的遍歷二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。從二29查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。查找指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱(chēng)關(guān)鍵字。若找到了滿足條件的結(jié)點(diǎn)，稱(chēng)查找成功；否則稱(chēng)查找失敗。衡量一個(gè)查找算法的主要標(biāo)準(zhǔn)是查找過(guò)程中對(duì)關(guān)鍵字進(jìn)行的平均比較次數(shù)。通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：1）順序查找：線性表中最簡(jiǎn)單的查找方法。最壞情況下需比較n次2）二分查找（折半查找）：是一種效率較高的查找方法，但是只適合順序存儲(chǔ)的有序表。

最壞情況下需比較log2n查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。30排序技術(shù)

排序指將一個(gè)無(wú)序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。排序方法中其排序?qū)ο笠话闶琼樞虼鎯?chǔ)的線性表。根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：插入類(lèi)排序法

簡(jiǎn)單插入排序

希爾排序選擇類(lèi)排序法簡(jiǎn)單選擇排序堆排序交換類(lèi)排序法

冒泡排序

快速排序排序技術(shù)排序指將一個(gè)無(wú)序序列整理成按關(guān)鍵字值遞增或遞減排列31

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱32結(jié)構(gòu)化程序設(shè)計(jì)

結(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í)行某一相同程序段。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：33

面向?qū)ο蟮某绦蛟O(shè)計(jì)

1、對(duì)象：是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。屬性即?duì)象所包含的信息操作描述了對(duì)象執(zhí)行的功能，操作也稱(chēng)為方法或服務(wù)。2、類(lèi)：是指具有共同屬性、共同方法的對(duì)象的集合。所以類(lèi)是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。3、消息：是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。

消息的組成包括（1）接收消息的對(duì)象的名稱(chēng)；（2）消息標(biāo)識(shí)符，也稱(chēng)消息名；（3）零個(gè)或多個(gè)參數(shù)。4、繼承：是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。單繼承指一個(gè)類(lèi)只允許有一個(gè)父類(lèi)多重繼承指一個(gè)類(lèi)允許有多個(gè)父類(lèi)。5、多態(tài)性：是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。面向?qū)ο蟮某绦蛟O(shè)計(jì)1、對(duì)象：是面向?qū)ο蠓椒ㄖ凶罨?4第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。

第三章軟件工程基礎(chǔ)考試大綱35

軟件工程概念軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。

軟件工程包括3個(gè)要素：方法、工具和過(guò)程。軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。

軟件生命周期三個(gè)階段:軟件定義、軟件開(kāi)發(fā)、運(yùn)行維護(hù)，主要活動(dòng)階段是：

（1）可行性研究與計(jì)劃制定；

（2）需求分析；

（3）軟件設(shè)計(jì)；

（4）軟件實(shí)現(xiàn)；

（5）軟件測(cè)試；

（6）運(yùn)行和維護(hù)。軟件工程概念軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)36

結(jié)構(gòu)化分析方法和設(shè)計(jì)方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具:1)數(shù)據(jù)流圖；2)數(shù)據(jù)字典；3)判定樹(shù)；

判定表。結(jié)構(gòu)化分析方法：

軟件設(shè)計(jì)包括：總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)

在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。常見(jiàn)的過(guò)程設(shè)計(jì)工具有：圖形工具（程序流程圖,N-S,PAD）表格工具（判定表）語(yǔ)言工具（PDL偽碼）

結(jié)構(gòu)化分析方法和設(shè)計(jì)方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)37程序流程圖N-S圖PAD圖程序流程圖N-S圖PAD圖38軟件測(cè)試軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。

軟件測(cè)試方法：1)靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際

運(yùn)行軟件，主要通過(guò)人工進(jìn)行。

2)動(dòng)態(tài)測(cè)試：是基本計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒

測(cè)試方法白盒測(cè)試方法有：邏輯覆蓋；基本路徑測(cè)試黑盒測(cè)試方法有：等價(jià)類(lèi)劃分法；邊界值分析法；錯(cuò)誤推測(cè)法軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試。軟件測(cè)試軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。39程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開(kāi)發(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）原因排除法。40程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開(kāi)第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。

4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱41數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)：實(shí)際上就是描述事物的符號(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ù)管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)系統(tǒng)：由數(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ù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。42數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫(kù)的應(yīng)用程序的集合。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫(kù)等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義和檢查數(shù)據(jù)庫(kù)的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS提供了相應(yīng)的語(yǔ)言：數(shù)據(jù)定義語(yǔ)言(DDL)數(shù)據(jù)操縱語(yǔ)言(DML)數(shù)據(jù)控制語(yǔ)言(DCL)數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和43數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員44。(1)人工管理階段：人工管理階段：存儲(chǔ)設(shè)備比較落后第一代計(jì)算機(jī)：輸入

處理

輸出(2)文件系統(tǒng)階段：按名存取（出現(xiàn)數(shù)據(jù)與程序的概念）

實(shí)現(xiàn)了以文件為單位的數(shù)據(jù)共享(3)

數(shù)據(jù)庫(kù)系統(tǒng)管理階段:實(shí)現(xiàn)了以記錄和數(shù)據(jù)項(xiàng)為單位的文件共享

特點(diǎn)：1）提高數(shù)據(jù)的共享性2）減少數(shù)據(jù)的冗余（但并沒(méi)有消除）3）增加了數(shù)據(jù)余程序的獨(dú)立性數(shù)據(jù)庫(kù)管理系統(tǒng)的發(fā)展。數(shù)據(jù)庫(kù)管理系統(tǒng)的發(fā)展45數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶的數(shù)據(jù)視圖外模式：又稱(chēng)為用戶模式，是每個(gè)用戶的局部數(shù)據(jù)描述，用戶的數(shù)據(jù)視圖內(nèi)模式：又稱(chēng)為物理模式，是數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)和物理存取方法的描述二級(jí)映射概念模式到內(nèi)模式的映射外模式到概念模式的映射數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式46數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示和操作提供一個(gè)抽象的框架。數(shù)據(jù)模型描述的內(nèi)容包括三部分：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類(lèi)型：概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征47實(shí)體聯(lián)系(ER)模型E-R模型的基本概念

（1）實(shí)體：現(xiàn)實(shí)世界中的事物；

（2）屬性：事物的特性；

（3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。聯(lián)系：聯(lián)系反映概念世界中的實(shí)體集之間存在的一定關(guān)系。一對(duì)一聯(lián)系(1:1)一對(duì)多聯(lián)系(1:M)多對(duì)多聯(lián)系(M:N)實(shí)體聯(lián)系(ER)模型E-R模型的基本概念

（1）實(shí)體：現(xiàn)實(shí)世48ER模型圖示法ER圖是實(shí)體聯(lián)系模型的直觀圖形表示。E-R模型之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的基本單位，屬性有屬性域，每個(gè)實(shí)體可取屬性域內(nèi)的值。一個(gè)實(shí)體的所有屬性值叫元組。

E-R模型的圖示法：（1）實(shí)體集表示法：用長(zhǎng)方形（2）屬性表法：用橢圓形（3）聯(lián)系表示法：用菱形ER模型圖示法ER圖是實(shí)體聯(lián)系模型的直觀圖形表示。49層次模型（采用樹(shù)型結(jié)構(gòu)）圖1-4層次模型示例層次模型（采用樹(shù)型結(jié)構(gòu)）圖1-4層次模型示例50

網(wǎng)絡(luò)模型（采用無(wú)向圖型結(jié)構(gòu)）

網(wǎng)絡(luò)模型（采用無(wú)向圖型結(jié)構(gòu)）51關(guān)系模型（采用二維表結(jié)構(gòu)）關(guān)系模型（采用二維表結(jié)構(gòu)）52關(guān)系數(shù)據(jù)模型關(guān)系模型用二維表結(jié)構(gòu)來(lái)表示實(shí)體之間聯(lián)系的模型，簡(jiǎn)稱(chēng)表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。關(guān)系二維表（等價(jià)）

關(guān)系的組成：1）元組：二維表的每一行-----記錄（除過(guò)第一行）

2）屬性：二維表的每一列-----字段學(xué)號(hào)姓名性別出生日期入學(xué)成績(jī)四級(jí)通過(guò)否計(jì)算機(jī)等級(jí)考試備注尚杰男86-11-20520.5T一級(jí)余習(xí)芳女86-12-26513.5F二級(jí)張軼一男86-01-09612.0T陶紅莉女85-02-14535.0F二級(jí)關(guān)系數(shù)據(jù)模型關(guān)系模型用二維表結(jié)構(gòu)來(lái)表示實(shí)體之間聯(lián)系的模型，簡(jiǎn)53一個(gè)二維表要滿足下面7個(gè)性質(zhì)就可稱(chēng)為一個(gè)關(guān)系。①二維表中元組個(gè)數(shù)是有限的②二維表中元組均不相同③二維表中元組的次序可任意交換④二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)⑤二維表中屬性名各不相同⑥二維表中屬性與次序無(wú)關(guān)，可任意交換⑦二維表屬性中的分量具有與該屬性相同的值域一個(gè)二維表要滿足下面7個(gè)性質(zhì)就可稱(chēng)為一個(gè)關(guān)系。54關(guān)系模型的基本運(yùn)算：查詢選擇、投影、連接、并、交、差、笛卡爾積運(yùn)算數(shù)據(jù)更新插入、刪除、更新關(guān)系操作的特點(diǎn)集合操作方式，即操作的對(duì)象和結(jié)果都是集合。關(guān)系操作集合的并運(yùn)算關(guān)系模型的基本運(yùn)算：關(guān)系操作集合的并運(yùn)算55（1）投影對(duì)于關(guān)系R內(nèi)的域指定稱(chēng)為投影運(yùn)算。S關(guān)系就是對(duì)R關(guān)系指定A和B兩個(gè)域的結(jié)果ABCa32b01c21ABa3b0c2RS關(guān)系操作：選擇（2）選擇選擇運(yùn)算的關(guān)系是由關(guān)系R中那些滿足邏輯條件的元組所組成。S關(guān)系就是R關(guān)系中滿足A=‘a(chǎn)’的結(jié)果ABCa32b01a69c21RSABCa32a69有了投影和選擇運(yùn)算，我們對(duì)一個(gè)關(guān)系內(nèi)的任意行、列的數(shù)據(jù)都可以方便的找到。（1）投影ABCa32b01c21ABa3b0c2RS關(guān)系操56笛卡爾積：是對(duì)兩個(gè)關(guān)系的合并操作。

由兩個(gè)關(guān)系R、S得到TAmnBC13ABCm13n13RST笛卡爾積和自然連接運(yùn)算自然連接運(yùn)算：在實(shí)際應(yīng)用中一般相互連接的關(guān)系往往須滿足一些條件，所得到的結(jié)果也較為簡(jiǎn)單。自然連接滿足兩個(gè)關(guān)系：1）中有公共域；2）通過(guò)公共域的相等值進(jìn)行連接。笛卡爾積：是對(duì)兩個(gè)關(guān)系的合并操作。AmnBC13ABCm1357

數(shù)據(jù)庫(kù)設(shè)計(jì)與管理

數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法：

（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；

（2）面向過(guò)程：以處理需求為主，兼顧信息需求。

數(shù)據(jù)庫(kù)的生命周期：需求分析階段結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒〝?shù)據(jù)字典是各類(lèi)數(shù)據(jù)描述的集合，包括5個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲(chǔ)、處理過(guò)程。概念設(shè)計(jì)階段分析數(shù)據(jù)內(nèi)在語(yǔ)義關(guān)系。E-R模型邏輯設(shè)計(jì)階段物理設(shè)計(jì)階段編碼階段測(cè)試階段運(yùn)行階段進(jìn)一步修改階段數(shù)據(jù)庫(kù)設(shè)計(jì)與管理數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法：

（1）58數(shù)據(jù)庫(kù)設(shè)計(jì)與管理需求分析概念設(shè)計(jì)邏輯設(shè)計(jì)物理設(shè)計(jì)編碼測(cè)試運(yùn)行進(jìn)一步修改分析客戶的業(yè)務(wù)和數(shù)據(jù)處理需求;設(shè)計(jì)數(shù)據(jù)庫(kù)的E-R模型圖，確認(rèn)需求信息的正確和完整;將E-R圖轉(zhuǎn)換為多張表，進(jìn)行邏輯設(shè)計(jì),并應(yīng)用數(shù)據(jù)庫(kù)設(shè)計(jì)的三大范式進(jìn)行審核;

數(shù)據(jù)庫(kù)內(nèi)模式包括存儲(chǔ)結(jié)構(gòu)和存取方法。

重點(diǎn)記8個(gè)階段選擇具體數(shù)據(jù)庫(kù)進(jìn)行物理實(shí)現(xiàn)，并編寫(xiě)代碼實(shí)現(xiàn)前端應(yīng)用;

數(shù)據(jù)庫(kù)設(shè)計(jì)與管理需求分析概念設(shè)計(jì)邏輯設(shè)計(jì)物理設(shè)計(jì)編碼測(cè)試運(yùn)行59數(shù)據(jù)庫(kù)管理的內(nèi)容（1）數(shù)據(jù)庫(kù)的建立；（2）數(shù)據(jù)庫(kù)的調(diào)整；（3）數(shù)據(jù)庫(kù)的重組；（4）數(shù)據(jù)庫(kù)安全性與完整性控制；（5）數(shù)據(jù)庫(kù)的故障恢復(fù)；（6）數(shù)據(jù)庫(kù)監(jiān)控。數(shù)據(jù)庫(kù)管理的內(nèi)容（1）數(shù)據(jù)庫(kù)的建立；60計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱

數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)不單獨(dú)考試，與其他二級(jí)科目組合在一起，作為二級(jí)科目考核內(nèi)容的一部分?？荚嚪绞?上機(jī)考試題型：選擇題（

注：10道選擇題，占總分值的10%）計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱數(shù)據(jù)結(jié)構(gòu)與算法全國(guó)計(jì)算機(jī)等61第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)

考試大綱

1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序）。第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱62算法的定義對(duì)解題方案準(zhǔn)確而完整的描述稱(chēng)為算法。算法是程序設(shè)計(jì)的核心

算法的基本概念

算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程(計(jì)算的方法)。在這個(gè)過(guò)程中，無(wú)論是形成解題思路(推理實(shí)現(xiàn)的算法)還是編寫(xiě)程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。例：n個(gè)數(shù)從大到小進(jìn)行排序。

有多種排序方法，常用的有冒泡排序、選擇排序等。算法的定義算法是程序設(shè)計(jì)的核心算法的基本概念算法63

算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性確定性輸入輸出可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成算法的基本特征有窮性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)64

算法的兩個(gè)基本要素：基本運(yùn)算和操作算術(shù)運(yùn)算關(guān)系運(yùn)算邏輯運(yùn)算數(shù)據(jù)傳輸控制結(jié)構(gòu)

順序選擇循環(huán)

一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；

二是算法的控制結(jié)構(gòu)。算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法

算法的兩個(gè)基本要素：基本運(yùn)算和操作控制結(jié)構(gòu)65

算法的復(fù)雜度

評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲(chǔ)需求：時(shí)間復(fù)雜度：執(zhí)行這個(gè)算法所需要的計(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è)部分算法的復(fù)雜度66

計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問(wèn)題。數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

一般來(lái)說(shuō)，人們不會(huì)同時(shí)處理特征完全不同且互相之間沒(méi)有任何關(guān)系的各類(lèi)數(shù)據(jù)元素，對(duì)于具有不同特征的數(shù)據(jù)元素總是分別進(jìn)行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(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)系的一門(mén)學(xué)科，它包括三個(gè)方面。

（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)算。計(jì)算機(jī)在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元67

1.數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

1.數(shù)據(jù)的邏輯結(jié)構(gòu)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖68常見(jiàn)的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)。①線性結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；②樹(shù)形結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；③圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。其中，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱(chēng)為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來(lái)表示。常見(jiàn)的邏輯結(jié)構(gòu)有：①線性結(jié)構(gòu)69

數(shù)據(jù)的存儲(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)系不一定是相同的，而且一般也不可能相同。存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。常見(jià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)稱(chēng)為邏輯結(jié)構(gòu)。一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲(chǔ)結(jié)構(gòu)。常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)：1.線性表

2.棧和隊(duì)列

3.樹(shù)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）只抽象地反映數(shù)70線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹(shù)和圖都屬于非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)71１．線性表

線性表是由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個(gè)有限序列。簡(jiǎn)單的線性表春夏秋冬復(fù)雜的線性表記錄102011001張三男…記錄202011003李四女…記錄3記錄4線性表的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)１．線性表線性表是由n（n≥0）72線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱(chēng)作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元73順序表的插入和刪除運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為順序表。順序表的插入運(yùn)算順序表的刪除運(yùn)算

在線性表順序存儲(chǔ)情況下，要插入或刪除一個(gè)元素，都會(huì)由于數(shù)據(jù)元素的移動(dòng)而消耗大量的處理時(shí)間，所以這種存儲(chǔ)方式對(duì)于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動(dòng)的線性表是合適的。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的數(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)系：順序表的插入和刪除運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為順序表。順序74單鏈表的插入運(yùn)算

單鏈表的刪除運(yùn)算線性鏈表的插入和刪除運(yùn)算采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間開(kāi)銷(xiāo)較大，但是進(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單鏈表的插入運(yùn)算線性鏈表的插入和刪除運(yùn)算75雙向鏈表的存儲(chǔ)結(jié)構(gòu)HEAD31510a2a3a4a1

雙向鏈表可以克服單鏈表的單向性的缺點(diǎn)。

在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。線性表的存儲(chǔ)結(jié)構(gòu)有兩種

順序存儲(chǔ)結(jié)構(gòu)注意：數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的。一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且不同的存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表:{a1，a2，a3，a4，a5}雙向鏈表的存儲(chǔ)結(jié)構(gòu)HEAD31510a276棧和隊(duì)列棧和隊(duì)列都是特殊的線性表。

棧（Stack）及其基本運(yùn)算

隊(duì)列（Queue）及其基本運(yùn)算

循環(huán)隊(duì)列及其基本運(yùn)算棧和隊(duì)列棧和隊(duì)列都是特殊的線性表。77棧順序棧的進(jìn)棧和出棧運(yùn)算：棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種先進(jìn)后出（后進(jìn)先出）的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素棧順序棧的進(jìn)棧和出棧運(yùn)算：棧是限定僅在表的一端進(jìn)行插入和78隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱(chēng)為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱(chēng)為退隊(duì)。棧的物理存儲(chǔ)結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有三種：入隊(duì)＼出隊(duì)＼讀隊(duì)首元素隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(79

循環(huán)隊(duì)列

將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，當(dāng)R指向存儲(chǔ)空間的末端后，就把它重新置于始端。

循環(huán)隊(duì)列的運(yùn)算隊(duì)列中進(jìn)行插入的一端稱(chēng)做隊(duì)尾(rear),進(jìn)行刪除的一端稱(chēng)做隊(duì)首(front)。

線性表線性結(jié)構(gòu)棧

是特殊的線性表隊(duì)列也是一種操作受限的特殊的線性表樹(shù)（樹(shù)型結(jié)構(gòu)）是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)循環(huán)隊(duì)列隊(duì)列中進(jìn)行插入的一端稱(chēng)做隊(duì)80一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(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)

一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)其為非線性結(jié)構(gòu)。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個(gè)條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線81樹(shù)型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。

樹(shù)的概念

二叉樹(shù)的概念

二叉樹(shù)的存儲(chǔ)

二叉樹(shù)的遍歷樹(shù)與二叉樹(shù)樹(shù)型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹(shù)與二叉樹(shù)82樹(shù)及其基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹(shù)中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹(shù)是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹(shù)中：

(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。

(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。集合為空的樹(shù)簡(jiǎn)稱(chēng)為空樹(shù)；樹(shù)中的元素稱(chēng)為結(jié)點(diǎn)。樹(shù)及其基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹(shù)中，所有的數(shù)據(jù)元83樹(shù)型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM1)度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。2)葉子節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。3)層次：結(jié)點(diǎn)的層次從根開(kāi)始定義，根為第一層，根的孩子為第二層。4)深度：樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度或高度。5)結(jié)點(diǎn)的層次樹(shù)中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹(shù)的根為第2層，以此類(lèi)推；6)樹(shù)的深度

樹(shù)中所有結(jié)點(diǎn)層次的最大值；①②③④樹(shù)型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM1)度：結(jié)點(diǎn)擁有的84二叉樹(shù)二叉樹(shù)是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱(chēng)為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹(shù)，分別稱(chēng)為根的左子樹(shù)和右子樹(shù)。二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，并且二叉樹(shù)的子樹(shù)有左右之分，其順序不能任意顛倒。定義：二叉樹(shù)是一種有序的樹(shù)形結(jié)構(gòu)。它與一般樹(shù)形結(jié)構(gòu)的區(qū)別是：

1)每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；

2)子樹(shù)有左右之分，次序不能任意顛倒。二叉樹(shù)二叉樹(shù)是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或85二叉樹(shù)的基本性質(zhì)【性質(zhì)1】

在二叉樹(shù)的第K層上最多有2k-1個(gè)結(jié)點(diǎn)（k≥1）【性質(zhì)2】深度為h的二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn)（h≥1）【性質(zhì)3】二叉樹(shù)上葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1ABCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)二叉樹(shù)的基本性質(zhì)【性質(zhì)1】在二叉樹(shù)的第K86滿二叉樹(shù)

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹(shù)

ADCBEF滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)：如果一個(gè)深度為h的二叉樹(shù)擁有2h-1個(gè)結(jié)點(diǎn)，則將它稱(chēng)為滿二叉樹(shù)。完全二叉樹(shù)：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若將它與一棵同深度的滿二叉樹(shù)中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹(shù)中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹(shù)中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱(chēng)這棵二叉樹(shù)為完全二叉樹(shù)。滿二叉樹(shù)最大層的結(jié)點(diǎn)均向左靠齊完全二叉樹(shù)ADCBEF滿87二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。LlinkinfoRlink二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)ABDCFGEA∧G∧∧E∧∧F∧B∧C∧

Dt二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采88二叉樹(shù)的遍歷二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。從二叉樹(shù)的結(jié)構(gòu)定義得知，二叉樹(shù)是由"根結(jié)點(diǎn)"、"左子樹(shù)"和"右子樹(shù)"三部分構(gòu)成，則遍歷二叉樹(shù)的操作可分解為"訪問(wèn)根結(jié)點(diǎn)"、"遍歷左子樹(shù)"和"遍歷右子樹(shù)"三個(gè)子操作，并且由二叉樹(shù)的遞歸定義可知，遍歷左子樹(shù)和遍歷右子樹(shù)可如同遍歷二叉樹(shù)一樣"遞歸"進(jìn)行。

前序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹(shù)；

(3)先序遍歷右子樹(shù)。若二叉樹(shù)為空，則空操作；

否則

(1)中序遍歷左子樹(shù)；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹(shù)。若二叉樹(shù)為空，則空操作；

否則

(1)后序遍歷左子樹(shù)；

(2)后序遍歷右子樹(shù)；

(3)訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)的遍歷二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。從二89查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。查找指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱(chēng)關(guān)鍵字。若找到了滿足條件的結(jié)點(diǎn)，稱(chēng)查找成功；否則稱(chēng)查找失敗。衡量一個(gè)查找算法的主要標(biāo)準(zhǔn)是查找過(guò)程中對(duì)關(guān)鍵字進(jìn)行的平均比較次數(shù)。通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：1）順序查找：線性表中最簡(jiǎn)單的查找方法。最壞情況下需比較n次2）二分查找（折半查找）：是一種效率較高的查找方法，但是只適合順序存儲(chǔ)的有序表。

最壞情況下需比較log2n查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。90排序技術(shù)

排序指將一個(gè)無(wú)序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。排序方法中其排序?qū)ο笠话闶琼樞虼鎯?chǔ)的線性表。根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：插入類(lèi)排序法

簡(jiǎn)單插入排序

希爾排序選擇類(lèi)排序法簡(jiǎn)單選擇排序堆排序交換類(lèi)排序法

冒泡排序

快速排序排序技術(shù)排序指將一個(gè)無(wú)序序列整理成按關(guān)鍵字值遞增或遞減排列91

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱92結(jié)構(gòu)化程序設(shè)計(jì)

結(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í)行某一相同程序段。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：93

面向?qū)ο蟮某绦蛟O(shè)計(jì)

1、對(duì)象：是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。屬性即?duì)象所包含的信息操作描述了對(duì)象執(zhí)行的功能，操作也稱(chēng)為方法或服務(wù)。2、類(lèi)：是指具有共同屬性、共同方法的對(duì)象的集合。所以類(lèi)是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。3、消息：是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。

消息的組成包括（1）接收消息的對(duì)象的名稱(chēng)；（2）消息標(biāo)識(shí)符，也稱(chēng)消息名；（3）零個(gè)或多個(gè)參數(shù)。4、繼承：是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。單繼承指一個(gè)類(lèi)只允許有一個(gè)父類(lèi)多重繼承指一個(gè)類(lèi)允許有多個(gè)父類(lèi)。5、多態(tài)性：是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。面向?qū)ο蟮某绦蛟O(shè)計(jì)1、對(duì)象：是面向?qū)ο蠓椒ㄖ凶罨?4第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。

第三章軟件工程基礎(chǔ)考試大綱95

軟件工程概念軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。

軟件工程包括3個(gè)要素：方法、工具和過(guò)程。軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。

軟件生命周期三個(gè)階段:軟件定義、軟件開(kāi)發(fā)、運(yùn)行維護(hù)，主要活動(dòng)階段是：

（1）可行性研究與計(jì)劃制定；

（2）需求分析；

（3）軟件設(shè)計(jì)；

（4）軟件實(shí)現(xiàn)；

（5）軟件測(cè)試；

（6）運(yùn)行和維護(hù)。軟件工程概念軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)96

結(jié)構(gòu)化分析方法和設(shè)計(jì)方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具:1)數(shù)據(jù)流圖；2)數(shù)據(jù)字典；3)判定樹(shù)；

判定表。結(jié)構(gòu)化分析方法：

軟件設(shè)計(jì)包括：總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)

在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。常見(jiàn)的過(guò)程設(shè)計(jì)工具有：圖形工具（程序流程圖,N-S,PAD）表格工具（判定表）語(yǔ)言工具（PDL偽碼）

結(jié)構(gòu)化分析方法和設(shè)計(jì)方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)97程序流程圖N-S圖PAD圖程序流程圖N-S圖PAD圖98軟件測(cè)試軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。

軟件測(cè)試方法：1)靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際

運(yùn)行軟件，主要通過(guò)人工進(jìn)行。

2)動(dòng)態(tài)測(cè)試：是基本計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒

測(cè)試方法白盒測(cè)試方法有：邏輯覆蓋；基本路徑測(cè)試黑盒測(cè)試方法有：等價(jià)類(lèi)劃分法；邊界值分析法；錯(cuò)誤推測(cè)法軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試。軟件測(cè)試軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。99程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開(kāi)發(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）原因排除法。100程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開(kāi)第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。

4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱101數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)：實(shí)際上就是描述事物的符號(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ù)管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)系統(tǒng)：由數(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ù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。102數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫(kù)的應(yīng)用程序的集合。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫(kù)等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義和檢查數(shù)據(jù)庫(kù)的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS提供了相應(yīng)的語(yǔ)言：數(shù)據(jù)定義語(yǔ)言(DDL)數(shù)據(jù)操縱語(yǔ)言(DML)數(shù)據(jù)控制語(yǔ)言(DCL)數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和103數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員104。(1)人工管理階段：人工管理階段：存儲(chǔ)設(shè)備比較落后第一代計(jì)算機(jī)：輸入

處理

輸出(2)文件系統(tǒng)階段：按名存取（出現(xiàn)數(shù)據(jù)與程序的概念）

實(shí)現(xiàn)了以文件為單位的數(shù)據(jù)共享(3)

數(shù)據(jù)庫(kù)系統(tǒng)管理階段:實(shí)現(xiàn)了以記錄和數(shù)據(jù)項(xiàng)為單位的文件共享

特點(diǎn)：1）提高數(shù)據(jù)