2017全國計(jì)算機(jī)等級(jí)考試二級(jí)C語言知識(shí)點(diǎn)超全整打印版

1、全國計(jì)算機(jī)等級(jí)考試目錄第一部分 公共基礎(chǔ)知識(shí)第 1 章 算法與數(shù)據(jù)結(jié)構(gòu)1考點(diǎn) 1 算法1考點(diǎn) 2 數(shù)據(jù)結(jié)構(gòu)1考點(diǎn) 3 線性表及其順序存儲(chǔ)結(jié)構(gòu)1考點(diǎn) 4 棧和隊(duì)列1考點(diǎn) 5 線性鏈表2考點(diǎn) 6 樹與二叉樹2考點(diǎn) 7 查找技術(shù)3考點(diǎn) 8 排序技術(shù)3第 2 章 程序設(shè)計(jì)基礎(chǔ)4考點(diǎn) 1 程序設(shè)計(jì)方法與風(fēng)格4考點(diǎn) 2 結(jié)構(gòu)化程序設(shè)計(jì)5考點(diǎn) 3 面向?qū)ο蟮某绦蛟O(shè)計(jì)5第 3 章軟件工程基礎(chǔ)5考點(diǎn) 1 軟件工程基本概念5考點(diǎn) 2 軟件分析方法6考點(diǎn) 3 結(jié)構(gòu)化設(shè)計(jì)方法7考點(diǎn) 4 軟件測試8考點(diǎn) 5 程序的調(diào)試9第 4 章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)9考點(diǎn) 1 數(shù)據(jù)庫系統(tǒng)的基本概念9考點(diǎn) 2 數(shù)據(jù)庫系統(tǒng)的基本概念10考點(diǎn)

2、3 關(guān)系代數(shù)12考點(diǎn) 4 數(shù)據(jù)庫設(shè)計(jì)與管理12第二部分 二級(jí) C 語言第 1 章 程序設(shè)計(jì)基本概念14考點(diǎn) 1 程序設(shè)計(jì)14考點(diǎn) 2 C 程序的結(jié)構(gòu)和格式14考點(diǎn) 3 常量和變量14考點(diǎn) 4 算術(shù)表達(dá)式15考點(diǎn) 5 賦值表達(dá)式16考點(diǎn) 6 自加、自減和逗號(hào)運(yùn)算16第 2 章 順序結(jié)構(gòu)17考點(diǎn) 1 字符型常量與變量17考點(diǎn) 2 putchar 與 getchar 函數(shù)17考點(diǎn) 3 printf 函數(shù)17考點(diǎn) 4 scanf 函數(shù)18考點(diǎn) 5 位運(yùn)算的含義和應(yīng)用18第 3 章 選擇結(jié)構(gòu)19考點(diǎn) 1 關(guān)系運(yùn)算符和關(guān)系表達(dá)式19考點(diǎn) 2 邏輯運(yùn)算符和邏輯表達(dá)式19考點(diǎn) 3 if 語句及其構(gòu)成的選擇結(jié)構(gòu)

3、19考點(diǎn) 4 switch 語句與 break 語句20第 4 章 循環(huán)結(jié)構(gòu)20考點(diǎn) 1 while 循環(huán)結(jié)構(gòu)20考點(diǎn) 2 do-while 循環(huán)結(jié)構(gòu)21考點(diǎn) 3 for 循環(huán)結(jié)構(gòu)21考點(diǎn) 4 嵌套循環(huán)語句21第 5 章 函數(shù)21考點(diǎn) 1 庫函數(shù)21考點(diǎn) 2 函數(shù)的調(diào)用22考點(diǎn) 3 參數(shù)傳遞22考點(diǎn) 4 函數(shù)的遞歸調(diào)用23考點(diǎn) 5 局部、全局變量和存儲(chǔ)分類23第 6 章 地址與指針23考點(diǎn) 1 變量的地址和指針23考點(diǎn) 2 指針變量的操作24考點(diǎn) 3 函數(shù)之間地址的傳遞24第 7 章 數(shù)組24考點(diǎn) 1 一維數(shù)組的定義及元素的引用. 24考點(diǎn) 2 函數(shù)對(duì)一維數(shù)組及元素的引用. 25考點(diǎn) 3 二維

4、數(shù)組的定義25考點(diǎn) 4 二維數(shù)組和指針25考點(diǎn) 5 二維數(shù)組名和指針數(shù)組作為實(shí)參. 26第 8 章 字 符串26考點(diǎn) 1 用一維字符數(shù)組存放字符串26考點(diǎn) 2 使指針指向字符串26考點(diǎn) 3 字符串的輸入和輸出26考點(diǎn) 4 字符串?dāng)?shù)組27考點(diǎn) 5 用于字符串處理的函數(shù)27第 9 章 編譯預(yù)處理和動(dòng)態(tài)存儲(chǔ)分配27考點(diǎn) 1 編譯預(yù)處理27考點(diǎn) 2 宏替換27考點(diǎn) 3 文件包含處理28考點(diǎn) 4 動(dòng)態(tài)存儲(chǔ)分配28第 10 章 結(jié)構(gòu)體、共用體和用戶定義類型28考點(diǎn) 1 結(jié)構(gòu)體28考點(diǎn) 2 共用體29考點(diǎn) 3 用戶定義類型29第 11 章 文件29考點(diǎn) 1 文件指針29考點(diǎn) 2 文件的讀寫30第一部分 公共

5、基礎(chǔ)知識(shí)第 1 章 算法與數(shù)據(jù)結(jié)構(gòu)考點(diǎn) 1 算法1什么是算法算法是指對(duì)解題方案的準(zhǔn)確而完整的描述。計(jì)算機(jī)程序本質(zhì)上就是一個(gè)算法，它告訴計(jì)算機(jī)確切的步驟來執(zhí)行一個(gè)指定的任務(wù)。（1）算法的基本特征一般來說，算法應(yīng)具有：可行性、確定性、有窮性、擁有足夠的情報(bào)這幾個(gè)特征。（2）算法的組成要素通常，一個(gè)算法由兩部分組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。2算法的復(fù)雜度算法的復(fù)雜度是算法規(guī)模的度量，一個(gè)算法的復(fù)雜度高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少，所需的資源越多，就說明該算法的復(fù)雜度越高；反之，所需的資源越少，則該算法的復(fù)雜度越低。算法復(fù)雜度包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度

6、?？键c(diǎn) 2 數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)的概念所謂數(shù)據(jù)結(jié)構(gòu)是指由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成的集合。成員之間的關(guān)系有很多種，最常見的是前后件關(guān)系。2數(shù)據(jù)的邏輯結(jié)構(gòu)（1）邏輯結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。對(duì)于電腦上的數(shù)據(jù)而言，邏輯結(jié)構(gòu)就是能夠用眼睛看到的數(shù)據(jù)形式，包括在屏幕上看到的文本、圖片、視頻等。（2）邏輯結(jié)構(gòu)的分類根據(jù)數(shù)據(jù)結(jié)構(gòu)中各元素之間前后關(guān)系的復(fù)雜程度，將數(shù)據(jù)的邏輯結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。一個(gè)非空的線性結(jié)構(gòu)如果滿足以下兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也稱為數(shù)據(jù)的物理結(jié)

