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

1、全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)二級(jí)公共公共根底根底知識(shí)知識(shí)考試大綱考試大綱根本要求根本要求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)展軟件開(kāi)發(fā)的才干。運(yùn)用相關(guān)技術(shù)進(jìn)展軟件開(kāi)發(fā)的才干。6、掌握數(shù)據(jù)庫(kù)的根本知識(shí)，了解關(guān)系數(shù)、掌握數(shù)據(jù)庫(kù)的根本知識(shí)，了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。據(jù)庫(kù)的設(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)造和存儲(chǔ)、數(shù)據(jù)構(gòu)造的定義；數(shù)據(jù)的邏輯構(gòu)造和存儲(chǔ)構(gòu)造；數(shù)據(jù)構(gòu)造的圖形表示；線性構(gòu)造與非線構(gòu)造；數(shù)據(jù)構(gòu)造的圖形表示；線性構(gòu)造與非線性構(gòu)造的概念。性構(gòu)造的概念。3、線性表的定義；線性表的順序存儲(chǔ)構(gòu)造及、線性表的定義；線性表的順序存儲(chǔ)構(gòu)造及其插入刪除運(yùn)算。其插入刪除運(yùn)算。4、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)構(gòu)、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)構(gòu)造及其根本運(yùn)算。造及其根本運(yùn)算。5、線性單鏈表，雙向鏈表與循環(huán)鏈表的構(gòu)造、線

3、性單鏈表，雙向鏈表與循環(huán)鏈表的構(gòu)造及其根本運(yùn)算。及其根本運(yùn)算。6、樹(shù)的根本概念；二叉樹(shù)的定義及其存儲(chǔ)構(gòu)、樹(shù)的根本概念；二叉樹(shù)的定義及其存儲(chǔ)構(gòu)造；二叉樹(shù)的前序、中序和后序遍歷。造；二叉樹(shù)的前序、中序和后序遍歷。7、順序查找與二分查找算法；根本排序算法、順序查找與二分查找算法；根本排序算法(交換類(lèi)排序、選擇類(lèi)排序、插入類(lèi)排序交換類(lèi)排序、選擇類(lèi)排序、插入類(lèi)排序)。考試大綱考試大綱考試內(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ì)方法，對(duì)象，方法，、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及承繼與多

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

