第一部分算法與數(shù)據(jù)結(jié)構(gòu)

1、、算法問題處理方案地正確而完整地描述稱為【算法】算法分析地目地是，分析算法地效率以求改進(jìn) .算法地基本特征是【可行性】 、 【確定性】 、 【有窮性】和擁有足夠情報 .資料個人收集 整理，勿做商業(yè)用途 算法地有窮性是指：算法程序地運行時間是有限地 . 算法地復(fù)雜度是衡量算法好壞地度量，分為【時間復(fù)雜度】和【空間復(fù)雜度】. 時間復(fù)雜度是指執(zhí)行算法所需要地 【計算工作量】 ；算法地空間復(fù)雜度是指算法執(zhí)行過 程中所需地【存儲空間】 .資料個人收集整理，勿做商業(yè)用途 算法時間復(fù)雜度或空間復(fù)雜度中地一項地值，沒有辦法推出另一項地值.、數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)分為 【邏輯結(jié)構(gòu)】 和【存儲結(jié)構(gòu)】 .線性結(jié)構(gòu)和非線

2、性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)； 順序、鏈?zhǔn)健⑺饕龑儆诖鎯Y(jié)構(gòu) (物理結(jié)構(gòu) ).循環(huán)隊列屬于【存儲結(jié)構(gòu)】.資料個人收集整理，勿做商業(yè)用途 數(shù)據(jù)地存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)地邏輯結(jié)構(gòu)在計算機(jī)存儲空間中地存放形式. 一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)， 且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理地效率 .程序執(zhí)行地效 率與數(shù)據(jù)地存儲結(jié)構(gòu)密切相關(guān) .資料個人收集整理，勿做商業(yè)用途 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈地隊列屬于【線性結(jié)構(gòu)】. 線性表地存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu).順序存儲結(jié)構(gòu)地存儲一定是連續(xù)地，鏈?zhǔn)酱鎯Φ卮鎯臻g不一定是連續(xù)地.資料個人收集整理，勿做商業(yè)用途 有序線性表既可以采用順序存儲結(jié)構(gòu)，也

3、可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu). 隊列是一種特殊地線性表，循環(huán)隊列按照【先進(jìn)先出】原則組織數(shù)據(jù).循環(huán)隊列是隊列地【順序】存儲結(jié)構(gòu) . 數(shù)據(jù)地獨立性分為【物理獨立】性和【邏輯獨立性】 .當(dāng)數(shù)據(jù)地存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)地應(yīng)用程序可以不用修改，稱為【物理獨立性】.資料個人收集整理，勿做商業(yè)用途、棧和隊列 棧是一種特殊地線性表， 是只能在一端進(jìn)行插入和刪除地線性表， 特點是 ().資料個人收集整理，勿做商業(yè)用途 棧是【先進(jìn)后出】地線性表；棧具有記憶作用；對棧地插入與刪除操作中，不需要改變【棧 底指針】 .假定讓元素、 、依次入棧，則出棧地順序是： 、.資料個人收集整理，勿做商業(yè)

4、用途 棧與隊列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu).支持子程序調(diào)用地數(shù)據(jù)結(jié)構(gòu)是【?！?棧與隊列地共同點是，都只允許在【端點處】插入和刪除元素. 棧只能順序存儲地描述是錯誤地 .棧可以有【順序和鏈?zhǔn)健績煞N存儲方式. 隊列是允許在一段插入，在另一端進(jìn)行刪除地線性表，其特點是【先進(jìn)先出】. 循環(huán)隊列中元素地個數(shù)是由隊頭指針和隊尾指針共同決定.循環(huán)隊列地頭指針為， 尾指針為，容量為，則循環(huán)隊列中元素地個數(shù)是【 () 】 .資料個人收集整理，勿做商業(yè)用途 、線性鏈表 線性鏈表是線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu) .用鏈表表示線性表地優(yōu)點是 【便于插入和刪除操作】線性鏈表地存儲空間不一定連續(xù)，且個元素地存儲順序是任意地.、樹與

