公共基礎(chǔ)知識ppt課件

1、全國計(jì)算機(jī)等級考試二級二級公共公共根底根底知識知識考試大綱考試大綱根本要求根本要求1、掌握算法的根本概念。、掌握算法的根本概念。2、掌握根本數(shù)據(jù)構(gòu)造及其操作。、掌握根本數(shù)據(jù)構(gòu)造及其操作。3、掌握根本排序和查找算法。、掌握根本排序和查找算法。4、掌握逐漸求精的構(gòu)造化程序設(shè)計(jì)方法。、掌握逐漸求精的構(gòu)造化程序設(shè)計(jì)方法。5、掌握軟件工程的根本方法，具有初步、掌握軟件工程的根本方法，具有初步運(yùn)用相關(guān)技術(shù)進(jìn)展軟件開發(fā)的才干。運(yùn)用相關(guān)技術(shù)進(jìn)展軟件開發(fā)的才干。6、掌握數(shù)據(jù)庫的根本知識，了解關(guān)系數(shù)、掌握數(shù)據(jù)庫的根本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)。據(jù)庫的設(shè)計(jì)?？荚嚧缶V考試大綱考試內(nèi)容考試內(nèi)容一、根本數(shù)據(jù)構(gòu)造與算法一、

2、根本數(shù)據(jù)構(gòu)造與算法1、算法的根本概念；算法復(fù)雜度的概念和意、算法的根本概念；算法復(fù)雜度的概念和意義義(空間復(fù)雜度與時(shí)間復(fù)雜度空間復(fù)雜度與時(shí)間復(fù)雜度)。2、數(shù)據(jù)構(gòu)造的定義；數(shù)據(jù)的邏輯構(gòu)造和存儲、數(shù)據(jù)構(gòu)造的定義；數(shù)據(jù)的邏輯構(gòu)造和存儲構(gòu)造；數(shù)據(jù)構(gòu)造的圖形表示；線性構(gòu)造與非線構(gòu)造；數(shù)據(jù)構(gòu)造的圖形表示；線性構(gòu)造與非線性構(gòu)造的概念。性構(gòu)造的概念。3、線性表的定義；線性表的順序存儲構(gòu)造及、線性表的定義；線性表的順序存儲構(gòu)造及其插入刪除運(yùn)算。其插入刪除運(yùn)算。4、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲構(gòu)、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲構(gòu)造及其根本運(yùn)算。造及其根本運(yùn)算。5、線性單鏈表，雙向鏈表與循環(huán)鏈表的構(gòu)造、線

3、性單鏈表，雙向鏈表與循環(huán)鏈表的構(gòu)造及其根本運(yùn)算。及其根本運(yùn)算。6、樹的根本概念；二叉樹的定義及其存儲構(gòu)、樹的根本概念；二叉樹的定義及其存儲構(gòu)造；二叉樹的前序、中序和后序遍歷。造；二叉樹的前序、中序和后序遍歷。7、順序查找與二分查找算法；根本排序算法、順序查找與二分查找算法；根本排序算法(交換類排序、選擇類排序、插入類排序交換類排序、選擇類排序、插入類排序)?？荚嚧缶V考試大綱考試內(nèi)容考試內(nèi)容二、程序設(shè)計(jì)根底二、程序設(shè)計(jì)根底1、程序設(shè)計(jì)方法與風(fēng)格。、程序設(shè)計(jì)方法與風(fēng)格。2、構(gòu)造化程序設(shè)計(jì)。、構(gòu)造化程序設(shè)計(jì)。3、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，屬性及承繼與多

4、態(tài)性。屬性及承繼與多態(tài)性?？荚嚧缶V考試大綱考試內(nèi)容考試內(nèi)容三、軟件工程根底三、軟件工程根底1、軟件工程的根本概念；軟件生命周期概念；、軟件工程的根本概念；軟件生命周期概念；軟件工具與軟件開發(fā)環(huán)境。軟件工具與軟件開發(fā)環(huán)境。2、構(gòu)造化分析方法；數(shù)據(jù)流圖，數(shù)據(jù)字典，、構(gòu)造化分析方法；數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格闡明書。軟件需求規(guī)格闡明書。3、構(gòu)造化設(shè)計(jì)方法；、構(gòu)造化設(shè)計(jì)方法； 總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)?？傮w設(shè)計(jì)，詳細(xì)設(shè)計(jì)。4、軟件測試的方法；白盒測試，黑盒測試，、軟件測試的方法；白盒測試，黑盒測試，測試用例設(shè)計(jì)；軟件測試的實(shí)施；單元測試，測試用例設(shè)計(jì)；軟件測試的實(shí)施；單元測試，集成測試，系統(tǒng)測試。集成

5、測試，系統(tǒng)測試。5、程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。、程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試?？荚嚧缶V考試大綱考試內(nèi)容考試內(nèi)容四、數(shù)據(jù)庫設(shè)計(jì)根底四、數(shù)據(jù)庫設(shè)計(jì)根底1、數(shù)據(jù)庫的根本概念；數(shù)據(jù)庫，數(shù)據(jù)庫管理、數(shù)據(jù)庫的根本概念；數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2、數(shù)據(jù)模型；實(shí)體聯(lián)絡(luò)模型及、數(shù)據(jù)模型；實(shí)體聯(lián)絡(luò)模型及E-R圖，從圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3、關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投、關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、銜接運(yùn)算；數(shù)據(jù)庫規(guī)范化實(shí)際。影、銜接運(yùn)算；數(shù)據(jù)庫規(guī)范化實(shí)際。4、數(shù)據(jù)庫設(shè)計(jì)方法和步驟；需求分析、概念、數(shù)據(jù)庫設(shè)計(jì)方法和步驟；需求分析

6、、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)戰(zhàn)略。設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)戰(zhàn)略?？荚嚧缶V考試大綱考試題型考試題型選擇題選擇題10 題題每題每題 2 分分共共 20 分分填空題填空題5 題題每題每題 2 分分共共 10 分分合計(jì)合計(jì)30 分分?jǐn)?shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法關(guān)鍵考點(diǎn)關(guān)鍵考點(diǎn)算法根本概念及算法復(fù)雜度算法根本概念及算法復(fù)雜度數(shù)據(jù)的存儲構(gòu)造數(shù)據(jù)的存儲構(gòu)造棧和隊(duì)列棧和隊(duì)列線性鏈表線性鏈表二叉樹根本概念及其特性二叉樹根本概念及其特性查找技術(shù)查找技術(shù)數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念1、算法、算法算法是指解題方案的準(zhǔn)確而完好的描畫。算法是指解題方案的準(zhǔn)確而完好的描畫。留意：算

7、法與數(shù)學(xué)上的計(jì)算方法不是同一個留意：算法與數(shù)學(xué)上的計(jì)算方法不是同一個概念。算法要思索計(jì)算機(jī)的特點(diǎn)，要思索計(jì)概念。算法要思索計(jì)算機(jī)的特點(diǎn)，要思索計(jì)算方法的可行性。算方法的可行性。算法也不等于程序。算法不思索詳細(xì)的機(jī)算法也不等于程序。算法不思索詳細(xì)的機(jī)器及編程言語。處理問題時(shí)，總是先設(shè)計(jì)算器及編程言語。處理問題時(shí)，總是先設(shè)計(jì)算法，然后進(jìn)展編程。法，然后進(jìn)展編程。2、算法的根本特征、算法的根本特征可行性可行性確定性確定性有窮性有窮性擁有足夠的情報(bào)擁有足夠的情報(bào)算法是一個動態(tài)概念，強(qiáng)調(diào)實(shí)踐的執(zhí)行過算法是一個動態(tài)概念，強(qiáng)調(diào)實(shí)踐的執(zhí)行過程。程。數(shù)學(xué)上的計(jì)算方法是一個靜態(tài)概念，注重?cái)?shù)學(xué)上的計(jì)算方法是一個靜態(tài)

8、概念，注重實(shí)際上的正確性。實(shí)際上的正確性。數(shù)學(xué)上的計(jì)算方法是設(shè)計(jì)算法的根底。數(shù)學(xué)上的計(jì)算方法是設(shè)計(jì)算法的根底。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念3、算法的根本要素、算法的根本要素算法中對數(shù)據(jù)的運(yùn)算和操作算法中對數(shù)據(jù)的運(yùn)算和操作根本的運(yùn)算和操作有：算術(shù)運(yùn)算、邏輯運(yùn)算、根本的運(yùn)算和操作有：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制構(gòu)造算法的控制構(gòu)造控制構(gòu)造決議操作的執(zhí)行順序。要求符合構(gòu)控制構(gòu)造決議操作的執(zhí)行順序。要求符合構(gòu)造化原那么，強(qiáng)調(diào)易讀性。造化原那么，強(qiáng)調(diào)易讀性。4、算法設(shè)計(jì)根本方法、算法設(shè)計(jì)根本方法列舉法列舉法 列舉一切能夠情況，檢測其中符

