1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法算法-是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則算法的基本特征-可行性、確定型、有窮性、擁有足夠的情報(bào)算法的基本要素-一是對數(shù)據(jù)對象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)算法設(shè)計(jì)基本方法-列舉法、歸納法、遞推、遞歸、減半遞推算法的復(fù)雜度-包括時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度-執(zhí)行算法所需的計(jì)算工作量空間復(fù)雜度-執(zhí)行算法所需的內(nèi)存空間數(shù)據(jù)結(jié)構(gòu)-相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。；父親、兒兒等都是數(shù)據(jù)元素。前件-數(shù)據(jù)元間的關(guān)系，如父親是兒子和女兒的前件后件-如兒子是父親的后件結(jié)構(gòu)-指數(shù)據(jù)元間的前后件關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元間邏輯關(guān)系，而與它們在

2、計(jì)算機(jī)中的位置無關(guān)數(shù)據(jù)的結(jié)構(gòu)（物理結(jié)構(gòu)）-數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)空間中的存放形式，數(shù)據(jù)元素在計(jì)算機(jī)空間的位置關(guān)系可能與邏輯關(guān)系不同。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元構(gòu)與非線性結(jié)構(gòu)間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分兩類-線性結(jié)線性結(jié)構(gòu)（線性表）-滿足下列兩個條件（1）有且只有一個根結(jié)點(diǎn)（2）每一個結(jié)點(diǎn)最多有一個前件和后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，否則為非線性結(jié)構(gòu)。線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)元間的相對位置是線性的，其存儲方式為順序的，如數(shù)組棧-是限定在一端進(jìn)行與刪除的線性表，一端封閉(bottom)，另一端開口(top)，其操作原則是“先進(jìn)后出”，棧的運(yùn)算有入棧、退棧、讀棧頂元素隊(duì)列

3、-是指在一端進(jìn)行（稱為隊(duì)尾rear）而在另一端進(jìn)行刪除（稱為隊(duì)頭 front）的線性表，其操作規(guī)則是“先進(jìn)先出”，其運(yùn)算有入隊(duì)和退隊(duì)。順序結(jié)構(gòu)-運(yùn)算簡單，方便，適用于小線性表和長度固定的線性表鏈?zhǔn)浇Y(jié)構(gòu)-應(yīng)用于元素變動頻繁的大線性表樹-是一種簡單的非線性結(jié)構(gòu)，而且是層次結(jié)構(gòu)，是倒立的大樹，有根結(jié)點(diǎn)、父結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)。根結(jié)點(diǎn)在第一層，一個結(jié)點(diǎn)所擁有的后件的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為 樹的度，樹的最大層次稱為樹的深度。二叉樹-（1）非空二叉樹只有一個根結(jié)點(diǎn)（2）每一個結(jié)點(diǎn)最多有兩棵（樹和右），其結(jié)構(gòu)為鏈?zhǔn)?。二叉樹性質(zhì)-（1）K 層上最多有 2K-1（k=1）個結(jié)點(diǎn)（2）深度為

4、 m 的二叉樹最多有2m-1 個結(jié)點(diǎn)（3）度為 0 的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）比度為 2 的結(jié)點(diǎn)多一個（4）具有 n 個結(jié)點(diǎn)的二叉樹，其深度至少為Log2n+1，其中Log2n表示對 Log2n 取整滿二叉樹-除最后一層外，其余層的結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)完全二叉樹-除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉樹。完全二叉樹有兩個性質(zhì)：（1）具有 n 個結(jié)點(diǎn)的完全二叉樹的深度為Log2n+1（2）二叉樹遍歷-不重復(fù)地各個結(jié)點(diǎn)。分為前序遍歷(DLR-根左右)、中序遍歷(LDR-左根右)和后序遍歷

5、（LRD-左右根）查找技術(shù)-順序查找對于長度為 n 的有序線性表，查找時需要比較 n 次二分法查找對于長度為 n 的有序線性表，查找時需要比較 log2n 次排序技術(shù)-假設(shè)線性表的長度為 n，則冒泡排序和簡單排序的比較次數(shù)（時間復(fù)雜排序的比較次數(shù)為 O(n1 5)（O 代表不超過括號內(nèi)數(shù)值的最大整數(shù)值）;度）為 n(n-1)/2;簡單選擇排序的比較次數(shù)為 n(n-1)/2;堆排序的比較次數(shù)為 O(nlog2n).習(xí)題 1算法的時間復(fù)雜度是指（ ），算法的空間復(fù)雜度是指（ ）；隊(duì)列是（先進(jìn)先出），棧是（先進(jìn)后出）；下列二叉樹的遍歷結(jié)果：前序遍歷（ABDECF）、中序遍歷（DBEAFC）、后續(xù)遍歷