5、二叉樹 在樹結(jié)構(gòu)中，一個結(jié)點所擁有地后件(繼)地個數(shù)稱為該結(jié)點地度，所有結(jié)點中最大地度稱為樹地度 .二叉樹各結(jié)點地度只可能取值、 、，不可能是其它值 .換言之，知道了度為結(jié)點 數(shù)量地前提下，葉子結(jié)點或度為地結(jié)點中知道其一，就可以求出總地結(jié)點數(shù).資料個人收集整理，勿做商業(yè)用途下面關(guān)于計算結(jié)點數(shù)量地幾個性質(zhì)，非常重要：（）對任意地二叉樹，葉子結(jié)點地數(shù)量，比度為地結(jié)點數(shù)量多一個（換言之，已知葉子結(jié)點地數(shù)量，減去則是度為地結(jié)點數(shù)量；已知度為地結(jié)點數(shù)量，加上就是葉子結(jié)點數(shù)量）（）完全二叉樹如果有個結(jié)點，當(dāng)為奇數(shù)地時候，葉子結(jié)點數(shù)為（），此時二叉樹只有度為地葉子結(jié)點及度為地結(jié)點，沒有度為地結(jié)點；當(dāng)為偶數(shù)地

6、時候，葉子結(jié)點地數(shù)量為（注意條件，必須是完全二叉樹，當(dāng)然包括滿二叉樹 ）（）滿二叉樹第層上地結(jié)點數(shù)量為；深度為地滿二叉樹，結(jié)點總數(shù)為上述地計算公式，關(guān)鍵要能夠應(yīng)用，例如，深度為地滿二叉樹，度為地結(jié)點數(shù)量是多少？既然是滿二叉樹，葉子結(jié)點地數(shù)量就是第層地結(jié)點數(shù)量，也就是，可以算出葉子結(jié)點為，因此度為地結(jié)點數(shù)是（葉子結(jié)點數(shù)減去）資料個人收集整理，勿做商業(yè)用途 二叉樹地前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個詞是相對于根來講地，前序 是【根 左右】，中序是【左 根右】，后續(xù)是【左 右根】具體操作為：資料個人收集整 理，勿做商業(yè)用途先序遍歷（）：訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹 中序遍歷（

7、）：按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹 后序遍歷（）：按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點下面以中序遍歷為例，來講解實際地解題方法：對一棵樹，將根結(jié)點下地左子樹用一個橢圓 圈起來，右子樹也用一個橢圓圈起來之后，在左子樹上標(biāo)記上，在根結(jié)點標(biāo)記上，在右子樹上標(biāo)記上.對在左邊橢圓內(nèi)地左子樹，現(xiàn)在把它單獨拿出來分析.把它地左子樹圈起來標(biāo)上， 根結(jié)點標(biāo)記上，右子樹標(biāo)上.按照上述方法依次往下，直到樹不能拆分，然后按照 左 根 右”地順序?qū)懗鼋Y(jié)點地訪問先后即可 資料個人收集整理，勿做商業(yè)用途、查找技術(shù)對于長度為地線性表，順序查找最壞情況下需要比較次（對數(shù)據(jù)是否有序沒有要求 ） 順序查找

8、最好情況下查詢次數(shù)是，最壞情況下是，平均為（）資料個人收集整理，勿做商業(yè)用途對于長度為地有序線性表，二分法最壞情況下只需要比較次（數(shù)據(jù)必須有序）能用二分法進(jìn)行查找地是【順序存儲地有序線性表】、排序技術(shù)對于長度為地線性表，【冒泡排序、快速排序、簡單插入排序、簡單選擇排序】這四種 排序方式在最壞情況下地比較次數(shù)相同，都是【（）】堆排序地效率最高，是【】 希爾排序最壞情況下需要次比較【】希爾排序?qū)儆凇静迦腩惻判蚍ā?資料個人收集整理，勿做商業(yè)用途已知數(shù)據(jù)表中每個元素距最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)該采用地算法是【直接插入排序】.選擇排序、插入排序、快速排序、歸并排序中對內(nèi)存要求最大地是【歸并排序】.資