7、構(gòu)， 是指數(shù)據(jù)在計(jì)算機(jī)中存放的方式，包括數(shù)據(jù)元素的存儲(chǔ)和關(guān)系的存儲(chǔ)。通常，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。考點(diǎn) 3 線性表及其順序存儲(chǔ)結(jié)構(gòu)1線性表的基本概念線性表是由 n 個(gè)數(shù)據(jù)元素組成的有限序列，是最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。其中的數(shù)據(jù)元素有著廣泛的含義，可以是一個(gè)單獨(dú)的數(shù)字或字母，可以是矩陣中的一行或一列向量， 也可以是二維表中的一條記錄。線性表是一種線性結(jié)構(gòu)。數(shù)據(jù)元素在線性表中的位置，只取決于它們自己的序號(hào)，即數(shù)據(jù)元素之間的相對(duì)位置是線性的。2線性表的順序存儲(chǔ)結(jié)構(gòu)一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)。線性表的存儲(chǔ)結(jié)構(gòu)常用的是

8、順序存儲(chǔ)，也稱為順序分配。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。3順序表的插入所謂“順序表”指的是使用順序存儲(chǔ)結(jié)構(gòu)的線性表。在順序表中插入一個(gè)新的數(shù)據(jù)元素，就像是在排隊(duì)買票的時(shí)候進(jìn)來了一個(gè)插隊(duì)的人。4順序表的刪除在順序表中刪除一個(gè)數(shù)據(jù)元素，就像是在排隊(duì)買票的時(shí)候其中的一個(gè)人離開了。在平均情況下，要在線性表中刪除一個(gè)元素，需要移動(dòng)線性表中一半的數(shù)據(jù)元素?？键c(diǎn) 4 棧和隊(duì)列1棧及其基本運(yùn)算（1）什么是棧棧是一種特殊的線性表。在這種特殊的線性表中，其插入和刪除運(yùn)算都只能在線性表的一端進(jìn)行。一端是封閉的，

9、不允許插入和刪除數(shù)據(jù)元素；另一端是敞開的，允許插入和刪除數(shù)據(jù)元素。在棧中，允許插入和刪除數(shù)據(jù)元素的一端稱為棧頂，而不允許插入和刪除數(shù)據(jù)元素的一端稱為棧底。棧頂元素總會(huì)是被最后插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶的功能， 支持子程序的調(diào)用。通常用指針 top 來指示棧頂位置，用指針 bottom 來指示棧底的位置。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素稱為退棧運(yùn)算。通過棧頂指針 top 來反反映棧中元素的動(dòng)態(tài)變化情況。（2）棧的基本運(yùn)算棧的基本運(yùn)算有 3 種：

10、入棧、退棧與讀棧頂元素。入棧運(yùn)算。入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針進(jìn)一（即top 加 1），然后將新元素插入到棧頂指針指向的位置。退棧運(yùn)算。退棧運(yùn)算是指取出棧頂元素并賦給指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素賦值給一個(gè)指定的變量，然后將棧頂指針退一（即 top 減 1）。讀棧頂元素。讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量，但是不刪除棧頂元素。因此，在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。當(dāng)棧頂指針為 0 時(shí)，說明棧空，讀不到棧頂元素。2隊(duì)列及其基本運(yùn)算（1）什么是隊(duì)列隊(duì)列是指允許在表的一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱

11、為隊(duì)尾，通常用一個(gè)隊(duì)尾指針（rear）指向隊(duì)尾元素，隊(duì)尾指針總是指向最后被插入的元素；允許刪除的一端稱為排頭（也稱為隊(duì)頭），通常也用一個(gè)排頭指針（front）指向排頭元素的前一個(gè)位置。（2）循環(huán)隊(duì)列及其運(yùn)算隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂的循環(huán)隊(duì)列，就是將隊(duì)列的存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。入隊(duì)運(yùn)算。入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針進(jìn)一（即 rear=rera+1），并當(dāng) rear=m+1 時(shí)置 rear=1；然后將新元素插入到隊(duì)尾指針指向的位置。退隊(duì)運(yùn)算。退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭

12、位置退出一個(gè)元素并賦值給指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將排頭指針進(jìn)一（即 front=front+1），并當(dāng)front=m+1 時(shí)置 front=1；然后將排頭指針指向的元素賦給指定的變量。考點(diǎn) 5 線性鏈表1線性鏈表（1）線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在線性鏈表中，存儲(chǔ)空間上的每一個(gè)存儲(chǔ)結(jié)點(diǎn)都要分成兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)該數(shù)據(jù)元素的存儲(chǔ)序號(hào)（存儲(chǔ)結(jié)點(diǎn)的地址，即指向后件結(jié)點(diǎn)），稱為指針域。（2）線性鏈表的查找在非空的線性鏈表中查找指定元素的操作：從頭指針指向的結(jié)點(diǎn)開始往后沿著指針進(jìn)行掃描，如果找到要查找的內(nèi)容，則查找成功； 如果沒

13、有對(duì)應(yīng)的要查找的元素，則查找失敗。為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn)，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針（Llink），用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針（Rlink），用來指向其后件結(jié)點(diǎn)。這樣的線性表稱為雙向鏈表。（3）線性鏈表的插入在向線性鏈表中插入一個(gè)新元素之前，我們先要給該元素分配一個(gè)新結(jié)點(diǎn)，其中包括值域和指針域以便用于存儲(chǔ)該元素的值。然后找到插入位置，將插入位置前件的指針指向新結(jié)點(diǎn)，將新接點(diǎn)的指針指向插入位置后件的結(jié)點(diǎn)。（4）線性鏈表的刪除要從線性表中刪除一個(gè)元素，首先將要?jiǎng)h除元素的前后件兩個(gè)指針斷開，然后把要?jiǎng)h除結(jié)點(diǎn)的前件的指針，指向刪除結(jié)點(diǎn)后的數(shù)據(jù)元素。2循環(huán)鏈表循環(huán)

14、鏈表與單鏈表唯一的不同，就是最后一個(gè)結(jié)點(diǎn)的指針域中的值不同。單鏈表的最后一個(gè)結(jié)點(diǎn)的指針域存放的是一個(gè)空指針，而循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針域存放的是指向第一個(gè)結(jié)點(diǎn)的指針?？键c(diǎn) 6 樹與二叉樹1樹的基本概念樹是一種比較簡單的非線型結(jié)構(gòu)。在樹中所有的數(shù)據(jù)元素之間具有明顯的層次關(guān)系。之所以將這種數(shù)據(jù)結(jié)構(gòu)命名為“樹”，是因?yàn)槠浣Y(jié)構(gòu)看上去像一棵倒長著的樹。在樹的圖形表示中，上端的結(jié)點(diǎn)是前件，下端的結(jié)點(diǎn)是后件。2二叉樹及基本性質(zhì)（1）二叉樹二叉樹是一種特殊的樹，是一種很有用的非線型結(jié)構(gòu)。所有樹結(jié)構(gòu)上的術(shù)語都可以用在二叉樹上。二叉樹具有以下兩個(gè)特征： 非空二叉樹只有一個(gè)根結(jié)點(diǎn)； 每個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分

