全國(guó)計(jì)算機(jī)等級(jí)考試

二級(jí)公共基礎(chǔ)知識(shí)

基本要求1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力。6.掌握數(shù)據(jù)庫(kù)的基本知識(shí)，了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。一、基本數(shù)據(jù)結(jié)構(gòu)與算法1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6.樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序）。二、程序設(shè)計(jì)基礎(chǔ)1.程序設(shè)計(jì)方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計(jì)。3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。考試方式1、公共基礎(chǔ)的考試方式為筆試，與C語(yǔ)言（VisualBASIC、VisualFoxPro、Java、Access、VisualC++）的筆試部分合為一張?jiān)嚲怼９不A(chǔ)部分占全卷的30分。2、公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題。學(xué)習(xí)方法理解基本概念多做練習(xí)適當(dāng)記憶一些名詞與所學(xué)的VFP\c\Access程序設(shè)計(jì)知識(shí)結(jié)合起來(lái)，以增加對(duì)知識(shí)的理解能力1.基本數(shù)據(jù)結(jié)構(gòu)與算法算法的基本特征:(1)可行性(2)確定性(3)有窮性(4)輸入和輸出（擁有足夠的情報(bào)）1.1算法1.2算法復(fù)雜度1.2.1時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。通常有事后統(tǒng)計(jì)法和事前分析估算法。★算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量.★算法所執(zhí)行的基本運(yùn)算次數(shù)與問(wèn)題的規(guī)模n有關(guān).執(zhí)行算法所需要的計(jì)算工作量和f(n)同步增長(zhǎng)，記為:算法的工作量=f(n)時(shí)間復(fù)雜度=O(f(n))1.2.2算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來(lái)寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。

算法的時(shí)間復(fù)雜度是指A)執(zhí)行算法程序所需要的時(shí)間B)算法程序的長(zhǎng)度C)算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D)算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、

【1】和擁有足夠的情報(bào)。算法的空間復(fù)雜度是指

A)算法程序的長(zhǎng)度 B)算法程序中的指令條數(shù)

C)算法程序所占的存儲(chǔ)空間D)執(zhí)行過(guò)程中所需要的存儲(chǔ)空間在計(jì)算機(jī)中，算法是指

A)加工方法 B)解題方案的準(zhǔn)確而完整的描述

C)排序方法 D)查詢(xún)方法例題講解有窮性算法分析的目的是

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)找出算法中輸入和輸出之間的關(guān)系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少分別稱(chēng)為算法的【1】。時(shí)間復(fù)雜度和空間復(fù)雜度1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)1.2.1數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容(1)數(shù)據(jù)集中數(shù)據(jù)之間的邏輯關(guān)系線性樹(shù)圖(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(3)各種數(shù)據(jù)結(jié)構(gòu)的運(yùn)算（1）數(shù)據(jù)元素(DataElement)

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱(chēng)節(jié)點(diǎn)或記錄。1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲(chǔ)B鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面A.線性結(jié)構(gòu)(A,B,C,·······，X,Y,Z)例:學(xué)生成績(jī)表86胡孝臣95劉忠賞100張卓成績(jī)姓名學(xué)號(hào)①線性表②棧——后進(jìn)先出③隊(duì)列——先進(jìn)先出例:英文字母表①樹(shù)形結(jié)構(gòu)例:全校學(xué)生檔案管理的組織方式例:計(jì)算機(jī)文件管理系統(tǒng)也是典型的樹(shù)形結(jié)構(gòu)B．非線性結(jié)構(gòu)1423

例:數(shù)據(jù)結(jié)構(gòu)B(D,R)D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}213例:數(shù)據(jù)結(jié)構(gòu)C(D,R)D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

②圖形結(jié)構(gòu)元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(ai)=Lo+（i-1)*m1、順序存儲(chǔ)每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)（3）存儲(chǔ)結(jié)構(gòu)例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)

順序存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)地址數(shù)據(jù)7891011121314zhaoqiansunlizhouwuzhengwang7基地址順序存儲(chǔ)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里,具有以下特點(diǎn):1.隨機(jī)存取。2.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。3.長(zhǎng)度變化較大時(shí)，需按最大空間分配。4.表的容量難以擴(kuò)充。2、鏈?zhǔn)酱鎯?chǔ)每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來(lái)體現(xiàn)。例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：存儲(chǔ)地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針通常我們把鏈表畫(huà)成用箭頭相鏈接的結(jié)點(diǎn)的序列，結(jié)點(diǎn)之間的箭頭表示鏈域中的指針。zhaoqiansunlizhouwuzhengwang/H存儲(chǔ)地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針1.比順序存儲(chǔ)結(jié)構(gòu)多用空間(存儲(chǔ)密度小)(每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成)。2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3.插入、刪除靈活

(不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。4.非隨機(jī)存取。鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：鏈表不具有的特點(diǎn)是A)不必事先估計(jì)存儲(chǔ)空間B)可隨機(jī)訪問(wèn)任一元素C)插入刪除不需要移動(dòng)元素 D)所需空間與線性表長(zhǎng)度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于【1】

。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的

A)存儲(chǔ)結(jié)構(gòu) B)物理結(jié)構(gòu)

C)邏輯結(jié)構(gòu) D)物理和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】

兩大類(lèi)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指A）數(shù)據(jù)所占的存儲(chǔ)空間B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D）存儲(chǔ)在外存中的數(shù)據(jù)例題講解存儲(chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置

【2】的存儲(chǔ)單元中。

數(shù)據(jù)處理的最小單位是

A)數(shù)據(jù) B)數(shù)據(jù)元素C)數(shù)據(jù)項(xiàng) D)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門(mén)學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及

A)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B)計(jì)算方法C)數(shù)據(jù)映象D)邏輯存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是

A)順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)

B)隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)

C)隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)

D)任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)相鄰根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成

A)動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C)線性結(jié)構(gòu)和非線性結(jié)構(gòu)D)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的

【2】以及對(duì)數(shù)據(jù)的操作運(yùn)算。數(shù)據(jù)的基本單位是

【5】。下列敘述中，錯(cuò)誤的是

A)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)

B)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率無(wú)關(guān)

C)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的