5、測(cè)試，系統(tǒng)測(cè)試。5、程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。、程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試?？荚嚧缶V考試大綱考試內(nèi)容考試內(nèi)容四、數(shù)據(jù)庫(kù)設(shè)計(jì)根底四、數(shù)據(jù)庫(kù)設(shè)計(jì)根底1、數(shù)據(jù)庫(kù)的根本概念；數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理、數(shù)據(jù)庫(kù)的根本概念；數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。系統(tǒng)，數(shù)據(jù)庫(kù)系統(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ù)庫(kù)規(guī)范化實(shí)際。影、銜接運(yùn)算；數(shù)據(jù)庫(kù)規(guī)范化實(shí)際。4、數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟；需求分析、概念、數(shù)據(jù)庫(kù)設(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ù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的存儲(chǔ)構(gòu)造棧和隊(duì)列棧和隊(duì)列線性鏈表線性鏈表二叉樹(shù)根本概念及其特性二叉樹(shù)根本概念及其特性查找技術(shù)查找技術(shù)數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念1、算法、算法算法是指解題方案的準(zhǔn)確而完好的描畫(huà)。算法是指解題方案的準(zhǔn)確而完好的描畫(huà)。留意：算

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

8、概念，注重實(shí)際上的正確性。實(shí)際上的正確性。數(shù)學(xué)上的計(jì)算方法是設(shè)計(jì)算法的根底。數(shù)學(xué)上的計(jì)算方法是設(shè)計(jì)算法的根底。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念3、算法的根本要素、算法的根本要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法中對(duì)數(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ì)根本方法列舉法列舉法 列舉一切能夠情況，檢測(cè)其中符

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

10、續(xù)，假設(shè)試探失敗，那么回退。直至問(wèn)題處理。試探失敗，那么回退。直至問(wèn)題處理。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法算法的根本概念算法的根本概念5、算法的時(shí)間復(fù)雜度、算法的時(shí)間復(fù)雜度指執(zhí)行算法所需求的計(jì)算任務(wù)量指執(zhí)行算法所需求的計(jì)算任務(wù)量算法任務(wù)量的度量應(yīng)與計(jì)算機(jī)、編程言語(yǔ)、算法任務(wù)量的度量應(yīng)與計(jì)算機(jī)、編程言語(yǔ)、編程細(xì)節(jié)等無(wú)關(guān)。編程細(xì)節(jié)等無(wú)關(guān)。算法的任務(wù)量用算法所執(zhí)行的根本運(yùn)算次數(shù)算法的任務(wù)量用算法所執(zhí)行的根本運(yùn)算次數(shù)衡量。衡量。算法任務(wù)量是問(wèn)題規(guī)模的函數(shù)：算法的任務(wù)算法任務(wù)量是問(wèn)題規(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í)行算法所需求的存儲(chǔ)空間指執(zhí)行算法所需求的存儲(chǔ)空間包括：算法程序所占據(jù)的存儲(chǔ)空間包括：算法程序所占據(jù)的存儲(chǔ)空間待處置數(shù)據(jù)所占據(jù)的存儲(chǔ)空間待處置數(shù)據(jù)所占據(jù)的存儲(chǔ)空間算法程序執(zhí)行中所需求的額外存儲(chǔ)空間算法程序執(zhí)行中所需求的額外存儲(chǔ)空間假設(shè)額外存儲(chǔ)空間大小不隨問(wèn)題規(guī)模變化，假設(shè)額外存儲(chǔ)空間大小不隨問(wèn)題規(guī)模變化，那么稱(chēng)之為算法原地任務(wù)。那么稱(chēng)之為算法原地任務(wù)。降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲(chǔ)空降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲(chǔ)空間和額外空間入手。間和額外空間入手。算法定義特征復(fù)雜度時(shí)間

12、/空間數(shù)據(jù)構(gòu)造1.數(shù)據(jù)的邏輯構(gòu)造2.數(shù)據(jù)的存儲(chǔ)構(gòu)造3.數(shù)據(jù)的運(yùn)算線性線性表?xiàng)！㈥?duì)列非線性樹(shù)形構(gòu)造二叉樹(shù)滿(mǎn)二叉樹(shù)、完全二叉數(shù)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)查找順序、二分修正排序交換、插入、選擇插入刪除修正數(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ī)中的存儲(chǔ)關(guān)系數(shù)據(jù)元素在計(jì)算