9、合條列舉一切能夠情況，檢測其中符合條件的結(jié)果。件的結(jié)果。歸納法歸納法 列舉假設(shè)干特殊情況，分析歸納出普列舉假設(shè)干特殊情況，分析歸納出普通規(guī)律。通規(guī)律。遞推遞推 從知初始條件出發(fā)，逐漸推導(dǎo)出中從知初始條件出發(fā)，逐漸推導(dǎo)出中間及最后結(jié)果。間及最后結(jié)果。遞歸遞歸 將復(fù)雜問題歸結(jié)為簡單問題，在歸將復(fù)雜問題歸結(jié)為簡單問題，在歸結(jié)為更簡單問題，結(jié)為更簡單問題， 。減半遞推技術(shù)減半遞推技術(shù) 將問題規(guī)模將問題規(guī)?！皽p半，并反復(fù)減半，并反復(fù)該該“減半減半 的過程。的過程?；厮莘ɑ厮莘?分析問題，找出某些線索，沿線索分析問題，找出某些線索，沿線索逐漸試探。假設(shè)試探勝利，那么繼續(xù)，假設(shè)逐漸試探。假設(shè)試探勝利，那么繼

10、續(xù)，假設(shè)試探失敗，那么回退。直至問題處理。試探失敗，那么回退。直至問題處理。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念5、算法的時(shí)間復(fù)雜度、算法的時(shí)間復(fù)雜度指執(zhí)行算法所需求的計(jì)算任務(wù)量指執(zhí)行算法所需求的計(jì)算任務(wù)量算法任務(wù)量的度量應(yīng)與計(jì)算機(jī)、編程言語、算法任務(wù)量的度量應(yīng)與計(jì)算機(jī)、編程言語、編程細(xì)節(jié)等無關(guān)。編程細(xì)節(jié)等無關(guān)。算法的任務(wù)量用算法所執(zhí)行的根本運(yùn)算次數(shù)算法的任務(wù)量用算法所執(zhí)行的根本運(yùn)算次數(shù)衡量。衡量。算法任務(wù)量是問題規(guī)模的函數(shù)：算法的任務(wù)算法任務(wù)量是問題規(guī)模的函數(shù)：算法的任務(wù)量量= f (n)度量方法有：度量方法有：平均性態(tài)分析平均性態(tài)分析 計(jì)算其加計(jì)算其加權(quán)平均值權(quán)平均值最

11、壞情況分析最壞情況分析 計(jì)算其根本運(yùn)算的最計(jì)算其根本運(yùn)算的最大次數(shù)大次數(shù)6、算法的空間復(fù)雜度、算法的空間復(fù)雜度指執(zhí)行算法所需求的存儲空間指執(zhí)行算法所需求的存儲空間包括：算法程序所占據(jù)的存儲空間包括：算法程序所占據(jù)的存儲空間待處置數(shù)據(jù)所占據(jù)的存儲空間待處置數(shù)據(jù)所占據(jù)的存儲空間算法程序執(zhí)行中所需求的額外存儲空間算法程序執(zhí)行中所需求的額外存儲空間假設(shè)額外存儲空間大小不隨問題規(guī)模變化，假設(shè)額外存儲空間大小不隨問題規(guī)模變化，那么稱之為算法原地任務(wù)。那么稱之為算法原地任務(wù)。降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲空降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲空間和額外空間入手。間和額外空間入手。算法定義特征復(fù)雜度時(shí)間

12、/空間數(shù)據(jù)構(gòu)造1.數(shù)據(jù)的邏輯構(gòu)造2.數(shù)據(jù)的存儲構(gòu)造3.數(shù)據(jù)的運(yùn)算線性線性表?xiàng)?、?duì)列非線性樹形構(gòu)造二叉樹滿二叉樹、完全二叉數(shù)順序存儲鏈?zhǔn)酱鎯λ饕鎯ι⒘写鎯Σ檎翼樞?、二分修正排序交換、插入、選擇插入刪除修正數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造的根本概念數(shù)據(jù)構(gòu)造的根本概念1、數(shù)據(jù)構(gòu)造、數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)構(gòu)造是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)構(gòu)造是指帶有構(gòu)造的數(shù)據(jù)元素的集合。數(shù)據(jù)構(gòu)造是指帶有構(gòu)造的數(shù)據(jù)元素的集合。構(gòu)造構(gòu)造 通常指前后件關(guān)系。通常指前后件關(guān)系。主要研討：數(shù)據(jù)元素間的固有邏輯關(guān)系主要研討：數(shù)據(jù)元素間的固有邏輯關(guān)系 數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系數(shù)據(jù)元素在計(jì)算

13、機(jī)中的存儲關(guān)系 對各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算對各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算2、數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的邏輯構(gòu)造指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)構(gòu)造指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)構(gòu)造前后件前后件(直接前驅(qū)和直接后繼直接前驅(qū)和直接后繼)關(guān)系就是指邏關(guān)系就是指邏輯關(guān)系輯關(guān)系3、數(shù)據(jù)的存儲構(gòu)造、數(shù)據(jù)的存儲構(gòu)造數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的存儲方式數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的存儲方式存儲構(gòu)造也稱為物理構(gòu)造存儲構(gòu)造也稱為物理構(gòu)造同一種邏輯構(gòu)造可以有不同的存儲構(gòu)造同一種邏輯構(gòu)造可以有不同的存儲構(gòu)造常用的有：順序、鏈接、索引等方式常用的有：順序、鏈接、索引等方式數(shù)據(jù)構(gòu)造的根本概念數(shù)據(jù)構(gòu)造的根本概念4、數(shù)據(jù)構(gòu)造的表示、數(shù)據(jù)構(gòu)造

14、的表示二元關(guān)系表示：二元關(guān)系表示：兩個要素：數(shù)據(jù)元素的集合兩個要素：數(shù)據(jù)元素的集合D，該集合上的，該集合上的關(guān)系關(guān)系R。即：即：B=(D,R)如：如：D=春春,夏夏,秋秋,冬冬 R=(春春,夏夏),(夏夏,秋秋),(秋秋,冬冬)圖形表示：圖形表示：標(biāo)有元素值的方框表示結(jié)點(diǎn)，有向線段表示標(biāo)有元素值的方框表示結(jié)點(diǎn)，有向線段表示邏輯關(guān)系。邏輯關(guān)系。春春 夏夏 秋秋 冬冬5、線性構(gòu)造和非線性構(gòu)造、線性構(gòu)造和非線性構(gòu)造線性構(gòu)造：一個非空的線性構(gòu)造有且只需一線性構(gòu)造：一個非空的線性構(gòu)造有且只需一個根結(jié)點(diǎn)，每個結(jié)點(diǎn)最多只需一個直接前驅(qū)、個根結(jié)點(diǎn)，每個結(jié)點(diǎn)最多只需一個直接前驅(qū)、最多只需一個直接后繼。最多只需一

15、個直接后繼。非線性構(gòu)造：不是線性構(gòu)造的數(shù)據(jù)構(gòu)造。非線性構(gòu)造：不是線性構(gòu)造的數(shù)據(jù)構(gòu)造。線性表及其順序存儲構(gòu)造線性表及其順序存儲構(gòu)造1、線性表、線性表線性表是由線性表是由 n (n0)個元素組成的有限序列：個元素組成的有限序列：(a1,a2,ai,an)有且只需一個根結(jié)點(diǎn)，它無直接前驅(qū)。有且只需一個根結(jié)點(diǎn)，它無直接前驅(qū)。有且只需一個終端結(jié)點(diǎn)，它無直接后繼。有且只需一個終端結(jié)點(diǎn)，它無直接后繼。除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他一切結(jié)點(diǎn)都除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他一切結(jié)點(diǎn)都有且只需一個直接前驅(qū)和直接后繼。結(jié)點(diǎn)個有且只需一個直接前驅(qū)和直接后繼。結(jié)點(diǎn)個數(shù)數(shù)n稱為線性表的長度。稱為線性表的長度。n=0時(shí)，稱為空表。