15、別稱為該結(jié)點(diǎn)的左子樹和右子樹。在二叉樹中，每個(gè)結(jié)點(diǎn)的度最大為 2，所有的左子樹和右子樹也均是二叉樹。同時(shí)，在二叉樹中所有的結(jié)點(diǎn)可以沒有左子樹，也可以沒有右子樹。即沒有左子樹又沒有右子樹的結(jié)點(diǎn)是葉子結(jié)點(diǎn)。（2）滿二叉樹所謂滿二叉樹是指：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即滿二叉樹的第 k 層上有 2k-1 個(gè)結(jié)點(diǎn)，且深度為m 的滿二叉樹有 2m-1 個(gè)結(jié)點(diǎn)。（3）完全二叉樹所謂的完全二叉樹是指：除最后一層外， 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，最后一層上只缺少右邊的若干個(gè)結(jié)點(diǎn)。完全二叉樹就是去掉最后一層若干個(gè)右邊結(jié)點(diǎn)的滿二叉樹。（4

16、）二叉樹的基本性質(zhì)二叉樹的基本性質(zhì)。二叉樹具有以下幾個(gè)基本性質(zhì)：性質(zhì) 1：在二叉樹的第 K 層上最多有 2k-1（k1）個(gè)結(jié)點(diǎn)。性質(zhì) 2：深度為 m 的二叉樹最多有 2m-1 個(gè)結(jié)點(diǎn)。性質(zhì) 3：在任意一棵二叉樹中，葉子結(jié)點(diǎn)（即度為0 的結(jié)點(diǎn)），總比度為 2 的結(jié)點(diǎn)多一個(gè)。性質(zhì) 4：具有 n 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1。完全二叉樹的兩項(xiàng)特性。完全二叉樹還具有以下兩項(xiàng)特性：性質(zhì) 5：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為log2n+1。性質(zhì) 6：設(shè)完全二叉樹共有 n 個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始， 按層序（每一層從左到右）用自然數(shù)“1,2,，n”給結(jié)點(diǎn)進(jìn)行編號(hào)。3二叉樹的遍歷二叉樹的遍

17、歷是指按照一定的順序訪問二叉樹中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只被訪問一次。為了保證所有結(jié)點(diǎn)被不重不漏地訪問，必須按照一定的順序進(jìn)行。（1）前序遍歷（DLR）首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子樹時(shí)，也按上述的順序執(zhí)行?？梢娗靶虮闅v二叉樹是一個(gè)遞歸的過程。對(duì)于二叉樹的前序遍歷，具有如下的規(guī)則：對(duì)于空的二叉樹，不進(jìn)行操作返回空值。對(duì)于非空的二叉樹的遍歷按下列順序執(zhí)行：訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹。（2）中序遍歷（LDR）首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；在遍歷左、右子樹時(shí)，也按上述的順序執(zhí)行。可見中序遍歷二叉樹也是一個(gè)遞歸的過程。對(duì)于二叉樹的中序遍歷，具有

18、的規(guī)則：對(duì)于空的二叉樹，不進(jìn)行操作返回空值。對(duì)于非空的二叉樹的遍歷按下列順序執(zhí)行：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。（3）后序遍歷（LRD）首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；在遍歷左、右子樹時(shí)，也按上述的順序執(zhí)行。可見后序遍歷二叉樹同樣也是一個(gè)遞歸的過程。對(duì)于二叉樹的后序遍歷，具有的規(guī)則：對(duì)于空的二叉樹，不進(jìn)行操作返回空值。對(duì)于非空的二叉樹的遍歷按下列順序執(zhí)行：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)?？键c(diǎn) 7 查找技術(shù)查找就是從給定的一個(gè)數(shù)據(jù)結(jié)構(gòu)中，找出指定的數(shù)據(jù)元素。本節(jié)中我們只學(xué)習(xí)對(duì)線性表的查找，常用的查找方法有順序查找和二分法查找。1順序查找順序查找的過程是：

19、從線性表的第一個(gè)元素開始，依次將線性表中的數(shù)據(jù)與要查找的數(shù)據(jù)進(jìn)行比較，如果找到了相等的數(shù)據(jù)，則查找成功， 停止向下查找；如果比較完了線性表中的所有數(shù)據(jù)元素，沒有找到相等的數(shù)據(jù)，則查找失敗。2二分法查找二分法查找又稱為折半查找，只能應(yīng)用于順序存儲(chǔ)的有序表。有序表是指線性表中的元素已經(jīng)按值非遞減（從整體上看是升序，但相鄰的元素的值可以相同）排列?？键c(diǎn) 8 排序技術(shù)排序就是將一組無序的數(shù)據(jù)按照一定的順序排列起來。本節(jié)中所指的順序是非遞減順序（整體上呈升序，但相鄰的數(shù)據(jù)可以相等），基本排序算法主要有交換類排序、插入類排序和選擇類排序 3 大類。1交換類排序交換排序就是借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序

20、的方法。常用的交換排序方法有冒泡排序和快速排序。（1）冒泡排序冒泡排序的過程簡單，它的基本思想是通過對(duì)相鄰元素進(jìn)行比較，并根據(jù)比較的結(jié)果交換位置，從而逐步由任意序列變?yōu)橛行蛐蛄?。過程是：先從頭往后掃描、然后從后往頭掃描、再重復(fù)上述過程（2）快速排序快速排序就是一種可以通過一次交換而消除多個(gè)逆序的排序方法，因此相對(duì)冒泡排序法而言，速度要快。2插入類排序插入排序，就是將無序序列中的各個(gè)元素依次插入到已經(jīng)排好序的線性表中。常用的插入排序的方法有簡單插入排序和希爾排序。（1）簡單插入排序簡單插入排序的方法是：在初始序列中， 將只包含第 1 個(gè)元素的子序列看成是一個(gè)有序序列，然后從第 2 個(gè)元素起，依次

21、將每個(gè)元素插入到前 1 個(gè)有序子序列中。（2）希爾排序希爾排序的基本思想是：將整個(gè)無序序列分割成若干個(gè)子序列，對(duì)每個(gè)子序列分別進(jìn)行簡單插入排序，最后再對(duì)全體元素進(jìn)行一次簡單插入排序。與簡單插入排序的子序列構(gòu)成方式不同，希爾排序是將原序列中相隔某個(gè)增量h 的元素構(gòu)成一個(gè)子序列。在排序過程中逐步減少這個(gè)增量，最后當(dāng) h 減到 1 時(shí)，進(jìn)行一次插入排序，排序就完成了。增量序列一般取 hi = n/2k (k=1,2,，log2n)，其中 n 為待排序序列的長度。希爾排序的效率與所選取的增量序列有關(guān)。通過希爾排序法對(duì)長度為 n 的線性表進(jìn)行排序，如果選取了上述增量序列，最壞情況下，需要比較的次數(shù)為 O

22、(n1.5)。3選擇類排序常用的選擇排序有兩種，簡單選擇排序和堆排序。（1）簡單選擇排序簡單選擇排序的基本步驟是：在一組n 個(gè)數(shù)據(jù)中選擇出最小值；若它不是這組數(shù)據(jù)中的第 1 個(gè)數(shù)據(jù)，則將它與這組數(shù)據(jù)中的第 1 個(gè)數(shù)據(jù)互換位置；對(duì)剩下的子表采用同樣的方法，直到子表空為止。（2）堆排序法在學(xué)習(xí)堆排序之前，我們先來看一下堆的定義，堆的定義如下：具有n 個(gè)元素的序列（h1，h2，hn），當(dāng)且僅當(dāng)滿足或（i=1，2， ，n/2）時(shí)稱之為堆。第 2 章 程序設(shè)計(jì)基礎(chǔ)考點(diǎn) 1 程序設(shè)計(jì)方法與風(fēng)格程序是一組計(jì)算機(jī)指令的集合，是程序設(shè)計(jì)的最終成果。程序設(shè)計(jì)方法所要做的工作是，如何對(duì)實(shí)際問題進(jìn)行抽象和歸納以及對(duì)程