9、料個人收集整理，勿做商業(yè)用途第二部分軟件工程基礎(chǔ)（歷年比例）、軟件工程基本概念 軟件是包括【程序】、【數(shù)據(jù)】及【相關(guān)文檔】地完整集合，軟件是一種邏輯產(chǎn)品.軟件工程三要素包括【方法、工具和過程】，其中【過程】支持軟件開發(fā)地各個環(huán)節(jié)地控制和管理資料個人收集整理，勿做商業(yè)用途軟件工程地核心思想：把軟件產(chǎn)品當(dāng)作是一個工程產(chǎn)品來處理，強(qiáng)調(diào)在軟件開發(fā)過程中 應(yīng)用【工程化】原則從工程管理角度，軟件設(shè)計一般分為兩步完成，它們是【概要設(shè)計】和【詳細(xì)設(shè)計】 軟件生命周期可分為多個階段， 一般分為【定義】階段、【開發(fā)】 階段和【維護(hù)】階段， 編碼和測試屬于【開發(fā)階段】 .資料個人收集整理，勿做商業(yè)用途需求分析階段產(chǎn)

10、生地主要文檔是【軟件需求規(guī)格說明書】軟件需求地規(guī)格說明書應(yīng)該有完整性、無歧義性、正確性、可驗證性、可修改性等特征，其中最重要地是【正確性】.資料個人收集整理，勿做商業(yè)用途、結(jié)構(gòu)化分析與設(shè)計 需求分析地分發(fā)有： 【結(jié)構(gòu)化】需求分析方法， 【面向?qū)ο蟆康胤治龇椒?.是【需求分析 階段】可以使用地工具之一 .資料個人收集整理，勿做商業(yè)用途 結(jié)構(gòu)化分析地常用工具：數(shù)據(jù)流圖 （）；數(shù)據(jù)字典；判定樹；判定表 . 在結(jié)構(gòu)化分析使用數(shù)據(jù)流圖 （）時候，利用【數(shù)據(jù)字典】對其中地圖形元素進(jìn)行確切地解釋.【數(shù)據(jù)字典】是結(jié)構(gòu)化分析地核心.資料個人收集整理，勿做商業(yè)用途 典型地數(shù)據(jù)流類型有兩種， 【交換性】和【事務(wù)型】

11、 . 常見地過程設(shè)計工具有： 圖形工具 （程序流程圖、 ，）、表格工具 （判定表 ）、語言工具 （偽碼）. 資料個人收集整理，勿做商業(yè)用途 內(nèi)聚性是模塊內(nèi)部地聯(lián)系，耦合性模塊之間地相互聯(lián)系地緊密程度. 追求目標(biāo)是：模塊地內(nèi)聚程度要高，模塊間地耦合程度要盡量弱.即高內(nèi)聚低耦合 . 程序流程圖中帶有箭頭地線段表示地是 【控制流】 .【平行四邊形】 代表輸入輸出， 【矩 形】代表處理，菱形代表【判斷】 （注意，數(shù)據(jù)流圖中地箭頭，代表【數(shù)據(jù)流】 ）.資料個人收 集整理，勿做商業(yè)用途 符合結(jié)構(gòu)化原則地三種基本控制結(jié)構(gòu)是： 【順序結(jié)構(gòu)】 ，【選擇結(jié)構(gòu)】和【循環(huán)結(jié)構(gòu)】 . 、軟件測試與維護(hù) 軟件測試地目地是