16、時(shí)，稱為空表。2、線性表的順序存儲、線性表的順序存儲順序存儲也稱為順序分配順序存儲也稱為順序分配線性表中一切元素所占的存儲空間是延續(xù)的線性表中一切元素所占的存儲空間是延續(xù)的線性表中各元素在存儲空間中按照邏輯順序線性表中各元素在存儲空間中按照邏輯順序依次存儲依次存儲3、順序表的運(yùn)算、順序表的運(yùn)算線性表的順序存儲構(gòu)造通常稱為順序表線性表的順序存儲構(gòu)造通常稱為順序表包括：插入、刪除、查找、分解、合并、復(fù)包括：插入、刪除、查找、分解、合并、復(fù)制、制、逆轉(zhuǎn)等。逆轉(zhuǎn)等。在高級言語中，順序表對應(yīng)一維數(shù)組。在高級言語中，順序表對應(yīng)一維數(shù)組。順序表的查找方便，插入和刪除較費(fèi)事。順序表的查找方便，插入和刪除較費(fèi)事

17、。線性表及其順序存儲構(gòu)造線性表及其順序存儲構(gòu)造留意：留意： 線性表屬于線性構(gòu)造。線性表屬于線性構(gòu)造。 線性表的順序存儲構(gòu)造通常稱為順序表。線性表的順序存儲構(gòu)造通常稱為順序表。 在順序表中，一切元素按照其邏輯順序在順序表中，一切元素按照其邏輯順序延續(xù)存儲，前后件元素緊鄰，前件元素一定延續(xù)存儲，前后件元素緊鄰，前件元素一定存儲在后件元素的前面。邏輯上相鄰的數(shù)據(jù)存儲在后件元素的前面。邏輯上相鄰的數(shù)據(jù)元素物理上也相鄰元素物理上也相鄰 在程序設(shè)計(jì)言語中，線性表的順序存儲在程序設(shè)計(jì)言語中，線性表的順序存儲構(gòu)造對應(yīng)了一維數(shù)組。由于在程序設(shè)計(jì)言語構(gòu)造對應(yīng)了一維數(shù)組。由于在程序設(shè)計(jì)言語中，一維數(shù)組與計(jì)算機(jī)中實(shí)踐

18、的存儲空間構(gòu)中，一維數(shù)組與計(jì)算機(jī)中實(shí)踐的存儲空間構(gòu)造是一致的。造是一致的。 在順序表中，假設(shè)要在第在順序表中，假設(shè)要在第 i 個位置插入一個位置插入一個新元素，那么原第個新元素，那么原第 i 個元素以及之后的一個元素以及之后的一切元素都要依次后移一個位置。在平均情況切元素都要依次后移一個位置。在平均情況下，在順序表中插入一個新元素，需求挪動下，在順序表中插入一個新元素，需求挪動 n/2 個元素。個元素。 在順序表中，假設(shè)要刪除第在順序表中，假設(shè)要刪除第 i 個位置的元個位置的元素，那么原第素，那么原第 i 個元素之后的一切元素都要個元素之后的一切元素都要依次前移一個位置。在平均情況下，在順序依

19、次前移一個位置。在平均情況下，在順序表中刪除一個元素，需求挪動表中刪除一個元素，需求挪動 n/2 個元素。個元素。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法棧及其根本運(yùn)算棧及其根本運(yùn)算1、棧、棧棧棧(stack)是限定在一端進(jìn)展插入和刪除的線是限定在一端進(jìn)展插入和刪除的線性表性表允許進(jìn)展插入或刪除的一端稱為棧頂。允許進(jìn)展插入或刪除的一端稱為棧頂。不允許進(jìn)展插入或刪除的另一端稱為棧底。不允許進(jìn)展插入或刪除的另一端稱為棧底。其特點(diǎn)為其特點(diǎn)為“先入后出先入后出(FILO)或或“后入先出后入先出(LIFO)。(記憶作用記憶作用)通常設(shè)置指針通常設(shè)置指針top指向棧頂，指針指向棧頂，指針bottom指指向棧底。向棧底

20、。2、棧的順序存儲構(gòu)造、棧的順序存儲構(gòu)造棧的各個數(shù)據(jù)元素按其邏輯順序依次延續(xù)存棧的各個數(shù)據(jù)元素按其邏輯順序依次延續(xù)存儲。儲。由于插入刪除操作只能在棧頂一端進(jìn)展，所由于插入刪除操作只能在棧頂一端進(jìn)展，所以以不需求挪動數(shù)據(jù)元素。不需求挪動數(shù)據(jù)元素。3、棧的根本運(yùn)算、棧的根本運(yùn)算入棧：在棧頂位置插入新元素。入棧：在棧頂位置插入新元素。出棧：取出棧頂位置的元素。出棧：取出棧頂位置的元素。讀棧頂元素：讀出棧頂位置的元素。讀棧頂元素：讀出棧頂位置的元素?！吧弦纾喝霔r(shí)堆棧已滿。上溢：入棧時(shí)堆棧已滿。“下溢：下溢：出棧時(shí)堆棧已空。出棧時(shí)堆棧已空。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法隊(duì)列及其根本運(yùn)算隊(duì)列及其根本運(yùn)算1

21、、隊(duì)列、隊(duì)列隊(duì)列隊(duì)列(queue)是限定在一端進(jìn)展插入另一端進(jìn)是限定在一端進(jìn)展插入另一端進(jìn)展刪除的線性表展刪除的線性表允許進(jìn)展插入的一端稱為隊(duì)尾。允許進(jìn)展插入的一端稱為隊(duì)尾。允許進(jìn)展刪除的另一端稱為隊(duì)頭。允許進(jìn)展刪除的另一端稱為隊(duì)頭。其特點(diǎn)為其特點(diǎn)為“先入先出先入先出(FIFO)或或“后入后出后入后出(LILO)。(先來先效力先來先效力)通常設(shè)置指針通常設(shè)置指針rear指向隊(duì)尾，指針指向隊(duì)尾，指針front指向指向隊(duì)頭。隊(duì)頭。2、隊(duì)列的順序存儲構(gòu)造、隊(duì)列的順序存儲構(gòu)造隊(duì)列的各個數(shù)據(jù)元素按其邏輯順序依次延續(xù)隊(duì)列的各個數(shù)據(jù)元素按其邏輯順序依次延續(xù)存儲。存儲。由于插入刪除操作只能在隊(duì)列的兩端進(jìn)展，由

22、于插入刪除操作只能在隊(duì)列的兩端進(jìn)展，所以所以不需求挪動數(shù)據(jù)元素。不需求挪動數(shù)據(jù)元素。3、隊(duì)列的根本運(yùn)算、隊(duì)列的根本運(yùn)算在實(shí)踐運(yùn)用中經(jīng)常運(yùn)用循環(huán)隊(duì)列。在實(shí)踐運(yùn)用中經(jīng)常運(yùn)用循環(huán)隊(duì)列。入隊(duì)：在隊(duì)尾位置插入新元素。入隊(duì)：在隊(duì)尾位置插入新元素。 出隊(duì)：取出隊(duì)頭位置的元素。出隊(duì)：取出隊(duì)頭位置的元素。 “上溢：入隊(duì)時(shí)隊(duì)列已滿。上溢：入隊(duì)時(shí)隊(duì)列已滿?！跋乱纾合乱纾撼鲫?duì)時(shí)隊(duì)列已空。出隊(duì)時(shí)隊(duì)列已空。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法線性鏈表線性鏈表1、鏈?zhǔn)酱鎯Ψ绞?、鏈?zhǔn)酱鎯Ψ绞?結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域(存儲數(shù)據(jù)存儲數(shù)據(jù))、指針域指針域(指向其前件或后件指向其前件或后件)。 數(shù)據(jù)構(gòu)造的存儲空間可