23、序進(jìn)行編排，才能使程序的可讀性、穩(wěn)定性、可維護(hù)性、效率等更好。目前，主要有兩種程序設(shè)計(jì)方法：結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。1源程序文檔化符號(hào)名的命名：符號(hào)名的命名應(yīng)盡量表達(dá)一些實(shí)際意義，以增強(qiáng)程序的可讀性。程序注釋：良好的注釋能夠幫助讀者理解程序。注釋一般分為序言性注釋和功能性注釋，以給出程序的整體說明和程序的主要功能。序言性注釋一般位于每一個(gè)程序的開頭部分，它給出程序的整體說明；功能性注釋一般嵌在原程序之中。視覺組織：為使程序的結(jié)構(gòu)清晰明了， 可以在程序中利用空行、空格、縮進(jìn)等技巧使程序?qū)哟吻逦?數(shù)據(jù)說明的方法在編寫程序時(shí)，一定要注意數(shù)據(jù)說明的方法。為使程序中的數(shù)據(jù)說明易于理解和維護(hù)。

24、3語句的結(jié)構(gòu)程序的語句應(yīng)該簡單易懂，在編寫程序時(shí)，應(yīng)注重：每一行只寫一條語句。程序編寫優(yōu)先考慮清晰性。一般情況下，在編寫程序時(shí)， 要做到清晰第一，效率第二。首先要保證程序的正確性，然后再提高速度。避免使用臨時(shí)變量而使程序的可讀性下降。盡可能使用庫函數(shù)。避免不必要的轉(zhuǎn)移。利用信息隱蔽，保證每一個(gè)模塊的獨(dú)立性。避免使用復(fù)雜的條件嵌套語句。避免使用無條件轉(zhuǎn)移語句。盡量做到模塊功能單一化。不要修補(bǔ)不好的程序，要重新編寫。4輸入和輸出輸入和輸出的方式應(yīng)盡可能方便用戶的使用。系統(tǒng)能否讓用戶接受，往往取決于輸入和輸出的風(fēng)格?？键c(diǎn) 2 結(jié)構(gòu)化程序設(shè)計(jì)1結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)必須遵守模塊化、自頂向下

25、、逐步求精、限制使用 goto 語句的原則。2結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)與特點(diǎn)結(jié)構(gòu)化程序設(shè)計(jì)方法是一種程序設(shè)計(jì)的先進(jìn)方法。實(shí)事證明，在程序設(shè)計(jì)時(shí)，只要使用 3 種程序結(jié)構(gòu)就可以實(shí)現(xiàn)所有的結(jié)構(gòu)形式， 它們是順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。3結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用結(jié)構(gòu)化程序設(shè)計(jì)的效率較高，但是在實(shí)際設(shè)計(jì)程序時(shí)，應(yīng)要注意：使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。選用的控制結(jié)構(gòu)只允許有一個(gè)入口和一個(gè)出口。程序語句組成容易識(shí)別的語句序列塊，每塊只允許有一個(gè)入口和一個(gè)出口。復(fù)雜結(jié)構(gòu)的程序設(shè)計(jì)時(shí)，僅用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)。語言中所沒有的控制結(jié)構(gòu)，應(yīng)采用前后

26、一致的方法來模擬。嚴(yán)格控制 goto 語句的使用，但不是完全不能用。考點(diǎn) 3 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǎF(xiàn)在已經(jīng)發(fā)展為一種主流的軟件開發(fā)方法。它歷經(jīng)了多年的研究和發(fā)展，已經(jīng)日益成熟和完善，應(yīng)用也越來越深入和廣泛。1面向?qū)ο蠓椒ǖ奶攸c(diǎn)面向?qū)ο蟮某绦蛟O(shè)計(jì)，是在結(jié)構(gòu)化程序設(shè)計(jì)的基礎(chǔ)上，以更接近人們通常思維的方式來解決問題的一種全新的軟件開發(fā)技術(shù)。面向?qū)ο蟮某绦蛟O(shè)計(jì)以對(duì)象為核心，強(qiáng)調(diào)對(duì)象的“封裝性”“繼承性”“抽象性”和“多態(tài)性”。其本質(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識(shí)、理解和描述客觀事物。2面向?qū)ο蠓椒ǖ幕靖拍睿?）對(duì)象（object）面

27、向?qū)ο蠓椒ㄕJ(rèn)為：現(xiàn)實(shí)世界是由一系列的對(duì)象組成的。對(duì)象是現(xiàn)實(shí)世界中彼此相關(guān)并互通信息的實(shí)體。每個(gè)對(duì)象都包含了兩部分的內(nèi)容：描述對(duì)象狀態(tài)的數(shù)據(jù)和描述對(duì)象行為。對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。因此?面向?qū)ο蠓椒ㄖ械膶?duì)象是由描述該對(duì)象屬性的數(shù)據(jù)以及可以對(duì)這些數(shù)據(jù)施加的所有操作封裝在一起構(gòu)成的整體。對(duì)象可以做的操作表示它的動(dòng)態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)中，通常把對(duì)象的操作也稱為方法或服務(wù)。（2）類和實(shí)例類是具有共同屬性、共同方法的對(duì)象的集合，是關(guān)于對(duì)象的抽象描述，反應(yīng)屬于該對(duì)象類型的所有對(duì)象的性質(zhì)。（3）消息（Message）消息傳遞是對(duì)象間通信的手段，一個(gè)對(duì)象通過向另一對(duì)象發(fā)送信息來請(qǐng)求其

28、服務(wù)。消息機(jī)制統(tǒng)一了數(shù)據(jù)流和控制流，一個(gè)消息由下述3 部分組成：接收消息的對(duì)象名稱、消息名、零個(gè)或多個(gè)參數(shù)。（4）繼承（Inheritance）類的繼承：繼承廣義地說，是指能夠直接獲得已有的屬性和特征，而不必重復(fù)地定義。繼承的傳遞性：繼承具有傳遞性，如果類 A 繼承類 B，類 B 繼承類 C，則類 A 繼承類C。因此，一個(gè)類實(shí)際上繼承了它上層的全部基類特性，也就是說，屬于某類的對(duì)象除了具有該類定義的特性外，還具有該類上層全部基類定義的特性。單繼承：一個(gè)子類只有唯一的一個(gè)父類，這種繼承稱為單繼承。多重繼承：一個(gè)子類也可以有多個(gè)父類，它可以從多個(gè)父類中繼承特性。繼承的優(yōu)點(diǎn)：相似的對(duì)象可以共享程序代

29、碼和數(shù)據(jù)，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件修改維護(hù)。（5）多態(tài)性(Polymorphism)多態(tài)性：對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)可導(dǎo)致完全不同的行為，該現(xiàn)象稱為多態(tài)性。第 3 章軟件工程基礎(chǔ)考點(diǎn) 1 軟件工程基本概念1軟件的定義與特點(diǎn)（1）軟件的定義一般認(rèn)為計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合?？梢娷浖煞譃閮蓚€(gè)部分：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用相關(guān)的文檔。（2）軟件的特點(diǎn)計(jì)算機(jī)軟件具有如下的幾個(gè)特點(diǎn)：軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具