D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素1.7棧和隊(duì)列1.7.1棧和隊(duì)列的定義棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱(chēng)為限定性的數(shù)據(jù)結(jié)構(gòu)。1.棧棧——是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧頂——表尾。棧底——表頭。空棧——不含元素的空表。…a1a2an棧底棧頂進(jìn)棧出棧棧s=(a1,a2,…,an)后進(jìn)先出（LIFO）3.隊(duì)列定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱(chēng)為先進(jìn)先出（FIFO）表。a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭隊(duì)尾棧和隊(duì)列的共同特點(diǎn)是

A)都是先進(jìn)先出B)都是先進(jìn)后出

C)只允許在端點(diǎn)處插入和刪除元素D)沒(méi)有共同點(diǎn)如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意順序一些重要的程序語(yǔ)言(如C語(yǔ)言和Pascal語(yǔ)言)允許過(guò)程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用

A)棧 B)堆C)數(shù)組 D)鏈表例題講解棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是

A)線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B)散列方式和索引方式

C)鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D)線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)是【1】

。下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是

A)線性鏈表B)棧C)循環(huán)鏈表 D)順序表▽當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿(mǎn)，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱(chēng)為

【2】。鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組上溢由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是A)減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B)節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率C)減少存取時(shí)間，降低上溢發(fā)生的機(jī)率D)節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率下列關(guān)于棧的敘述中正確的是Ａ）在棧中只能插入數(shù)據(jù)B）在棧中只能刪除數(shù)據(jù)C）棧是先進(jìn)先出的線性表D）棧是后進(jìn)先出的線性表下列關(guān)于隊(duì)列的敘述中正確的是Ａ）在隊(duì)列中只能插入數(shù)據(jù)B）在隊(duì)列中只能刪除數(shù)據(jù)C）隊(duì)列是先進(jìn)先出的線性表D）隊(duì)列是后進(jìn)先出的線性表1.6.1樹(shù)的定義由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。ACGT2DHIT3J

MBELKT1F現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類(lèi)的家族血緣關(guān)系等。1.6樹(shù)介紹幾個(gè)概念：結(jié)點(diǎn)（Node）：樹(shù)中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱(chēng)端結(jié)點(diǎn)。孩子（Child）：結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱(chēng)為這些結(jié)點(diǎn)的雙親。樹(shù)的深度（Depth)：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。樹(shù)的度：結(jié)點(diǎn)所具有的最大的度.森林（Forest）：M棵互不相交的樹(shù)的集合。ACGDHI

J

MBELKT1F1.6.2二叉樹(shù)（BinaryTree）1、二叉樹(shù)的定義及其性質(zhì)

(1)二叉樹(shù)的定義二叉樹(shù)的五種基本形態(tài)

二叉樹(shù)一種特殊的樹(shù)形結(jié)構(gòu)，特點(diǎn)是樹(shù)中每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)(即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn))，且子樹(shù)有左右之分，次序不能顛倒。

空二叉樹(shù)

僅有根結(jié)點(diǎn)

右子樹(shù)為空

左子樹(shù)為空左右子樹(shù)均非空性質(zhì)1:二叉樹(shù)的第i層上至多有2i-1（i

1）個(gè)結(jié)點(diǎn)。(2)二叉樹(shù)的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個(gè)節(jié)點(diǎn)。性質(zhì)2:深度為k的二叉樹(shù)中至多含有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)３：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。證明：設(shè)n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù)；∵二叉樹(shù)中所有結(jié)點(diǎn)的度均小于或等于2∴其結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2∵二叉樹(shù)中除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入設(shè)分支總數(shù)為B；則n=B+1;∵二叉樹(shù)的分支是由度為1或2的結(jié)點(diǎn)射出的∴B=n1+2*n2∴n=n1+2*n2+1=n0+n1+n2

n0=n2+1ABFCJM一般樹(shù)★滿(mǎn)二叉樹(shù)423167891011121314155特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。★完全二叉樹(shù)423167891011125特點(diǎn)：(1)除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，(2)最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。性質(zhì)４：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為112345678910121例：n=2k=2n=6k=3n=7k=3n=8k=4n=12k=4性質(zhì)５：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1=<i=<n)有：(2)如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));

否則其左孩子Lchild(i)是結(jié)點(diǎn)2i。

(3)如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子;

否則其右孩子Rchild(i)是結(jié)點(diǎn)2i+1。(1)如果i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根,無(wú)雙親;

如果i>1,則雙親Parent(i)是結(jié)點(diǎn)|i/2|。

例：112345678910121i=6其雙親為|i/2|=3；其左孩子為2*i=12;i=1是樹(shù)的根,無(wú)雙親;其左孩子為2*i=2,右孩子為2*i+1=3.∵2*i=18>122*i+1=19>12∴其無(wú)左、右孩子。∵2*i+1=13>12∴其無(wú)右孩子。i=9其雙親為|i/2|=4；1.6.3二叉樹(shù)的遍歷查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄?shù)中全部結(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹(shù)中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。按先左后右的原則，一般使用三種遍歷：先序遍歷(DLR):

訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。中序遍歷(LDR):

按中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。后序遍歷(LRD):

按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉樹(shù)已遍歷完。

（2）遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCDLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過(guò)程ABDCBDACDBCA已知二叉樹(shù)后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是

A)acbedB)decabC)deabc D)cedba已知一棵二叉樹(shù)前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序遍歷為

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG樹(shù)是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是

A)有且只有1 B)1或多于1C)0或1 D)至少2下列敘述中正確的是

A)線性表是線性結(jié)構(gòu) B)棧與隊(duì)列是非線性結(jié)構(gòu)

C)線性鏈表是非線性結(jié)構(gòu) D)二叉樹(shù)是線性結(jié)構(gòu)例題講解在深度為5的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A)32 B)31C)16 D)15若某二叉樹(shù)的前序遍歷訪問(wèn)順序是abdgcefh，中序遍歷訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是

A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有【1】。具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)設(shè)一棵二叉樹(shù)中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為

A)12 B)13C)14 D)15雙親結(jié)點(diǎn)設(shè)有下列二叉樹(shù)：

對(duì)此二叉樹(shù)前序遍歷的結(jié)果為A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPT設(shè)有下列二叉樹(shù)：對(duì)此二叉樹(shù)的中序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA設(shè)樹(shù)T的度為4,其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1。則T中的葉子結(jié)點(diǎn)數(shù)為A）8B）7C）6D）5設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。

