國(guó)二公共基礎(chǔ)知識(shí)

公共基礎(chǔ)知識(shí)算法與數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)基礎(chǔ)軟件工程數(shù)據(jù)庫(kù)基礎(chǔ)1．算法的概念、算法時(shí)間復(fù)雜度及空間復(fù)雜度的概念2．?dāng)?shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輯結(jié)構(gòu)及物理結(jié)構(gòu)的定義3．棧的定義及其運(yùn)算、線性鏈表的存儲(chǔ)方式4．樹(shù)與二叉樹(shù)的概念、二叉樹(shù)的基本性質(zhì)、完全二叉樹(shù)的概念、二叉樹(shù)的遍歷5．查找6．排序第一章算法與數(shù)據(jù)結(jié)構(gòu)一、算法的基本概念

1、算法：解題方案的準(zhǔn)確而完整的描述，包括解決問(wèn)題的方法和步驟

。

算法≠程序≠計(jì)算方法

2、算法的基本特征：⑴可行性：算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次數(shù)來(lái)實(shí)現(xiàn)

⑵確定性：算法的每個(gè)步驟必須明確定義，不允許有多義性。⑶有窮性：指算法必須能在有限的時(shí)間內(nèi)做完(即算法的運(yùn)行時(shí)間有限)。⑷擁有足夠的情報(bào)：指運(yùn)算對(duì)象的初始輸入要完備且正確1.1算法二、算法復(fù)雜度1、時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量2、空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間（存儲(chǔ)空間）。注意：1）時(shí)間復(fù)雜度通過(guò)算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量

2）空間復(fù)雜度的內(nèi)存空間主要用于：內(nèi)存空間算法程序初始數(shù)據(jù)運(yùn)行過(guò)程中所需的額外空間執(zhí)行過(guò)程的工作單元附加空間3）時(shí)間復(fù)雜度和空間復(fù)雜度不相關(guān)4）算法的效率與問(wèn)題的規(guī)模和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)都是息息相關(guān)的。算法習(xí)題(1)算法是指（）A.查詢方法B.交工方法C.解題方案的準(zhǔn)確而完整的描述D.排序方法(2)算法的有窮性是指：A.算法程序的運(yùn)行時(shí)間是有限的B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長(zhǎng)度是有限的D.算法程序只能被有限的用戶使用(3)算法的時(shí)間復(fù)雜度是指（）A.算法的執(zhí)行時(shí)間

B.算法所處理的數(shù)據(jù)量C.算法程序中的語(yǔ)句或指令數(shù)

D.算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)(4)下列敘述中正確的是（）A.一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B.一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定小C.一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度也必定大D.上述三種說(shuō)法都不對(duì)1.2數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)：是抽象地研究數(shù)據(jù)的組織形式及其相互關(guān)系的一門學(xué)科。

數(shù)據(jù)的結(jié)構(gòu)分為：

（1）物理結(jié)構(gòu)：也被稱為“存儲(chǔ)結(jié)構(gòu)”，是指數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)介質(zhì)中真正存儲(chǔ)的結(jié)構(gòu)。

（2）邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)2、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（即存儲(chǔ)結(jié)構(gòu)）和算法。注意：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)沒(méi)有必然的聯(lián)系，也不一定是一一對(duì)應(yīng)的。二、數(shù)據(jù)的邏輯結(jié)構(gòu)：

反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。1、線性結(jié)構(gòu)：⑴有且僅有一個(gè)根結(jié)點(diǎn)⑵每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，也最多只有一個(gè)后件。例如：主要有線性表、棧、隊(duì)列、串等。

前后件關(guān)系2、非線性結(jié)構(gòu)：該結(jié)構(gòu)中一個(gè)結(jié)點(diǎn)可能有多個(gè)前件或后件。主要有樹(shù)和圖等。FCEGDABPH三、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式（邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示）1、順序存儲(chǔ)：邏輯上相鄰的數(shù)據(jù)元素，在物理存儲(chǔ)位置上也相鄰。2、鏈?zhǔn)酱鎯?chǔ)：邏輯上相鄰的元素其物理位置不一定相鄰，元素間的邏輯關(guān)系由附加的指針字段表示。注意：1）一種邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu)

2）存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率例題：下列敘述中正確的是：A、程序執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B、程序執(zhí)行效率只取決于程序的控制結(jié)構(gòu)C、程序執(zhí)行效率只取決于所處理的數(shù)據(jù)量D、以上三種說(shuō)法都不對(duì)1.3、線性表1、線性表的定義線性表是n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，……，an

的有序集合。線性表是一種線性結(jié)構(gòu)，每個(gè)元素在表中的位置僅取決于元素本身的序號(hào)。n為線性表的長(zhǎng)度，n為0的表稱為空表。學(xué)號(hào)姓名語(yǔ)文數(shù)學(xué)計(jì)算機(jī)980001張三708069980002吳軍897698980003王平878776980004李帆768689無(wú)后件無(wú)前件a1a2a3…aiai+1…an…特點(diǎn)：⑴線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的⑵線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按照邏輯順序依次存放的⑶可以隨機(jī)訪問(wèn)

缺點(diǎn)：插入和刪除運(yùn)算不方便；由于要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行2、線性表的存儲(chǔ)結(jié)構(gòu)（1）線性表的順序存儲(chǔ)結(jié)構(gòu)：當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，稱之為順序表。即用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素。在程序設(shè)計(jì)語(yǔ)言中，通常定義一個(gè)一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間。⑴順序表的插入：要在第i(1≤i≤n)個(gè)元素之前插入一個(gè)新元素時(shí)，需要移動(dòng)n-i+1個(gè)元素⑵順序表的刪除：要?jiǎng)h除第i(1≤i≤n)個(gè)元素時(shí)，需要移動(dòng)n-i個(gè)元素真題：下列有關(guān)順序存儲(chǔ)結(jié)構(gòu)的敘述中，不正確的是：

A、存儲(chǔ)密度大

B、邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

C、可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

D、插入、刪除操作不方便

用一組任意的存儲(chǔ)單元（可以是連續(xù)的，也可以不連續(xù)）來(lái)存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素（稱為結(jié)點(diǎn)）的存儲(chǔ)結(jié)構(gòu)由兩部分組成：一部分用于存儲(chǔ)數(shù)據(jù)元素本身的信息（稱為數(shù)據(jù)域），另一部分用于存儲(chǔ)直接后繼的存儲(chǔ)位置（稱為指針域）,如下圖所示：3、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：①元素的存儲(chǔ)空間可以連續(xù)，也可以不連續(xù)②元素的邏輯關(guān)系通過(guò)鏈結(jié)點(diǎn)的指針?lè)从?。③順序訪問(wèn)