30、有抽象性；與硬件的生產(chǎn)不同，軟件沒有明顯的制作過程；軟件在使用期間不存在磨損、老化問題； 對(duì)硬件和環(huán)境具有依賴性；軟件復(fù)雜度高，成本昂貴；軟件開發(fā)涉及諸多的社會(huì)因素。（3）軟件的分類計(jì)算機(jī)軟件按功能可分為 3 類：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或稱為工具軟件）。2軟件危機(jī)和軟件工程軟件工程概念的出現(xiàn)源自軟件危機(jī)。（1）軟件危機(jī)“軟件危機(jī)”是 20 世紀(jì) 60 年代末以后出現(xiàn)的，其泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題。實(shí)際上，幾乎所有的軟件都不同程度地存在這些問題。隨著計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)用領(lǐng)域的擴(kuò)大，軟件已經(jīng)成為計(jì)算機(jī)科學(xué)發(fā)展的“瓶頸”。（2）軟件工程為了消除軟件危機(jī)，通過

31、認(rèn)真研究軟件危機(jī)的方法，認(rèn)識(shí)到軟件工程是使計(jì)算機(jī)軟件走向工程科學(xué)的途徑，逐步形成了軟件工程概念，開辟了工程學(xué)的新興領(lǐng)域軟件工程學(xué)。它是采用工程的概念、原理、技術(shù)和方法來開發(fā)與維護(hù)軟件，把經(jīng)過時(shí)間考驗(yàn)而證明正確的管理技術(shù)與當(dāng)前能夠得到的最好的技術(shù)方法結(jié)合起來，經(jīng)濟(jì)地開發(fā)出高質(zhì)量的軟件并有效地維護(hù)它。3軟件工程過程與軟件生命周期（1）軟件工程過程ISO 9000 定義：軟件工程過程是指把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。（2）軟件生命周期軟件生命周期是指軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的整個(gè)過程。也就是說，軟件產(chǎn)品從考慮其概念開始，到該軟件產(chǎn)品不能使用為止的整個(gè)時(shí)期都屬于軟件生

32、命周期。一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測試、交付使用以及維護(hù)等活動(dòng)。這些階段可以有重復(fù)，執(zhí)行時(shí)也可以有迭代。4軟件工程的目標(biāo)與原則（1）軟件工程的目標(biāo)軟件工程的目標(biāo)是：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。為實(shí)現(xiàn)軟件工程的目標(biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括軟件開發(fā)技術(shù)和軟件工程管理兩個(gè)方面。（2）軟件工程的原則為了達(dá)到上述的軟件工程目標(biāo)，在軟件開發(fā)過程中，必須遵循以下軟件工程的基本原則：抽象、確定性、模塊化、信息隱蔽、局部化、完備性、一致性、可驗(yàn)證性。5軟件開發(fā)工具與軟件開發(fā)

33、環(huán)境軟件工程技術(shù)鼓勵(lì)研制和采用各種先進(jìn)的軟件開發(fā)方法、工具和環(huán)境。工具和環(huán)境的使用進(jìn)一步提高了軟件的開發(fā)效率、維護(hù)效率和軟件質(zhì)量。（1）軟件開發(fā)工具軟件開發(fā)工具的發(fā)展是從單項(xiàng)工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境。（2）軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境或稱軟件工程環(huán)境是指全面支持軟件開發(fā)全過程的軟件工具的集合。計(jì)算機(jī)輔助軟件工程（CASE）是當(dāng)前軟件開發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。考點(diǎn) 2 軟件分析方法軟件開發(fā)方法是指軟件開發(fā)過程所遵循的方法和步驟，其目的在于有效地得到一些工作產(chǎn)品， 即滿足質(zhì)量要求的程序和文檔。軟件開發(fā)方法包括分析方法、設(shè)

34、計(jì)方法和程序設(shè)計(jì)方法。1需求分析與需求分析方法軟件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過程。需求分析的目標(biāo)是創(chuàng)建所需的數(shù)據(jù)模型、功能模型和控制模型。（1）需求分析的定義1997 年 IEEE 軟件工程標(biāo)準(zhǔn)詞匯表對(duì)需求分析定義如下：用戶解決問題或達(dá)到目標(biāo)所需的條件或功能；系統(tǒng)或系統(tǒng)部件要滿足合同、標(biāo)準(zhǔn)、規(guī)范或其他正式規(guī)定文檔所需具有的條件或功能；一種反映或所描述的條件或功能的文檔說明。（2）需求分析階段的工作需求分析階段的工作主要分為 4 個(gè)方面： 需求獲取、需求分析、編寫需求規(guī)格說明書、需求評(píng)審。（3）需求分析方法

35、常用的需求分析方法有兩種：結(jié)構(gòu)化分析方法。主要包括：面向數(shù)據(jù)結(jié)構(gòu)的 Jackson 方法（JSD），面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA），面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD）。面向?qū)ο蟮姆治龇椒ǎ∣OA）。從需求分析建立的模型的特性來分，需求分析方法又分為靜態(tài)分析方法和動(dòng)態(tài)分析方法。2結(jié)構(gòu)化分析方法（1）結(jié)構(gòu)化分析方法的基本概念結(jié)構(gòu)化分析方法是面向數(shù)據(jù)流、自頂向下、逐步求精、進(jìn)行需求分析的方法。該方法使用簡單易讀符號(hào)，根據(jù)軟件內(nèi)部數(shù)據(jù)傳遞、變換的關(guān)系，自頂向下、逐層分解，描繪出滿足要求的軟件模型。（2）結(jié)構(gòu)化分析的常用工具結(jié)構(gòu)化分析方法利用圖形等結(jié)構(gòu)化的描述方式表達(dá)需求，簡明易懂，用

36、它們形成需求說明書中的主要部分。這種方法所用的常用工具有：數(shù)據(jù)流圖、數(shù)據(jù)字典、判定樹和判定表。3軟件需求規(guī)格說明書軟件需求規(guī)格說明書（SRS）是需求分析階段得出的最主要的文檔。它通常用自然語言完整、準(zhǔn)確、具體地描述系統(tǒng)的數(shù)據(jù)要求、功能需求、性能需求、可靠性和可用性要求、出錯(cuò)處理需求、接口需求、約束、逆向需求以及將來可能提出的要求。軟件需求規(guī)格說明書的作用軟件需求規(guī)格說明書具有幾個(gè)作用：便于用戶、開發(fā)人員進(jìn)行理解和交流；反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)；作為確認(rèn)測試和驗(yàn)收的依據(jù)。軟件需求規(guī)格說明書的內(nèi)容軟件需求規(guī)格說明書是作為需求分析的一部分而制定的可交付文檔。軟件需求規(guī)格

37、說明書的特點(diǎn)軟件需求規(guī)格說明書是確保軟件質(zhì)量的有力措施，衡量軟件需求規(guī)格說明書質(zhì)量的標(biāo)準(zhǔn)：正確性、無歧義性、完整性、一致性、可理解性、可驗(yàn)證性、可修改性和可追蹤性。 考點(diǎn) 3 結(jié)構(gòu)化設(shè)計(jì)方法1軟件設(shè)計(jì)的基本概念（1）軟件設(shè)計(jì)的基礎(chǔ)軟件設(shè)計(jì)是一個(gè)把軟件需求轉(zhuǎn)化為軟件表示的過程，是軟件工程的重要階段。軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象、概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。（2）軟件設(shè)計(jì)的基本原理軟件設(shè)計(jì)應(yīng)遵循軟件工程的基本目標(biāo)和原則，建立適用于在軟件設(shè)計(jì)中應(yīng)該遵守的基本原理和軟件設(shè)計(jì)中的有關(guān)概念。模塊化、抽象、信息隱藏和局部化、模塊獨(dú)立性。（3）結(jié)構(gòu)化設(shè)計(jì)方法結(jié)構(gòu)