13、機(jī)中的存儲(chǔ)關(guān)系 對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算對(duì)各種數(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ù)的存儲(chǔ)構(gòu)造、數(shù)據(jù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的存儲(chǔ)方式數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的存儲(chǔ)方式存儲(chǔ)構(gòu)造也稱(chēng)為物理構(gòu)造存儲(chǔ)構(gòu)造也稱(chēng)為物理構(gòu)造同一種邏輯構(gòu)造可以有不同的存儲(chǔ)構(gòu)造同一種邏輯構(gòu)造可以有不同的存儲(chǔ)構(gòu)造常用的有：順序、鏈接、索引等方式常用的有：順序、鏈接、索引等方式數(shù)據(jù)構(gòu)造的根本概念數(shù)據(jù)構(gòu)造的根本概念4、數(shù)據(jù)構(gòu)造的表示、數(shù)據(jù)構(gòu)造

14、的表示二元關(guān)系表示：二元關(guān)系表示：兩個(gè)要素：數(shù)據(jù)元素的集合兩個(gè)要素：數(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è)非空的線性構(gòu)造有且只需一線性構(gòu)造：一個(gè)非空的線性構(gòu)造有且只需一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多只需一個(gè)直接前驅(qū)、個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多只需一個(gè)直接前驅(qū)、最多只需一個(gè)直接后繼。最多只需一

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

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

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

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

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

20、。2、棧的順序存儲(chǔ)構(gòu)造、棧的順序存儲(chǔ)構(gòu)造棧的各個(gè)數(shù)據(jù)元素按其邏輯順序依次延續(xù)存棧的各個(gè)數(shù)據(jù)元素按其邏輯順序依次延續(xù)存儲(chǔ)。儲(chǔ)。由于插入刪除操作只能在棧頂一端進(jìn)展，所由于插入刪除操作只能在棧頂一端進(jìn)展，所以以不需求挪動(dòng)數(shù)據(jù)元素。不需求挪動(dòng)數(shù)據(jù)元素。3、棧的根本運(yùn)算、棧的根本運(yùn)算入棧：在棧頂位置插入新元素。入棧：在棧頂位置插入新元素。出棧：取出棧頂位置的元素。出棧：取出棧頂位置的元素。讀棧頂元素：讀出棧頂位置的元素。讀棧頂元素：讀出棧頂位置的元素?！吧弦纾喝霔r(shí)堆棧已滿(mǎn)。上溢：入棧時(shí)堆棧已滿(mǎn)?！跋乱纾合乱纾撼鰲r(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)展插入的一端稱(chēng)為隊(duì)尾。允許進(jìn)展插入的一端稱(chēng)為隊(duì)尾。允許進(jìn)展刪除的另一端稱(chēng)為隊(duì)頭。允許進(jìn)展刪除的另一端稱(chēng)為隊(duì)頭。其特點(diǎn)為其特點(diǎn)為“先入先出先入先出(FIFO)或或“后入后出后入后出(LILO)。(先來(lái)先效力先來(lái)先效力)通常設(shè)置指針通常設(shè)置指針rear指向隊(duì)尾，指針指向隊(duì)尾，指針front指向指向隊(duì)頭。隊(duì)頭。2、隊(duì)列的順序存儲(chǔ)構(gòu)造、隊(duì)列的順序存儲(chǔ)構(gòu)造隊(duì)列的各個(gè)數(shù)據(jù)元素按其邏輯順序依次延續(xù)隊(duì)列的各個(gè)數(shù)據(jù)元素按其邏輯順序依次延續(xù)存儲(chǔ)。存儲(chǔ)。由于插入刪除操作只能在隊(duì)列的兩端進(jìn)展，由

22、于插入刪除操作只能在隊(duì)列的兩端進(jìn)展，所以所以不需求挪動(dòng)數(shù)據(jù)元素。不需求挪動(dòng)數(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ì)列已滿(mǎn)。上溢：入隊(duì)時(shí)隊(duì)列已滿(mǎn)?！跋乱纾合乱纾撼鲫?duì)時(shí)隊(duì)列已空。出隊(duì)時(shí)隊(duì)列已空。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法線性鏈表線性鏈表1、鏈?zhǔn)酱鎯?chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式 結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域(存儲(chǔ)數(shù)據(jù)存儲(chǔ)數(shù)據(jù))、指針域指針域(指向其前件或后件指向其前件或后件)。 數(shù)據(jù)構(gòu)造的存儲(chǔ)空間可

23、以不延續(xù)，存儲(chǔ)順數(shù)據(jù)構(gòu)造的存儲(chǔ)空間可以不延續(xù)，存儲(chǔ)順序與邏輯關(guān)系可以不一致。序與邏輯關(guān)系可以不一致。 鏈?zhǔn)酱鎯?chǔ)方式既可以用來(lái)表示線性構(gòu)造，鏈?zhǔn)酱鎯?chǔ)方式既可以用來(lái)表示線性構(gòu)造，也可以表示非線性構(gòu)造。也可以表示非線性構(gòu)造。2、線性鏈表、線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為線性鏈表。線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為線性鏈表。(棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為鏈棧、隊(duì)列的鏈?zhǔn)酱鏃５逆準(zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為鏈棧、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為鏈隊(duì)列儲(chǔ)構(gòu)造稱(chēng)為鏈隊(duì)列)常用的線性鏈表有：常用的線性鏈表有：?jiǎn)捂湵韱捂湵?(一個(gè)指針域，指向直接后繼一個(gè)指針域，指向直接后繼)雙向鏈表雙向鏈表 (兩個(gè)指針域，指向直接后繼及后繼兩個(gè)指針域，指向直接后繼及后

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)造與算法樹(shù)的根本概念樹(shù)的根本概念1、樹(shù)、樹(shù)樹(shù)是一種簡(jiǎn)單的非線性構(gòu)樹(shù)是一種簡(jiǎn)單的非線性構(gòu)造。造。元素間的關(guān)系具有明顯的元素間的關(guān)系具有明顯的層次構(gòu)造。層次構(gòu)造。2、相關(guān)的術(shù)語(yǔ)、相關(guān)的術(shù)語(yǔ)根結(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)子樹(shù)子樹(shù)結(jié)點(diǎn)的度結(jié)點(diǎn)的度樹(shù)的度樹(shù)的度樹(shù)的深度樹(shù)的深度數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法二叉樹(shù)二叉樹(shù)1、二叉樹(shù)的特點(diǎn)、二叉樹(shù)的特點(diǎn)非空二叉樹(shù)只需一個(gè)根結(jié)點(diǎn)。非空二叉樹(shù)只需一個(gè)根結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)最多有左右兩棵子樹(shù)。每個(gè)結(jié)點(diǎn)最多有左右兩棵子樹(shù)。2、二叉樹(shù)的根本性質(zhì)、二叉樹(shù)的根本性質(zhì)第第 k 層上最多有層上最多有 2 k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)深度為深度為 m 的二叉樹(shù)最多有的二叉樹(shù)最多有 2m-1個(gè)結(jié)個(gè)結(jié)點(diǎn)點(diǎn)任何二叉樹(shù)葉結(jié)點(diǎn)總比度為任何二叉樹(shù)葉結(jié)點(diǎn)總比度為 2 的節(jié)點(diǎn)的節(jié)點(diǎn)多一個(gè)多一個(gè)n 個(gè)節(jié)點(diǎn)的二叉樹(shù)的深度為個(gè)節(jié)點(diǎn)的二叉樹(shù)的深度為 log2n+13、滿(mǎn)二叉樹(shù)、滿(mǎn)二叉樹(shù)4、完全二叉樹(shù)、完全

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