ABC…

…NULLhead注：分單向、雙向和循環(huán)鏈表ABC…

…h(huán)eadABC…

…NULLhead循環(huán)鏈表：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。雙向鏈表特點(diǎn)：在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向前件，另一指向后件。真題：1、下列敘述中正確的是：

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需存儲(chǔ)空間相同

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需存儲(chǔ)空間一般多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需存儲(chǔ)空間一般少于順序存儲(chǔ)結(jié)構(gòu)

D、以上三種說(shuō)法都不對(duì)2、下列敘述中正確的是：A、有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B、只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C、循環(huán)鏈表是非線性結(jié)構(gòu)D、雙向鏈表是非線性結(jié)構(gòu)3、在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素的位置插入一個(gè)新元素，需要向后移動(dòng)

個(gè)元素。4、在長(zhǎng)度為n的順序表中插入一個(gè)元素，最壞情況下要移動(dòng)表中

個(gè)元素。5、下列敘述中正確的是A)結(jié)點(diǎn)中有多個(gè)指針域的所有鏈表一定是非線性結(jié)構(gòu)B)帶鏈的棧與隊(duì)列是線性結(jié)構(gòu)C)能順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D)存儲(chǔ)空間不連續(xù)的所有鏈表一定是非線性結(jié)構(gòu)1.4棧與隊(duì)列1、棧的定義棧是一種特殊的線性表，是限定在一端進(jìn)行插入和刪除運(yùn)算的線性表。允許插入與刪除的一端稱為棧頂（top)，另一端稱為棧底(bottom）。

2、特點(diǎn)最先進(jìn)入棧的元素一定在棧底，最后進(jìn)入棧的元素一定在棧頂。所以堆棧又稱為“后進(jìn)先出”表或“先進(jìn)后出”表提示：程序設(shè)計(jì)語(yǔ)言中的遞歸調(diào)用采用的“棧”這種數(shù)據(jù)結(jié)構(gòu)同樣有順序和鏈?zhǔn)絻煞N。（1）、入棧PUSH（S，X）

棧頂指針TOP加1，插入新元素X；若堆棧已滿，再做入棧運(yùn)算時(shí)會(huì)產(chǎn)生溢出（通常稱為上溢）。（2）、出棧POP（S）取出棧頂元素賦給變量、棧頂指針TOP減1；若堆棧為空，再做出棧運(yùn)算時(shí)會(huì)產(chǎn)生溢出（通常稱為下溢）。

（3）、讀棧頂元素GETTOP（S）將棧頂元素賦給變量但不改變TOP指針。3、存儲(chǔ)結(jié)構(gòu)及運(yùn)算真題：1、下列關(guān)于棧敘述正確的是A)棧頂元素最先能被刪除 B)棧頂元素最后才能被刪除C)棧底元素永遠(yuǎn)不能被刪除 D)以上三種說(shuō)法都不對(duì)2、下列敘述中正確的是A)在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化B)在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化C)在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化D)上述三種說(shuō)法都不對(duì)3、假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組(數(shù)組元素的下標(biāo)從0～49)作為棧的存儲(chǔ)空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom＝49，top＝30(數(shù)組下標(biāo))，則棧中具有__

__個(gè)元素。4、若進(jìn)棧序列為1，2，3，4，且進(jìn)棧過(guò)程中可以出棧，則不可能的出棧序列是（A）1，4，3，2（B）2，3，4，1

（C）3，1，4，2（D）3，4，2，15、在程序設(shè)計(jì)語(yǔ)言中的遞歸調(diào)用的存儲(chǔ)分配通常用（）A)棧B)堆C)數(shù)組D)鏈表隊(duì)列1、定義是一種只允許在表的一端進(jìn)行插入操作而在另一端進(jìn)行刪除操作的線性表。2、特點(diǎn)允許插入的一端稱為隊(duì)尾（rear),允許刪除的一端稱為隊(duì)頭(front)。新來(lái)的元素總是加入到隊(duì)尾，每次離隊(duì)的總是對(duì)頭的元素。因此，也將隊(duì)列稱為“先進(jìn)先出”FIFO（FirstInFirstOut）3、存儲(chǔ)結(jié)構(gòu)同樣有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4、基本運(yùn)算①入隊(duì):插入運(yùn)算稱為入隊(duì)，rear=rear+1,rear指示了實(shí)際的隊(duì)尾位置②出隊(duì):刪除運(yùn)算稱為出隊(duì),front=front+1，front指示的是對(duì)頭的前一個(gè)位置假溢出(a)圖是空隊(duì)列，表示該隊(duì)列最大長(zhǎng)度maxnum=6(d）圖中rear=maxnum，如果這時(shí)有J7要入隊(duì)，則會(huì)產(chǎn)生假溢出5、循環(huán)隊(duì)列(順序存儲(chǔ))注意：rear=front則表示可能隊(duì)滿，也可能隊(duì)空循環(huán)隊(duì)列的基本運(yùn)算①入隊(duì)：插入運(yùn)算稱為，rear=rear+1；當(dāng)rear=m+1時(shí)(m為隊(duì)列的總?cè)萘?，則重置rear=1。②出隊(duì)：刪除運(yùn)算稱為出隊(duì)，front=front+1；當(dāng)front=m+1時(shí)(m為隊(duì)列的總?cè)萘?，則重置front=1。1、一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4，則隊(duì)列的輸出序列是

A)4321B)1234

C)1432D)3

2

4

1

2、在一個(gè)容量為24的循環(huán)隊(duì)列中，若頭指針front=8，尾指針rear=3，則該循環(huán)隊(duì)列中共有__________個(gè)元素3、對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是A)隊(duì)頭指針是固定不變的B)隊(duì)頭指針一定大于隊(duì)尾指針C)隊(duì)頭指針一定小于隊(duì)尾指針D)隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針4、在一個(gè)容量為24的循環(huán)隊(duì)列中，經(jīng)過(guò)一系列入隊(duì)和出隊(duì)運(yùn)算，若頭指針front=8，尾指針rear=8，則該循環(huán)隊(duì)列中共有__________個(gè)元素重要考點(diǎn)：已知循環(huán)隊(duì)列容量m，隊(duì)頭指針front和隊(duì)尾指針rear，求隊(duì)列元素個(gè)數(shù)n①當(dāng)front<rear時(shí)：n=rear-front②當(dāng)front>rear時(shí)：n=m+(rear-front)1、樹(shù)的基本概念⑴定義

樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)（數(shù)據(jù)元素）的有窮集合，是一種非線性結(jié)構(gòu)。N=0時(shí)稱為空樹(shù)。⑵特點(diǎn)①有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，即樹(shù)的根結(jié)點(diǎn)。②除根結(jié)點(diǎn)以外，其余所有結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)。③包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼結(jié)點(diǎn)⑶基本概念①結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱為該結(jié)點(diǎn)的度②樹(shù)的度：結(jié)點(diǎn)中最大的度即為樹(shù)的度。③樹(shù)的深度：樹(shù)的最大層次。④葉子結(jié)點(diǎn)：沒(méi)有子數(shù)，該結(jié)點(diǎn)的度為0.FCEGDABPH1.5樹(shù)與二叉樹(shù)2、二叉樹(shù)⑴特點(diǎn)只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有左、右兩棵子樹(shù)組成。若集合為空，則為空二叉樹(shù)。二叉樹(shù)的結(jié)點(diǎn)有三種：度為0的葉子結(jié)點(diǎn)、度為1的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)⑵基本性質(zhì)①二叉樹(shù)的第K層上最多有2k-1個(gè)結(jié)點(diǎn)。②深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。③任意二叉樹(shù)中，度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多1個(gè)。或者表述為：二叉樹(shù)中度為2的結(jié)點(diǎn)有n個(gè)，則該二叉樹(shù)中有n+1個(gè)葉子結(jié)點(diǎn)。④具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，深度至少為[log2n]+1ABCFEDJn0=n2+1二叉樹(shù)中結(jié)點(diǎn)總數(shù)：n0+n1+n23、滿二叉樹(shù)與完全二叉樹(shù)⑴滿二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，即每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。⑵完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

(a)深度為3的滿二叉樹(shù)(b)深度為3的完全二叉樹(shù)的幾種形態(tài)說(shuō)明：滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)未必是滿二叉樹(shù)。前（根）序遍歷：訪問(wèn)根結(jié)點(diǎn)——左子樹(shù)——右子樹(shù)

ABDEHJCFG中（根）序遍歷：左子樹(shù)——訪問(wèn)根結(jié)點(diǎn)——右子樹(shù)

DBHEJAFCG后（根）序遍歷：左子樹(shù)——右子樹(shù)——訪問(wèn)根結(jié)點(diǎn)

DHJEBFGCAABCFEGDHJ(3)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)(4)二叉樹(shù)的操作：遍歷真題：1、一棵二叉樹(shù)的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為

。2、

①

有下列二叉樹(shù)，對(duì)此二叉樹(shù)中序遍歷的結(jié)果為（）

A）BDYEACFXZB）DYBEAFCZXC）ABCDEFXYZD）ABDYECFXZ

②某二叉樹(shù)共有60個(gè)葉子結(jié)點(diǎn)與50個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為（）。

A）148B）169C）182D）198

③在深度為5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A)32B)31C)16D)15④某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹(shù)的深度為()(假設(shè)根結(jié)點(diǎn)在第1層)

A)3 B)4 C)6 D)7n0=60推出n2=n0-1=59共有:n0+n1+n2=60+50+59=16925-11.6查找1、順序查找（1）基本思想：從第一個(gè)數(shù)據(jù)元素開(kāi)始，逐個(gè)把數(shù)據(jù)元素的關(guān)鍵字值和給定值比較，若某個(gè)元素的關(guān)鍵字值和給定值相等，則查找成功；否則，若全部比較完都不等，則查找失敗。（2）在下列兩種情況下只能采用順序查找：①如果線性表為無(wú)序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序查找。②即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。2、二分查找前提：順序存儲(chǔ)的有序表。基本思想：待查元素與表的“中間位置”元素的關(guān)鍵值進(jìn)行比較，若大于關(guān)鍵字，則在查找表的后半部分繼續(xù)二分查找，否則在前半部分進(jìn)行二分查找。在最壞情況下，順序查找需要比較n次，二分查找需要比較log2n次。

排序冒泡排序快速排序簡(jiǎn)單插入排序希爾排序簡(jiǎn)單選擇排序堆排序最壞情況下比較次數(shù)O(nlog2n)次n(n-1)/2次O(n1.5)次1.7排序下列排序方法中，最壞情況下比較次數(shù)最少的是

A)

冒泡排序

B)

簡(jiǎn)單選擇排序

C)

直接插入排序

D)

堆排序1、交換類排序①冒泡排序基本思想：⑴首先，從前往后掃描線性表,逐次比較相鄰兩個(gè)元素的大小,若前者大于后者，則兩兩交換位置，最后將最大的元素放到了表的末尾；⑵然后，從后往前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，最后將最小者放到表的最前面。⑶再對(duì)剩余元素進(jìn)行第二趟比較…，直到n個(gè)元素按遞增順序排列好為止。其特點(diǎn)是：第一趟排序后，最小元素被交換到第一位，最大元素被交換到最后一位。②快速排序基本思想：從序列中選取一個(gè)元素，設(shè)為T，將序列中小于T的元素移到T前面，大于T的元素移到T后面，T插入到序列分界線的位置，這個(gè)過(guò)程叫分割。然后對(duì)分割的兩部分做再次分割，直至使序列變成有序的。2、插入類排序①簡(jiǎn)單插入排序基本思想：把n個(gè)數(shù)據(jù)元素的序列分成兩部分，{R1，…，Ri-1}為已排好序的有序部分，{Ri,Ri+1,….,Rn}為未排序部分，這時(shí)，把未排序部分的元素逐個(gè)插入到有序部分的合適位置上。②希爾排序基本思想：把整個(gè)無(wú)序序列按某個(gè)增量H分割成若干小的子序列分別進(jìn)行插入排序，在排序過(guò)程中逐次縮小這個(gè)增量，直至H為13、選擇類排序(1)簡(jiǎn)單選擇排序基本思想：第一趟排序是在無(wú)序的{R1，…，Rn}中按排序碼選出最小的元素，將它與R1交換；第二趟排序是在無(wú)序的{R2，…，Rn}中按排序碼選出最小的元素，將它與R2交換，…，最終得到遞增有序的序列。89215648851619471621564885891947第1遍第2遍1619564885892147第3遍1619214885895647其特點(diǎn)是：第一趟排序后，最小元素被交換到第一位。(2)堆排序第二章程序設(shè)計(jì)基礎(chǔ)1．結(jié)構(gòu)化程序設(shè)計(jì)方法的四個(gè)原則2．對(duì)象、類、消息、繼承的概念、類與實(shí)例的區(qū)別程序設(shè)計(jì)的方法與風(fēng)格

