公共基礎(chǔ)部分

全國(guó)計(jì)算機(jī)等級(jí)考試——二級(jí)公共基礎(chǔ)知識(shí)部分目錄PAGE目錄第1章數(shù)據(jù)結(jié)構(gòu)與算法 11、算法 12、數(shù)據(jù)結(jié)構(gòu)的基本概念 23、線性表及其存儲(chǔ)結(jié)構(gòu) 24、棧和隊(duì)列 35、線性鏈表 36、樹(shù)與二叉樹(shù) 47、查找技術(shù) 58、排序技術(shù) 5第2章程序設(shè)計(jì)基礎(chǔ) 61、程序設(shè)計(jì)方法與風(fēng)格 62、結(jié)構(gòu)化程序設(shè)計(jì) 63、面向?qū)ο蟮某绦蛟O(shè)計(jì) 7第3章軟件工程基礎(chǔ) 71、軟件工程基礎(chǔ)概念 72、結(jié)構(gòu)化分析方法 83、結(jié)構(gòu)化設(shè)計(jì)方法 94、軟件測(cè)試 95、程序的調(diào)試 9第4章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 101、數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 102、數(shù)據(jù)模型 113、關(guān)系代數(shù) 124、數(shù)據(jù)設(shè)計(jì)與管理 12 第1章數(shù)據(jù)結(jié)構(gòu)與算法PAGE5數(shù)據(jù)結(jié)構(gòu)與算法算法算法的概念：是指解題方案的準(zhǔn)確而完整的描述。算法的基本特征：可行性確定性有窮性擁有足夠的情報(bào)算法的基本要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸算法的控制結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）循環(huán)結(jié)構(gòu)算法設(shè)計(jì)基本方法列舉法：根據(jù)提出的問(wèn)題列舉所有可能的情況，并用問(wèn)題中給定的條件進(jìn)行檢驗(yàn)，找出答案。學(xué)用于解決“是否存在”或“有多少種可能”等類型的問(wèn)題。歸納法：通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。遞推：指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。（本質(zhì)上也屬于歸納法）遞歸：將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。直接遞歸：一個(gè)算法P顯式調(diào)用自己間接遞歸：算法P調(diào)用另一算法Q，而算法Q又調(diào)用算法P。減半遞推技術(shù)：指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變（即減半）并重復(fù)進(jìn)行（即遞推）。回溯法：通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，每步試探成功則繼續(xù)，直至問(wèn)題解決，否則換路線再試探。算法的復(fù)雜度算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量。計(jì)算方法（P4）：用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)：算法的工作量＝f(n)其中n是問(wèn)題的規(guī)模。同一問(wèn)題規(guī)模下分析算法的工作量方法：平均性態(tài)（P5）：指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。最壞情況復(fù)雜性（P5）：指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。算法的空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)學(xué)科討論的三個(gè)問(wèn)題：數(shù)據(jù)集合中各數(shù)據(jù)之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。研究數(shù)據(jù)結(jié)構(gòu)的目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量減少數(shù)據(jù)處理過(guò)程中占用的計(jì)算機(jī)存儲(chǔ)空間。什么是數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的概念：反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示（或指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合），至少應(yīng)包含以下信息：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，它有兩個(gè)要素：（P9）B=(D,R)D={1,2,3,4}R={(1,2),(2,3),(3,4)}數(shù)據(jù)元素的集合，通常記為D；數(shù)據(jù)元素集合上的關(guān)系（即反映D中各數(shù)據(jù)元素之間前后件的關(guān)系），通常記為R數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式（即數(shù)據(jù)的物理結(jié)構(gòu)）。常見(jiàn)的存儲(chǔ)結(jié)構(gòu)有4種：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。數(shù)據(jù)結(jié)構(gòu)的圖形表示(P11例1.8)線性結(jié)構(gòu)與非線性結(jié)構(gòu)：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度可分為兩大類型，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)：一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足以下兩個(gè)條件即為線性結(jié)構(gòu)，或稱線性表。線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還是線性結(jié)構(gòu)。常見(jiàn)的線性表如：線性表、線性鏈表、棧、隊(duì)列等。有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：不符合線性結(jié)構(gòu)規(guī)則的數(shù)據(jù)結(jié)構(gòu)稱非線性結(jié)構(gòu)。如樹(shù)、二叉樹(shù)和圖等。線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表的基本概念線性表：由n(n>=0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中每一個(gè)數(shù)據(jù)元素除第一個(gè)外，有且只有一個(gè)前件，除最后一個(gè)外，有且只有一個(gè)后件。線性表也可以是一個(gè)空表，即n=0。線性表順序存儲(chǔ)兩個(gè)基本特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。順序表：用順序存儲(chǔ)方式形成的線性表稱順序表，順序表的結(jié)構(gòu)簡(jiǎn)單，適合存放元素不經(jīng)常變動(dòng)的線性表。順序存儲(chǔ)方式：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，可以實(shí)現(xiàn)隨機(jī)存取。順序表的插入運(yùn)算：在順序表中插入元素，會(huì)使插入位置后的其它元素依次后移，如插入時(shí)系統(tǒng)為線性表開(kāi)辟的存儲(chǔ)空間已滿，則會(huì)造成“上溢”錯(cuò)誤。順序表較長(zhǎng)時(shí)，插入運(yùn)算的效率很低。順序表的刪除運(yùn)算：刪除順序表的一個(gè)元素，會(huì)使刪除位置后的其它元素依次前移。順序表較長(zhǎng)時(shí)，刪除運(yùn)算的效率也很低。棧和隊(duì)列棧：只允許在一端進(jìn)行插入與刪除元素操作的線性表稱“棧”也稱“堆?！薄Ｔ试S插入與刪除的一端稱“棧頂”，不允許進(jìn)行插入與刪除的一端稱“棧底”。棧按照“先進(jìn)后出、后進(jìn)先出”的原則組織數(shù)據(jù)。棧的順序存儲(chǔ)：可以用一維數(shù)組作為棧的順序存儲(chǔ)空間，另需用一個(gè)變量作棧頂指針，記錄棧頂位置。棧的運(yùn)算：入棧運(yùn)算：往棧中插入一個(gè)元素。首先將棧頂指針進(jìn)一，然后將新元素插入到棧頂指針指向的位置。如棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置則棧滿，再進(jìn)行入棧操作就會(huì)造成“上溢”錯(cuò)誤。退棧（出棧）：從棧中刪除一個(gè)元素。首先將棧頂元素的值賦給一個(gè)指定的變量，然后將棧頂指針退一。如棧頂指針為0則棧空，如再進(jìn)行退棧操作則會(huì)造成“下溢”錯(cuò)誤。讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。讀棧操作不會(huì)改變棧頂指針，即不刪除棧頂元素。如棧頂指針為0則因棧空而讀不到棧頂元素。隊(duì)列：允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為排頭（也稱隊(duì)頭）。隊(duì)列按照“先進(jìn)先出、后進(jìn)后出”的原則組織數(shù)據(jù)。隊(duì)列的順序存儲(chǔ)：隊(duì)列也可以用一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間。另需一個(gè)變量記錄隊(duì)尾位置（rear），另一個(gè)變量記錄排頭前一個(gè)位置(front)，還有一個(gè)變量記錄隊(duì)中元素個(gè)數(shù)。循環(huán)隊(duì)列：將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。循環(huán)隊(duì)列的初始狀態(tài)為空，即隊(duì)尾、排頭都指向數(shù)組的最后一個(gè)單元，隊(duì)列元素個(gè)數(shù)為0。循環(huán)隊(duì)列的運(yùn)算：入隊(duì)運(yùn)算：首先將隊(duì)尾加1（如超過(guò)最后一個(gè)單元位置時(shí)變?yōu)?），隊(duì)列元素記錄變量也加1，然后將新元素插入到隊(duì)尾指向的位置，當(dāng)隊(duì)列非空，而隊(duì)尾等于排頭時(shí)則隊(duì)列已滿，再入隊(duì)就會(huì)“上溢”錯(cuò)誤；退隊(duì)（出隊(duì)）運(yùn)算：首先將排頭加1（如排頭超過(guò)最后一個(gè)單元位置時(shí)就變?yōu)?），隊(duì)列元素記錄變量減1，然后將排頭指向的元素值賦給指定的變量，當(dāng)隊(duì)列為空時(shí)再進(jìn)行退隊(duì)操作就會(huì)“下溢”錯(cuò)誤。線性鏈表基本概念：指針：用來(lái)存放存儲(chǔ)位置的存儲(chǔ)單元（變量）稱指針。結(jié)點(diǎn)：假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。鏈?zhǔn)酱鎯?chǔ)方式：由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放指針的指針域兩部分構(gòu)成結(jié)點(diǎn)，指針域記錄前后結(jié)點(diǎn)的位置，形成像鏈條一樣的存儲(chǔ)方式稱為鏈?zhǔn)酱鎯?chǔ)方式。鏈?zhǔn)酱鎯?chǔ)方式中存儲(chǔ)單元可以是不連續(xù)的，但訪問(wèn)必須順序進(jìn)行。線性鏈表：用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)線性表稱為線性鏈表。在鏈表中有一個(gè)頭結(jié)點(diǎn)（HEAD），它是為方便運(yùn)算的實(shí)現(xiàn)而增加的。線性單鏈表：即指針域只記錄前結(jié)點(diǎn)位置或后結(jié)點(diǎn)位置形成的線性鏈表。線性雙向鏈表：即指針域同時(shí)記錄前后結(jié)點(diǎn)位置形成的線性鏈表。其中一個(gè)稱為左指針用于指向前件結(jié)點(diǎn)，另一個(gè)稱右指針，用于指向后件結(jié)點(diǎn)。帶鏈的棧和隊(duì)列：使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)棧和隊(duì)列。線性鏈表的基本運(yùn)算：在線性鏈表中查找指定元素線性鏈表的插入線性鏈表的刪除循環(huán)鏈表循環(huán)鏈表：在鏈表中增加頭結(jié)點(diǎn)，并讓最后一個(gè)結(jié)點(diǎn)的指針批向頭結(jié)點(diǎn)，形成一個(gè)環(huán)狀鏈；基本運(yùn)算：插入與刪除結(jié)點(diǎn)。樹(shù)與二叉樹(shù)樹(shù)：概念：每個(gè)結(jié)點(diǎn)只有一個(gè)前件（父結(jié)點(diǎn)），而后件（子結(jié)點(diǎn)）可以有多個(gè)。沒(méi)有前件的結(jié)點(diǎn)稱樹(shù)根，沒(méi)有后件的結(jié)點(diǎn)稱葉子。度：一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中的最大的度稱為樹(shù)的度。層：樹(shù)的結(jié)構(gòu)是分層的，樹(shù)的最大層次稱為樹(shù)的深度。子樹(shù)：以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該結(jié)點(diǎn)的一棵子樹(shù)。二叉樹(shù)：概念：只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（左子樹(shù)與右子樹(shù)），這樣的樹(shù)稱二叉樹(shù)。基本性質(zhì)：性質(zhì)1：第k層上最多有2k-1(k>=1)個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。性質(zhì)3：在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，其深度到少為(Log2N)+1的整數(shù)值。性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1性質(zhì)6：設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序（每層從左到右）用自然數(shù)列給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k的結(jié)點(diǎn)有以下結(jié)論：若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)；若k>1則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為Int(k/2)。若2k<=n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)。若2k+1<=n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。滿二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，則該二叉樹(shù)稱滿二叉樹(shù)。滿二叉樹(shù)每層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹(shù)：除最后一層外，每個(gè)層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，而最后一層上只缺少右邊的若干結(jié)點(diǎn)。完全二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為：總結(jié)點(diǎn)數(shù)－int(總結(jié)點(diǎn)數(shù)/2)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：二叉樹(shù)通常用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)。二叉樹(shù)的遍歷：不重復(fù)地訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)稱遍歷。遍歷二叉樹(shù)的過(guò)程是一個(gè)遞歸的過(guò)程。前序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，最好訪問(wèn)右子樹(shù)。中序遍歷：首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。后序遍歷：首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。查找技術(shù)順序查找：又稱順序搜索，指從第一個(gè)元素開(kāi)始在線性表中查找指定的元素。對(duì)大的線性表順序查找的效率很低，但在下列兩種情況下只能采用順序查找：如果線性表為無(wú)序表；采用鏈?zhǔn)浇Y(jié)構(gòu)的有序線性表。二分查找：從有序表的中間開(kāi)始查找，如比中間小則在前半部分的中間再找，否則從后半部分的中間再找，重復(fù)上面的過(guò)程，直至找到指定的元素。二分查找只能查找順序存儲(chǔ)的有序表，查找效率比順序查找高得多，長(zhǎng)度為n的有序線性線最壞情況下二分查找只要比較log2n次，而順序查找需比較n次。排序技術(shù)：指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。交換類排序法：指通過(guò)互相交換數(shù)據(jù)元素值方法進(jìn)行排序。常見(jiàn)有以下兩種：冒泡排序法：依次掃描線性表，把表相阾兩個(gè)元素中較大的元素往后移（每次移動(dòng)稱消去一個(gè)逆序），直到把最大的元素移到表尾，然后再重復(fù)上面過(guò)程，在剩下的線性表中進(jìn)行排序，直到剩下的線性表為空。所以冒泡排序又稱下沉排序。假設(shè)線性表長(zhǎng)度為n，冒泡排序的最壞情況需要經(jīng)過(guò)n(n-1)/2遍比較?？焖倥判蚍ǎ簭木€性表中選取一個(gè)元素T作為標(biāo)準(zhǔn)，把比T小的元素移到前面，比T大的元素移到后面，結(jié)果就將線性表分成了兩個(gè)子表，然后對(duì)子表分別重復(fù)上面的過(guò)程，直至各子表為空。具體實(shí)現(xiàn)如下：首先在表的第一、中間一個(gè)和最后一個(gè)元素中選取一個(gè)中項(xiàng)（設(shè)為p(k)元素），并用變量T記住P(k)的值，再將第一個(gè)元素移動(dòng)到p(k)位置上，然后設(shè)置兩個(gè)指針I(yè)和j，I記錄表的起始位置，j記錄表的結(jié)束位置；將j逐漸減小，并不斷比較p(j)與T，如發(fā)現(xiàn)p(j)<T則P(j)移到p(i)位置上；將I逐漸增大，并不斷比較p(i)與T，如發(fā)現(xiàn)p(i)>T，將p(i)移動(dòng)到p(j)位置上。不斷重復(fù)b)中的操作，直至指針I(yè)與j相等（即指向同一位置），將T移到p(i)位置上。插入類排序法：指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中而完成的排序操作。簡(jiǎn)單插入排序法：把第一個(gè)元素看作一個(gè)有序子表。用T記住剩下線性表的第一個(gè)元素值。從有序子表最后一個(gè)元素開(kāi)始掃描，把比T大的元素依次后移一個(gè)位置，直至發(fā)現(xiàn)不大于T的元素或沒(méi)有發(fā)現(xiàn)不大于T的元素為止，把T插入到有序子表中空出來(lái)的位置上，使有序子表長(zhǎng)度加1。重復(fù)上面的操作，直至有序子表長(zhǎng)度與線性表相同。排序效率與冒泡排序一樣，最壞情況下，長(zhǎng)度為n的線性表使用簡(jiǎn)單插入排序需要n(n-1)/2次比較。希爾排序法：將整個(gè)無(wú)序序列分割成若干個(gè)小的子序列，然后分別進(jìn)行插入排序。具體實(shí)現(xiàn)時(shí)一般會(huì)先以序列的一半長(zhǎng)度作為分割子序列單位，然后再逐次減小分割單位，直至分割單位為1。本排序的效率與所選取的增量序列有關(guān)，按上述增量最壞情況下希爾排序所需要的比較次數(shù)為O(n1.5)。選擇類排序法：掃描整個(gè)線性表，選出最小的元素將它交換到表的最前面；然后在剩下的子表中重復(fù)使用這個(gè)操作，直至子表為空。簡(jiǎn)單選擇排序法：最壞情況下需要比較n(n-1)/2次堆排序法P38：最壞情況下，堆排序需要比較的次數(shù)為O(nlog2n)。*歸并排序：指將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。它的內(nèi)存量較前面幾種都要大。幾個(gè)補(bǔ)充算法分析：是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量分析，目的是要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，提高算法的執(zhí)行效率。*強(qiáng)連通圖：在有向圖中若任意兩個(gè)頂點(diǎn)都連通，則該圖為強(qiáng)連通圖。有n個(gè)頂點(diǎn)的強(qiáng)連通圖到少有n條邊。鏈表與順序表比較：順序表訪問(wèn)方便，可以隨機(jī)訪問(wèn)；鏈表插入刪除結(jié)點(diǎn)比順序方便。第2章程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)方法與風(fēng)格當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格：清晰第一，效率第二。形成良好程序設(shè)計(jì)風(fēng)格：源程序文檔化數(shù)據(jù)說(shuō)明的次序規(guī)范，變量安排有序，使用注釋。語(yǔ)句的結(jié)構(gòu)輸入和輸出盡可能方便用戶使用。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下：程序設(shè)計(jì)時(shí)從總體到細(xì)節(jié)，從全局目標(biāo)到局部目標(biāo)。逐步求精：對(duì)復(fù)雜問(wèn)題應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)化。模塊化：總目標(biāo)分解為人目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)稱為一個(gè)模塊。限制使用goto語(yǔ)句。結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)順序結(jié)構(gòu)：是最基本、最常用的結(jié)構(gòu)，按程序語(yǔ)句的自然順序一條一條地執(zhí)行。選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)。根據(jù)設(shè)定的條件選擇其中一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列。重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)。根據(jù)給定的條件，重復(fù)執(zhí)行同一相同或類似的程序段，直到允許循環(huán)的條件被破壞為止。總之，遵循結(jié)構(gòu)化程序的設(shè)計(jì)原則可以有以下優(yōu)點(diǎn)：易于理解使用和維護(hù)；提高編程工作的效率，降低開(kāi)發(fā)成本。結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用使用順序、選擇和循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；選用的控制結(jié)構(gòu)只許有一個(gè)入口和一個(gè)出口；程序塊組成要容易識(shí)別，每塊只有一個(gè)入口和一個(gè)出口；使用基本控制結(jié)構(gòu)進(jìn)行嵌套與組合來(lái)實(shí)現(xiàn)復(fù)雜結(jié)構(gòu)；用前后一致的方法來(lái)模擬三種基本結(jié)構(gòu)以外的控制結(jié)構(gòu)；嚴(yán)格控制GOTO語(yǔ)句的使用。面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ谋举|(zhì)：系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)地反映問(wèn)題域中固有事物及關(guān)系。面向?qū)ο竽Ｐ妥罨镜母拍顬閷?duì)象和類。基本原理：使用現(xiàn)實(shí)世界的抽象地思考問(wèn)題從而自然地解決問(wèn)題。它強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不強(qiáng)調(diào)算法，鼓勵(lì)開(kāi)發(fā)者在軟件開(kāi)發(fā)的絕大部分中都用應(yīng)用領(lǐng)域的概念去思考。面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：與人類習(xí)慣的思維方法一致，面向?qū)ο蟮暮诵氖菍?duì)象。穩(wěn)定性好可重用性好：可繼承父類的所有屬性和方法。易于開(kāi)發(fā)大型軟件產(chǎn)品可維護(hù)性好穩(wěn)定性好容易修改容易理解易于測(cè)試和調(diào)試面向?qū)ο蠓椒ǖ幕靖拍顚?duì)象（object）：應(yīng)用領(lǐng)域中有意義的、與所要解決的問(wèn)題有關(guān)系的任何事物都可以作為對(duì)象，它既可以是具體的物理實(shí)體的抽象，也可以是人為的概念。對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性分類性多態(tài)性封裝性模塊獨(dú)立性好類和實(shí)例類：指具有共同屬性、方法的對(duì)象的集合。實(shí)例：類的其中一個(gè)具體應(yīng)用就是一個(gè)實(shí)例。消息：實(shí)例之間相互傳遞的信息叫消息，傳送的消息實(shí)質(zhì)上是接受對(duì)象所具有的操作/方法名稱，有時(shí)還包括相應(yīng)參數(shù)。繼承：使用已有的類定義作基礎(chǔ)建立新類的定義技術(shù)。它是面向?qū)ο蠓椒ǖ囊粋€(gè)主要特征。繼續(xù)分為單繼承與多重繼承。單繼承：指一個(gè)類只允許有一個(gè)父類。多重繼承：指一個(gè)類允許有多個(gè)父類。多態(tài)性：指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同行動(dòng)的現(xiàn)象。第3章軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件工程的基本概念軟件：是計(jì)算機(jī)系統(tǒng)中與硬件相互儲(chǔ)存的程序、數(shù)據(jù)及相關(guān)文檔的完整集合。所以軟件由機(jī)器可以執(zhí)行的程序和數(shù)據(jù)，及是機(jī)器不可執(zhí)行的相關(guān)文檔兩部分構(gòu)成。程序：是軟件開(kāi)發(fā)人員根據(jù)用戶需求開(kāi)發(fā)的、用程序設(shè)計(jì)語(yǔ)言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語(yǔ)句）序列。數(shù)據(jù)：是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔：是與程序開(kāi)發(fā)、維護(hù)和使用有關(guān)的圖文資料。軟件的特點(diǎn)軟件是一種邏輯實(shí)體，不是物理實(shí)體，具有抽象性。軟件的生產(chǎn)與硬件不同，沒(méi)有明顯的制作過(guò)程。軟件的運(yùn)行與使用不存在磨損與老化問(wèn)題。軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制。軟件復(fù)雜性高，成本昂貴。軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。軟件的分類：按功能分可為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（工具軟件）。軟件危機(jī)與軟件工程軟件危機(jī)：泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。歸結(jié)起來(lái)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。軟件工程：是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程三要素：方法、工具和過(guò)程。軟件工程的核心思想：把軟件產(chǎn)品看作是一個(gè)工程產(chǎn)品來(lái)處理。軟件工程過(guò)程：是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。軟件工程過(guò)程是指為獲得軟件產(chǎn)品，在軟件工具運(yùn)行下由軟件工程師完成的一系列軟件工程活動(dòng)。包括4種基本活動(dòng)：軟件規(guī)格說(shuō)明、軟件開(kāi)發(fā)、軟件確認(rèn)、軟件演進(jìn)。從軟件開(kāi)發(fā)的觀點(diǎn)看，它是使用適當(dāng)?shù)馁Y源為開(kāi)發(fā)軟件進(jìn)行的一組開(kāi)發(fā)活動(dòng)，在過(guò)程結(jié)束時(shí)將輸入轉(zhuǎn)化為輸出。軟件生命周期：通常將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期?？梢源致詣澐譃檐浖x、軟件開(kāi)發(fā)、和軟件運(yùn)行維護(hù)三個(gè)階段。軟件生命周期的主要活動(dòng)階段是：可行性研究與計(jì)劃制定：確定開(kāi)發(fā)目標(biāo)和總的要求，給出可行方案，制定開(kāi)發(fā)計(jì)劃。需求分析：根據(jù)用戶的需求進(jìn)行分析并給出詳細(xì)定義，即確定軟件系統(tǒng)的功能。軟件設(shè)計(jì)：在反復(fù)理解軟件需求的基礎(chǔ)上給出軟件結(jié)構(gòu)、模塊劃分、功能分配及處理流程。軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼，即完成源程序的編碼和相關(guān)用戶文檔，編寫(xiě)單元測(cè)試計(jì)劃。軟件測(cè)試：檢驗(yàn)軟件的各個(gè)組成部分，編寫(xiě)測(cè)試分析報(bào)告。運(yùn)行和維護(hù)：交付使用，并不斷進(jìn)行維護(hù)，根據(jù)新需求進(jìn)行擴(kuò)充和刪改。本階段所花的費(fèi)用遠(yuǎn)遠(yuǎn)大于開(kāi)發(fā)階段。軟件的維護(hù)分改正性維護(hù)、適應(yīng)性維護(hù)、完善性維護(hù)和預(yù)防性維護(hù)4種。軟件工程的目標(biāo)與原則軟件工程的目標(biāo)：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程的理論和技術(shù)研究的主要包括：軟件開(kāi)發(fā)技術(shù)和軟件工程管理。軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。這也是軟件設(shè)計(jì)所必須遵循的原則。P54軟件開(kāi)發(fā)環(huán)境：是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。計(jì)算機(jī)輔助軟件工程縮寫(xiě)CASE結(jié)構(gòu)化分析方法軟件開(kāi)發(fā)方法：是軟件開(kāi)發(fā)過(guò)程所遵循的方法和步驟。包括分析方法、設(shè)計(jì)方法和程序設(shè)計(jì)方法。結(jié)構(gòu)化分析方法：其核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論，包括結(jié)構(gòu)化分析方法、結(jié)構(gòu)化設(shè)計(jì)方法和結(jié)構(gòu)化編程方法。需求分析與其方法需求分析：指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。有四個(gè)方面的工作：需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)和需求評(píng)審。需求分析方法：結(jié)構(gòu)分析方法：包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法。面向?qū)ο蟮姆治龇椒ò葱枨蠓治鼋⒌哪Ｐ吞匦苑挚煞譃殪o態(tài)分析方法和動(dòng)態(tài)分析方法。結(jié)構(gòu)化分析方法：是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。數(shù)據(jù)流圖P56：是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)字典：是結(jié)構(gòu)化分析方法的核心，是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表。判定樹(shù)、判定表軟件需求規(guī)格說(shuō)明書(shū)：是需求分析階段的最后成果，是軟件開(kāi)發(fā)中的重要文檔之一。其作用為便于理解與交流作為軟件開(kāi)發(fā)的基礎(chǔ)和依據(jù)作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)結(jié)構(gòu)需求分析的常用工具：數(shù)據(jù)流圖（DFD）：用于描述數(shù)據(jù)處理過(guò)程。主要的描述圖符有加工（轉(zhuǎn)換）“○”、數(shù)據(jù)流“→”、存儲(chǔ)文件（數(shù)據(jù)源）“〓”、源和潭“□”。數(shù)據(jù)字典（DD）：是各類數(shù)據(jù)描述的集合，通常包括數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲(chǔ)和處理過(guò)程5個(gè)部分。判定樹(shù)判定表結(jié)構(gòu)化設(shè)計(jì)方法軟件設(shè)計(jì)的基本概念軟件設(shè)計(jì)的構(gòu)成：軟件結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和操作系統(tǒng)之間及軟件與人之間如何通信；過(guò)程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述。軟件設(shè)計(jì)的步驟：從工程管理角度，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)：即總體設(shè)計(jì)或結(jié)構(gòu)設(shè)計(jì)基本任務(wù)：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)、編寫(xiě)概要設(shè)計(jì)文檔和概要設(shè)計(jì)文檔評(píng)審等，在需求分析基礎(chǔ)上把復(fù)雜的系統(tǒng)功能分解成一系列比較簡(jiǎn)單的功能。數(shù)據(jù)流類型：變換型和事務(wù)型常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖（由四種模塊構(gòu)成：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊）。詳細(xì)設(shè)計(jì)：其任務(wù)是為軟件結(jié)構(gòu)圖的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常用的表達(dá)工具有：程序流程圖（PFD）、N－S、PAD、HIPO、判定表和PDL（偽碼）等。程序流程圖：也稱程序框圖，其中箭頭表示控制流，方塊表示加工步驟，菱形表示邏輯條件。N－S圖：用方框圖來(lái)代替?zhèn)鹘y(tǒng)的程序流程圖。軟件設(shè)計(jì)的一般過(guò)程：軟件設(shè)計(jì)是一個(gè)迭代的過(guò)程，先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)，后進(jìn)行低層次的過(guò)程設(shè)計(jì)，中間穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。軟件設(shè)計(jì)的基本原理P61結(jié)構(gòu)化設(shè)計(jì)方法：采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分以及各成分之間的內(nèi)部聯(lián)系的技術(shù)。軟件測(cè)試：是保證軟件質(zhì)量的重要手段，包括需求定義階段的需求測(cè)試、編碼階段的單元測(cè)試、集成階段以及后期的確認(rèn)測(cè)試、系統(tǒng)測(cè)試，以驗(yàn)證軟件是否合格、能否交付用戶使用等。測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤。測(cè)試的準(zhǔn)則：所有測(cè)試都應(yīng)追溯到需求嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排隊(duì)測(cè)試的隨意性充分注意測(cè)試中的群集現(xiàn)象程序員應(yīng)避免檢查自己的程序窮舉測(cè)試不可能妥善保存測(cè)試計(jì)劃、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告，為維護(hù)提供方便。測(cè)試技術(shù)與方法P72按是否需要執(zhí)行被測(cè)試軟件分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。按功能劃分可分為白盒和黑盒測(cè)試。白盒測(cè)試：用于測(cè)試程序內(nèi)部結(jié)構(gòu)，此方法將程序看作邏輯路徑的集合。有邏輯覆蓋、基本路徑測(cè)試等，其中邏輯覆蓋分語(yǔ)句覆蓋、路徑覆蓋、判定覆蓋、條件覆蓋、判斷－條件覆蓋；黑盒測(cè)試：是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測(cè)試和驗(yàn)證。分等價(jià)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法。軟件測(cè)試的過(guò)程：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試。單元測(cè)試：對(duì)軟件的最小設(shè)計(jì)單元－模塊進(jìn)行正確性檢驗(yàn)的測(cè)試。集成測(cè)試：是測(cè)試和組裝軟件的測(cè)試，目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。驗(yàn)收測(cè)試：即確認(rèn)測(cè)試，是驗(yàn)證軟件的功能和性能及其他特性是否滿足需求規(guī)格說(shuō)明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測(cè)試：是將通過(guò)測(cè)試確認(rèn)的軟件加入的整個(gè)計(jì)算機(jī)系統(tǒng)中進(jìn)行測(cè)試，目的是在真實(shí)的系統(tǒng)工作環(huán)境下檢驗(yàn)軟件是否能與系統(tǒng)正確連接，發(fā)現(xiàn)軟件與系統(tǒng)需求不一致地方。程序的調(diào)試基本概念程序調(diào)試活動(dòng)的組成：根據(jù)錯(cuò)誤的跡象確定程序中錯(cuò)誤的確切性質(zhì)、原因和位置，對(duì)程序進(jìn)行修改排隊(duì)這個(gè)錯(cuò)誤。其目的是診斷和改正程序中的錯(cuò)誤。程序調(diào)試的基本步驟錯(cuò)誤定位修改設(shè)計(jì)和代碼，以排除錯(cuò)誤進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤程序調(diào)試的原則P81軟件調(diào)試方法強(qiáng)行排錯(cuò)法回溯法原因排除法第4章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)（Date）：描述事物的符號(hào)記錄。數(shù)據(jù)一般分臨時(shí)性數(shù)據(jù)與持久性數(shù)據(jù)兩類。處理數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)，若干數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素。數(shù)據(jù)庫(kù)（DataBase）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。也就是說(shuō)它是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合，具有集成、共享之特點(diǎn)。數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)：是一種系統(tǒng)軟件，是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，是數(shù)據(jù)庫(kù)系統(tǒng)的核心，負(fù)責(zé)數(shù)據(jù)庫(kù)的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。主要有以下六方面功能：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)數(shù)據(jù)的服務(wù)幾個(gè)相關(guān)縮寫(xiě)：數(shù)據(jù)定義語(yǔ)言（DDL）、數(shù)據(jù)操縱語(yǔ)言（DML）、數(shù)據(jù)控制語(yǔ)言（DCL）數(shù)據(jù)庫(kù)管理員（DBA）：主要工作為數(shù)據(jù)庫(kù)設(shè)計(jì)數(shù)據(jù)庫(kù)維護(hù)改善系統(tǒng)性能，提高系統(tǒng)效率。數(shù)據(jù)庫(kù)系統(tǒng)（DBS）：以數(shù)據(jù)庫(kù)為核心的由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)管理員系統(tǒng)軟、硬件平臺(tái)五部分構(gòu)成的完整的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）：在數(shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ)上加上應(yīng)用軟件及應(yīng)用界面，包括數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、系統(tǒng)軟、硬件平臺(tái)、應(yīng)用軟件、應(yīng)用界面七部分構(gòu)成的有機(jī)整體。數(shù)據(jù)庫(kù)管理的發(fā)展三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展三個(gè)階段：文件系統(tǒng)階段、層次數(shù)據(jù)庫(kù)和網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)階段和關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)階段。目前三種比較重要的數(shù)據(jù)庫(kù)技術(shù)：面向?qū)ο髷?shù)據(jù)庫(kù)系統(tǒng)、知識(shí)庫(kù)系統(tǒng)、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的擴(kuò)充。數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)：數(shù)據(jù)的集成性數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)高獨(dú)立性數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系三級(jí)模式：數(shù)據(jù)模式是數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式。概念模式：是數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）數(shù)據(jù)視圖。以概念模式為框架所組成的數(shù)據(jù)為叫概念數(shù)據(jù)庫(kù)。外模式：也稱子模式或用戶模式，是用戶的數(shù)據(jù)視圖。以外模式為框架所組成數(shù)據(jù)庫(kù)叫用戶數(shù)據(jù)庫(kù)。內(nèi)模式：又稱物理模式，是數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法，如數(shù)據(jù)存儲(chǔ)的文件結(jié)構(gòu)、索引、集簇及hash等。是數(shù)據(jù)的物理結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。以內(nèi)模式為框架所組成的數(shù)據(jù)庫(kù)叫物理數(shù)據(jù)庫(kù)。二級(jí)映射：概念模式到內(nèi)模式的映射外模式到概念模式的映射數(shù)據(jù)模型數(shù)據(jù)模型的基本概念數(shù)據(jù)模式的內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型的應(yīng)用層次概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型E－R模型（實(shí)體聯(lián)系模型）：由實(shí)體、聯(lián)系和屬性三者結(jié)合起來(lái)表示現(xiàn)實(shí)世界?；靖拍顚?shí)體：是概念世界的基本單位，是客觀存在的且又能被相互區(qū)別的事物。屬性：實(shí)體的特征聯(lián)系：事物之間的關(guān)聯(lián)，也就是實(shí)體間的函數(shù)關(guān)系，常見(jiàn)的函數(shù)關(guān)系有一對(duì)一（實(shí)體間一一對(duì)應(yīng)）、一對(duì)多（實(shí)體A對(duì)應(yīng)多個(gè)其它實(shí)體，而其他實(shí)體只對(duì)應(yīng)實(shí)體A）、多對(duì)多（多個(gè)實(shí)體間相互有多個(gè)關(guān)系）。E－R圖示法實(shí)體集表示法屬性表示法聯(lián)系表示法實(shí)體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系層次模型：以樹(shù)形結(jié)構(gòu)表示現(xiàn)實(shí)世界，具有以下特性：每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱為根樹(shù)中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。網(wǎng)狀模型P95關(guān)系模型：關(guān)系的數(shù)據(jù)結(jié)構(gòu)：用二維表表示，簡(jiǎn)稱表。二維表由表框架和表的元組組成。表框架上按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，一個(gè)元組由n個(gè)元組分量組成，每個(gè)元組分量是表框架上每個(gè)屬性的投影值。滿足下列7個(gè)性質(zhì)的二維表稱關(guān)系：元組個(gè)數(shù)有限性元組的惟一性元組的次序無(wú)關(guān)性元組分量的原子性屬性名惟一性屬性的次序無(wú)關(guān)性分量值域的同一性關(guān)系的操縱：是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