23、以不延續(xù)，存儲順數(shù)據(jù)構(gòu)造的存儲空間可以不延續(xù)，存儲順序與邏輯關(guān)系可以不一致。序與邏輯關(guān)系可以不一致。 鏈?zhǔn)酱鎯Ψ绞郊瓤梢杂脕肀硎揪€性構(gòu)造，鏈?zhǔn)酱鎯Ψ绞郊瓤梢杂脕肀硎揪€性構(gòu)造，也可以表示非線性構(gòu)造。也可以表示非線性構(gòu)造。2、線性鏈表、線性鏈表線性表的鏈?zhǔn)酱鎯?gòu)造稱為線性鏈表。線性表的鏈?zhǔn)酱鎯?gòu)造稱為線性鏈表。(棧的鏈?zhǔn)酱鎯?gòu)造稱為鏈棧、隊(duì)列的鏈?zhǔn)酱鏃５逆準(zhǔn)酱鎯?gòu)造稱為鏈棧、隊(duì)列的鏈?zhǔn)酱鎯?gòu)造稱為鏈隊(duì)列儲構(gòu)造稱為鏈隊(duì)列)常用的線性鏈表有：常用的線性鏈表有：單鏈表單鏈表 (一個指針域，指向直接后繼一個指針域，指向直接后繼)雙向鏈表雙向鏈表 (兩個指針域，指向直接后繼及后繼兩個指針域，指向直接后繼及后

24、繼) 循環(huán)鏈表循環(huán)鏈表 (一切結(jié)點(diǎn)的指針構(gòu)成循環(huán)鏈一切結(jié)點(diǎn)的指針構(gòu)成循環(huán)鏈)3、線性鏈表的根本運(yùn)算、線性鏈表的根本運(yùn)算查找：在線性鏈表中查找指定元素。查找：在線性鏈表中查找指定元素。插入：在線性鏈表中插入新結(jié)點(diǎn)。插入：在線性鏈表中插入新結(jié)點(diǎn)。刪除：在線性鏈表中刪除指定結(jié)點(diǎn)。刪除：在線性鏈表中刪除指定結(jié)點(diǎn)。表頭指針表頭指針data next newnodepnewnodep數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法樹的根本概念樹的根本概念1、樹、樹樹是一種簡單的非線性構(gòu)樹是一種簡單的非線性構(gòu)造。造。元素間的關(guān)系具有明顯的元素間的關(guān)系具有明顯的層次構(gòu)造。層次構(gòu)造。2、相關(guān)的術(shù)語、相關(guān)的術(shù)語根結(jié)點(diǎn)根結(jié)點(diǎn)葉節(jié)點(diǎn)葉節(jié)

25、點(diǎn)父結(jié)點(diǎn)父結(jié)點(diǎn)子結(jié)點(diǎn)子結(jié)點(diǎn)子樹子樹結(jié)點(diǎn)的度結(jié)點(diǎn)的度樹的度樹的度樹的深度樹的深度數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法二叉樹二叉樹1、二叉樹的特點(diǎn)、二叉樹的特點(diǎn)非空二叉樹只需一個根結(jié)點(diǎn)。非空二叉樹只需一個根結(jié)點(diǎn)。每個結(jié)點(diǎn)最多有左右兩棵子樹。每個結(jié)點(diǎn)最多有左右兩棵子樹。2、二叉樹的根本性質(zhì)、二叉樹的根本性質(zhì)第第 k 層上最多有層上最多有 2 k-1個結(jié)點(diǎn)個結(jié)點(diǎn)深度為深度為 m 的二叉樹最多有的二叉樹最多有 2m-1個結(jié)個結(jié)點(diǎn)點(diǎn)任何二叉樹葉結(jié)點(diǎn)總比度為任何二叉樹葉結(jié)點(diǎn)總比度為 2 的節(jié)點(diǎn)的節(jié)點(diǎn)多一個多一個n 個節(jié)點(diǎn)的二叉樹的深度為個節(jié)點(diǎn)的二叉樹的深度為 log2n+13、滿二叉樹、滿二叉樹4、完全二叉樹、完全

26、二叉樹5、二叉樹的遍歷、二叉樹的遍歷先序遍歷先序遍歷 中序遍歷中序遍歷后序遍后序遍歷歷ABDEGCFHI DBGEACHFIDGEBHIFCA數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法查找技術(shù)查找技術(shù)1、順序查找、順序查找從線性表的第一個元素開場，依次與指定數(shù)從線性表的第一個元素開場，依次與指定數(shù)據(jù)比較，假設(shè)相等那么查找勝利，假設(shè)比較據(jù)比較，假設(shè)相等那么查找勝利，假設(shè)比較的一切元素都不相等，那么查找失敗。的一切元素都不相等，那么查找失敗。最壞情況的比較次數(shù)為表長最壞情況的比較次數(shù)為表長n，平均情況為，平均情況為n/2。無序順序表的查找只能采用順序查找的方法。無序順序表的查找只能采用順序查找的方法。線性表在鏈

27、式存儲時(shí)也只能采用順序查找的線性表在鏈?zhǔn)酱鎯r(shí)也只能采用順序查找的方法。方法。2、二分法查找、二分法查找在順序存儲的線性表為有序的情況下，可以在順序存儲的線性表為有序的情況下，可以運(yùn)用二分法查找。運(yùn)用二分法查找。方法為：方法為：將待查數(shù)據(jù)與線性表的中間項(xiàng)比較：將待查數(shù)據(jù)與線性表的中間項(xiàng)比較：假設(shè)相等，那么查找勝利；假設(shè)相等，那么查找勝利；假設(shè)小于，那么在線性表的前半部分進(jìn)展假設(shè)小于，那么在線性表的前半部分進(jìn)展二分法查找；二分法查找；假設(shè)大于，那么在線性表的后半部分進(jìn)展假設(shè)大于，那么在線性表的后半部分進(jìn)展二分法查找；二分法查找；反復(fù)進(jìn)展直到相等反復(fù)進(jìn)展直到相等(查找勝利查找勝利)或子表長度或子表

28、長度為為0(查找失敗查找失敗)。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法排序技術(shù)排序技術(shù)1、交換類排序、交換類排序起泡排序起泡排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 快速排序快速排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 2、插入類排序、插入類排序簡單插入排序簡單插入排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 希爾排序希爾排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 O( n 1.5) 。3、選擇類排序、選擇類排序簡單項(xiàng)選擇擇排序簡單項(xiàng)選擇擇排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。堆排

29、序堆排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 O( n log2n) 。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法本章重點(diǎn)本章重點(diǎn)1、算法是問題處置方案正確而完好的描畫，算、算法是問題處置方案正確而完好的描畫，算法的效率與數(shù)據(jù)的存儲構(gòu)造有親密的關(guān)系。法的效率與數(shù)據(jù)的存儲構(gòu)造有親密的關(guān)系。2、數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表示、數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表示(存儲方存儲方式式)稱為數(shù)據(jù)的存儲構(gòu)造稱為數(shù)據(jù)的存儲構(gòu)造(物理構(gòu)造物理構(gòu)造)。一種邏。一種邏輯構(gòu)造可以有多種存儲構(gòu)造。輯構(gòu)造可以有多種存儲構(gòu)造。3、在長度為、在長度為 n 的順序表中，插入或刪除一個元的順序表中，插入或刪除一個元素平均需求挪動一半元素。

30、素平均需求挪動一半元素。4、棧是特殊的線性表，具有記憶作用。特點(diǎn)是、棧是特殊的線性表，具有記憶作用。特點(diǎn)是“先進(jìn)后出先進(jìn)后出(后進(jìn)先出后進(jìn)先出)。棧頂指針動態(tài)反映。棧頂指針動態(tài)反映了棧中元素的變化情況。了棧中元素的變化情況。5、隊(duì)列是特殊的線性表。特點(diǎn)是、隊(duì)列是特殊的線性表。特點(diǎn)是“先進(jìn)先出先進(jìn)先出(后后進(jìn)后出進(jìn)后出)。隊(duì)頭和隊(duì)尾指針動態(tài)地反映了隊(duì)。隊(duì)頭和隊(duì)尾指針動態(tài)地反映了隊(duì)列中元素的變化情況。列中元素的變化情況。6、線性鏈表是線性表的鏈?zhǔn)酱鎯?gòu)造。在線性、線性鏈表是線性表的鏈?zhǔn)酱鎯?gòu)造。在線性鏈表中，各元素節(jié)點(diǎn)的存儲空間可以不延續(xù)，鏈表中，各元素節(jié)點(diǎn)的存儲空間可以不延續(xù)，存儲順序也可以與邏

31、輯順序不一致。線性鏈存儲順序也可以與邏輯順序不一致。線性鏈表的插入刪除操作不需求挪動數(shù)據(jù)元素。表的插入刪除操作不需求挪動數(shù)據(jù)元素。7、二叉樹是一種非線性構(gòu)造。主要性質(zhì)有：、二叉樹是一種非線性構(gòu)造。主要性質(zhì)有：第第k層上最多有層上最多有 2 k-1 個結(jié)點(diǎn)個結(jié)點(diǎn)深度為深度為 m 時(shí)，最多有時(shí)，最多有2 m 1 個結(jié)點(diǎn)個結(jié)點(diǎn)度為度為0的結(jié)點(diǎn)比度為的結(jié)點(diǎn)比度為2的多一個的多一個深度至少為深度至少為 log2n +1數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法本章重點(diǎn)本章重點(diǎn)8、滿二叉樹是二叉樹的特殊形狀，滿二叉樹的、滿二叉樹是二叉樹的特殊形狀，滿二叉樹的各層結(jié)點(diǎn)都到達(dá)最大值，葉結(jié)點(diǎn)只出如今最各層結(jié)點(diǎn)都到達(dá)最大值，葉