一、程序設(shè)計(jì)方法與風(fēng)格1、符號(hào)名的命名應(yīng)具有一定含義2、必要的程序注釋：分為序言性注釋和功能性注釋(可讀性)

3、程序編寫清晰第一、效率第二（易讀性）4、避免不必要的語(yǔ)句轉(zhuǎn)移5、程序設(shè)計(jì)要采用模塊化二、結(jié)構(gòu)化程序設(shè)計(jì)1、設(shè)計(jì)原則①自頂向下②逐步求精③模塊化④限制使用GOTO語(yǔ)句最關(guān)鍵的是“以提高程序清晰性為目標(biāo)”

2、程序基本結(jié)構(gòu)①順序結(jié)構(gòu)②選擇結(jié)構(gòu)③循環(huán)結(jié)構(gòu)三、面向?qū)ο蟮某绦蛟O(shè)計(jì)1、對(duì)象⑴定義：對(duì)象是由數(shù)據(jù)和允許的操作組成的封裝體，可以用來(lái)表示客觀世界中的任何實(shí)體。⑵屬性：對(duì)象所包含的信息（靜態(tài)）⑶方法：即對(duì)象的操作，描述了對(duì)象執(zhí)行的功能（動(dòng)態(tài)）⑷特征：⑴標(biāo)識(shí)唯一性：對(duì)象是可以區(qū)分的。⑵分類性：可以將具有相同屬性和操作的對(duì)象抽象成類。⑶多態(tài)性：同一個(gè)操作可以是不同對(duì)象的行為。⑷封裝性：實(shí)現(xiàn)信息屏蔽。⑸模塊獨(dú)立性：內(nèi)聚性強(qiáng)、耦合度弱。2、類類是具有共同屬性、共同方法的對(duì)象的集合、對(duì)象是類的實(shí)例?？梢杂苫悾ǜ割悾┊a(chǎn)生子類，子類可以繼承其父類的全部方法和屬性。3、消息對(duì)象間相互合作的機(jī)制稱為消息，對(duì)象間通過(guò)傳遞消息相互聯(lián)系4、繼承繼承是一種類之間共享屬性和操作的機(jī)制。子類可以繼承其父類的全部方法和屬性，繼承具有傳遞性5、多態(tài)性同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行為真題：1、下列不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的是()A）可封裝B）自頂向下C）模塊化D）逐步求精2、結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括（）A）順序結(jié)構(gòu)B）GOTO跳轉(zhuǎn)C）選擇結(jié)構(gòu)D）循環(huán)結(jié)構(gòu)3、面向?qū)ο蠓椒ㄖ?，繼承是指（）A）一組對(duì)象所具有的相似性質(zhì)B）一個(gè)對(duì)象具有另一個(gè)對(duì)象的性質(zhì)C）各對(duì)象之間的共同性質(zhì)D）類之間共享屬性和操作的機(jī)制4、在面向?qū)ο蠓椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠（）A）對(duì)象的繼承B）對(duì)象的多態(tài)C）對(duì)象的封裝D）對(duì)象的分類5、以下不屬于對(duì)象的基本特點(diǎn)的是（）A)分類性B)多態(tài)性C)一致性D)封裝性6、對(duì)象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對(duì)數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行（）A)結(jié)合B)隱藏C)封裝D)抽象7、在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā)送（）A)調(diào)用語(yǔ)句B)命令C)口令D）消息第三章軟件工程基礎(chǔ)一、軟件的定義1、軟件：包括程序、數(shù)據(jù)和相關(guān)文檔的完整集合。2、軟件按功能劃分：應(yīng)用軟件、系統(tǒng)軟件與支撐軟件（或工具軟件）。應(yīng)用軟件：QQ、Office(word、excel等）、Wps系統(tǒng)軟件：Windows、OS/2、Linux、Unix二、軟件危機(jī)與軟件工程1、軟件危機(jī)⑴概念：出現(xiàn)于20世紀(jì)60年代末，泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。⑵軟件危機(jī)的主要表現(xiàn)：①用戶對(duì)交付使用的軟件系統(tǒng)不滿意。②軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。③軟件的質(zhì)量無(wú)法保證。④現(xiàn)有軟件維護(hù)困難。⑤軟件的成本不斷提高。⑥軟件開(kāi)發(fā)的速度跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？偟膩?lái)說(shuō)，歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。下面描述中，不屬于軟件危機(jī)表現(xiàn)的是A)

軟件過(guò)程不規(guī)范B)

軟件開(kāi)發(fā)生產(chǎn)率低C)

軟件質(zhì)量難以控制

D)

軟件成本不斷提高2、軟件工程為了擺脫軟件危機(jī)，提出了軟件工程的概念。所謂軟件工程，是指采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開(kāi)發(fā)與維護(hù)。軟件工程學(xué)是研究軟件開(kāi)發(fā)和維護(hù)的普遍原理與技術(shù)的一門工程學(xué)科。⑴軟件工程三要素①方法：是完成軟件工程項(xiàng)目的技術(shù)手段②工具：支持軟件的開(kāi)發(fā)、管理、文檔生成③過(guò)程：支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理⑵軟件工程核心思想：把軟件產(chǎn)品看作是一個(gè)工程產(chǎn)品來(lái)處理。(3)、軟件工程研究的內(nèi)容與原則軟件工程研究的主要內(nèi)容：軟件開(kāi)發(fā)技術(shù)和軟件工程管理軟件工程的原則：抽象、信息屏蔽、模塊化等(4)軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。三、軟件生命周期是指軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的全過(guò)程。劃分為如下三個(gè)階段：①軟件定義②軟件開(kāi)發(fā)③軟件維護(hù)3、軟件生命周期各階段的主要任務(wù)是：階段任務(wù)描述軟件定義階段可行性研究與計(jì)劃制定確定開(kāi)發(fā)目標(biāo)，制定實(shí)施計(jì)劃。需求分析對(duì)待開(kāi)發(fā)軟件提出需求進(jìn)行分析，確定軟件系統(tǒng)的功能需求并給出詳細(xì)定義。編寫軟件規(guī)格說(shuō)明書及初步的用戶手冊(cè)，提交評(píng)審。需求分析的成果：需求規(guī)格說(shuō)明書軟件開(kāi)發(fā)階段軟件設(shè)計(jì)分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)階段，給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。這階段提交評(píng)審的文檔有概要設(shè)計(jì)說(shuō)明書、詳細(xì)設(shè)計(jì)說(shuō)明書和測(cè)試計(jì)劃初稿。軟件實(shí)現(xiàn)在軟件設(shè)計(jì)的基礎(chǔ)上編寫程序。軟件測(cè)試在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。編寫測(cè)試分析報(bào)告。軟件維護(hù)運(yùn)行維護(hù)將已交付的軟件投入運(yùn)行，同時(shí)不斷的維護(hù)，進(jìn)行必要而且可行的擴(kuò)充和刪改。結(jié)構(gòu)化分析方法（軟件定義階段）一、需求分析1、需求分析的成果：需求規(guī)格說(shuō)明書2、需求分析方法⑴結(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)開(kāi)發(fā)方法DSSD⑵面向?qū)ο蟮姆治龇椒ǎ篛OA二、結(jié)構(gòu)化分析方法