27、式存儲(chǔ)時(shí)也只能采用順序查找的線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)也只能采用順序查找的方法。方法。2、二分法查找、二分法查找在順序存儲(chǔ)的線性表為有序的情況下，可以在順序存儲(chǔ)的線性表為有序的情況下，可以運(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)展直到相等(查找勝利查找勝利)或子表長(zhǎng)度或子表

28、長(zhǎng)度為為0(查找失敗查找失敗)。數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法排序技術(shù)排序技術(shù)1、交換類(lèi)排序、交換類(lèi)排序起泡排序起泡排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 快速排序快速排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 2、插入類(lèi)排序、插入類(lèi)排序簡(jiǎn)單插入排序簡(jiǎn)單插入排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 希爾排序希爾排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 O( n 1.5) 。3、選擇類(lèi)排序、選擇類(lèi)排序簡(jiǎn)單項(xiàng)選擇擇排序簡(jiǎn)單項(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、算法是問(wèn)題處置方案正確而完好的描畫(huà)，算、算法是問(wèn)題處置方案正確而完好的描畫(huà)，算法的效率與數(shù)據(jù)的存儲(chǔ)構(gòu)造有親密的關(guān)系。法的效率與數(shù)據(jù)的存儲(chǔ)構(gòu)造有親密的關(guān)系。2、數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表示、數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表示(存儲(chǔ)方存儲(chǔ)方式式)稱(chēng)為數(shù)據(jù)的存儲(chǔ)構(gòu)造稱(chēng)為數(shù)據(jù)的存儲(chǔ)構(gòu)造(物理構(gòu)造物理構(gòu)造)。一種邏。一種邏輯構(gòu)造可以有多種存儲(chǔ)構(gòu)造。輯構(gòu)造可以有多種存儲(chǔ)構(gòu)造。3、在長(zhǎng)度為、在長(zhǎng)度為 n 的順序表中，插入或刪除一個(gè)元的順序表中，插入或刪除一個(gè)元素平均需求挪動(dòng)一半元素。

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

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

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

33、次。次。12、在長(zhǎng)度為、在長(zhǎng)度為 n 的線性表中進(jìn)展對(duì)分查找，最的線性表中進(jìn)展對(duì)分查找，最壞情況需求比較壞情況需求比較 log2n 次。但對(duì)分查找只適用次。但對(duì)分查找只適用于有序順序表。于有序順序表。13、在冒泡排序、快速排序、簡(jiǎn)單插入排序、在冒泡排序、快速排序、簡(jiǎn)單插入排序、選擇排序的方法中，最壞情況下需求比較的選擇排序的方法中，最壞情況下需求比較的次數(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ù)的開(kāi)展而言就程序設(shè)計(jì)的方法和技術(shù)的開(kāi)展而言主要閱歷了構(gòu)造化程序設(shè)計(jì)和面向?qū)ο蟪讨饕啔v了構(gòu)造化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)兩個(gè)階段序設(shè)計(jì)兩個(gè)階段2、程序設(shè)計(jì)風(fēng)格、程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所表現(xiàn)出來(lái)的程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所表現(xiàn)出來(lái)的特點(diǎn)、習(xí)慣和邏輯思緒。特點(diǎn)、習(xí)慣和邏輯思緒。程序設(shè)計(jì)風(fēng)格會(huì)深化影響軟件的質(zhì)量和可維程序設(shè)計(jì)風(fēng)格會(huì)深化影響軟件的質(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ù)聽(tīng)闡明的方法數(shù)聽(tīng)闡明的方法語(yǔ)句的構(gòu)造語(yǔ)句的構(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é)，先全局后部分。逐漸求精逐漸求精對(duì)復(fù)雜問(wèn)題設(shè)計(jì)子目的過(guò)度，對(duì)復(fù)雜問(wèn)題設(shè)計(jì)子目的過(guò)度，逐漸細(xì)化。逐漸細(xì)化。模塊化模塊化 將復(fù)雜問(wèn)題分解為假設(shè)干簡(jiǎn)單問(wèn)題。將復(fù)雜問(wèn)題分解為假設(shè)干簡(jiǎn)單問(wèn)題。限