32、結(jié)點(diǎn)只出如今最后一層。后一層。9、完全二叉樹是二叉樹的特殊形狀，完全二叉、完全二叉樹是二叉樹的特殊形狀，完全二叉樹除最后一層外，各層結(jié)點(diǎn)都到達(dá)最大值，樹除最后一層外，各層結(jié)點(diǎn)都到達(dá)最大值，葉結(jié)點(diǎn)只出如今最后兩層。滿二叉樹屬于完葉結(jié)點(diǎn)只出如今最后兩層。滿二叉樹屬于完全二叉樹。全二叉樹。10、根據(jù)掃描根結(jié)點(diǎn)的順序，按照先左后右的、根據(jù)掃描根結(jié)點(diǎn)的順序，按照先左后右的原那么，遍歷二叉樹有三種原那么，遍歷二叉樹有三種方法：前序遍歷、中序遍歷、后序遍歷。方法：前序遍歷、中序遍歷、后序遍歷。11、在長度為、在長度為 n 的線性表中進(jìn)展順序查找，最的線性表中進(jìn)展順序查找，最壞情況需求比較壞情況需求比較 n

33、次。次。12、在長度為、在長度為 n 的線性表中進(jìn)展對分查找，最的線性表中進(jìn)展對分查找，最壞情況需求比較壞情況需求比較 log2n 次。但對分查找只適用次。但對分查找只適用于有序順序表。于有序順序表。13、在冒泡排序、快速排序、簡單插入排序、在冒泡排序、快速排序、簡單插入排序、選擇排序的方法中，最壞情況下需求比較的選擇排序的方法中，最壞情況下需求比較的次數(shù)為次數(shù)為 n(n-1)/2 。程序設(shè)計(jì)根底程序設(shè)計(jì)根底關(guān)鍵考點(diǎn)關(guān)鍵考點(diǎn)構(gòu)造化設(shè)計(jì)的原那么構(gòu)造化設(shè)計(jì)的原那么面向?qū)ο蠓椒ǖ母靖拍蠲嫦驅(qū)ο蠓椒ǖ母靖拍畛绦蛟O(shè)計(jì)根底程序設(shè)計(jì)根底程序設(shè)計(jì)方法與風(fēng)格程序設(shè)計(jì)方法與風(fēng)格1、程序設(shè)計(jì)方法、程序設(shè)計(jì)方法就

34、程序設(shè)計(jì)的方法和技術(shù)的開展而言就程序設(shè)計(jì)的方法和技術(shù)的開展而言主要閱歷了構(gòu)造化程序設(shè)計(jì)和面向?qū)ο蟪讨饕啔v了構(gòu)造化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)兩個階段序設(shè)計(jì)兩個階段2、程序設(shè)計(jì)風(fēng)格、程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出來的程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出來的特點(diǎn)、習(xí)慣和邏輯思緒。特點(diǎn)、習(xí)慣和邏輯思緒。程序設(shè)計(jì)風(fēng)格會深化影響軟件的質(zhì)量和可維程序設(shè)計(jì)風(fēng)格會深化影響軟件的質(zhì)量和可維護(hù)性，良好的程序設(shè)計(jì)風(fēng)格可以使程序的構(gòu)護(hù)性，良好的程序設(shè)計(jì)風(fēng)格可以使程序的構(gòu)造明晰合理，使程序代碼便于維護(hù)。造明晰合理，使程序代碼便于維護(hù)。程序設(shè)計(jì)風(fēng)格的主導(dǎo)：程序設(shè)計(jì)風(fēng)格的主導(dǎo)：“明晰第一，效率第二明晰第一，效

35、率第二。主要要素：主要要素：源程序文檔化源程序文檔化數(shù)聽闡明的方法數(shù)聽闡明的方法語句的構(gòu)造語句的構(gòu)造輸入和輸出輸入和輸出程序設(shè)計(jì)根底程序設(shè)計(jì)根底構(gòu)造化程序設(shè)計(jì)構(gòu)造化程序設(shè)計(jì)1、構(gòu)造化程序設(shè)計(jì)、構(gòu)造化程序設(shè)計(jì)要求把程序的構(gòu)造限制為順序、選擇和循環(huán)要求把程序的構(gòu)造限制為順序、選擇和循環(huán)三種根本構(gòu)造。三種根本構(gòu)造。2、構(gòu)造化程序設(shè)計(jì)的原那么、構(gòu)造化程序設(shè)計(jì)的原那么自頂向下自頂向下先總體后細(xì)節(jié)，先全局后部分。先總體后細(xì)節(jié)，先全局后部分。逐漸求精逐漸求精對復(fù)雜問題設(shè)計(jì)子目的過度，對復(fù)雜問題設(shè)計(jì)子目的過度，逐漸細(xì)化。逐漸細(xì)化。模塊化模塊化 將復(fù)雜問題分解為假設(shè)干簡單問題。將復(fù)雜問題分解為假設(shè)干簡單問題。限

36、制運(yùn)用限制運(yùn)用GOTO語句語句防止呵斥程序邏輯構(gòu)防止呵斥程序邏輯構(gòu)造混亂。造混亂。3、三種根本構(gòu)造、三種根本構(gòu)造順序構(gòu)造順序構(gòu)造 選擇構(gòu)造選擇構(gòu)造循環(huán)構(gòu)造循環(huán)構(gòu)造4、特點(diǎn)、特點(diǎn)一切控制構(gòu)造由三種根本構(gòu)造組成一切控制構(gòu)造由三種根本構(gòu)造組成各個模塊單入口單出口各個模塊單入口單出口模塊的內(nèi)聚性強(qiáng)模塊的內(nèi)聚性強(qiáng) 模塊間的巧合性低模塊間的巧合性低程序設(shè)計(jì)根底程序設(shè)計(jì)根底面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)1、面向?qū)ο?、面向?qū)ο竺嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，是從客觀世界固有的面向?qū)ο蠓椒ǖ谋举|(zhì)，是從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，用現(xiàn)實(shí)生活中常用的事物出發(fā)來構(gòu)造系統(tǒng)，用現(xiàn)實(shí)生活中常用的思想方法來描畫客觀事物，是系

37、統(tǒng)中的對象思想方法來描畫客觀事物，是系統(tǒng)中的對象及對象間的關(guān)系能照實(shí)反映事物及其關(guān)系。及對象間的關(guān)系能照實(shí)反映事物及其關(guān)系。2、主要優(yōu)點(diǎn)、主要優(yōu)點(diǎn)與人類習(xí)慣的思想方法一致與人類習(xí)慣的思想方法一致穩(wěn)定性好穩(wěn)定性好可重用性好可重用性好易于開發(fā)大型軟件產(chǎn)品易于開發(fā)大型軟件產(chǎn)品可維護(hù)性好可維護(hù)性好3、根本概念、根本概念對象對象類和實(shí)例類和實(shí)例音訊音訊承繼承繼多態(tài)性多態(tài)性程序設(shè)計(jì)根底程序設(shè)計(jì)根底本章重點(diǎn)本章重點(diǎn)1、程序設(shè)計(jì)并不等于編程，編程只是程序設(shè)、程序設(shè)計(jì)并不等于編程，編程只是程序設(shè)計(jì)過程中的一小步。計(jì)過程中的一小步。2、構(gòu)造化程序設(shè)計(jì)要求把程序的構(gòu)造限制為、構(gòu)造化程序設(shè)計(jì)要求把程序的構(gòu)造限制為順序

38、、選擇、循環(huán)三種根本構(gòu)造。順序、選擇、循環(huán)三種根本構(gòu)造。3、模塊化設(shè)計(jì)是指把一個大程序按人們能了、模塊化設(shè)計(jì)是指把一個大程序按人們能了解的大小規(guī)模進(jìn)展分解。劃分模塊的根本原解的大小規(guī)模進(jìn)展分解。劃分模塊的根本原那么是使每個模塊都易于了解。在按功能劃那么是使每個模塊都易于了解。在按功能劃分模塊時(shí)，要求各模塊功能盡量單一，各模分模塊時(shí)，要求各模塊功能盡量單一，各模塊之間的聯(lián)絡(luò)盡量的少。塊之間的聯(lián)絡(luò)盡量的少。4、客觀世界是由實(shí)體及其聯(lián)絡(luò)所組成的?？汀⒖陀^世界是由實(shí)體及其聯(lián)絡(luò)所組成的?？陀^世界中的實(shí)體稱為問題域的對象。觀世界中的實(shí)體稱為問題域的對象。5、類描畫的是具有類似性質(zhì)一組對象。一個、類描畫的是