1、分析手段：分解和抽象2、分析工具⑴數(shù)據(jù)流圖DFD（注意主要圖形元素說(shuō)明）

加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換輸出。數(shù)據(jù)流：沿箭頭放心傳送數(shù)據(jù)的通道。存儲(chǔ)文件（數(shù)據(jù)源）：表示處理過(guò)程中存放各種數(shù)據(jù)的文件。源，潭：表示系統(tǒng)和環(huán)境的接口。⑵數(shù)據(jù)字典DD：作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素的確切解釋，（

數(shù)據(jù)字典（DD)

所定義的對(duì)象都包含于數(shù)據(jù)流圖中）是結(jié)構(gòu)化分析的核心。⑶判定樹(shù)⑷判定表三、軟件需求規(guī)格說(shuō)明書軟件需求規(guī)格說(shuō)明書是需求分析階段的最后成果。軟件需求規(guī)格說(shuō)明書的作用包括

：A)

軟件驗(yàn)收的依據(jù)

B)

用戶與開(kāi)發(fā)人員對(duì)軟件要做什么的共同理解C)

軟件設(shè)計(jì)的依據(jù)

結(jié)構(gòu)化設(shè)計(jì)方法

（開(kāi)發(fā)階段）一、軟件設(shè)計(jì)的基本概念1、軟件設(shè)計(jì)：把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程，分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步完成。2、設(shè)計(jì)原則⑴抽象：把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。⑵模塊化：模塊是指把一個(gè)待開(kāi)發(fā)的軟件分解成若干小的簡(jiǎn)單的部分。模塊化是指解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過(guò)程。⑶信息隱蔽：信息隱蔽是指在一個(gè)模塊內(nèi)包含的信息（過(guò)程或數(shù)據(jù)），對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。⑷模塊獨(dú)立性：模塊獨(dú)立性是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。劃分模塊的原則要盡量做到“高內(nèi)聚，低耦合”。二、總體設(shè)計(jì)（概要設(shè)計(jì)）：1、基本任務(wù)⑴設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)⑵數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)⑶編寫概要設(shè)計(jì)文檔⑷概要設(shè)計(jì)文檔評(píng)審2、設(shè)計(jì)工具：結(jié)構(gòu)圖SC(StructureChart)3、面向數(shù)據(jù)流的設(shè)計(jì)方法典型的數(shù)據(jù)流類型：變換型和事務(wù)型扇入：是指直接調(diào)用該模塊的上級(jí)模塊的個(gè)數(shù)。扇入大表示模塊的復(fù)用程序高。扇出：是指該模塊直接調(diào)用的下級(jí)模塊的個(gè)數(shù)一個(gè)模塊的扇入是指有多少個(gè)上級(jí)模塊調(diào)用它。扇人越大，表示該模塊被更多的上級(jí)模塊共享。這當(dāng)然是我們所希望的。但是不能為了獲得高扇人而不惜代價(jià)，例如把彼此無(wú)關(guān)的功能湊在一起構(gòu)成一個(gè)模塊，雖然扇人數(shù)高了，但這樣的模塊內(nèi)聚程度必然低。這是我們應(yīng)避免的。設(shè)計(jì)得好的系統(tǒng)，上層模塊有較高的扇出，下層模塊有較高的扇人。其結(jié)構(gòu)圖像清真寺的塔，上面尖，中間寬，下面小。例題：某系統(tǒng)結(jié)構(gòu)圖如下圖所示，該系統(tǒng)結(jié)構(gòu)圖的最大扇出數(shù)是（）A)4B)1C)3D)n某系統(tǒng)結(jié)構(gòu)圖如下圖所示

，該系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)：A）n

B）

1

C）

2

D）3

某系統(tǒng)結(jié)構(gòu)圖如下圖所示，該系統(tǒng)結(jié)構(gòu)圖中最大扇入是

A）0

B）1

C）2

D）3

三、詳細(xì)設(shè)計(jì)：1、基本任務(wù)：為每個(gè)模塊確定算法和局部數(shù)據(jù)結(jié)構(gòu)2、設(shè)計(jì)工具⑴圖形工具：①程序流程圖：構(gòu)成程序流程圖的基本圖符及含義：→或↓表示控制流；□表示加工步驟；

表示邏輯條件。

②N-S圖：③PAD圖：④HIPO⑵表格工具：判定表⑶語(yǔ)言工具：PDL(偽碼），是一種混合語(yǔ)言，采用英語(yǔ)的詞匯和結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言的語(yǔ)法，類似編程語(yǔ)言。軟件工程階段用到的方法用到的工具生成的文檔需求分析結(jié)構(gòu)化分析SA數(shù)據(jù)流圖DFD數(shù)據(jù)字典DD判定表判定樹(shù)軟件需求規(guī)格說(shuō)明書概要設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)SD軟件結(jié)構(gòu)圖SC概要設(shè)計(jì)說(shuō)明書數(shù)據(jù)庫(kù)設(shè)計(jì)說(shuō)明書集成測(cè)試計(jì)劃詳細(xì)設(shè)計(jì)結(jié)構(gòu)化編程SP程序流程圖N-S圖問(wèn)題分析圖PAD偽碼PDL軟件測(cè)試一、定義：軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。軟件測(cè)試是保證軟件質(zhì)量的重要手段。