在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有（）個(gè)元素。設(shè)一棵二叉樹(shù)的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（）。3503DEBFCA1.7查找和排序順序查找與二分查找算法基本排序算法（交換類(lèi)排序、選擇類(lèi)排序、插入類(lèi)排序）1.7.1順序查找（線性查找）◆查找過(guò)程：對(duì)給定的一關(guān)鍵字K，從線性表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。◆可以采用從前向后查，也可采用從后向前查的方法。◆在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長(zhǎng)度較大。最好情況：1最壞情況：n◆在下面兩種情況下只能采取順序查找：

a.線性表為無(wú)序表（元素排列是無(wú)序的）；

b.即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1.7.1折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。分三種情況：

1）若中間項(xiàng)的值等于x,則說(shuō)明已查到。

2）若x小于中間項(xiàng)的值,則在線性表的前半部分查找；

3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。排序方法插入排序選擇排序交換排序歸并排序簡(jiǎn)單插入排序希爾排序簡(jiǎn)單選擇排序堆排序起泡排序快速排序1.7.2排序在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為

【2】。假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為

A)log2n B)n2C)O(n1..5) D)n(n-1)/2例題講解log2n冒泡排序算法在最好的情況下的元素交換次數(shù)為【1】

。在最壞情況下，堆排序需要比較的次數(shù)為

【2】。排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見(jiàn)的排序方法有插入排序、【1】

和選擇排序等。0nlog2n交換排序2.程序設(shè)計(jì)基礎(chǔ)2.1程序設(shè)計(jì)方法與風(fēng)格2.1.1程序設(shè)計(jì)方法結(jié)構(gòu)化設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法2.2結(jié)構(gòu)化程序設(shè)計(jì)基本概念三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)三種基本結(jié)構(gòu)的特點(diǎn)只有一個(gè)入口只有一個(gè)出口每一個(gè)基本結(jié)構(gòu)中的每一部分都有機(jī)會(huì)執(zhí)行到結(jié)構(gòu)內(nèi)不存在“死循環(huán)”設(shè)計(jì)原則自頂向下（先總體，后細(xì)節(jié)）逐步求精（設(shè)計(jì)子目標(biāo)過(guò)渡）模塊化（分解總目標(biāo)）限制使用goto語(yǔ)句對(duì)象(Object)對(duì)象是基本的運(yùn)行時(shí)認(rèn)得實(shí)體，它既包括數(shù)據(jù)（屬性），也包括作用于數(shù)據(jù)的操作（行為）。一個(gè)對(duì)象把屬性和行為封裝為一個(gè)整體一個(gè)對(duì)象通常可由對(duì)象名、屬性和操作3部分組成對(duì)象的基本特性：（1）標(biāo)識(shí)唯一性（對(duì)象可區(qū)分）（2）分類(lèi)性（對(duì)象抽象成類(lèi)）（3）多態(tài)性（同一操作可以是不同對(duì)象的行為）（4）封裝性（只能看到對(duì)象的外部特性）（5）模塊獨(dú)立性好（對(duì)象內(nèi)部各元素結(jié)合緊密、內(nèi)聚性強(qiáng)）2.3面向?qū)ο蟮某绦蛟O(shè)計(jì)方法類(lèi)(Class)和實(shí)例一個(gè)類(lèi)定義了一組大體上相似的對(duì)象。一個(gè)類(lèi)所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行為和屬性。類(lèi)是在對(duì)象之上的抽象，對(duì)象是類(lèi)的具體化，是類(lèi)的實(shí)例封裝(Encapsulation)將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構(gòu)成一個(gè)具有類(lèi)類(lèi)型的對(duì)象的描述。對(duì)象的內(nèi)部實(shí)現(xiàn)受保護(hù)，外界不能訪問(wèn)封裝簡(jiǎn)化了程序員對(duì)對(duì)象的使用繼承(Inheritance)繼承是父類(lèi)和子類(lèi)之間共享數(shù)據(jù)的方法的機(jī)制一個(gè)子類(lèi)可以繼承它的父類(lèi)（或祖先類(lèi)）中的屬性和操作子類(lèi)中可以定義自己的屬性和操作單重繼承、多重繼承多態(tài)性(Polymorphism)不同的對(duì)象收到同一消息可以產(chǎn)生完全不同的結(jié)構(gòu)，這一現(xiàn)象叫做多態(tài)性多態(tài)的實(shí)現(xiàn)受到繼承的支持消息(Message)

對(duì)象之間進(jìn)行通信的一種構(gòu)造結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是

A)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)B)分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)

C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu)D)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)在設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是

A)不限制goto語(yǔ)句的使用B)減少或取消注解行

C)程序越短越好D)程序結(jié)構(gòu)應(yīng)有助于讀者理解程序設(shè)計(jì)語(yǔ)言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和

A)對(duì)象成分 B)變量成分

C)語(yǔ)句成分 D)傳輸成分例題講解結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是

A)程序的規(guī)模 B)程序的效率

C)程序設(shè)計(jì)語(yǔ)言的先進(jìn)性 D)程序易讀性以下不屬于對(duì)象的基本特點(diǎn)的是

A)分類(lèi)性B)多態(tài)性C)繼承性 D)封裝性對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是

A)程序應(yīng)簡(jiǎn)單、清晰、可讀性好 B)符號(hào)名的命名只要符合語(yǔ)法

C)充分考慮程序的執(zhí)行效率 D)程序的注釋可有可無(wú)在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的

A)安全性 B)一致性C)可理解性 D)合理性程序的3種基本控制結(jié)構(gòu)是

A)過(guò)程、子過(guò)程和分程序 B)順序、選擇和重復(fù)

C)遞歸、堆棧和隊(duì)列 D)調(diào)用、返回和轉(zhuǎn)移下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則的是

A)自頂向下 B)由底向上

C)模塊化 D)限制使用goto語(yǔ)句對(duì)象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對(duì)數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行

A)結(jié)合 B)隱藏C)封裝 D)抽象☆類(lèi)是一個(gè)支持集成的抽象數(shù)據(jù)類(lèi)型，而對(duì)象是類(lèi)的_______。實(shí)例在面向?qū)ο蠓椒ㄖ校粋€(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送A）調(diào)用語(yǔ)句B）命令C）口令D）消息信息屏蔽的概念與下述哪一種概念直接相關(guān)A）軟件結(jié)構(gòu)定義B）模塊獨(dú)立性C）模塊類(lèi)型劃分D）模塊偶合度下列對(duì)象概念描述錯(cuò)誤的是A）任何對(duì)象都必須有繼承性B）對(duì)象是屬性和方法的封裝體C）對(duì)象間的通訊靠消息傳遞D）操作是對(duì)象的動(dòng)態(tài)屬性下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法

D)面向?qū)ο蟮姆治龇椒ㄔ诿嫦驅(qū)ο蟮某绦蛟O(shè)計(jì)中，類(lèi)描述的是具有相似性質(zhì)的一組