39、具有類似性質(zhì)一組對象。一個對象稱為類的實(shí)例。對象稱為類的實(shí)例。6、允許作用于某個對象上的各種操作稱為方、允許作用于某個對象上的各種操作稱為方法。法。7、音訊是用來懇求對象執(zhí)行某一處置或回答、音訊是用來懇求對象執(zhí)行某一處置或回答某些信息的要求。某些信息的要求。8、承繼是表示類之間的類似性的一種機(jī)制。、承繼是表示類之間的類似性的一種機(jī)制。9、封裝是一種信息隱蔽機(jī)制，目的是將對象、封裝是一種信息隱蔽機(jī)制，目的是將對象的運(yùn)用者與對象的設(shè)計(jì)者分開。用戶只需了的運(yùn)用者與對象的設(shè)計(jì)者分開。用戶只需了解對象封裝界面上的信息，不用知道內(nèi)部的解對象封裝界面上的信息，不用知道內(nèi)部的詳細(xì)細(xì)節(jié)。詳細(xì)細(xì)節(jié)。軟件工程根底軟

40、件工程根底關(guān)鍵考點(diǎn)關(guān)鍵考點(diǎn)軟件定義與特點(diǎn)軟件定義與特點(diǎn)軟件開發(fā)過程的過程化原那么軟件開發(fā)過程的過程化原那么構(gòu)造化分析方法構(gòu)造化分析方法構(gòu)造化設(shè)計(jì)方法構(gòu)造化設(shè)計(jì)方法軟件測試技術(shù)與方法軟件測試技術(shù)與方法程序調(diào)試根本概念程序調(diào)試根本概念軟件工程根底軟件工程根底軟件工程根本概念軟件工程根本概念1、軟件、軟件軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完好集軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完好集合。合。2、軟件的特點(diǎn)、軟件的特點(diǎn)籠統(tǒng)性籠統(tǒng)性可大量拷貝可大量拷貝無磨損及老化問題無磨損及老化問題受計(jì)算機(jī)系統(tǒng)限制受計(jì)算機(jī)系統(tǒng)限制(移植問移植問題題)復(fù)雜性高本錢昂貴復(fù)雜性高本錢昂貴開發(fā)過程涉及諸多社會要開發(fā)過程涉及諸多社會

41、要素素3、軟件工程、軟件工程軟件工程是運(yùn)用于計(jì)算機(jī)軟件的定義、開發(fā)軟件工程是運(yùn)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)際規(guī)和維護(hù)的一整套方法、工具、文檔、實(shí)際規(guī)范和工序。范和工序。三個要素三個要素方法：完成軟件工程工程的技術(shù)手段。方法：完成軟件工程工程的技術(shù)手段。工具：支持軟件的開發(fā)、管理、文檔生成。工具：支持軟件的開發(fā)、管理、文檔生成。過程：支持軟件開發(fā)各個環(huán)節(jié)的管理、控過程：支持軟件開發(fā)各個環(huán)節(jié)的管理、控制。制。目的：在給定本錢、進(jìn)度的前提下，開發(fā)出目的：在給定本錢、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可了解性、可維護(hù)性、具有有效性、可靠性、可了解性、可維護(hù)性、可順

42、應(yīng)性、可追蹤性、可互操作性滿足用戶可順應(yīng)性、可追蹤性、可互操作性滿足用戶要求的軟件產(chǎn)品。要求的軟件產(chǎn)品。軟件工程根底軟件工程根底軟件開發(fā)過程的過程化原那么軟件開發(fā)過程的過程化原那么1、軟件工程過程、軟件工程過程 為獲得軟件產(chǎn)品，在軟件工具支持下的一為獲得軟件產(chǎn)品，在軟件工具支持下的一系列軟件工程活動。系列軟件工程活動。Plan 軟件規(guī)格闡明。軟件規(guī)格闡明。Do軟件軟件開發(fā)。開發(fā)。Check軟件確認(rèn)。軟件確認(rèn)。Action軟件演進(jìn)。軟件演進(jìn)。 運(yùn)用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)展的一組運(yùn)用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)展的一組開發(fā)活動，在過程終了時(shí)將用戶要求轉(zhuǎn)化為開發(fā)活動，在過程終了時(shí)將用戶要求轉(zhuǎn)化為軟件產(chǎn)

43、品。軟件產(chǎn)品。軟件工程過程應(yīng)確定方法運(yùn)用的順序、要求軟件工程過程應(yīng)確定方法運(yùn)用的順序、要求交付的文檔資料、為保證質(zhì)量與順應(yīng)變化所交付的文檔資料、為保證質(zhì)量與順應(yīng)變化所需求的管理、軟件開發(fā)各階段要完成的義務(wù)。需求的管理、軟件開發(fā)各階段要完成的義務(wù)。2、軟件生命周期、軟件生命周期 定義階段定義階段可行性研討及工程方案可行性研討及工程方案需求分需求分析析 開發(fā)階段開發(fā)階段概要設(shè)計(jì)概要設(shè)計(jì)詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)實(shí)現(xiàn)測試測試 維護(hù)階段維護(hù)階段運(yùn)用運(yùn)用維護(hù)維護(hù)退役退役軟件工程根底軟件工程根底構(gòu)造化分析方法構(gòu)造化分析方法在系統(tǒng)分析階段，構(gòu)造化分析方法用來對系統(tǒng)在系統(tǒng)分析階段，構(gòu)造化分析方法用來對系統(tǒng)進(jìn)展邏輯設(shè)

44、計(jì)。進(jìn)展邏輯設(shè)計(jì)。1、需求分析、需求分析需求分析的義務(wù)是發(fā)現(xiàn)需求、求精、建模和需求分析的義務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求。定義需求。 常見的需求分析方法：構(gòu)造化分析方法常見的需求分析方法：構(gòu)造化分析方法 面向?qū)ο蟮姆治龇椒嫦驅(qū)ο蟮姆治龇椒?、構(gòu)造化分析方法、構(gòu)造化分析方法 構(gòu)造化分析就是運(yùn)用數(shù)據(jù)流圖構(gòu)造化分析就是運(yùn)用數(shù)據(jù)流圖(DFD)、數(shù)據(jù)、數(shù)據(jù)字典字典(DD)、構(gòu)造化英語、斷定表和斷定樹等、構(gòu)造化英語、斷定表和斷定樹等工具，來建立一種被稱為構(gòu)造化規(guī)格闡明的工具，來建立一種被稱為構(gòu)造化規(guī)格闡明的目的文檔。目的文檔。 構(gòu)造化分析方法的本質(zhì)是著眼于構(gòu)造化分析方法的本質(zhì)是著眼于數(shù)據(jù)流的、自頂向

45、下逐層分解的、建立系統(tǒng)數(shù)據(jù)流的、自頂向下逐層分解的、建立系統(tǒng)的處置流程，它以數(shù)據(jù)流圖和數(shù)據(jù)字典為主的處置流程，它以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。要工具，建立系統(tǒng)的邏輯模型。3、 軟件需求規(guī)格闡明書軟件需求規(guī)格闡明書是需求分析階段的最后成果，是軟件開發(fā)的是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。重要文檔之一。軟件需求規(guī)格闡明書把軟件方案中確定的軟軟件需求規(guī)格闡明書把軟件方案中確定的軟件范圍加以展開，制定出完好的信息描畫、件范圍加以展開，制定出完好的信息描畫、詳細(xì)的功能闡明、恰當(dāng)?shù)臋z驗(yàn)規(guī)范、其他與詳細(xì)的功能闡明、恰當(dāng)?shù)臋z驗(yàn)規(guī)范、其他與要求有關(guān)的信息。要求有關(guān)的信息。軟

46、件工程根底軟件工程根底構(gòu)造化設(shè)計(jì)方法構(gòu)造化設(shè)計(jì)方法1、軟件設(shè)計(jì)、軟件設(shè)計(jì)軟件設(shè)計(jì)是把軟件需求轉(zhuǎn)換為軟件表示的過軟件設(shè)計(jì)是把軟件需求轉(zhuǎn)換為軟件表示的過程。程。從技術(shù)角度：軟件設(shè)計(jì)包括構(gòu)造設(shè)計(jì)、數(shù)據(jù)從技術(shù)角度：軟件設(shè)計(jì)包括構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。從工程角度：軟件設(shè)計(jì)包括概要設(shè)計(jì)、詳細(xì)從工程角度：軟件設(shè)計(jì)包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)。設(shè)計(jì)。軟件設(shè)計(jì)的根本原理包括：籠統(tǒng)、模塊化、軟件設(shè)計(jì)的根本原理包括：籠統(tǒng)、模塊化、信息隱蔽、模塊獨(dú)立性信息隱蔽、模塊獨(dú)立性2、概要設(shè)計(jì)、概要設(shè)計(jì)概要設(shè)計(jì)的根本義務(wù)：系統(tǒng)構(gòu)造設(shè)計(jì)概要設(shè)計(jì)的根本義務(wù)：系統(tǒng)構(gòu)造設(shè)計(jì)數(shù)數(shù)據(jù)構(gòu)造設(shè)計(jì)據(jù)構(gòu)造設(shè)計(jì)編