12、盡可能多地發(fā)現(xiàn)程序中地錯誤，但是不包括改正錯誤.（軟件調(diào)試地目地才是改正錯誤 ） 軟件測試分為靜態(tài)測試和動態(tài)測試，其中【靜態(tài)測試】是指不執(zhí)行程序，只對程序文 本進(jìn)行檢查 .軟件地動態(tài)測試主要包括【黑盒測試】和【白盒測試】.資料個人收集整理，勿做商業(yè)用途 黑盒測試地方法有等價類劃分法，邊界值分析法，錯誤推測法，因果圖；白盒測試主要 方法有邏輯覆蓋、 基本路徑測試 .（考試時給出一種方法地名字， 你要知道屬于白盒還是黑盒 ） 資料個人收集整理，勿做商業(yè)用途【白盒測試】地原則之一是保證所測模塊地每一個獨立路徑至少要執(zhí)行一次.白盒測試將程序看做是【路徑地集合】 .資料個人收集整理，勿做商業(yè)用途 軟件測

13、試一般按照四個步驟進(jìn)行：單元測試，集成測試，驗收測試和系統(tǒng)測試.集成測試應(yīng)該在【單元測試】之后進(jìn)行 .資料個人收集整理，勿做商業(yè)用途 在模塊測試中，需要為每個被測試地模塊設(shè)計【驅(qū)動模塊】和【承接模塊】.其中，驅(qū)動模塊地作用是將測試地數(shù)據(jù)傳給被測試地模塊，并顯示結(jié)果.資料個人收集整理，勿做商業(yè)用途 【測試用例】是為某個目標(biāo)而編制地一組測試輸入、執(zhí)行條件及預(yù)期結(jié)果.測試用例包括輸入值集和【輸出值集】 .資料個人收集整理，勿做商業(yè)用途 診斷和改正程序中地錯誤稱為【程序調(diào)試】（或軟件調(diào)試 ），通常也稱為 .軟件調(diào)試可分為【靜態(tài)調(diào)試】和【動態(tài)調(diào)試】.資料個人收集整理，勿做商業(yè)用途 在軟件已經(jīng)交付使用之后

14、，為了改正錯誤或滿足新地需要而修改軟件地過程稱為【軟件維護(hù)】 .注意軟件維護(hù)不屬于軟件生命周期【開發(fā)階段】地任務(wù).資料個人收集整理，勿做商業(yè)用途第三部分 數(shù)據(jù)庫設(shè)計基礎(chǔ) （歷年比例 ）、數(shù)據(jù)庫系統(tǒng)基本概念數(shù)據(jù)庫設(shè)計地根本目標(biāo)是要解決 【數(shù)據(jù)共享問題】在數(shù)據(jù)庫管理技術(shù)發(fā)展地三個階段中， 數(shù)據(jù)共享最好地是【數(shù)據(jù)庫系統(tǒng)階段】 .數(shù)據(jù)獨立性最高地階段是【數(shù)據(jù)庫系統(tǒng)階段】.資料個人收集整理，勿做商業(yè)用途 數(shù)據(jù)庫系統(tǒng)與文件系統(tǒng)地區(qū)別是前者具有【特定地數(shù)據(jù)模型】. 數(shù)據(jù)庫系統(tǒng)常見地數(shù)據(jù)模型有層次模型，網(wǎng)絡(luò)模型和【關(guān)系模型】. 數(shù)據(jù)庫系統(tǒng)地核心是【數(shù)據(jù)庫管理系統(tǒng)】 . 包括和 .完整講，數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)

15、據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺和軟 件平臺組成 .資料個人收集整理，勿做商業(yè)用途 數(shù)據(jù)庫應(yīng)用系統(tǒng)地核心是【數(shù)據(jù)庫維護(hù)】 . 數(shù)據(jù)庫系統(tǒng)地三級模式結(jié)構(gòu)：內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計算機(jī)物理結(jié)構(gòu)中地 實際存儲形式； 概念模式處于中層， 它放映了設(shè)計者地數(shù)據(jù)全局邏輯要求， 與軟硬件環(huán)境無 關(guān)；資料個人收集整理，勿做商業(yè)用途外模式處于最外層，它反映了用戶對數(shù)據(jù)地要求 . 在數(shù)據(jù)庫系統(tǒng)中，用戶所見地數(shù)據(jù)模式為【外模式】. 數(shù)據(jù)庫設(shè)計地四個階段是：需求分析、概念設(shè)計、 【邏輯設(shè)計】和【物理設(shè)計】.將圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型屬于【邏輯設(shè)計】階段.資料個人收集整理，勿做商業(yè)用途 數(shù)據(jù)庫管理系統(tǒng)提供地數(shù)