【3】

在面向?qū)ο蠓椒ㄖ校?lèi)之間共享屬性和操作的機(jī)制稱(chēng)為

【2】。一個(gè)類(lèi)可以從直接或間接的祖先中繼承所有屬性和方法。采用這個(gè)方法提高了軟件的

【3】。對(duì)象的共同行為和屬性繼承可重用性面向?qū)ο蟮哪Ｐ椭校罨镜母拍钍菍?duì)象和

【3】。在面向?qū)ο蟮脑O(shè)計(jì)中，用來(lái)請(qǐng)求對(duì)象執(zhí)行某一處理或回答某些信息的要求稱(chēng)為

【4】。在程序設(shè)計(jì)階段應(yīng)該采取

【2】和逐步求精的方法，把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而用某種程序設(shè)計(jì)語(yǔ)言寫(xiě)成程序。在面向?qū)ο蠓椒ǚN，類(lèi)之間共享屬性和操作的機(jī)制稱(chēng)為_(kāi)_____。消息自頂向下屬性、行為繼承

【3】是一種信息隱蔽技術(shù)，目的在于將對(duì)象的使用者和對(duì)象的設(shè)計(jì)者分開(kāi)。可以把具有相同屬性的一些不同對(duì)象歸類(lèi)，稱(chēng)為

【3】。子程序通常分為兩類(lèi)：

【2】和函數(shù)，前者是命令的抽象，后者是為了求值。源程序文檔化要求程序應(yīng)加注釋。注釋一般分為序言性注釋和_____。在面向?qū)ο蠓椒ǚN，信息屏蔽是通過(guò)對(duì)象的_______性來(lái)實(shí)現(xiàn)的。封裝類(lèi)過(guò)程功能性注釋封裝3.軟件工程基礎(chǔ)3.1基本概念軟件程序數(shù)據(jù)相關(guān)文檔機(jī)器可執(zhí)行的程序和數(shù)據(jù)機(jī)器不能執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔軟件的特點(diǎn)包括：（1）軟件是一種邏輯實(shí)體；（2）軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程；（3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題；（4）軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題；（5）軟件復(fù)雜性高，成本昂貴；（6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。軟件按功能分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。1.軟件危機(jī)早期的軟件主要指程序，采用個(gè)體工作方式，缺少相關(guān)文檔，質(zhì)量低，維護(hù)困難，這些問(wèn)題稱(chēng)為“軟件危機(jī)”，軟件工程概念的出現(xiàn)源自于軟件危機(jī)。軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問(wèn)題。2.軟件工程軟件工程是指應(yīng)用計(jì)算機(jī)科學(xué)、數(shù)學(xué)及管理科學(xué)等原理，以工程化的原則和方法來(lái)解決軟件問(wèn)題的工程。其目的是提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低軟件成本。軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。

3.軟件工程三要素方法：完成軟件工程項(xiàng)目的技術(shù)手段工具：支持軟件的開(kāi)發(fā)、管理、文檔生成過(guò)程：支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理;

將方法和工具綜合起來(lái),以達(dá)到合理、及時(shí)地進(jìn)行計(jì)算機(jī)軟件開(kāi)發(fā)的目的。4.軟件生命周期將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用退役的過(guò)程稱(chēng)為軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)3個(gè)階段。維護(hù)是持續(xù)時(shí)間最長(zhǎng)，花費(fèi)代價(jià)最大的一個(gè)階段，軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)代價(jià)6個(gè)活動(dòng)階段可行性研究與計(jì)劃制定：確定系統(tǒng)的總體目標(biāo)。參加人員有用戶(hù)、項(xiàng)目負(fù)責(zé)人和系統(tǒng)分析員，產(chǎn)生文檔有可行性分析報(bào)告、項(xiàng)目計(jì)劃書(shū)等需求分析：確定系統(tǒng)的邏輯模型。參加人員有用戶(hù)、項(xiàng)目負(fù)責(zé)人和系統(tǒng)分析員。產(chǎn)生文檔為需求規(guī)格說(shuō)明書(shū)，其作用：（1）便于用戶(hù)、開(kāi)發(fā)人員進(jìn)行理解交流；（2）反映用戶(hù)問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù)；（3）作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)。軟件設(shè)計(jì)：包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)和過(guò)程設(shè)計(jì)。結(jié)構(gòu)設(shè)計(jì)是定義軟件系統(tǒng)各部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)是將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和操作系統(tǒng)之間及軟件與人之間如何通信；過(guò)程設(shè)計(jì)是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述。軟件設(shè)計(jì)分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。參加人員有系統(tǒng)分析員和高級(jí)程序員。產(chǎn)生的文檔有設(shè)計(jì)規(guī)格說(shuō)明書(shū)。軟件實(shí)現(xiàn)：編程。高級(jí)程序員和程序員產(chǎn)生源程序清單軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。產(chǎn)生軟件測(cè)試計(jì)劃和軟件測(cè)試報(bào)告運(yùn)行與維護(hù)3.2需求分析與結(jié)構(gòu)化分析方法需求分析的方法結(jié)構(gòu)化分析方法面向?qū)ο蟮姆治龇椒嫦驍?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)開(kāi)發(fā)方法(DSSD)結(jié)構(gòu)化分析常用工具:(1)數(shù)據(jù)流圖DFD(2)數(shù)據(jù)字典DD(3)判定樹(shù)(4)判定表結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。3.3結(jié)構(gòu)化設(shè)計(jì)方法、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)軟件設(shè)計(jì)○軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。○軟件設(shè)計(jì)是開(kāi)發(fā)階段最重要的步驟，是將需求準(zhǔn)確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系。數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。過(guò)程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述。從工程管理角度來(lái)看：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)的基本原理：（1）抽象（2）模塊化（3）信息隱蔽（4）模塊獨(dú)立化內(nèi)聚性：耦合性：在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。3.3.2概要設(shè)計(jì)設(shè)計(jì)的基本任務(wù)軟件的系統(tǒng)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)設(shè)計(jì)編寫(xiě)概要設(shè)計(jì)文檔概要設(shè)計(jì)文檔評(píng)審需求分析邏輯模型數(shù)據(jù)流圖概要設(shè)計(jì)系統(tǒng)結(jié)構(gòu)圖物理模型概要設(shè)計(jì)的方法:結(jié)構(gòu)圖（SC)：概要設(shè)計(jì)(軟件結(jié)構(gòu)設(shè)計(jì))的工具:3.3.3詳細(xì)設(shè)計(jì)根本目標(biāo)確定應(yīng)用怎樣具體的實(shí)現(xiàn)所要求的系統(tǒng)，不是具體的編寫(xiě)程序，而是要設(shè)計(jì)程序的“藍(lán)圖”詳細(xì)設(shè)計(jì)常用的設(shè)計(jì)工具（工程設(shè)計(jì)工具）：圖形工具：程序流程圖：箭頭表示控制流，方框表示加工步驟，菱形表示邏輯條件。N-S圖：有五種基本圖形。PAD圖：?jiǎn)栴}分析圖，有五種基本圖型。表格工具：判定表。語(yǔ)言工具：PDL——過(guò)程設(shè)計(jì)語(yǔ)言（結(jié)構(gòu)化的英語(yǔ)和偽碼）。3.4軟件測(cè)試

軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程3.4.1意義目的為了發(fā)現(xiàn)錯(cuò)誤希望能以最少的人力和時(shí)間發(fā)現(xiàn)潛在的各種錯(cuò)誤和缺陷保證系統(tǒng)質(zhì)量和可靠性的關(guān)鍵步驟

3.4.2測(cè)試方法靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試。主要包括白盒測(cè)試方法和黑盒測(cè)試方法。3.4.3白盒測(cè)試結(jié)構(gòu)測(cè)試將軟件看成透明的白盒，根據(jù)程序的內(nèi)部結(jié)構(gòu)和邏輯結(jié)構(gòu)來(lái)設(shè)計(jì)測(cè)試?yán)樱瑢?duì)程序的路徑和過(guò)程進(jìn)行測(cè)試，檢查是否滿(mǎn)足設(shè)計(jì)的要求主要方法：邏輯覆蓋、基本路徑測(cè)試3.4.4黑盒測(cè)試功能測(cè)試將軟件看成黑盒子，在完全不考慮軟件內(nèi)部結(jié)構(gòu)和特性的情況下，測(cè)試軟件的外部特性主要方法：等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法3.5程序調(diào)試1．任務(wù)根據(jù)測(cè)試時(shí)發(fā)現(xiàn)的錯(cuò)誤，（１）找出原因和具體的位置．（２）進(jìn)行改正，排除錯(cuò)誤由程序開(kāi)發(fā)人員來(lái)進(jìn)行，誰(shuí)開(kāi)發(fā)的程序就由誰(shuí)來(lái)進(jìn)行調(diào)試2.程序調(diào)試的基本步驟：（1）錯(cuò)誤定位；（2）修改設(shè)計(jì)和代碼，以排除錯(cuò)誤；（3）進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。3.調(diào)試方法：（靜態(tài)、動(dòng)態(tài)調(diào)試法）強(qiáng)行排錯(cuò)法回溯法原因排除法（演繹、歸納、二分法)為了提高測(cè)試的效率，應(yīng)該

A)隨機(jī)選取測(cè)試數(shù)據(jù)B)取一切可能的輸入數(shù)據(jù)作為測(cè)試數(shù)據(jù)

C)在完成編碼以后制定軟件的測(cè)試計(jì)劃D)集中對(duì)付那些錯(cuò)誤群集的程序軟件生命周期中所花費(fèi)用最多的階段是

A)詳細(xì)設(shè)計(jì) B)軟件編碼C)軟件測(cè)試D)軟件維護(hù)下列敘述中，不屬于軟件需求規(guī)格說(shuō)明書(shū)的作用的是

A)便于用戶(hù)、開(kāi)發(fā)人員進(jìn)行理解和交流

B)反映出用戶(hù)問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù)

C)作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)

D)便于開(kāi)發(fā)人員進(jìn)行需求分析下列不屬于軟件工程的3個(gè)要素的是Ａ)工具 Ｂ)過(guò)程Ｃ)方法 Ｄ)環(huán)境例題講解

軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)、接口和過(guò)程設(shè)計(jì)，其中軟件的過(guò)程設(shè)計(jì)是指

A)模塊間的關(guān)系 B)系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述

C)軟件層次結(jié)構(gòu) D)軟件開(kāi)發(fā)過(guò)程檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱(chēng)為Ａ)確認(rèn)測(cè)試Ｂ)集成測(cè)試Ｃ)驗(yàn)證測(cè)試Ｄ)驗(yàn)收測(cè)試數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成。下列圖符名標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是Ａ)控制流 Ｂ)加工Ｃ)數(shù)據(jù)存儲(chǔ) Ｄ)源和流開(kāi)發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱(chēng)作

A)軟件投機(jī) B)軟件危機(jī)C)軟件工程D)軟件產(chǎn)生下面不屬于軟件設(shè)計(jì)原則的是Ａ)抽象 Ｂ)模塊化Ｃ)自底向上Ｄ)信息隱蔽開(kāi)發(fā)大型軟件時(shí)，產(chǎn)生困難的根本原因是

A)大系統(tǒng)的復(fù)雜性 B)人員知識(shí)不足

C)客觀世界千變?nèi)f化 D)時(shí)間緊、任務(wù)重軟件工程的出現(xiàn)是由于

A)程序設(shè)計(jì)方法學(xué)的影響 B)軟件產(chǎn)業(yè)化的需要

C)軟件危機(jī)的出現(xiàn) D)計(jì)算機(jī)的發(fā)展軟件開(kāi)發(fā)離不開(kāi)系統(tǒng)環(huán)境資源的支持，其中必要的測(cè)試數(shù)據(jù)屬于

A)硬件資源B)通信資源C)支持軟件D)輔助資源在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列不屬于結(jié)構(gòu)化分析的常用工具的是

A)數(shù)據(jù)流圖 B)數(shù)據(jù)字典C)判定樹(shù)D)PAD圖在軟件生產(chǎn)過(guò)程中，需求信息的給出者是