6、（DEBFCA）；在深度為 5 的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為（16）；設(shè)樹T 的度為 4，其中度為 1，2，3；線性表、棧、隊(duì)列、線性鏈表是（線性結(jié)構(gòu)），樹是（非線性結(jié)構(gòu)）；數(shù)據(jù)的結(jié)構(gòu)是指（ ）；，4 的結(jié)點(diǎn)的個數(shù)分別為 4，2，1，1。則 T 中的葉子結(jié)點(diǎn)的個數(shù)為（8）；對于長度為 n 的有序線性表，順序查找次數(shù)為（n）,二分法查找次數(shù)為（log2n）；一棵完全二叉樹共有 700 個結(jié)點(diǎn)，則在該二叉樹中有（350）個葉子結(jié)點(diǎn)；一棵二叉樹的中序遍歷結(jié)果為 DBEAFC，前序遍歷結(jié)果為 ABDECF，則后續(xù)遍歷結(jié)果為（DEBFCA）；冒泡排序的時間復(fù)雜度為（n(n-1)/2）;在一個容量為 1

7、5 的循環(huán)隊(duì)列中，若頭指針 front=6,尾指針 rear=9,則該循環(huán)隊(duì)列有（3）元素；第二章 程序設(shè)計(jì)基礎(chǔ)結(jié)構(gòu)化程序設(shè)計(jì)的三種結(jié)構(gòu)-是順序、選擇（分支）和循環(huán)（重復(fù)）對象-表示客觀世界的任何實(shí)體對象基本特點(diǎn)-標(biāo)識惟一性、分類型、多態(tài)性、封裝性、模塊獨(dú)立性好類-是具有共同屬性和方法的對象的集合實(shí)例-任何一個對象都是其對應(yīng)類的實(shí)例消息-一個實(shí)例和另一個實(shí)例之間傳遞的信息繼承-是指直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。例如子類繼承父類面象方法的主要特征結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)-程序的易讀性良好的程序設(shè)計(jì)風(fēng)格是-程序應(yīng)簡單、清晰、可讀性好習(xí)題 2在面象方法中，一個對象請求另一個對象為其服務(wù)

8、的方式是通過發(fā)送（消息）來實(shí)現(xiàn)的信息隱蔽的概念與（模塊獨(dú)立性）概念直接相關(guān)（任何對象都具有繼承性）這句話是錯誤的注釋分為（序言性注釋）和（功能性注釋）在面象方法中，信息隱蔽是通過對象的（封裝性）來實(shí)現(xiàn)的類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的（實(shí)例）在面象方法中，類之間共享屬性和操作的機(jī)制稱為（繼承）第三章工程基礎(chǔ)工程過程四種基本活動-規(guī)格說明、開發(fā)、確認(rèn)、演進(jìn)（PDCA）主要表現(xiàn)在成本、質(zhì)量和生產(chǎn)率的問題生命周期-產(chǎn)品從提出、實(shí)現(xiàn)、使用三個階段。到停止使用退役的過程。分為定義、開發(fā)、運(yùn)行生命周期的主要活動階段-可行性分析、需求分析（定義階段）、設(shè)計(jì)（概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)）、實(shí)現(xiàn)、測試（開發(fā)

9、階段）、運(yùn)行、和退役（階段）。常見的需求分析方法-（1）結(jié)構(gòu)化分析方法-主要包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法 SA；面向數(shù)據(jù)結(jié)構(gòu)的Jackson 方法 JSD；面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法 DSSD。（2）面象的分析方法 OOA結(jié)構(gòu)化分析方法工具-（1）數(shù)據(jù)流圖 DFD，記住 DFD 圖的幾個符號：加工（轉(zhuǎn)換）數(shù)據(jù)流文件（數(shù)據(jù)源）源（潭）（2）數(shù)據(jù)字典DD（3）判定樹（4）判定表詳細(xì)設(shè)計(jì)的過程設(shè)計(jì)工具-程序結(jié)構(gòu)圖（SC），N-S 圖，問題分析圖（PAD），PDL 語言(程序設(shè)計(jì)語言)程序流程圖（PFD）的幾個符號：控制流加工步驟邏輯條件的模塊獨(dú)立性-內(nèi)聚性（一個模塊各個元間彼此結(jié)合的緊密