47、寫設(shè)計(jì)文檔編寫設(shè)計(jì)文檔設(shè)計(jì)文設(shè)計(jì)文檔評審檔評審構(gòu)造圖是軟件構(gòu)造設(shè)計(jì)的常用工具。構(gòu)造圖是軟件構(gòu)造設(shè)計(jì)的常用工具。3、詳細(xì)設(shè)計(jì)、詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)的義務(wù)，是為軟件構(gòu)造圖中的每一詳細(xì)設(shè)計(jì)的義務(wù)，是為軟件構(gòu)造圖中的每一個模塊確定算法和部分?jǐn)?shù)據(jù)構(gòu)造，用某種選個模塊確定算法和部分?jǐn)?shù)據(jù)構(gòu)造，用某種選定的工具表示算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。定的工具表示算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。常見的設(shè)計(jì)工具：常見的設(shè)計(jì)工具：圖形工具：流程圖、圖形工具：流程圖、N - S、PAD、HIPO表格工具：斷定表表格工具：斷定表言語工具：言語工具：PDL(偽碼偽碼)軟件工程根底軟件工程根底軟件測試軟件測試1、測試、測試軟件測試的目的是在精心控制的

48、環(huán)境下執(zhí)行軟件測試的目的是在精心控制的環(huán)境下執(zhí)行程序，以發(fā)現(xiàn)程序中的錯誤，給出程序可靠程序，以發(fā)現(xiàn)程序中的錯誤，給出程序可靠性的鑒定。性的鑒定。測試不是為了證明程序是正確的，目的是設(shè)測試不是為了證明程序是正確的，目的是設(shè)法暴露程序中的錯誤和缺陷。法暴露程序中的錯誤和缺陷。測試只能闡明程序有錯，不能證明程序無錯。測試只能闡明程序有錯，不能證明程序無錯。程序不能程序不能100%可靠?？煽?。2、測試方法、測試方法程序的靜態(tài)分析程序的靜態(tài)分析程序的動態(tài)分析程序的動態(tài)分析自自動測試工具動測試工具3、測試層次、測試層次模塊測試模塊測試(單元測試單元測試)整體測試整體測試(集成測試集成測試)又分為又分為 功

49、能測試功能測試 和和 驗(yàn)收測試驗(yàn)收測試 兩種。兩種。4、白盒法、白盒法根據(jù)對程序內(nèi)部邏輯構(gòu)造的分析來導(dǎo)出測試根據(jù)對程序內(nèi)部邏輯構(gòu)造的分析來導(dǎo)出測試用例。用例。5、黑盒法、黑盒法不思索程序的內(nèi)部構(gòu)造特征，根據(jù)程序功能不思索程序的內(nèi)部構(gòu)造特征，根據(jù)程序功能導(dǎo)出測試用例。導(dǎo)出測試用例。軟件工程根底軟件工程根底程序調(diào)試程序調(diào)試1、調(diào)試與測試、調(diào)試與測試 測試的目的是發(fā)現(xiàn)錯誤，評價(jià)可靠性；調(diào)測試的目的是發(fā)現(xiàn)錯誤，評價(jià)可靠性；調(diào)試的目的是發(fā)現(xiàn)錯誤的位置，矯正發(fā)現(xiàn)的錯試的目的是發(fā)現(xiàn)錯誤的位置，矯正發(fā)現(xiàn)的錯誤。誤。 測試提示設(shè)計(jì)人員的過失，由非設(shè)計(jì)人員測試提示設(shè)計(jì)人員的過失，由非設(shè)計(jì)人員承當(dāng)；調(diào)試協(xié)助設(shè)計(jì)人員

50、矯正錯誤，由設(shè)計(jì)承當(dāng)；調(diào)試協(xié)助設(shè)計(jì)人員矯正錯誤，由設(shè)計(jì)人員本人承當(dāng)。人員本人承當(dāng)。 測試是機(jī)械的、強(qiáng)迫的、嚴(yán)厲的、可預(yù)測測試是機(jī)械的、強(qiáng)迫的、嚴(yán)厲的、可預(yù)測的；調(diào)試要求隨機(jī)應(yīng)變、聯(lián)想、閱歷、智力，的；調(diào)試要求隨機(jī)應(yīng)變、聯(lián)想、閱歷、智力，并要求自主地完成。并要求自主地完成。 測試發(fā)現(xiàn)的錯誤可立刻進(jìn)展調(diào)試矯正，然測試發(fā)現(xiàn)的錯誤可立刻進(jìn)展調(diào)試矯正，然后還必需再進(jìn)展測試。后還必需再進(jìn)展測試。 調(diào)試用例與測試用例可以一致也可以不一調(diào)試用例與測試用例可以一致也可以不一致。致。2、調(diào)試方法、調(diào)試方法 強(qiáng)行排錯法強(qiáng)行排錯法 回溯法回溯法 緣由排除法緣由排除法軟件工程根底軟件工程根底本章重點(diǎn)本章重點(diǎn)1、軟件生命

51、周期分為三個時(shí)期共八個階段：、軟件生命周期分為三個時(shí)期共八個階段：軟件定義期：問題定義、可行性研討、需求軟件定義期：問題定義、可行性研討、需求分析。分析。軟件開發(fā)期：系統(tǒng)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、軟件開發(fā)期：系統(tǒng)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測試。測試。軟件維護(hù)期：運(yùn)轉(zhuǎn)維護(hù)。軟件維護(hù)期：運(yùn)轉(zhuǎn)維護(hù)。2、在系統(tǒng)分析階段，構(gòu)造化分析方法用來對、在系統(tǒng)分析階段，構(gòu)造化分析方法用來對系統(tǒng)進(jìn)展邏輯設(shè)計(jì)，此時(shí)不思索物理實(shí)現(xiàn)的系統(tǒng)進(jìn)展邏輯設(shè)計(jì)，此時(shí)不思索物理實(shí)現(xiàn)的問題，而只思索問題，而只思索“做什么的問題，系統(tǒng)的物做什么的問題，系統(tǒng)的物理設(shè)計(jì)理設(shè)計(jì)(“如何做如何做)的問題留在系統(tǒng)設(shè)計(jì)階段的問題留在系統(tǒng)設(shè)計(jì)階段用構(gòu)造化設(shè)計(jì)

52、方法來完成。用構(gòu)造化設(shè)計(jì)方法來完成。3、數(shù)據(jù)流圖有兩種典型的構(gòu)造方式：變換型、數(shù)據(jù)流圖有兩種典型的構(gòu)造方式：變換型、事務(wù)型。事務(wù)型。4、評價(jià)模塊的獨(dú)立性的規(guī)范有兩個：、評價(jià)模塊的獨(dú)立性的規(guī)范有兩個：耦合性：闡明兩個模塊間聯(lián)絡(luò)的強(qiáng)弱。耦合性：闡明兩個模塊間聯(lián)絡(luò)的強(qiáng)弱。內(nèi)聚性：闡明模塊內(nèi)部聯(lián)絡(luò)能否嚴(yán)密。內(nèi)聚性：闡明模塊內(nèi)部聯(lián)絡(luò)能否嚴(yán)密。內(nèi)聚性要強(qiáng)，巧合性要弱。內(nèi)聚性要強(qiáng)，巧合性要弱。5、軟件測試是在精心控制的環(huán)境下執(zhí)行程序，、軟件測試是在精心控制的環(huán)境下執(zhí)行程序，發(fā)現(xiàn)程序中的錯誤，給出程序可靠性的鑒定。發(fā)現(xiàn)程序中的錯誤，給出程序可靠性的鑒定。6、測試是程序執(zhí)行的過程，目的在于發(fā)現(xiàn)錯、測試是程序執(zhí)行

53、的過程，目的在于發(fā)現(xiàn)錯誤；一個好的測試在于能發(fā)現(xiàn)至今未能發(fā)現(xiàn)誤；一個好的測試在于能發(fā)現(xiàn)至今未能發(fā)現(xiàn)的錯誤，一個勝利的測試是發(fā)現(xiàn)了至今未發(fā)的錯誤，一個勝利的測試是發(fā)現(xiàn)了至今未發(fā)現(xiàn)的錯誤?，F(xiàn)的錯誤。7、測試發(fā)現(xiàn)錯誤后，可進(jìn)展調(diào)試；調(diào)試后的、測試發(fā)現(xiàn)錯誤后，可進(jìn)展調(diào)試；調(diào)試后的程序還應(yīng)再測試，以檢驗(yàn)調(diào)試效果。程序還應(yīng)再測試，以檢驗(yàn)調(diào)試效果。數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底關(guān)鍵考點(diǎn)關(guān)鍵考點(diǎn)數(shù)據(jù)庫系統(tǒng)根本概念數(shù)據(jù)庫系統(tǒng)根本概念數(shù)據(jù)模型數(shù)據(jù)模型數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫系統(tǒng)的根本概念數(shù)據(jù)庫系統(tǒng)的根本概念1、數(shù)據(jù)庫、數(shù)據(jù)庫 DB是數(shù)據(jù)的集合，具有一致的構(gòu)造方式并存放是數(shù)據(jù)的集合，具有一致的構(gòu)造方式并存放