38、化設(shè)計(jì)方法是目前采用最為廣泛的一種軟件設(shè)計(jì)方法，其基本思想是將軟件設(shè)計(jì)成由相對(duì)獨(dú)立、單一功能的模塊組成的結(jié)構(gòu)2概要設(shè)計(jì)概要設(shè)計(jì)又稱為總體設(shè)計(jì)或初步設(shè)計(jì)。軟件概要設(shè)計(jì)的基本任務(wù)是：設(shè)計(jì)軟件的系統(tǒng)結(jié)構(gòu)。在需求分析階段， 已經(jīng)把系統(tǒng)分解成層次結(jié)構(gòu)，而在概要設(shè)計(jì)階段， 需要進(jìn)一步分解，劃分為模塊以及模塊的層次結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)。數(shù)據(jù)設(shè)計(jì)是實(shí)現(xiàn)需求定義和規(guī)格說明過程中提出的數(shù)據(jù)對(duì)象的邏輯表示。編寫概要設(shè)計(jì)文檔。在概要設(shè)計(jì)階段， 需要編寫的文檔有：概要設(shè)計(jì)說明書、數(shù)據(jù)庫設(shè)計(jì)說明書、集中測試計(jì)劃等。概要設(shè)計(jì)文檔評(píng)審。在概要設(shè)計(jì)中，對(duì)設(shè)計(jì)部分是否完整地實(shí)現(xiàn)了需求中規(guī)定的功能、性能等要求，設(shè)計(jì)方案的可行

39、性，關(guān)鍵的處理及內(nèi)外部接口定義正確性、有效性，各部分之間的一致性等都要進(jìn)行評(píng)審，以免在以后的設(shè)計(jì)中出現(xiàn)大的問題而返工。2概要設(shè)計(jì)工具結(jié)構(gòu)圖（SC），也稱程序結(jié)構(gòu)圖，是描述軟件結(jié)構(gòu)的圖形工具，是常用的軟件結(jié)構(gòu)設(shè)計(jì)工具。模塊用一個(gè)矩形表示，矩形內(nèi)注明模塊的功能和名字；箭頭或直線表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。常用的結(jié)構(gòu)圖有 4 種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。3面向數(shù)據(jù)流的設(shè)計(jì)方法在需求分析階段，主要是分析信息在系統(tǒng)中的加工和流動(dòng)情況。面向數(shù)據(jù)流的設(shè)計(jì)方法的目標(biāo)是給出設(shè)計(jì)軟件結(jié)構(gòu)的一個(gè)系統(tǒng)化的途徑。（1）數(shù)據(jù)流類型。典型的數(shù)

40、據(jù)流類型有兩種：變換型和事務(wù)型。（2）面向數(shù)據(jù)流設(shè)計(jì)方法的實(shí)施要點(diǎn)與設(shè)計(jì)過程。4設(shè)計(jì)的準(zhǔn)則通過大量設(shè)計(jì)實(shí)踐證明，以下設(shè)計(jì)準(zhǔn)則可以借鑒為設(shè)計(jì)的指導(dǎo)和對(duì)軟件結(jié)構(gòu)圖進(jìn)行優(yōu)化。提高模塊獨(dú)立性、模塊規(guī)模適中、深度、寬度、扇出和扇入適當(dāng)、使模塊的作用域在該模塊的控制域內(nèi)、應(yīng)減少模塊的接口和界面的復(fù)雜性、設(shè)計(jì)成單入口、單出口的模塊和設(shè)計(jì)功能可預(yù)測的模塊。3詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)的任務(wù)就是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常用的設(shè)計(jì)工具有以下幾種：（1）圖形工具程序流程圖：程序流程圖是軟件過程的設(shè)計(jì)表示工具，表達(dá)直觀、清晰，易于學(xué)習(xí)和掌握。N-S 圖

41、：NS 圖是用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖的技術(shù)?；緢D形有 5 種。PAD 圖： PAD 圖即問題分析圖（ Problem Analysis Diagram）。它是繼程序流程圖和方框圖之后，提出的又一種描述軟件詳細(xì)設(shè)計(jì)的圖形工具?；緢D形有 5 種。（2）表格工具用表格來描述處理動(dòng)作及相應(yīng)的各種條件或描述輸入、處理、輸出的過程。（3）語言工具用與程序設(shè)計(jì)語言很相近的偽碼描述處理過程的細(xì)節(jié)。過程設(shè)計(jì)語言（PDL）也稱為結(jié)構(gòu)化的英語和偽碼，它是一種混合語言，采用英語的詞匯和結(jié)構(gòu)化程序設(shè)計(jì)語言的語法，類似編程語言?？键c(diǎn) 4 軟件測試軟件測試就是在軟件投入運(yùn)行之前，盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤。它是對(duì)

42、軟件規(guī)格說明、設(shè)計(jì)和編碼的最后復(fù)審。通常，軟件測試的工作量往往占軟件開發(fā)總工作量的40%以上。1軟件測試的目的軟測試的目的：測試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程；一個(gè)好的測試用例是指很可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例；一個(gè)成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測試；測試是要以查找錯(cuò)誤為中心，而不是為了演示軟件的正確功能。2軟件測試的準(zhǔn)則要作好軟件測試，必須設(shè)計(jì)有效的測試方案和好的測試用例。3軟件測試技術(shù)和方法軟件測試的方法是多種多樣的。若從是否需要執(zhí)行被測軟件的角度劃分，可以分為靜態(tài)測試和動(dòng)態(tài)測試；若按照功能劃分，可以分為白盒測試和黑盒測試。（1）靜態(tài)測試與動(dòng)態(tài)測試靜態(tài)測試：靜態(tài)測試包括代碼

43、檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。靜態(tài)測試主要由人工進(jìn)行，充分發(fā)揮人的邏輯思維優(yōu)勢，也可以借助軟件工具自動(dòng)進(jìn)行。動(dòng)態(tài)測試：動(dòng)態(tài)測試是基于計(jì)算機(jī)的測試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。（2）白盒測試與測試用例設(shè)計(jì)白盒測試的方法也稱結(jié)構(gòu)測試或邏輯測試。它是根據(jù)軟件的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作是否符合設(shè)計(jì)要求。白盒測試允許測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息來設(shè)計(jì)和選擇測試用例，對(duì)程序所有的邏輯路徑進(jìn)行測試。邏輯覆蓋測試。邏輯覆蓋測試泛指以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計(jì)書。從覆蓋源程序語句的詳盡程度分析，大致有以下一些不同的覆蓋標(biāo)準(zhǔn)：語句覆蓋、判定覆蓋、條件覆蓋、判

44、斷-條件覆蓋?；韭窂綔y試?；韭窂綔y試的思想和步驟是，根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測試用例對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測試。（3）黑盒測試與測試用例設(shè)計(jì)黑盒測試也稱功能測試或數(shù)據(jù)驅(qū)動(dòng)測試， 是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測試和驗(yàn)證。所以，黑盒測試的測試用例是根據(jù)程序的外部功能進(jìn)行設(shè)計(jì)的，在軟件接口處進(jìn)行，完成功能驗(yàn)證。4軟件測試的實(shí)施軟件測試是保證軟件質(zhì)量的重要手段。為使軟件測試工作系統(tǒng)化，我們應(yīng)制定測試流程。所謂測試流程就是軟件測試這個(gè)過程規(guī)定的程序。軟件測試過程一般按 4 個(gè)步驟進(jìn)行，即單元測試、集成測試、驗(yàn)收測試（