36、制運(yùn)用限制運(yùn)用GOTO語(yǔ)句語(yǔ)句防止呵斥程序邏輯構(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)造組成各個(gè)模塊單入口單出口各個(gè)模塊單入口單出口模塊的內(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ā)來(lái)構(gòu)造系統(tǒng)，用現(xiàn)實(shí)生活中常用的事物出發(fā)來(lái)構(gòu)造系統(tǒng)，用現(xiàn)實(shí)生活中常用的思想方法來(lái)描畫(huà)客觀事物，是系

37、統(tǒng)中的對(duì)象思想方法來(lái)描畫(huà)客觀事物，是系統(tǒng)中的對(duì)象及對(duì)象間的關(guān)系能照實(shí)反映事物及其關(guān)系。及對(duì)象間的關(guān)系能照實(shí)反映事物及其關(guān)系。2、主要優(yōu)點(diǎn)、主要優(yōu)點(diǎn)與人類(lèi)習(xí)慣的思想方法一致與人類(lèi)習(xí)慣的思想方法一致穩(wěn)定性好穩(wěn)定性好可重用性好可重用性好易于開(kāi)發(fā)大型軟件產(chǎn)品易于開(kāi)發(fā)大型軟件產(chǎn)品可維護(hù)性好可維護(hù)性好3、根本概念、根本概念對(duì)象對(duì)象類(lèi)和實(shí)例類(lèi)和實(shí)例音訊音訊承繼承繼多態(tài)性多態(tài)性程序設(shè)計(jì)根底程序設(shè)計(jì)根底本章重點(diǎn)本章重點(diǎn)1、程序設(shè)計(jì)并不等于編程，編程只是程序設(shè)、程序設(shè)計(jì)并不等于編程，編程只是程序設(shè)計(jì)過(guò)程中的一小步。計(jì)過(guò)程中的一小步。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ì)是指把一個(gè)大程序按人們能了、模塊化設(shè)計(jì)是指把一個(gè)大程序按人們能了解的大小規(guī)模進(jìn)展分解。劃分模塊的根本原解的大小規(guī)模進(jìn)展分解。劃分模塊的根本原那么是使每個(gè)模塊都易于了解。在按功能劃那么是使每個(gè)模塊都易于了解。在按功能劃分模塊時(shí)，要求各模塊功能盡量單一，各模分模塊時(shí)，要求各模塊功能盡量單一，各模塊之間的聯(lián)絡(luò)盡量的少。塊之間的聯(lián)絡(luò)盡量的少。4、客觀世界是由實(shí)體及其聯(lián)絡(luò)所組成的。客、客觀世界是由實(shí)體及其聯(lián)絡(luò)所組成的?？陀^世界中的實(shí)體稱(chēng)為問(wèn)題域的對(duì)象。觀世界中的實(shí)體稱(chēng)為問(wèn)題域的對(duì)象。5、類(lèi)描畫(huà)的是具有類(lèi)似性質(zhì)一組對(duì)象。一個(gè)、類(lèi)描畫(huà)的是

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

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

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

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

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