二、目標(biāo)：測(cè)試是為了發(fā)現(xiàn)軟件中的錯(cuò)誤而運(yùn)行軟件的過(guò)程好的測(cè)試方案是盡可能地發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試方案成功的測(cè)試則是發(fā)現(xiàn)出了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。軟件測(cè)試的目的是A)

評(píng)估軟件可靠性

B)

發(fā)現(xiàn)并改正程序中的錯(cuò)誤C)

改正程序中的錯(cuò)誤

D)

發(fā)現(xiàn)程序中的錯(cuò)誤三、原則：不要抱有“軟件不會(huì)有錯(cuò)或認(rèn)為查不出錯(cuò)的“幻想”設(shè)計(jì)測(cè)試用例時(shí)，應(yīng)同時(shí)確定輸出結(jié)果設(shè)計(jì)測(cè)試用例時(shí)，應(yīng)包括合理的數(shù)據(jù)和不合理的數(shù)據(jù)軟件設(shè)計(jì)者應(yīng)當(dāng)避免測(cè)試自己的程序嚴(yán)格全面地執(zhí)行測(cè)試計(jì)劃妥善保存測(cè)試計(jì)劃、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告四、軟件測(cè)試技術(shù)與方法按照是否需要執(zhí)行軟件劃分：靜態(tài)測(cè)試、動(dòng)態(tài)測(cè)試。按照功能劃分：白盒測(cè)試、黑盒測(cè)試1、靜態(tài)測(cè)試與動(dòng)態(tài)測(cè)試⑴靜態(tài)測(cè)試：由人工或借助工具對(duì)軟件進(jìn)行閱讀和檢查。靜態(tài)測(cè)試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。⑵動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。動(dòng)態(tài)測(cè)試的關(guān)鍵是設(shè)計(jì)高效、合理的測(cè)試用例。2、白盒測(cè)試與黑盒測(cè)試⑴白盒測(cè)試：又稱為結(jié)構(gòu)測(cè)試或邏輯測(cè)試。利用程序內(nèi)部的邏輯結(jié)構(gòu)和特性來(lái)設(shè)計(jì)測(cè)試用例，檢查程序中的邏輯通路是否都按預(yù)定的要求正確地工作。測(cè)試的基本原則：保證每一條獨(dú)立路徑至少執(zhí)行一次。測(cè)試的主要方法包括邏輯覆蓋、基本路徑測(cè)試⑵黑盒測(cè)試：又稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試，是對(duì)軟件的功能進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和特性，只根據(jù)程序的需求和功能設(shè)計(jì)測(cè)試用例。測(cè)試的常用方法有等價(jià)分類法、邊界值分析法、錯(cuò)誤推測(cè)法和因果圖。使用白盒測(cè)試方法時(shí)，設(shè)計(jì)測(cè)試用例應(yīng)根據(jù)

A）程序的內(nèi)部邏輯B）程序的復(fù)雜結(jié)構(gòu)C）程序的功能

D）使用說(shuō)明書五、軟件測(cè)試的實(shí)施軟件測(cè)試過(guò)程一般按4個(gè)步驟進(jìn)行，即單元測(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系統(tǒng)測(cè)試。1、單元測(cè)試：對(duì)模塊進(jìn)行測(cè)試，目的是發(fā)現(xiàn)模塊內(nèi)部可能存在的錯(cuò)誤。2、集成測(cè)試：測(cè)試和組裝軟件，目的是發(fā)現(xiàn)和接口有關(guān)的錯(cuò)誤。3、確認(rèn)測(cè)試：驗(yàn)證軟件的功能和性能是否符合需求。4、系統(tǒng)測(cè)試：將通過(guò)測(cè)試的軟件與硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起進(jìn)行測(cè)試。

下面不屬于軟件測(cè)試實(shí)施步驟的是

A)

集成測(cè)試

B)

回歸測(cè)試

C)

確認(rèn)測(cè)試

D)

單元測(cè)試程序的調(diào)試在對(duì)程序進(jìn)行了成功的測(cè)試之后將進(jìn)入程序調(diào)試（通常稱Debug，即排錯(cuò)）。注：軟件調(diào)試與軟件測(cè)試是不同的概念，軟件調(diào)試的目的是為了改正程序中的錯(cuò)誤。一、基本概念1、程序調(diào)試的任務(wù)：診斷和改正程序中的錯(cuò)誤。軟件測(cè)試貫穿整個(gè)軟件生命期，調(diào)試則主要在開(kāi)發(fā)階段進(jìn)行。2、程序調(diào)試的步驟⑴錯(cuò)誤定位⑵修改設(shè)計(jì)和代碼，以排除錯(cuò)誤；⑶進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。二、軟件調(diào)試的方法調(diào)試的關(guān)鍵在于推斷程序內(nèi)部的錯(cuò)誤位置及原因。軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。主要的調(diào)試方法有：強(qiáng)行排錯(cuò)法、回溯法、原因排除法1、程序測(cè)試的目的是（）A）發(fā)現(xiàn)程序中的錯(cuò)誤

B）發(fā)現(xiàn)并改正程序中的錯(cuò)誤C）診斷并改正程序中的錯(cuò)誤

D）執(zhí)行測(cè)試用例2、下面不屬于軟件開(kāi)發(fā)階段任務(wù)的是（）

A）測(cè)試

B）設(shè)計(jì)

C）可行性研究D)實(shí)現(xiàn)3、下面可以作為軟件設(shè)計(jì)工具的是

DA）數(shù)據(jù)字典（DD）

B）甘特圖C）數(shù)據(jù)流程圖（DED圖）D）系統(tǒng)結(jié)構(gòu)圖4、下面對(duì)軟件測(cè)試和軟件調(diào)試有關(guān)概念敘述錯(cuò)誤的是A）程序調(diào)試通常也稱為Debug

B）設(shè)計(jì)正確的測(cè)試用例C）軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤和改正錯(cuò)誤D）嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性5、下面屬于白盒測(cè)試方法的是A)

等價(jià)類劃分法B)

邊界值分析法

C)

基本路徑測(cè)試D)

錯(cuò)誤推測(cè)法6、軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則是

A)

低內(nèi)聚低耦合

B)

高耦合高內(nèi)聚C)

高內(nèi)聚低耦合7、軟件生命周期是指A)

軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程B)