10、程度的度量）越強(qiáng)，耦合性（模塊之間相互連接的緊密程度的度量）越弱，模塊獨(dú)立性越好測試：靜態(tài)測試和動態(tài)測試測試的過程：單元測試-集成測試-確認(rèn)測試-系統(tǒng)測試黑盒測試：功能測試（數(shù)據(jù)驅(qū)動測試），主要方法-等價類劃分法，邊界值分析法和錯誤推測法動態(tài)測試白盒測試：結(jié)構(gòu)測試（邏輯驅(qū)動測試），主要方法-邏輯覆蓋、基本路徑調(diào)試習(xí)題 3在生命周期中，能準(zhǔn)確地判斷系統(tǒng)必須做什么和必須具備哪些功能的階段是（需求分析）工程的 3 個要素（工具），（過程），（方法）檢查產(chǎn)品是否符合需求定義的過程稱為（確認(rèn)測試）設(shè)計(jì)原則是（抽象）、（模塊化）、（信息隱蔽）需求分析常用的工具是（DFD）在結(jié)構(gòu)化方法中，功能分解屬于（總體

11、設(shè)計(jì)）階段測試的目的是（改正錯誤 ），調(diào)試（debug）的目的是（改正錯誤）需求分析 階段 可分為四個方面（需求獲取）、（需求分析）、（編寫需求格式說明）、（需求評審）是（程序）、（數(shù)據(jù)）、（文檔）的集合Jakson 方法是一中面向（數(shù)據(jù)流）的結(jié)構(gòu)化方法工程的內(nèi)容包括（開發(fā)技術(shù)）、（工程管理）數(shù)據(jù)流圖的類型有（交換型）、（事務(wù)型）開發(fā)環(huán)境是全面支持開發(fā)全過程的（工具）集合第四章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫-DB；數(shù)據(jù)庫管理系統(tǒng)-DBMS；數(shù)據(jù)庫管理員-DBA；數(shù)據(jù)庫系統(tǒng)-DBS；數(shù)據(jù)庫應(yīng)用系統(tǒng)-DBAS數(shù)據(jù)模型所描述的內(nèi)容分三個部分（數(shù)據(jù)結(jié)構(gòu)）、（數(shù)據(jù)操作）、（數(shù)據(jù)約束）邏輯數(shù)據(jù)模型分（層次模型）、

12、（網(wǎng)狀模型）、（關(guān)系模型）、（面象模型）數(shù)據(jù)庫系統(tǒng)三層模式：概念模式，外模式（用戶模式），內(nèi)模式（物理模式）E-R 模型-實(shí)體關(guān)系模型，主要由實(shí)體、屬性、聯(lián)系組成，聯(lián)系分：1 對 1，1 對多，多對多；實(shí)體集屬性聯(lián)系集以二維表為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型，關(guān)系模型采用二維表來表示，簡稱表，由行和列組成，行稱為元組或，列稱為字段或?qū)傩灾麈I-唯一標(biāo)識一個的字段外鍵-一個表的字段是其他表的主鍵習(xí)題 4在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段，其中數(shù)據(jù)獨(dú)立性最高的階段是（數(shù)據(jù)庫系統(tǒng)）數(shù)據(jù)庫系統(tǒng)減少了（數(shù)據(jù)冗余）；數(shù)據(jù)庫系統(tǒng)的是（數(shù)據(jù)庫管理系統(tǒng)）用樹型結(jié)構(gòu)來表示實(shí)體間聯(lián)系的模型稱為（層次模型）關(guān)系表中的每一行稱為（元組）關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)的專門關(guān)系運(yùn)算包括（選擇）、（投影）、（連接）在關(guān)系數(shù)據(jù)庫中，用來表示實(shí)體之間聯(lián)系的是（二維表）數(shù)據(jù)庫設(shè)計(jì)包括兩方面的設(shè)計(jì)內(nèi)容（概念設(shè)計(jì)）、（邏輯設(shè)計(jì)）（注釋：需求分析-（需求說明）-概念設(shè)計(jì)-（概念結(jié)構(gòu)）-邏輯結(jié)構(gòu)設(shè)計(jì)-（邏輯結(jié)構(gòu)）-物理設(shè)計(jì)-（物理結(jié)構(gòu)）-）將 E-R 圖轉(zhuǎn)換到關(guān)系模式時，實(shí)體與聯(lián)系都可以表示成