45、確認(rèn)測試）和系統(tǒng)測試?？键c(diǎn) 5 程序的調(diào)試1基本概念在對(duì)程序進(jìn)行了成功的測試之后將進(jìn)入程序調(diào)試（通常稱 Debug，即排錯(cuò)）。程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。（1）程序調(diào)試的基本步驟錯(cuò)誤定位：從錯(cuò)誤的外部表現(xiàn)形式入手，研究有關(guān)部分的程序，確定程序中出錯(cuò)位置，找出錯(cuò)誤的內(nèi)在原因。修改設(shè)計(jì)和代碼，以排除錯(cuò)誤： 排錯(cuò)是軟件開發(fā)過程中一項(xiàng)艱苦的工作，這也決定了調(diào)試工作是一個(gè)具有很強(qiáng)技術(shù)性和技巧性的工作。進(jìn)行回歸測試，防止引進(jìn)新的錯(cuò)誤：重復(fù)進(jìn)行暴露這個(gè)錯(cuò)誤的原始測試或某些有關(guān)測試，以確認(rèn)該錯(cuò)誤是否被排除、是否引進(jìn)了新的錯(cuò)誤。（2）程序調(diào)試的原則調(diào)試活動(dòng)由對(duì)程序中錯(cuò)誤的定性、定位和排錯(cuò)兩部分組成，

46、因此調(diào)試原則也從確定錯(cuò)誤的性質(zhì)和位置時(shí)的注意事項(xiàng)和修改錯(cuò)誤的原則兩個(gè)方面考慮。2軟件測試方法調(diào)試的關(guān)鍵在于推斷程序內(nèi)部的錯(cuò)誤位置及原因。軟件調(diào)試可以分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。軟件測試中討論的靜態(tài)分析方法同樣適用靜態(tài)調(diào)試。靜態(tài)調(diào)試主要指通過人的思維來分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試的。主要的調(diào)試方法有強(qiáng)行排錯(cuò)法、回溯法和原因排除法。第 4 章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)考點(diǎn) 1 數(shù)據(jù)庫系統(tǒng)的基本概念1數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)（1）數(shù)據(jù)數(shù)據(jù)：描述事物的符號(hào)記錄。計(jì)算機(jī)中的數(shù)據(jù)一般分成兩部分，其中一部分與程序僅有短時(shí)間的交互關(guān)系，隨著程序的結(jié)束而消亡，這樣的數(shù)據(jù)稱為臨時(shí)性數(shù)據(jù)，

47、 一般存放在計(jì)算機(jī)內(nèi)存中；而另一部分?jǐn)?shù)據(jù)則對(duì)系統(tǒng)起著長期持久的作用，這樣的數(shù)據(jù)稱為持久性數(shù)據(jù)，一般存放在計(jì)算機(jī)的長期存儲(chǔ)設(shè)備（如硬盤）中。數(shù)據(jù)庫系統(tǒng)中處理的就是這種持久性數(shù)據(jù)。（2）數(shù)據(jù)庫數(shù)據(jù)庫：數(shù)據(jù)庫（DataBase，DB）是指長期存儲(chǔ)在計(jì)算機(jī)內(nèi)的、具有統(tǒng)一的結(jié)構(gòu)形式、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲(chǔ)，具有較小的冗余度、較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性，并可為各種應(yīng)用程序所共享。（3）數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)： 數(shù)據(jù)庫管理系統(tǒng)（DataBase Management System， DBMS）是管理數(shù)據(jù)庫的機(jī)構(gòu)，是一個(gè)系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱

48、、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心，其主要功能包括幾個(gè)方面：數(shù)據(jù)模式定義、數(shù)據(jù)存取的物理構(gòu)建、數(shù)據(jù)操縱、數(shù)據(jù)的完整性、安全性定義與檢查、數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)和數(shù)據(jù)的服務(wù)。（4）數(shù)據(jù)庫管理員數(shù)據(jù)庫管理員：對(duì)數(shù)據(jù)庫的規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等進(jìn)行管理的人員，稱為數(shù)據(jù)庫管理員。其主要工作：數(shù)據(jù)庫設(shè)計(jì)、數(shù)據(jù)庫維護(hù)和改善系統(tǒng)性能。（5）數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)（DBS）是指引入數(shù)據(jù)庫后的計(jì)算機(jī)系統(tǒng)，一般由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理員和用戶構(gòu)成。（6）數(shù)據(jù)庫應(yīng)用系統(tǒng)數(shù)據(jù)庫應(yīng)用系統(tǒng)（DBAS）是數(shù)據(jù)庫系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面這三者所組成，具體包括：數(shù)據(jù)

49、庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺(tái)、軟件平臺(tái)、應(yīng)用軟件、應(yīng)用界面。2數(shù)據(jù)庫系統(tǒng)的發(fā)展數(shù)據(jù)管理發(fā)展到今經(jīng)歷了：人工管理、文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng) 3 個(gè)階段。其中數(shù)據(jù)獨(dú)立性最高的是數(shù)據(jù)庫系統(tǒng)，這里的數(shù)據(jù)獨(dú)立性指的是數(shù)據(jù)庫和應(yīng)用程序的相互獨(dú)立。（1）文件系統(tǒng)階段文件系統(tǒng)是數(shù)據(jù)庫系統(tǒng)發(fā)展的初級(jí)階段， 它提供了簡單的數(shù)據(jù)共享和數(shù)據(jù)管理能力，但是它無法提供完整統(tǒng)一的管理和數(shù)據(jù)共享的能力。（2）層次與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段從 20 世紀(jì) 60 年代末起，真正的數(shù)據(jù)庫系統(tǒng)層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫開始發(fā)展， 它們?yōu)榻y(tǒng)一管理與共享數(shù)據(jù)提供了大力支撐。但是這兩個(gè)系統(tǒng)也存在不足，主要是其脫胎與文件系統(tǒng)，受文件的物理影

50、響較大，對(duì)數(shù)據(jù)庫使用帶來的諸多不便，同時(shí)，此類系統(tǒng)的數(shù)據(jù)模式構(gòu)造繁瑣不宜于推廣。（3）關(guān)系數(shù)據(jù)庫系統(tǒng)階段關(guān)系數(shù)據(jù)庫系統(tǒng)結(jié)構(gòu)簡單、使用方便、邏輯性強(qiáng)、物理性少。在數(shù)據(jù)庫的儲(chǔ)多新技術(shù)中，下面 3 種是比較重要的：面向?qū)ο髷?shù)據(jù)庫系統(tǒng)、知識(shí)庫系統(tǒng)和關(guān)系數(shù)據(jù)庫系統(tǒng)的擴(kuò)充。3數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)數(shù)據(jù)庫技術(shù)是在文件系統(tǒng)基礎(chǔ)上發(fā)展產(chǎn)生的，兩者都以數(shù)據(jù)文件的形式組織數(shù)據(jù)，但由于數(shù)據(jù)庫系統(tǒng)在文件系統(tǒng)之上加入 DBMS 對(duì)數(shù)據(jù)進(jìn)行管理，從而使得數(shù)據(jù)庫系統(tǒng)具有以下特點(diǎn)。（1）數(shù)據(jù)的高集成性數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)高集成性主要表現(xiàn)在如下幾個(gè)方面：在數(shù)據(jù)庫系統(tǒng)中采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)方式，如在數(shù)據(jù)庫中采用二維表作為統(tǒng)一結(jié)構(gòu)方式。在數(shù)