軟件從需求分析、設(shè)計(jì)、實(shí)現(xiàn)到測(cè)試完成的過(guò)程C)

軟件的開(kāi)發(fā)過(guò)程

D)

軟件的運(yùn)行維護(hù)過(guò)程8、下面描述中錯(cuò)誤的是A)

系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細(xì)設(shè)計(jì)B)

軟件設(shè)計(jì)是將軟件需求轉(zhuǎn)換為軟件表示的過(guò)程C)

數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)設(shè)計(jì)是軟件設(shè)計(jì)的任務(wù)之一D)

PAD圖是軟件詳細(xì)設(shè)計(jì)的表示工具9、軟件按功能可以分為應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應(yīng)用

軟件的是A)

學(xué)生成績(jī)管理系統(tǒng)

B)

C語(yǔ)言編譯程序C)

UNIX

操作系統(tǒng)

D)

數(shù)據(jù)庫(kù)管理系統(tǒng)10、構(gòu)成計(jì)算機(jī)軟件的是A)

源代碼

B)

程序和數(shù)據(jù)C)

程序和文檔

D)

程序、數(shù)據(jù)及相關(guān)文檔11、數(shù)據(jù)流圖中帶有箭頭的線段表示的是

A)

控制流

B)

事件驅(qū)動(dòng)

C)

模塊調(diào)用

D)

數(shù)據(jù)流12、在軟件開(kāi)發(fā)中，需求分析階段可以使用的工具是A)

N-S圖

B)

DFD圖

C)

PAD圖

D)

程序流程圖第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)一、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)1、數(shù)據(jù)(Data)：描述事物的符號(hào)記錄。2、數(shù)據(jù)庫(kù)(DB)：數(shù)據(jù)的集合。3、數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)：是在操作系統(tǒng)支持下管理數(shù)據(jù)庫(kù)的系統(tǒng)軟件，是數(shù)據(jù)庫(kù)系統(tǒng)的核心。

⑴數(shù)據(jù)庫(kù)管理系統(tǒng)的功能：①數(shù)據(jù)模式定義②數(shù)據(jù)存取的物理構(gòu)建③數(shù)據(jù)操縱：數(shù)據(jù)查詢、數(shù)據(jù)的刪除、數(shù)據(jù)插入、數(shù)據(jù)修改④數(shù)據(jù)的完整性、安全性定義與檢查⑤數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)⑥數(shù)據(jù)的服務(wù)⑵數(shù)據(jù)庫(kù)管理系統(tǒng)提供的數(shù)據(jù)語(yǔ)言：①數(shù)據(jù)定義語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。②數(shù)據(jù)操縱語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的操縱，包括數(shù)據(jù)的增、刪、改和查詢。③數(shù)據(jù)控制語(yǔ)言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。4、數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)(DBAS)：利用數(shù)據(jù)庫(kù)系統(tǒng)開(kāi)發(fā)的應(yīng)用軟件。5、數(shù)據(jù)庫(kù)管理員(DBA):負(fù)責(zé)定義書庫(kù)內(nèi)容、決定存儲(chǔ)結(jié)構(gòu)和存取策略及安全授權(quán)等工作。6、數(shù)據(jù)庫(kù)系統(tǒng)(DBS)：包含硬件系統(tǒng)、軟件系統(tǒng)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理員和用戶。二、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展1、人工管理階段：數(shù)據(jù)無(wú)法共享，冗余度大，不獨(dú)立，完全依賴于程序。2、文件系統(tǒng)階段：數(shù)據(jù)共享性差，獨(dú)立性也較差。3、數(shù)據(jù)庫(kù)系統(tǒng)階段：數(shù)據(jù)獨(dú)立性最高。三、數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)1、數(shù)據(jù)的集成性2、數(shù)據(jù)的高共享性和低冗余性：數(shù)據(jù)共享可以減少數(shù)據(jù)集冗余，并且避免數(shù)據(jù)的不一致性。

數(shù)據(jù)的一致性是指在系統(tǒng)中同一數(shù)據(jù)在不同地方出現(xiàn)應(yīng)保持相同的值。3、數(shù)據(jù)獨(dú)立性：數(shù)據(jù)與程序獨(dú)立存放⑴物理獨(dú)立性：當(dāng)數(shù)據(jù)的物理結(jié)構(gòu)改變時(shí)，如存儲(chǔ)結(jié)構(gòu)改變、存儲(chǔ)設(shè)備的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，應(yīng)用程序不用改變。⑵邏輯獨(dú)立性：當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要改變應(yīng)用程序。4、數(shù)據(jù)統(tǒng)一管理與控制四、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系1、三級(jí)模式⑴概念模式：是對(duì)數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式。⑵外模式：是數(shù)據(jù)庫(kù)用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù)模式，由概念模式推導(dǎo)而出。一個(gè)概念模式可以有若干個(gè)外模式。⑶內(nèi)模式：給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲(chǔ)形式，概念模式處于中間層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層，它反映了用戶對(duì)數(shù)據(jù)的要求。2、兩級(jí)映射：概念模式到內(nèi)模式的映射、外模式到概念模式的映射。保證了數(shù)據(jù)庫(kù)系統(tǒng)中的數(shù)據(jù)能夠具有較高的邏輯獨(dú)立性和物理獨(dú)立性。1、數(shù)據(jù)庫(kù)管理系統(tǒng)是________。A)一種編譯系統(tǒng)B)一種操作系統(tǒng)C)操作系統(tǒng)的一部分D)在操作系統(tǒng)支持下的系統(tǒng)軟件2、數(shù)據(jù)庫(kù)系統(tǒng)的核心是

系統(tǒng)3、在數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是________。A)數(shù)據(jù)庫(kù)系統(tǒng)階段B)三個(gè)階段相同C)人工管理階段D)文件系統(tǒng)階段4、在數(shù)據(jù)庫(kù)管理系統(tǒng)提供的數(shù)據(jù)定義語(yǔ)言、數(shù)據(jù)操縱語(yǔ)言和數(shù)據(jù)控制語(yǔ)言中，

語(yǔ)言負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。5、數(shù)據(jù)庫(kù)DB、數(shù)據(jù)庫(kù)系統(tǒng)DBS、數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS之間的關(guān)系是________。A)DBS包含DB和DBMSB)沒(méi)有任何關(guān)系C)DB包含DBS和DBMSD)DBMS包含DB和DBS

6、數(shù)據(jù)庫(kù)管理系統(tǒng)中負(fù)責(zé)數(shù)據(jù)模式定義的語(yǔ)言是