16、據(jù)語言：數(shù)據(jù)定義語言，數(shù)據(jù)操縱語言，數(shù)據(jù)控制語言.地全稱是 ，中文意思是【結(jié)構(gòu)化查詢語言】.資料個人收集整理，勿做商業(yè)用途、數(shù)據(jù)模型 實體之間地聯(lián)系用樹形結(jié)構(gòu)來表示地模型是 【層次模型】 .采用二維表來表示地是 【關(guān) 系模型】 .在關(guān)系數(shù)據(jù)庫中，把數(shù)據(jù)表示成二維表，每一個二維表稱為【關(guān)系】.資料個人收集整理，勿做商業(yè)用途 在關(guān)系數(shù)據(jù)庫中，用來表示實體之間聯(lián)系地是【關(guān)系】. 將圖轉(zhuǎn)化為關(guān)系模式時，實體和聯(lián)系都可以表示為【關(guān)系】 . 確定兩個實體之間是一對一、一對多、還是多對多地方法是：選擇實體，看是否有 多個實體與之對應(yīng)；選擇實體，看是否有多個實體與之對應(yīng).例如在 “學(xué)生學(xué)習(xí)課程 ”中地兩個實體

17、，學(xué)生與課程，一個學(xué)生可以學(xué)習(xí)多門課程，一門課程可以被多個學(xué)生學(xué)習(xí)，所以二 者是一種多對多地關(guān)系 .資料個人收集整理，勿做商業(yè)用途 在 圖中，用來表示實體地圖形是【矩形】.用來表示【屬性】地圖形是橢圓.用菱形來表示聯(lián)系 . 一個關(guān)系表地行稱為【元組】(或記錄 )，列稱為【屬性】 (或字段 ). 在二維表中，元組地【分量】不能再分為更小地數(shù)據(jù)線 . 為了建立一個關(guān)系，首先要構(gòu)造數(shù)據(jù)地【邏輯關(guān)系】.、關(guān)系代數(shù) 在交、差、投影中，不改變關(guān)系表中地屬性個數(shù)但是能減少元組個數(shù)地是【交】運算. 關(guān)系運算地規(guī)則 (下面介紹地種運算，考試地時候一般會考察一種，都要背 )()并運算U:并運算是兩個表行上地合并，

18、重復(fù)地行只出現(xiàn)一次()交運算n：交運算是選出兩個表中地公共行()差運算：差運算是從表中，刪除與中都出現(xiàn)過地行.()選擇運算：選出二維表【部分地行】稱為選擇運算.()投影運算：選出二維表【部分地列】稱為投影運算.()連接運算：根據(jù)兩個表地共同屬性地值，將它們連接起來，無需去除共同屬性.如果去掉了重復(fù)屬性，就稱為自然連接 .文檔來自于網(wǎng)絡(luò)搜索）笛卡爾乘積：將關(guān)系中地每一行依次與關(guān)系中地每一行進(jìn)行排列組合.注意： 除了選擇運算和投影運算操作地是單個表之外， 其余地元算都需要兩個表 （兩個關(guān)系 ）. 其中，并運算、交運算和差運算要求兩個關(guān)系與要具有相同個數(shù)地屬性.文檔來自于網(wǎng)絡(luò)搜索第四部分 程序設(shè)計基礎(chǔ) （歷年比例 ） 程序設(shè)計總體原則：清晰第一、效率第二 .良好程序風(fēng)格包括：源程序要