54、于一致的存儲介質(zhì)中，是多種運(yùn)用數(shù)據(jù)的集于一致的存儲介質(zhì)中，是多種運(yùn)用數(shù)據(jù)的集成，可被各個運(yùn)用程序所共享。成，可被各個運(yùn)用程序所共享。2、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng) DBMS數(shù)據(jù)庫的管理機(jī)構(gòu)，系統(tǒng)軟件，擔(dān)任數(shù)據(jù)組數(shù)據(jù)庫的管理機(jī)構(gòu)，系統(tǒng)軟件，擔(dān)任數(shù)據(jù)組織、支配、維護(hù)、控制、維護(hù)等?？?、支配、維護(hù)、控制、維護(hù)等。為數(shù)據(jù)庫構(gòu)作方式為數(shù)據(jù)庫構(gòu)作方式為數(shù)據(jù)方式的實(shí)現(xiàn)提供方法和手段為數(shù)據(jù)方式的實(shí)現(xiàn)提供方法和手段為用戶運(yùn)用提供查詢、插入、修正、刪除為用戶運(yùn)用提供查詢、插入、修正、刪除等功能等功能提供對數(shù)據(jù)庫中數(shù)據(jù)的多種效力功能提供對數(shù)據(jù)庫中數(shù)據(jù)的多種效力功能(復(fù)復(fù)制、重組、檢測等制、重組、檢測等)。3、D

55、BMS提供的言語提供的言語數(shù)據(jù)定義言語數(shù)據(jù)定義言語數(shù)據(jù)支配言語數(shù)據(jù)支配言語數(shù)據(jù)控制言語數(shù)據(jù)控制言語數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫系統(tǒng)的根本概念數(shù)據(jù)庫系統(tǒng)的根本概念4、數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)庫系統(tǒng) DBS由由DB、DBMS、數(shù)據(jù)庫管理員、數(shù)據(jù)庫管理員(DBA)、硬件、硬件平臺、軟件平臺組成。平臺、軟件平臺組成。5、數(shù)據(jù)庫系統(tǒng)的根本特點(diǎn)、數(shù)據(jù)庫系統(tǒng)的根本特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的集成性數(shù)據(jù)的高共享性低冗余性數(shù)據(jù)的高共享性低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)一致管理和控制數(shù)據(jù)一致管理和控制6、數(shù)據(jù)庫系統(tǒng)的三級方式、數(shù)據(jù)庫系統(tǒng)的三級方式概念方式：概念方式：數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯描畫，與詳細(xì)的數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)

56、的邏輯描畫，與詳細(xì)的軟硬件環(huán)境無關(guān)。軟硬件環(huán)境無關(guān)。外方式：外方式：也叫用戶方式，是用戶的數(shù)據(jù)視圖。也叫用戶方式，是用戶的數(shù)據(jù)視圖。內(nèi)方式：內(nèi)方式：也叫物理方式，描畫數(shù)據(jù)庫中數(shù)據(jù)的存儲也叫物理方式，描畫數(shù)據(jù)庫中數(shù)據(jù)的存儲構(gòu)造和存取方式。構(gòu)造和存取方式。數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)模型數(shù)據(jù)模型1、三種不同運(yùn)用層次的數(shù)據(jù)模型、三種不同運(yùn)用層次的數(shù)據(jù)模型概念模型：概念模型：概念數(shù)據(jù)模型，面向客觀世界、面向用戶，概念數(shù)據(jù)模型，面向客觀世界、面向用戶，與詳細(xì)的與詳細(xì)的DBMS無關(guān)。無關(guān)。數(shù)據(jù)模型：數(shù)據(jù)模型：邏輯數(shù)據(jù)模型，面向邏輯數(shù)據(jù)模型，面向DBS的模型，著重于數(shù)的模型，著重于數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)。據(jù)庫

57、系統(tǒng)的實(shí)現(xiàn)。物理模型：物理模型：物理數(shù)據(jù)模型，面向計(jì)算機(jī)系統(tǒng)，是數(shù)據(jù)模物理數(shù)據(jù)模型，面向計(jì)算機(jī)系統(tǒng)，是數(shù)據(jù)模型的物理表示。型的物理表示。2、實(shí)體集之間的聯(lián)絡(luò)、實(shí)體集之間的聯(lián)絡(luò)一對一一對一 一對多或多對一一對多或多對一多對多多對多3、E - R模型的圖示法模型的圖示法實(shí)體集表示法：在實(shí)體集表示法：在E - R圖中用矩形表示實(shí)體圖中用矩形表示實(shí)體集，矩形內(nèi)注明實(shí)體集稱號。集，矩形內(nèi)注明實(shí)體集稱號。屬性表示法：在屬性表示法：在E - R圖中用橢圓，橢圓中注圖中用橢圓，橢圓中注明屬性稱號。明屬性稱號。聯(lián)絡(luò)表示法：在聯(lián)絡(luò)表示法：在E - R圖中用菱形表示聯(lián)絡(luò)，圖中用菱形表示聯(lián)絡(luò)，菱形中注明聯(lián)絡(luò)稱號。菱形

58、中注明聯(lián)絡(luò)稱號。實(shí)體集與屬性之間的銜接關(guān)系：在實(shí)體集與屬性之間的銜接關(guān)系：在E - R圖中圖中用銜接兩個圖形的無向線段表示。用銜接兩個圖形的無向線段表示。數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)模型數(shù)據(jù)模型4、層次模型、層次模型 層次模型的根本構(gòu)造是樹形構(gòu)造。層次模型的根本構(gòu)造是樹形構(gòu)造。5、網(wǎng)狀模型、網(wǎng)狀模型網(wǎng)狀模型是一個不加任何條件限制的無向圖。網(wǎng)狀模型是一個不加任何條件限制的無向圖。6、關(guān)系模型、關(guān)系模型關(guān)系模型用二維表表示關(guān)系。關(guān)系模型用二維表表示關(guān)系。二維表有表框架二維表有表框架(關(guān)系方式關(guān)系方式)和表元組組成。和表元組組成。表框架由表框架由n個命名的屬性組成。個命名的屬性組成。屬性的取值范

59、圍稱為值域。屬性的取值范圍稱為值域。二維表中可以獨(dú)一標(biāo)識元組的最小屬性集成二維表中可以獨(dú)一標(biāo)識元組的最小屬性集成為為“鍵鍵(關(guān)鍵字關(guān)鍵字)。二維表中能夠有假設(shè)干鍵，稱為侯選鍵二維表中能夠有假設(shè)干鍵，稱為侯選鍵(侯選侯選關(guān)鍵字關(guān)鍵字) 。侯選鍵中選擇作為用戶運(yùn)用的稱為主鍵侯選鍵中選擇作為用戶運(yùn)用的稱為主鍵(主關(guān)主關(guān)鍵字鍵字) 。關(guān)系框架和關(guān)系元組構(gòu)成關(guān)系。關(guān)系框架和關(guān)系元組構(gòu)成關(guān)系。數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底關(guān)系代數(shù)關(guān)系代數(shù)1、關(guān)系模型的根本操作、關(guān)系模型的根本操作插入插入刪除刪除 修正修正 查詢查詢2、根本運(yùn)算、根本運(yùn)算并運(yùn)算并運(yùn)算(插入插入)差運(yùn)算差運(yùn)算(刪除刪除)投影投影(查詢查詢)選擇選擇(查詢查詢) 笛卡爾積笛卡爾積(查詢查詢)交運(yùn)算交運(yùn)算除運(yùn)算除運(yùn)算銜接運(yùn)算銜接運(yùn)算(有條件的笛卡爾積有條件的笛卡爾積) 自然銜接運(yùn)算自然銜接運(yùn)算(公共域等值銜接公共域等值銜接)數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)根底數(shù)據(jù)庫設(shè)計(jì)與管理數(shù)據(jù)庫設(shè)計(jì)與管理1、數(shù)據(jù)庫設(shè)計(jì)、數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)的根本義務(wù)是根據(jù)用戶的