。7、數(shù)據(jù)獨(dú)立性是數(shù)據(jù)庫(kù)技術(shù)的重要特點(diǎn)之一。所謂數(shù)據(jù)獨(dú)立性是指________。A)不同的數(shù)據(jù)只能被對(duì)應(yīng)的應(yīng)用程序所使用B)三種說(shuō)法都不對(duì)C)數(shù)據(jù)與程序獨(dú)立存放D)不同的數(shù)據(jù)被存放在不同的文件中

一、數(shù)據(jù)模型是對(duì)現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象。是指反映客觀事物及客觀事物間聯(lián)系的數(shù)據(jù)組織的結(jié)構(gòu)和形式。現(xiàn)實(shí)世界人的抽象認(rèn)識(shí)信息世界：概念模型機(jī)器世界：具體的數(shù)據(jù)模型數(shù)據(jù)模型

1、概念數(shù)據(jù)模型：對(duì)客觀事物抽象化，實(shí)體-聯(lián)系數(shù)據(jù)模型即E-R模型2、邏輯數(shù)據(jù)模型：把概念數(shù)據(jù)邏輯化，依賴某種數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)模型通常由數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束三部分組成。層次模型、網(wǎng)狀模型和關(guān)系模型二、E-R模型1、實(shí)體：現(xiàn)實(shí)世界中客觀存在且可以相互區(qū)別的事物。2、屬性：描述實(shí)體的特征3、實(shí)體間聯(lián)系：一對(duì)一1∶1；一對(duì)多1∶m；多對(duì)多m∶n4、實(shí)體型：實(shí)體屬性的集合5、實(shí)體集：相同類型實(shí)體的集合實(shí)體集屬性聯(lián)系6、圖示法：矩形-實(shí)體集；橢圓-屬性；菱形-聯(lián)系學(xué)生1(學(xué)號(hào)、姓名、性別、出生日期、系別、籍貫)實(shí)體屬性實(shí)體集實(shí)體型學(xué)生2(學(xué)號(hào)、姓名、性別、出生日期、系別、籍貫)學(xué)生n(學(xué)號(hào)、姓名、性別、出生日期、系別、籍貫)三、數(shù)據(jù)庫(kù)管理系統(tǒng)所支持的數(shù)據(jù)模型分為3種：層次模型、網(wǎng)狀模型和關(guān)系模型。層次模型：描述數(shù)據(jù)之間的從屬層次關(guān)系。網(wǎng)狀模型：描述數(shù)據(jù)之間的多種從屬的網(wǎng)狀關(guān)系。關(guān)系模型：主要描述那種具有相關(guān)性而非從屬性的平行的數(shù)據(jù)之間按照某種序列排列的集合關(guān)系。格式為：關(guān)系名（屬性名1，屬性名2，…

，屬性名n）1、元組——記錄——行；屬性——字段——列四、關(guān)系模型：二維表結(jié)構(gòu)2、域：屬性的取值范圍3、碼（鍵）：二維表中唯一標(biāo)識(shí)元組的最小屬性值。一個(gè)表可能有若干鍵，它們稱為該表的候選碼（或候選鍵），從候選鍵中選取一個(gè)作為用戶使用的鍵稱為主鍵（或主碼）。如表A中的某屬性是某表B的鍵，則稱該屬性為A的外鍵（或外碼）例：1、在關(guān)系A(chǔ)(S，SN，D)和關(guān)系B(D，CN，NM)中，A的主關(guān)鍵字是S，B的主關(guān)鍵字是D，則稱

是關(guān)系A(chǔ)的外碼。2、圖書館數(shù)據(jù)庫(kù)系統(tǒng)中有下列模式書（書號(hào)，類別，書名，出版社，年份，作者，價(jià)格，總藏書量，現(xiàn)有庫(kù)存）借書卡（卡號(hào)，姓名，單位，類別）

借書記錄（卡號(hào)，書號(hào)，借期，還期）其中關(guān)系書和關(guān)系借書卡的主鍵分別為書號(hào)和卡號(hào)，關(guān)系借書記錄的主鍵為A）卡號(hào)，書號(hào)B）書號(hào)，借期C）卡號(hào)，書號(hào)，借期D）卡號(hào)，借期

二維表的性質(zhì)：⑴二維表中元組個(gè)數(shù)是有限的——元組個(gè)數(shù)有限性；⑵二維表中元組均不相同——元組的唯一性；⑶二維表中元組的次序可以任意交換——元組的次序無(wú)關(guān)性；⑷二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)——元組分量的原子性；⑸二維表中屬性名各不相同——屬性名唯一性；⑹二維表中屬性與次序無(wú)關(guān)，可任意交換——屬性的次序無(wú)關(guān)性；⑺二維表屬性的分量具有與該屬性相同的值域——分量值域的統(tǒng)一性。4、關(guān)系操縱：數(shù)據(jù)查詢、數(shù)據(jù)的刪除、數(shù)據(jù)插入、數(shù)據(jù)修改。5、關(guān)系中的數(shù)據(jù)約束：實(shí)體完整性約束、參照完整性約束、用戶定義的完整性約束實(shí)體完整性約束：關(guān)系中每一個(gè)元組的主碼（主鍵）屬性不能重復(fù)，并且不能取空值，關(guān)系表中至少有一個(gè)字段滿足沒(méi)有重復(fù)值（即至少有一個(gè)候選索引)參照完整性：父表關(guān)鍵字更改，子表是否作相應(yīng)的變化

例題：有三個(gè)關(guān)系表R、S和T如下，其中三個(gè)關(guān)系對(duì)應(yīng)的關(guān)鍵字分別為A,B和符合關(guān)鍵字（A,B）。表T的記錄項(xiàng)(b,q,4)違反了用戶定義的完整性約束參照完整性約束實(shí)體完整性約束AA1a1bnBB1B2fghlxynpxABCaf3bq4RST一、專門的關(guān)系模型的基本運(yùn)算1、選擇()：從一個(gè)關(guān)系R中找出滿足給定條件F的元組(記錄)的操作成為選擇。記為：σF(R)關(guān)系運(yùn)算2023/2/220:50選擇運(yùn)算–例子關(guān)系RABCDA=B^D>5

(R)ABCD123710∧∨非與(and)或(or)有關(guān)系R如下：ABCDaa22be12cc114ee61則運(yùn)算A<>B^D>=2R的結(jié)果為：空(a,a,2,2)