A)程序員B)項(xiàng)目管理者

C)軟件分析設(shè)計(jì)人員 D)軟件用戶(hù)下列工具不是過(guò)程設(shè)計(jì)常用工具的是Ａ)PAD Ｂ)PFDＣ)N-S Ｄ)DFD模塊獨(dú)立性是軟件模塊化所提出的要求，衡量模塊獨(dú)立性的度量標(biāo)準(zhǔn)則是模塊的

A)抽象和信息隱蔽 B)局部化和封裝化

C)內(nèi)聚性和耦合性 D)激活機(jī)制和控制方法軟件開(kāi)發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成

A)定義、開(kāi)發(fā)、運(yùn)行維護(hù)B)設(shè)計(jì)階段、編程階段、測(cè)試階段

C)總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編程調(diào)試D)需求分析、功能定義、系統(tǒng)設(shè)計(jì)在軟件工程中，白箱測(cè)試法可用于測(cè)試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是

A)路徑的集合B)循環(huán)的集合C)目標(biāo)的集合D)地址的集合完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導(dǎo)出測(cè)試用例的測(cè)試方法是

A)黑箱測(cè)試法B)白箱測(cè)試法C)錯(cuò)誤推測(cè)法D)安裝測(cè)試法在結(jié)構(gòu)化設(shè)計(jì)方法中，生成的結(jié)構(gòu)圖(SC)中，帶有箭頭的連線表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列選項(xiàng)中，不屬于模塊間耦合的是

A)數(shù)據(jù)耦合B)同構(gòu)耦合C)異構(gòu)耦合D)公用耦合下列敘述中，不屬于測(cè)試的特征的是

A)測(cè)試的挑剔性 B)完全測(cè)試的不可能性

C)測(cè)試的可靠性 D)測(cè)試的經(jīng)濟(jì)性需求分析中開(kāi)發(fā)人員要從用戶(hù)那里了解

A)軟件做什么 B)用戶(hù)使用界面

C)輸入的信息 D)軟件的規(guī)模下列不屬于軟件調(diào)試技術(shù)的是

A)強(qiáng)行排錯(cuò)法 B)集成測(cè)試法

C)回溯法 D)原因排除法為了避免流程圖在描述程序邏輯時(shí)的靈活性，提出了用方框圖來(lái)代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱(chēng)為

A)PAD圖 B)N-S圖C)結(jié)構(gòu)圖 D)數(shù)據(jù)流圖軟件復(fù)雜性度量的參數(shù)包括

A)效率 B)規(guī)模C)完整性 D)容錯(cuò)性下列敘述中，正確的是

A)軟件就是程序清單B)軟件就是存放在計(jì)算機(jī)中的文件

C)軟件應(yīng)包括程序清單及運(yùn)行結(jié)果D)軟件包括程序和文檔軟件設(shè)計(jì)中，有利于提高模塊獨(dú)立性的一個(gè)準(zhǔn)則是

A)低內(nèi)聚低耦合 B)低內(nèi)聚高耦合

C)高內(nèi)聚低耦合 D)高內(nèi)聚高耦合軟件生命周期中花費(fèi)時(shí)間最多的階段是

A)詳細(xì)設(shè)計(jì) B)軟件編碼C)軟件測(cè)試D)軟件維護(hù)下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法

D)面向?qū)ο蟮姆治龇椒ㄔ敿?xì)設(shè)計(jì)的結(jié)果基本決定了最終程序的

A)代碼的規(guī)模 B)運(yùn)行速度

C)質(zhì)量 D)可維護(hù)性下列不屬于靜態(tài)測(cè)試方法的是

A)代碼檢查 B)白盒法

C)靜態(tài)結(jié)構(gòu)分析 D)代碼質(zhì)量度量在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須局別哪些功能的階段是A）概要設(shè)計(jì)B）詳細(xì)設(shè)計(jì)C）可行性分析D）需求分析檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱(chēng)為A）確認(rèn)測(cè)試B）集成測(cè)試C）驗(yàn)證測(cè)試D）驗(yàn)收測(cè)試數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成，下列圖符名標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是A）控制流B）加工C）數(shù)據(jù)存儲(chǔ)D）源和潭下面不屬于軟件設(shè)計(jì)原則的是A）抽象B）模塊化C）自底向上D）信息屏蔽程序流程圖（PFD）中的箭頭代表的是A）數(shù)據(jù)流B）控制流C）調(diào)用關(guān)系D）組成關(guān)系下列工具中為需求分析常用工具的是A）PADB）PFDC）N-SD）DFD在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開(kāi)發(fā)中的階段是A）詳細(xì)設(shè)計(jì)B）需求分析C）總體設(shè)計(jì)D）編程調(diào)試軟件調(diào)試的目的是A）發(fā)現(xiàn)錯(cuò)誤B）改正錯(cuò)誤C）改善軟件的性能D）挖掘軟件的潛能軟件需求分析階段的工作，可以分為四個(gè)方面：需求獲取，需求分析，編寫(xiě)需求規(guī)格說(shuō)明書(shū)，以及A）階段性報(bào)告B）需求評(píng)審C）總結(jié)D）都不正確軟件是程序、數(shù)據(jù)和____的集合。Jackson方法是一種面向____的結(jié)構(gòu)化方法。軟件工程研究的內(nèi)容主要包括：____技術(shù)和軟件工程管理。文檔數(shù)據(jù)結(jié)構(gòu)軟件開(kāi)發(fā)

通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱(chēng)為

【4】。耦合和內(nèi)聚是評(píng)價(jià)模塊獨(dú)立性的兩個(gè)主要標(biāo)準(zhǔn)，其中

【3】

反映了模塊內(nèi)各成分之間的聯(lián)系。軟件工程研究的內(nèi)容主要包括：

【4】技術(shù)和軟件工程管理。軟件設(shè)計(jì)模塊化的目的是