51、據(jù)庫系統(tǒng)中按照多個(gè)應(yīng)用的需要組織全局統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)（即數(shù)據(jù)模式），數(shù)據(jù)模式不僅可以建立全局的數(shù)據(jù)結(jié)構(gòu)，還可以建立數(shù)據(jù)間的語義聯(lián)系，從而構(gòu)成一個(gè)內(nèi)在緊密聯(lián)系的數(shù)據(jù)整體。數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)模式是多個(gè)應(yīng)用共同的、全局的數(shù)據(jù)結(jié)構(gòu)，而每個(gè)應(yīng)用的數(shù)據(jù)則是全局結(jié)構(gòu)中的一部分，稱為局部結(jié)構(gòu)（即視圖），這種全局與局部的結(jié)構(gòu)模式構(gòu)成了數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)集成性的主要特征。（2）數(shù)據(jù)的高共享性與低冗余性由于數(shù)據(jù)的集成性使得數(shù)據(jù)可為多個(gè)應(yīng)用所共享。數(shù)據(jù)共享的使用大大減少數(shù)據(jù)冗余，節(jié)約存儲(chǔ)空間。減少冗余性以避免數(shù)據(jù)的不同出現(xiàn)是保證系統(tǒng)一致性的基礎(chǔ)。（3）數(shù)據(jù)高獨(dú)立性數(shù)據(jù)獨(dú)立性是指數(shù)據(jù)與程序間的互不依賴性，是數(shù)據(jù)庫中常用的術(shù)語

52、。其包括數(shù)據(jù)的物理獨(dú)立性和數(shù)據(jù)的邏輯獨(dú)立性。（4）數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)庫系統(tǒng)不僅為數(shù)據(jù)提供高度集成環(huán)境， 同時(shí)它還為數(shù)據(jù)提供操作功能，這主要包含以下3 個(gè)方面：數(shù)據(jù)的完整性檢查、數(shù)據(jù)的安全性保護(hù)、并發(fā)控制。4數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)系統(tǒng)數(shù)據(jù)庫系統(tǒng)在其內(nèi)部具有三級(jí)模式和二級(jí)映射，三級(jí)模式分別是外模式、概念模式與內(nèi)模式。二級(jí)映射則分別是，外模式概念模式映射和概念模式內(nèi)模式映射。這種三級(jí)模式與二級(jí)映射構(gòu)成了數(shù)據(jù)庫系統(tǒng)內(nèi)部的抽象結(jié)構(gòu)體系。（1）數(shù)據(jù)庫系統(tǒng)的三級(jí)模式數(shù)據(jù)模式是數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式，它具有不同的層次與結(jié)構(gòu)方式：外模式也稱子模式或用戶模式。它能夠看見和使用局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征

53、的描述，它是用戶的數(shù)據(jù)視圖，一個(gè)數(shù)據(jù)庫可以有多個(gè)外模式。概念模式是數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。一個(gè)數(shù)據(jù)庫只有一個(gè)概念模式。內(nèi)模式又稱物理模式，一個(gè)數(shù)據(jù)庫只有一個(gè)內(nèi)模式。它是數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述， 是數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式。（2）數(shù)據(jù)庫系統(tǒng)的兩級(jí)映射數(shù)據(jù)庫系統(tǒng)的三級(jí)模式是對(duì)數(shù)據(jù)的 3 個(gè)級(jí)別的抽象，它把數(shù)據(jù)具體物理實(shí)現(xiàn)留給物理模式，使用戶能邏輯地、抽象地處理數(shù)據(jù)，而不必關(guān)心數(shù)據(jù)在計(jì)算機(jī)中的具體表示方式和存儲(chǔ)方式。考點(diǎn) 2 數(shù)據(jù)庫系統(tǒng)的基本概念1數(shù)據(jù)模型的基本概念數(shù)據(jù)模型（Data Model）研究的就是數(shù)據(jù)的組織形式及方式。數(shù)據(jù)庫是某個(gè)企業(yè)、組

54、織或部門所涉及的數(shù)據(jù)的綜合，它不僅要反映數(shù)據(jù)本身的內(nèi)容，而且要反映數(shù)據(jù)之間的聯(lián)系。數(shù)據(jù)模型通常由數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和完整性約束 3 部分組成。（1）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是所研究的對(duì)象類型的集合。數(shù)據(jù)結(jié)構(gòu)是對(duì)系統(tǒng)靜態(tài)特征的描述。（2）數(shù)據(jù)操作數(shù)據(jù)操作是指對(duì)數(shù)據(jù)庫中各種對(duì)象的實(shí)例允許執(zhí)行的操作的集合，包括操作及有關(guān)的操作規(guī)則。數(shù)據(jù)操作是對(duì)系統(tǒng)動(dòng)態(tài)特征的描述。（3）數(shù)據(jù)的約束條件數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的約束和依存規(guī)則，用以限定符合數(shù)據(jù)模型的數(shù)據(jù)庫狀態(tài)以及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效、相容。2數(shù)據(jù)模型的分類數(shù)據(jù)模型按不同的應(yīng)用層次分成 3

55、 種類型，它們是概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。（1）概念數(shù)據(jù)模型概念數(shù)據(jù)模型簡稱概念模型，它是一種面向客觀世界、面向用戶的模型；它與具體的數(shù)據(jù)庫管理系統(tǒng)無關(guān)，與具體的計(jì)算機(jī)平臺(tái)無關(guān)。概念模型是整個(gè)數(shù)據(jù)模型的基礎(chǔ)。（2）邏輯數(shù)據(jù)模型邏輯數(shù)據(jù)模型又稱數(shù)據(jù)模型，它是一種面向數(shù)據(jù)庫系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫系統(tǒng)一級(jí)的實(shí)現(xiàn)。目前，數(shù)據(jù)庫領(lǐng)域中最常用的邏輯數(shù)據(jù)模型有四種，分別為：層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ?。?）物理數(shù)據(jù)模型物理數(shù)據(jù)模型又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。3E-R 模型概念模型是面向現(xiàn)實(shí)世界，它的出發(fā)點(diǎn)是有效和自然地模擬現(xiàn)實(shí)世界，給出數(shù)據(jù)的概念化結(jié)構(gòu)。它的表示方法很多，其中最著名是 ER 模型（或?qū)嶓w聯(lián)系模型），它于 1976 年由 Peter Chen 首先提出。（1）E-R 模型的基本概念實(shí)體是客觀存在并可相互區(qū)別的事物。實(shí)體可以是具體的人、事、物，也可以是抽象的概念或聯(lián)系。屬性是實(shí)體所具有的某一特性。一個(gè)實(shí)體可由若干個(gè)屬性來刻畫。碼是能夠唯一標(biāo)識(shí)實(shí)體的屬性集。屬性的取值范圍稱為該屬性的域。用實(shí)體名及其屬性名集合來抽象和刻畫同類實(shí)體，稱為實(shí)體型。同型實(shí)體的集合稱為實(shí)體集。例如，全體學(xué)生就是一個(gè)實(shí)體集。在現(xiàn)實(shí)世界中，