【文章內(nèi)容簡(jiǎn)介】 模式。 兩級(jí)映射 ：模式到內(nèi)模式（數(shù)據(jù)的物理獨(dú)立性）、外模式到模式（數(shù)據(jù)的邏輯獨(dú)立性） 數(shù)據(jù)模型的三要素： 數(shù)據(jù)結(jié) 構(gòu)、數(shù)據(jù)操作、數(shù)據(jù)的約束條件。 目或度 n:R 上的 n 元關(guān)系，元數(shù)：屬性的個(gè)數(shù)，基數(shù)：元組的個(gè)數(shù)記錄數(shù)，候選碼：唯一標(biāo)識(shí)一個(gè)元組，主碼：關(guān)鍵字， 20 主屬性：全部候選碼，全碼：所有屬性都是候選碼。 三類完整性約束條件 ：實(shí)體的（主屬性不空）、參照的即引用的、用戶定義的完整性 。 五個(gè)基本運(yùn)算 ：并∪、 2－差、 3笛卡兒積 from、 4 投影п select、 5 選擇σ where 擴(kuò)展運(yùn)算 ： 1 交∩ R∩ S＝ R－ (RS)， 2 連接◇， 3 除 規(guī)范化 1NT:沒有表中表， 2NT 消除了 1NT 中非主屬性對(duì)碼的部分函數(shù)依賴即每一個(gè)非主屬性 完全依賴于全部的碼（ XY 即 Y 依賴 X）、 3NT 消除了非主屬性對(duì)碼傳遞依賴、BCNF 消除了主屬性對(duì)碼的部分和傳遞依賴、 4NT 表中沒有多值依賴 事務(wù)的四個(gè)特征 ：原子性、一致性（數(shù)據(jù)不會(huì)因事務(wù)而破壞）、隔離性（事務(wù)獨(dú)立運(yùn)行）、持久性（事務(wù)一旦提交）。 BEGIN TRANSACTION 。 COMMIT。ROLLBACK 并發(fā)控制 的主要技術(shù)是封鎖，三級(jí)封鎖協(xié)議： 1 級(jí)可解決丟失更新問題； 2 級(jí)可解決讀臟數(shù)據(jù)； 3 級(jí)防止丟失更新、不讀臟數(shù)據(jù)、防不可重復(fù)讀 建立冗余數(shù)據(jù)的方法是數(shù)據(jù)轉(zhuǎn)儲(chǔ)和登記日志文件。 8 數(shù)據(jù)結(jié)構(gòu) 棧 ：先 進(jìn)后 出 ； 隊(duì) 列 ： 尾 進(jìn)頭 出 循 環(huán)對(duì) 列 F ＝(R+1+Memory_Length) mod M 串 ： (主串 n 模式串 m)樸素的模式匹配算法即布魯特－福斯 21 算法 :最好情況平均比較次數(shù)＝ (n+m)/2 最壞＝ m(n+m)/2 二叉樹 ： i 層至多 2i1個(gè)結(jié)點(diǎn)；深度為 k 的二叉樹最多 2k1 個(gè)結(jié)點(diǎn)；具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為└ log2n ┘ + 1；森林和樹的轉(zhuǎn)換利用樹的孩子兄弟表示法。 哈夫曼樹即最優(yōu)二叉樹 ，是帶權(quán)路徑最短的樹。 圖 ： N 個(gè)頂點(diǎn)的無向完全圖有 n(n1)/2 條邊；任何圖的邊＝頂點(diǎn)總度數(shù) /2； 連通圖 是指無向圖 任兩頂點(diǎn)連通，最大的連通子圖叫連通分量； 生成樹 是極小連通圖； n 個(gè)頂點(diǎn) e 條邊的無向圖的鄰接鏈表需要 n 個(gè)頭結(jié)點(diǎn)和 2e 個(gè)表結(jié)點(diǎn)。求最小生成樹有普里姆算法 prim 和克魯斯卡爾算法 Kruskal； AOV 網(wǎng) ：工程可行性； AOV 的拓?fù)渑判颍ㄟx入度為 0 的輸出、刪） AOE 網(wǎng) ：工程需時(shí)和關(guān)鍵活動(dòng)；關(guān)鍵路徑是最長(zhǎng)路徑。 最短路徑 ：迪杰斯特拉算法 查找 ：①順序查找平均查找次數(shù) ASL＝ (n+1)/2；②折半 ASL＝ (n+1)/2 * log2(n+1) 1 ；③分塊 (s 是每塊的個(gè)數(shù) )塊內(nèi)塊間都順序 ASL＝ (n/s + s )/2 +1 塊內(nèi)順序塊間折半 ASL= log2(n/s+1) + s/2 二叉排序樹 即二叉查找樹 左小于右；平衡二叉樹 AVL 樹左右深度差不超過一； m 階 B－樹 根至少有兩棵子樹其他非葉至少有 m/2 進(jìn)位取整棵 哈希表 散列表 ：構(gòu)造方法有直接定址法、數(shù)字分析法、平 22 均取中法、折疊法、隨機(jī)數(shù)法、除留余數(shù)法；沖突處理方法有開放地址法、鏈地址法、再哈希法、建公共溢出區(qū)法；裝填因子＝表中記錄數(shù) /哈希表長(zhǎng)度。 排序 ：堆排序 建堆從最后一個(gè)非葉開始（一直往下）一個(gè)個(gè)往前篩選。 直接插入 好 O(n) 均 O(n2) 壞 O(n2) 輔 O(1) 穩(wěn)定 直接選擇 O(n2) O(n2) O(n2) O(1) 不穩(wěn) 冒泡排序 O(n) O(n2) O(n2) O(1) 穩(wěn)定 希爾排序 ――― O() 不穩(wěn) 縮小增量排序 快速排序 O(nlogn) O(nlogn) O(n2) O(nlogn)不穩(wěn)后往前找小交換 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不穩(wěn) 歸并排序 O(nlogn) O(nlogn)O(nlogn) O(1) 穩(wěn)定 兩兩排序歸并 基數(shù)排序 O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd) 穩(wěn)定 r=10,d位數(shù) 線性表的第 i 個(gè)元素存儲(chǔ)位置為 loc(a1)+(i1)*L ； 線性表的平均移動(dòng)次數(shù) (n1)/2； 線性表的順序查找平均長(zhǎng)度為 (n+1)/2； 判斷循環(huán)隊(duì)列滿：==(+1)%m m 為隊(duì)列最大長(zhǎng)度 ； 判斷循環(huán)隊(duì)列滿： == 23 指令流水線計(jì)算時(shí)間公式 NT+(n1)T T 是流水線的周期， N是流水線的段數(shù)， n是有多少條流水 線指令 系統(tǒng)可靠性計(jì)算方法： 串聯(lián)系統(tǒng) 可靠性 R = R1*R2*R3 失效率 y = y1 + y2 + y3 并聯(lián)系統(tǒng) 可靠性 R = 1 (1 R1)*(1 R2)*(1 R3) 平均無故障時(shí)間 MTBF = 1/u = 指令流水線計(jì)算方法； 第一類是各指令段 ,有同步時(shí)間 ,即有指令流操作周期 .當(dāng)某指令段執(zhí)行完畢后 ,必須等到下一個(gè)操作周期來臨時(shí) ,才能執(zhí)行下一條指令的相同段 .其計(jì)算公式是 : (指令所分段數(shù) 1)*指令流操作周期 +指令數(shù) *指令流操作周期 . 同指令的段數(shù) *操作周 期 +(總的指令數(shù) 1)*操作周期 . 第二類是各指令段 ,沒有同步時(shí)間 ,每段執(zhí)行完畢 ,不需要等待 ,直接執(zhí)行下一條執(zhí)令相同的段 .其計(jì)算方法 。 第一條指令執(zhí)行時(shí)間 +(指令數(shù) 1)*各指令段執(zhí)行時(shí)間中最大的執(zhí)行時(shí)間 CPI = 所有的指令執(zhí)行時(shí)間 /指令總數(shù) MIPS = 機(jī)器頻率 /CPI 9 常用算法 算法的五特性： 有窮性、確定性、可行性、輸入、輸出 24 好的算法的目標(biāo) ：正確性、可讀、健壯、效率與低存儲(chǔ)需求 迭代法： 求方程近似根 ，對(duì)分法和梯度法 。窮舉搜索法。遞推法。 遞歸法： 執(zhí)行過程分遞推和回歸兩階段 。 背包問 題 ?；厮莘丛囂椒?。 貪心法： 不求最優(yōu)但求快速有解， 哈夫曼算法 裝箱問題 馬的遍歷 0/1 背包 。分治法： 大問題分成小問題解決 快速排序 比賽日程 。 動(dòng)態(tài)規(guī)劃法 ：求兩字符串中最長(zhǎng)公共字符序列。 10 面向?qū)ο蠹夹g(shù) 面向?qū)ο蠹夹g(shù) 面向?qū)ο?＝對(duì)象＋分類＋繼承＋通過消息的通訊。對(duì)象有對(duì)象名（標(biāo)識(shí)）、屬性和操作（方法）組成。對(duì)象是類的實(shí)例。類解決數(shù)據(jù)保護(hù)問題，繼承是父子共享數(shù)據(jù)和方法的機(jī)制。 注意類中的靜態(tài)變量，該變量可以通過 類名：：靜態(tài)成員名訪問 ，類的所有對(duì)象共享該靜態(tài)成員變 量。 對(duì)于靜態(tài)成員變量的初始化方式： 類型類型 類名 ::靜態(tài)數(shù)據(jù)成員名 = 值 Smalltalk全面支持面向?qū)ο蟾拍睿?eiffel是全面的靜態(tài)類型化也支持全面的面向?qū)ο蟾拍??！邦惖膶哟谓Y(jié)構(gòu)”指導(dǎo)編譯程序進(jìn)行類的實(shí)例化過程。 多態(tài) ：是不同對(duì)象收到同一消息產(chǎn)生不同結(jié)果。 通用多態(tài)有參數(shù)多態(tài)（最純的、類屬），包含多態(tài)（子類型化）； 特定多態(tài)有 過載多態(tài)（同一變量被用來表示不同功能）、強(qiáng)制多態(tài)。類屬 (模版類 )是一種參數(shù)多態(tài)機(jī)制。 25 好的 OOP 必須支持 ：被封裝的對(duì)象、類和實(shí)例的概念、繼承性、多態(tài)。 程序設(shè)計(jì)的 發(fā)展： 過程程序設(shè)計(jì)、模塊化、函數(shù)、邏輯、面向?qū)ο蟆? 面向?qū)ο蟮暮锰?：對(duì)象技術(shù)解決了產(chǎn)品質(zhì)量和生產(chǎn)率間的平衡；繼承機(jī)制使系統(tǒng)具有很高的靈活性和易擴(kuò)充性；面向?qū)ο笫且粋€(gè)能管理復(fù)雜性并增強(qiáng)伸縮性的工具；從概念模型化到分析設(shè)計(jì)編碼可以無縫傳遞；封裝有助于建立安全的系統(tǒng)。 面向?qū)ο蟮母拍?：對(duì)象、類、方法、實(shí)例變量、消息、子類、繼承 類的訪問控制符 ： Private 類內(nèi) Protected 類及友元 Public 消息傳遞機(jī)制和對(duì)象自身引用 將方法與特定的對(duì)象動(dòng)態(tài)地聯(lián)系在一起，使得不同對(duì)象在執(zhí)行同樣的方法體時(shí)可因?qū)ο蟮臓顟B(tài)不 同而產(chǎn)生不同的行為，從而使方法對(duì)具體地對(duì)象具有個(gè)性。 衡量開發(fā)人員 ：能否最好地發(fā)揮已有類庫地優(yōu)點(diǎn)、將已有類庫與新問題緊密匹配地能力、不得不另外編寫地代碼最少。 面向?qū)ο蠓治龇椒?OOA：將數(shù)據(jù)和功能合在一起考慮，把系統(tǒng)地行為和信息間地關(guān)系表示為迭代構(gòu)造特征。 五個(gè)活動(dòng) ：認(rèn)識(shí)對(duì)象、組織對(duì)象、對(duì)象間地相互作用、基于對(duì)象地操作。 面向?qū)ο笤O(shè)計(jì) OOD：設(shè)計(jì)分析模型和實(shí)現(xiàn)源代碼。構(gòu)件是 26 功能和數(shù)據(jù)的封裝。 面向?qū)ο鬁y(cè)試 ：?jiǎn)卧獪y(cè)試－綜合測(cè)試－系統(tǒng)測(cè)試；算法層－類層－模板層－系統(tǒng)層。常采用回歸測(cè)試和自動(dòng)測(cè)試。 面向?qū)ο蟮姆治龊驮O(shè) 計(jì)方法： 1） Peter Coad 的 OOA 模型 的五個(gè)層次：主題層、對(duì)象類層、結(jié)構(gòu)層、屬性層、服務(wù)層；兩種結(jié)構(gòu)分類結(jié)構(gòu)（一般和特殊）和組裝結(jié)構(gòu)（整體和部分）。OOD 的四個(gè)活動(dòng)：設(shè)計(jì)問題域部件、設(shè)計(jì)人機(jī)交互部件、設(shè)計(jì)任務(wù)管理部件、設(shè)計(jì)數(shù)據(jù)管理部件。 2） Booch 的 OOD：認(rèn)為軟件開發(fā)是螺旋的，每個(gè)周期包括標(biāo)識(shí)類和對(duì)象、確定他們的含義、標(biāo)識(shí)他們的關(guān)系、說明每一個(gè)類的界面和實(shí)現(xiàn)。3）對(duì)象建模技術(shù) OMT： 三個(gè)模型即對(duì)象模型（鏈和關(guān)聯(lián)、泛化、聚集、模塊）、動(dòng)態(tài)模型（與時(shí)間和操作順序有關(guān)的特征，用狀態(tài)圖表示）、功能模型（描 述與值變換有關(guān)的特征 用數(shù)據(jù)流圖表示）。 4）統(tǒng)一建模語 UML： UML 三要素（ UML 的基本構(gòu)造塊、支配這些構(gòu)造塊如何存放的規(guī)則、運(yùn)用與整個(gè)語言的一些公共機(jī)制）。 三種構(gòu)造塊 （事物、關(guān)系、圖）。 四種事務(wù) ：結(jié)構(gòu)事物 (靜態(tài)部分類 接口 協(xié)作 用例 主動(dòng)類 構(gòu)件 結(jié)點(diǎn) )、行為事物（交互和狀態(tài)機(jī)）、分組事物（包 是概念性的僅在開發(fā)時(shí)存在）、注釋事物。 四種關(guān)系 ： 依賴（事物間語義關(guān)系）、關(guān)聯(lián)（結(jié)構(gòu)關(guān)系）、聚集（特殊的關(guān)聯(lián) 整體和部分）、泛化（一般和特殊）、實(shí)現(xiàn)（類元之間的語義關(guān)系）。 27 五類 9 種圖： ①用例圖 （用戶角度描述系統(tǒng) 功能，用于對(duì)系統(tǒng)的語境和需求建模）、 ②靜態(tài)圖 （類圖、對(duì)象圖；定義類之間關(guān)系和類內(nèi)結(jié)構(gòu)）、 ③行為圖 （狀態(tài)圖由狀態(tài)轉(zhuǎn)換事件和活動(dòng)組成；活動(dòng)圖用于工作流建模和對(duì)操作建模）、 ④交互圖 （順序圖 合作圖：描述對(duì)象間的交互關(guān)系）、 ⑤實(shí)現(xiàn)圖（構(gòu)件圖：描述代碼部件的物理結(jié)構(gòu)及各部件之間的關(guān)系； 配置圖即部署圖：定義系統(tǒng)中軟硬件關(guān)系。） 11 標(biāo)準(zhǔn)化知識(shí) 國(guó)際標(biāo)準(zhǔn)化組織 ISO 和 IEC。統(tǒng)一是標(biāo)準(zhǔn)化的本質(zhì)， 目的 是建立最佳秩序和獲得最佳效益。標(biāo)準(zhǔn)復(fù)審（ 5 年次）要確保其有效性、先進(jìn)性、適用性。 按性質(zhì)分類 ：技術(shù)標(biāo)準(zhǔn)、管理標(biāo)準(zhǔn)、工作標(biāo)準(zhǔn)。 采用國(guó)際和國(guó)外先進(jìn)標(biāo)準(zhǔn)的方法 ：認(rèn)可法、封面法、完全重印法、翻譯法、重新制定法、包括引用法。采用程度 ：等同 idt、等效 eqv、非等效采用 neq。 標(biāo)準(zhǔn)化條碼 EAN，共有 13 位： 3 位前綴表示國(guó)家、 4 位廠商代碼、 5位商品代碼、 1 位效驗(yàn)碼。 ISO9000： 是質(zhì)量管理和質(zhì)量保證的標(biāo)準(zhǔn)，按照全面質(zhì)量管理的 PDCA 模式工作。 ISO9000： 2020 現(xiàn)有 13 項(xiàng)標(biāo)準(zhǔn)，有 4個(gè)核心標(biāo)準(zhǔn)（基礎(chǔ)和術(shù)語 用概念圖描述、要求、業(yè)績(jī)改進(jìn)指南、審核指南）。標(biāo)準(zhǔn)確認(rèn)的 8 項(xiàng)原則：以顧客為中心、領(lǐng)導(dǎo)作用、全員參與、過程方法（ 4 大過程即管理職責(zé)、資源管理、產(chǎn)品實(shí)現(xiàn)、測(cè)量分析和改進(jìn)）、管理的系統(tǒng)方法、 28 持續(xù)改進(jìn)、基于實(shí)事的決策方法、互利的供求關(guān)系。 標(biāo)準(zhǔn)化對(duì)象有技術(shù)標(biāo)準(zhǔn)、管理標(biāo)準(zhǔn)和工作標(biāo)準(zhǔn)。 計(jì)算機(jī)軟件產(chǎn)品編制開發(fā)指南是國(guó)家批準(zhǔn)的標(biāo)準(zhǔn)，所以是推薦性的國(guó)家標(biāo)準(zhǔn)。 信息產(chǎn)業(yè)部批準(zhǔn)的標(biāo)準(zhǔn)應(yīng)該是行業(yè)標(biāo)準(zhǔn)，因?yàn)樵摬块T是國(guó)家的行政管理部門。 IEC 國(guó)際電工委員會(huì) 國(guó)際電信聯(lián)盟 ITU指定了 X和 V系列標(biāo)準(zhǔn)， V系列建議是針對(duì)電話通信、 X系列是針對(duì)網(wǎng)絡(luò)接口和公用網(wǎng)絡(luò)例如 定了分組交換網(wǎng)絡(luò)接口標(biāo)準(zhǔn)， 準(zhǔn)。 IEEE 美國(guó)電氣電子工程師學(xué)會(huì) 制 定了 802局域網(wǎng)標(biāo)準(zhǔn)。 CMM 成熟度模型 1)初始級(jí) ――軟件過程的特點(diǎn)是無秩序的，有時(shí)甚至是混亂的。軟件過程定義幾乎處于無章法可循的狀態(tài)，軟件產(chǎn)品所取得的成功往往依賴極個(gè)別人的努力和機(jī)遇。 2)可重復(fù)級(jí) ――已建立了基本的項(xiàng)目管理賽程，可用于對(duì)成本、進(jìn)度和功能特性進(jìn)行跟蹤。對(duì)類似的應(yīng)用項(xiàng)目，有章可循并能重復(fù)以往所取得的成功。 3)已定義級(jí) ――用于管理的和工程的軟件過程均已文檔化、標(biāo)準(zhǔn)化，并形成了整修軟件組織的標(biāo)準(zhǔn)軟件過程。全部項(xiàng)目均采用與實(shí)際情況相吻合的、適當(dāng)修改后的標(biāo)準(zhǔn)軟件過程來進(jìn)行操作。 4) 已管理級(jí) ― ―軟件過程和產(chǎn)品質(zhì)量有詳細(xì)的度 29 量標(biāo)準(zhǔn)。軟件過程和產(chǎn)品質(zhì)量得到了有效的認(rèn)識(shí)和控制。 5)優(yōu)化級(jí) ――通過對(duì)來自過程、新概念和新技術(shù)等方面的各種有用信息的有效分析，能夠不斷地、持續(xù)性地對(duì)過程進(jìn)行改進(jìn)。 12 知識(shí)產(chǎn)權(quán)知識(shí) 《民法通則》保護(hù)。 知識(shí)產(chǎn)權(quán) 分為兩類工業(yè)產(chǎn)權(quán)和著作權(quán)。特點(diǎn)：無形性、雙重性、確認(rèn)性、獨(dú)占性、地域性、時(shí)間性（專利 20 年，實(shí)用新型和外觀 10 年，到期前 6