【4】。軟件生命周期耦合軟件開(kāi)發(fā)降低復(fù)雜性4.數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.1基本概念1.數(shù)據(jù)(Data)實(shí)際上就是描述事物的符號(hào)記錄軟件中的數(shù)據(jù)是有一定結(jié)構(gòu)的2.數(shù)據(jù)庫(kù)(DB)長(zhǎng)期存儲(chǔ)在計(jì)算機(jī)內(nèi)的，有組織的，可共享的數(shù)據(jù)集合。數(shù)據(jù)庫(kù)中的數(shù)據(jù)按一定的數(shù)學(xué)模型組織、描述和存儲(chǔ)，具有較小的冗余度，較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性，并可為各種用戶(hù)共享。3.數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)系統(tǒng)的核心軟件要在操作系統(tǒng)支持下工作解決如何科學(xué)地組織和存儲(chǔ)數(shù)據(jù)，如何高效的獲取和維護(hù)數(shù)據(jù)的系統(tǒng)軟件主要功能包括數(shù)據(jù)模式定義數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS一般提供相應(yīng)的數(shù)據(jù)語(yǔ)言：數(shù)據(jù)定義語(yǔ)言（DDL）數(shù)據(jù)操縱語(yǔ)言（DML）數(shù)據(jù)控制語(yǔ)言（DCL）數(shù)據(jù)語(yǔ)言按其使用方式具有兩種結(jié)構(gòu)形式交互式命令語(yǔ)言宿主型語(yǔ)言4.數(shù)據(jù)庫(kù)管理員主要工作包括：數(shù)據(jù)庫(kù)設(shè)計(jì)數(shù)據(jù)庫(kù)維護(hù)改善系統(tǒng)性能，提高系統(tǒng)效率5.數(shù)據(jù)庫(kù)系統(tǒng)（DBS）由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、系統(tǒng)平臺(tái)之硬件平臺(tái)（硬件）和軟件平臺(tái)（軟件）構(gòu)成。6.數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）利用數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行應(yīng)用開(kāi)發(fā)7.數(shù)據(jù)庫(kù)管理技術(shù)的發(fā)展人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)階段（層次、網(wǎng)狀、關(guān)系）8.數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)數(shù)據(jù)的集成性采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)方式按照多個(gè)應(yīng)用的需要組主全局的統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)模式是多個(gè)應(yīng)用共同的、全局的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)獨(dú)立性物理獨(dú)立性和邏輯獨(dú)立性數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)的完整性檢查數(shù)據(jù)的安全性檢查并發(fā)控制9.數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式（1）概念模式（2）外模式（3）內(nèi)模式內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲(chǔ)形式概念模式處于中層，它放映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求外模式處于最外層，它反映了用戶(hù)對(duì)數(shù)據(jù)的要求一、外模式/模式映象數(shù)據(jù)的邏輯獨(dú)立性：當(dāng)模式改變時(shí)，由外模式/模式映象作相應(yīng)的改變，可以保持外模式不變。應(yīng)用程序是依據(jù)數(shù)據(jù)的外模式編寫(xiě)的，從而應(yīng)用程序不必修改，保證了數(shù)據(jù)與程序的邏輯獨(dú)立性。數(shù)據(jù)的物理獨(dú)立性：當(dāng)內(nèi)模式改變時(shí)，由模式/內(nèi)模式映象作相應(yīng)的改變，可以保持模式不變。從而應(yīng)用程序也不必改變，保證了數(shù)據(jù)與程序的物理獨(dú)立性。二、模式/內(nèi)模式映象4.2數(shù)據(jù)模型數(shù)據(jù)模型：是現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象。在數(shù)據(jù)庫(kù)中用數(shù)據(jù)模型這個(gè)工具來(lái)抽象、表示和處理現(xiàn)實(shí)世界中的數(shù)據(jù)和信息。通俗地講數(shù)據(jù)模型就是現(xiàn)實(shí)世界的模擬。數(shù)據(jù)模型應(yīng)滿(mǎn)足三方面的要求：（1）能比較真實(shí)地模擬現(xiàn)實(shí)世界。（2）容易為人理解。（3）便于在計(jì)算機(jī)上實(shí)現(xiàn)。4.2.1數(shù)據(jù)模型的基本概念數(shù)據(jù)模型是數(shù)據(jù)特性的抽象數(shù)據(jù)模型描述的內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類(lèi)型概念數(shù)據(jù)模型（概念模型）邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）物理數(shù)據(jù)模型（物理模型）E-R圖、擴(kuò)充的E-R圖。。。。層次模型網(wǎng)狀模型關(guān)系模型面向?qū)ο?.2.2E-R模型（實(shí)體聯(lián)系模型）基本概念（1）實(shí)體（2）屬性（3）聯(lián)系一對(duì)一（1：1）一對(duì)多（1：M或M：1）多對(duì)多（M：N）班級(jí)擁有班長(zhǎng)11班級(jí)擁有學(xué)生1n課程選修學(xué)生mn運(yùn)算符集合運(yùn)算:專(zhuān)門(mén)的關(guān)系運(yùn)算:比較運(yùn)算:>>=<=<=<>邏輯運(yùn)算:4.3關(guān)系代數(shù)設(shè)關(guān)系R和關(guān)系S具有相同的目n,且相應(yīng)的屬性取自同一個(gè)域,則可有如下定義:1.并2.差3.交傳統(tǒng)的集合運(yùn)算例子:ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c1ABCRSa1a1a2a1b1b2b2b3c1c2c1c2ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c1ABCRSa1a2b2b2c2c1ABCR-Sa1b1c1RSa1a1a1a1a1a1a2a2a2ABCABCb1b1b1b2b2b2b2b2b2c1c1c1c2c2c2c1c1c1a1a1a2a1a1a2a1a1a2b2b3b2b2b3b2b2b3b2c2c2c1c2c2c1c2c2c1ABCRa1a1a2b1b2b2c1c2c1ABCSa1a1a2b2b3b2c2c2c14.笛卡兒×專(zhuān)門(mén)的關(guān)系運(yùn)算：1.選擇例子1:查詢(xún)信息系(IS系)的全體學(xué)生.

SnoSnameSsexSageSdept劉晨張立9500295004ISIS女男1919

SnoSnameSsexSageSdept李勇劉晨王敏張立95001950029500395004CSISMAIS男女女男201918192.投影例子4:查詢(xún)學(xué)生的姓名和所在系.