44、計(jì)。進(jìn)展邏輯設(shè)計(jì)。1、需求分析、需求分析需求分析的義務(wù)是發(fā)現(xiàn)需求、求精、建模和需求分析的義務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求。定義需求。 常見(jiàn)的需求分析方法：構(gòu)造化分析方法常見(jiàn)的需求分析方法：構(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)造化英語(yǔ)、斷定表和斷定樹(shù)等、構(gòu)造化英語(yǔ)、斷定表和斷定樹(shù)等工具，來(lái)建立一種被稱(chēng)為構(gòu)造化規(guī)格闡明的工具，來(lái)建立一種被稱(chēng)為構(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ī)格闡明書(shū)軟件需求規(guī)格闡明書(shū)是需求分析階段的最后成果，是軟件開(kāi)發(fā)的是需求分析階段的最后成果，是軟件開(kāi)發(fā)的重要文檔之一。重要文檔之一。軟件需求規(guī)格闡明書(shū)把軟件方案中確定的軟軟件需求規(guī)格闡明書(shū)把軟件方案中確定的軟件范圍加以展開(kāi)，制定出完好的信息描畫(huà)、件范圍加以展開(kāi)，制定出完好的信息描畫(huà)、詳細(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)換為軟件表示的過(guò)軟件設(shè)計(jì)是把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程。程。從技術(shù)角度：軟件設(shè)計(jì)包括構(gòu)造設(shè)計(jì)、數(shù)據(jù)從技術(shù)角度：軟件設(shè)計(jì)包括構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(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、寫(xiě)設(shè)計(jì)文檔編寫(xiě)設(shè)計(jì)文檔設(shè)計(jì)文設(shè)計(jì)文檔評(píng)審檔評(píng)審構(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)造圖中的每一個(gè)模塊確定算法和部分?jǐn)?shù)據(jù)構(gòu)造，用某種選個(gè)模塊確定算法和部分?jǐn)?shù)據(jù)構(gòu)造，用某種選定的工具表示算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。定的工具表示算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。常見(jiàn)的設(shè)計(jì)工具：常見(jiàn)的設(shè)計(jì)工具：圖形工具：流程圖、圖形工具：流程圖、N - S、PAD、HIPO表格工具：斷定表表格工具：斷定表言語(yǔ)工具：言語(yǔ)工具：PDL(偽碼偽碼)軟件工程根底軟件工程根底軟件測(cè)試軟件測(cè)試1、測(cè)試、測(cè)試軟件測(cè)試的目的是在精心控制的

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

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

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

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

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

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

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

55、BMS提供的言語(yǔ)提供的言語(yǔ)數(shù)據(jù)定義言語(yǔ)數(shù)據(jù)定義言語(yǔ)數(shù)據(jù)支配言語(yǔ)數(shù)據(jù)支配言語(yǔ)數(shù)據(jù)控制言語(yǔ)數(shù)據(jù)控制言語(yǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)根底數(shù)據(jù)庫(kù)設(shè)計(jì)根底數(shù)據(jù)庫(kù)系統(tǒng)的根本概念數(shù)據(jù)庫(kù)系統(tǒng)的根本概念4、數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng) DBS由由DB、DBMS、數(shù)據(jù)庫(kù)管理員、數(shù)據(jù)庫(kù)管理員(DBA)、硬件、硬件平臺(tái)、軟件平臺(tái)組成。平臺(tái)、軟件平臺(tái)組成。5、數(shù)據(jù)庫(kù)系統(tǒng)的根本特點(diǎn)、數(shù)據(jù)庫(kù)系統(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ù)庫(kù)系統(tǒng)的三級(jí)方式、數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)方式概念方式：概念方式：數(shù)據(jù)庫(kù)中全局?jǐn)?shù)據(jù)的邏輯描畫(huà)，與詳細(xì)的數(shù)據(jù)庫(kù)中全局?jǐn)?shù)據(jù)

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

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ò)一對(duì)一一對(duì)一 一對(duì)多或多對(duì)一一對(duì)多或多對(duì)一多對(duì)多多對(duì)多3、E - R模型的圖示法模型的圖示法實(shí)體集表示法：在實(shí)體集表示法：在E - R圖中用矩形表示實(shí)體圖中用矩形表示實(shí)體集，矩形內(nèi)注明實(shí)體集稱(chēng)號(hào)。集，矩形內(nèi)注明實(shí)體集稱(chēng)號(hào)。屬性表示法：在屬性表示法：在E - R圖中用橢圓，橢圓中注圖中用橢圓，橢圓中注明屬性稱(chēng)號(hào)。明屬性稱(chēng)號(hào)。聯(lián)絡(luò)表示法：在聯(lián)絡(luò)表示法：在E - R圖中用菱形表示聯(lián)絡(luò)，圖中用菱形表示聯(lián)絡(luò)，菱形中注明聯(lián)絡(luò)稱(chēng)號(hào)。菱形

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

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