SnoSnameSsexSageSdept李勇劉晨王敏張立95001950029500395004CSISMAIS男女女男20191819SnameSdept李勇劉晨王敏張立CSISMAIS3.連接例子:ABCRa1a1a2a2b1b2b3b456812BESb1b2b3a2a1371022…說(shuō)明:（1）A和B分別是R和S上度相等且可比的屬性組。（2）是比較運(yùn)算符。等值連接:當(dāng)連接條件為“=”時(shí)的連接運(yùn)算.AR.BCS.BEABCRa1a1a2a2b1b2b3b456812BESb1b2b3b3b5371022a2b38b310a2b38b32AR.BCEa1a1a2a2b1b2b3b3568837102自然連接:是一種特殊的等值連接,它要求兩個(gè)關(guān)系中進(jìn)行比較的分量是相同的屬性組,并且在結(jié)果中把重復(fù)的屬性列去掉.ABCRa1a1a2a2b1b2b3b456812BESb1b2b3b3b53710224.4數(shù)據(jù)庫(kù)設(shè)計(jì)與管理4.4.1數(shù)據(jù)庫(kù)設(shè)計(jì)概述設(shè)計(jì)一個(gè)能滿(mǎn)足用戶(hù)要求，性能良好的數(shù)據(jù)庫(kù)基本任務(wù)：根據(jù)用戶(hù)對(duì)象的信息需求、處理需求和數(shù)據(jù)庫(kù)的支持環(huán)境設(shè)計(jì)出數(shù)據(jù)模式兩種方法：以信息需求為主，兼顧處理需求（面向數(shù)據(jù)的方法）以處理需求為主，兼顧信息需求（面向過(guò)程的方法）面向數(shù)據(jù)的設(shè)計(jì)方法已成為主流方法數(shù)據(jù)庫(kù)設(shè)計(jì)目前一般采用生命周期法，分若干階段需求分析階段概念設(shè)計(jì)階段邏輯設(shè)計(jì)階段物理設(shè)計(jì)階段編碼階段測(cè)試階段運(yùn)行階段進(jìn)一步修改階段在數(shù)據(jù)庫(kù)設(shè)計(jì)中采用前四個(gè)階段，并且重點(diǎn)以數(shù)據(jù)結(jié)構(gòu)與模型的設(shè)計(jì)為主線E-R圖關(guān)系模型4.4.3數(shù)據(jù)庫(kù)概念設(shè)計(jì)概述目的：分析數(shù)據(jù)間內(nèi)在語(yǔ)義關(guān)聯(lián)，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)的抽象模型設(shè)計(jì)方法：集中式模式設(shè)計(jì)法和視圖集成設(shè)計(jì)法設(shè)計(jì)的過(guò)程選擇局部應(yīng)用視圖設(shè)計(jì)：3種設(shè)計(jì)次序（自頂向下、由底向上、由內(nèi)向外）視圖集成數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS中用來(lái)定義模式、內(nèi)模式和外模式的語(yǔ)言為

A)C B)BasicC)DDL D)DML下列有關(guān)數(shù)據(jù)庫(kù)的描述，正確的是

A)數(shù)據(jù)庫(kù)是一個(gè)DBF文件 B)數(shù)據(jù)庫(kù)是一個(gè)關(guān)系

C)數(shù)據(jù)庫(kù)是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合 D)數(shù)據(jù)庫(kù)是一組文件下列有關(guān)數(shù)據(jù)庫(kù)的描述，正確的是

A)數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過(guò)程

B)數(shù)據(jù)的物理獨(dú)立性是指當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不變

C)關(guān)系中的每一列稱(chēng)為元組，一個(gè)元組就是一個(gè)字段

D)如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)關(guān)系的關(guān)鍵字，則稱(chēng)其為本關(guān)系的外關(guān)鍵字例題講解應(yīng)用數(shù)據(jù)庫(kù)的主要目的是

A)解決數(shù)據(jù)保密問(wèn)題 B)解決數(shù)據(jù)完整性問(wèn)題

C)解決數(shù)據(jù)共享問(wèn)題 D)解決數(shù)據(jù)量大的問(wèn)題在數(shù)據(jù)庫(kù)設(shè)計(jì)中，將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過(guò)程屬于

A)需求分析階段 B)邏輯設(shè)計(jì)階段

C)概念設(shè)計(jì)階段 D)物理設(shè)計(jì)階段在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是Ａ)數(shù)據(jù)庫(kù)系統(tǒng) Ｂ)文件系統(tǒng)Ｃ)人工管理 Ｄ)數(shù)據(jù)項(xiàng)管理下述關(guān)于數(shù)據(jù)庫(kù)系統(tǒng)的敘述中正確的是Ａ)數(shù)據(jù)庫(kù)系統(tǒng)減少了數(shù)據(jù)冗余Ｂ)數(shù)據(jù)庫(kù)系統(tǒng)避免了一切冗余Ｃ)數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類(lèi)型一致Ｄ)數(shù)據(jù)庫(kù)系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)索引屬于

A)模式 B)內(nèi)模式C)外模式 D)概念模式數(shù)據(jù)庫(kù)系統(tǒng)的核心是

A)數(shù)據(jù)庫(kù) B)數(shù)據(jù)庫(kù)管理系統(tǒng)

C)模擬模型 D)軟件工程分布式數(shù)據(jù)庫(kù)系統(tǒng)不具有的特點(diǎn)是

A)數(shù)據(jù)分布性和邏輯整體性B)位置透明性和復(fù)制透明性

C)分布性 D)數(shù)據(jù)冗余關(guān)系表中的每一橫行稱(chēng)為一個(gè)Ａ)元組 Ｂ)字段Ｃ)屬性 Ｄ)碼下列數(shù)據(jù)模型中，具有堅(jiān)實(shí)理論基礎(chǔ)的是

A)層次模型 B)網(wǎng)狀模型

C)關(guān)系模型 D)以上3個(gè)都是下列SQL語(yǔ)句中，用于修改表結(jié)構(gòu)的是

A)ALTER B)CREATEC)UPDATED)INSERT數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)系統(tǒng)和數(shù)據(jù)庫(kù)管理系統(tǒng)之間的關(guān)系是

A)數(shù)據(jù)庫(kù)包括數(shù)據(jù)庫(kù)系統(tǒng)和數(shù)據(jù)庫(kù)管理系統(tǒng)

B)數(shù)據(jù)庫(kù)系統(tǒng)包括數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理系統(tǒng)

C)數(shù)據(jù)庫(kù)管理系統(tǒng)包括數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)系統(tǒng)

D)3者沒(méi)有明顯的包含關(guān)系關(guān)系模型允許定義3類(lèi)數(shù)據(jù)約束，下列不屬于數(shù)據(jù)約束的是

A)實(shí)體完整性