二級(jí)公共基礎(chǔ)知識(shí)培訓(xùn)課件

全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)1第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱 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.樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱2知識(shí)點(diǎn)歸納算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。嚴(yán)格來說，一個(gè)算法必須具有以下五個(gè)主要特征：可行性確定性有窮性輸入輸出綜上，所謂算法，是一組嚴(yán)格定義運(yùn)算順序的規(guī)則，而且每一個(gè)規(guī)則都是有效且明確的，此順序?qū)⒃谟邢薜拇螖?shù)終止。知識(shí)點(diǎn)歸納算法的基本概念3算法的基本概念算法的組成要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法的控制結(jié)構(gòu)算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸減半遞推回溯法算法的基本概念算法的組成要素4算法的復(fù)雜度算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量算法優(yōu)劣的量度。1.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)。算法的時(shí)間量度記作：T(n)=O(f(n))，表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱為算法的(漸進(jìn))時(shí)間復(fù)雜度。算法的復(fù)雜度算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量5算法的復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？

任何一個(gè)算法都是由一個(gè)“控制結(jié)構(gòu)”和若干“原操作”組成的，因此一個(gè)算法的執(zhí)行時(shí)間可以看成是所有原操作的執(zhí)行時(shí)間之和

∑(原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間)

則算法的執(zhí)行時(shí)間與所有原操作的執(zhí)行次數(shù)之和成正比。從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法時(shí)間復(fù)雜度的依據(jù)。這種衡量效率的辦法所得出的不是時(shí)間量，而是一種增長趨勢(shì)的量度。它與軟硬件環(huán)境無關(guān)，只暴露算法本身執(zhí)行效率的優(yōu)劣。

算法的復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？

任何一個(gè)算法都6算法的復(fù)雜度算法的空間復(fù)雜度算法的空間負(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?？臻g復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作：S(n)=O(g(n))，其中n為問題的規(guī)模，表示隨問題規(guī)模的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。算法的復(fù)雜度算法的空間復(fù)雜度7數(shù)據(jù)結(jié)構(gòu)利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)8數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容是指在存儲(chǔ)空間中使用一個(gè)存儲(chǔ)結(jié)點(diǎn)來存儲(chǔ)一個(gè)數(shù)據(jù)元素，在存儲(chǔ)空間中建立各存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)，來表示數(shù)據(jù)元素之間的邏輯關(guān)系。常見的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器10線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表、棧、隊(duì)列、線性鏈表等）在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)（樹、二叉樹和圖等）非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹和圖都屬于非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表、棧、隊(duì)列、線性鏈表等）11線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：

(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個(gè)數(shù)n定義為線性表的表長；n=0時(shí)的線性表被稱為空表。稱i為ai在線性表中的位序。線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：12線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元13線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加一個(gè)新結(jié)點(diǎn)。一般情況下，要在第i(1≤i≤n)個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入到第i項(xiàng)。刪除運(yùn)算是指撤銷結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)。一般情況，要?jiǎng)h除第i(1≤i≤n)個(gè)元素，要從第i+1個(gè)元素開始，直到第n個(gè)元素，共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加14棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進(jìn)先出的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和15棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。棧的操作入棧：在棧頂位置插入一個(gè)新元素，棧頂指針top加1。退棧：取出棧頂元素并賦值給一個(gè)指定的變量，棧頂指針top減1。取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間16棧如果某棧的入棧順序是ABCDEF，則出棧順序不可能是哪個(gè)（）A、DCEFBAB、ABCDEFC、EDFCABD、CBAEDF棧如果某棧的入棧順序是ABCDEF，則出棧順序不可能是哪個(gè)（17隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱為退隊(duì)。隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(18循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。循環(huán)隊(duì)列初始狀態(tài)為空，即front=rear=m。入隊(duì)操作時(shí)，rear加1，若rear=m+1，則置rear=1；退隊(duì)操作時(shí)，front加1，若front=m+1，則置front=1。在循環(huán)隊(duì)列為空或?yàn)闈M時(shí)，均有front=rear，因此需要設(shè)置標(biāo)志s進(jìn)行區(qū)分，定義s=0表示隊(duì)列為空，s=1表示隊(duì)列非空。循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏19單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以連續(xù)，也可以不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需要存儲(chǔ)其后繼元素的存儲(chǔ)位置信息(指針域)。指針域中存儲(chǔ)的信息稱為指針或鏈，N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于結(jié)點(diǎn)中只包含一個(gè)指針域，故稱為單鏈表。單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以20單鏈表通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的地址，稱為頭指針。整個(gè)鏈表的存儲(chǔ)必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，其指針域?yàn)榭?。單鏈表通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的21單鏈表的插入和刪除單鏈表的插入和刪除22雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。HEAD…∧…∧HEAD…HEAD雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)23樹及其基本概念樹是一種簡單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹，并且稱為根的子樹。集合為空的樹簡稱為空樹；樹中的元素稱為結(jié)點(diǎn)。樹及其基本概念樹是一種簡單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元24樹的主要術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。葉節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。雙親、孩子和兄弟：結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱為兄弟。層次：結(jié)點(diǎn)的層次從根開始定義，根為第一層，根的孩子為第二層。深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。樹的主要術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。25二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。二叉樹是另一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或26二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）性質(zhì)3對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則：n0=n2+1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-127滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(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)。完全二叉樹除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為[log2n]+1。從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹

ADCBEF滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)28二叉樹的基本性質(zhì)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[log2n]+1）的結(jié)點(diǎn)按層序（從第1層到第[log2n]+1層，每層從左到右）從1起開始編號(hào)，則對(duì)任一編號(hào)為i的結(jié)點(diǎn)(1≤i≤n)，則:

(1)如果i=1，則編號(hào)為i的結(jié)點(diǎn)是二叉樹的根，無雙親；如果i>1，則其雙親結(jié)點(diǎn)parent(i)的編號(hào)是[i/2]。

(2)如果2i>n，則編號(hào)為i的結(jié)點(diǎn)無左孩子（編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編號(hào)是2i。

(3)如果2i+1>n，則編號(hào)為i的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)的編號(hào)是結(jié)點(diǎn)2i+1。

二叉樹的基本性質(zhì)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉29二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲(chǔ)左右子樹根節(jié)點(diǎn)的存儲(chǔ)位置，即指針。L(i)V(i)R(i)LchildvalueRchild二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三30二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)31二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由"根結(jié)點(diǎn)"、"左子樹"和"右子樹"三部分構(gòu)成，則遍歷二叉樹的操作可分解為"訪問根結(jié)點(diǎn)"、"遍歷左子樹"和"遍歷右子樹"三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進(jìn)行。

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二32二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA二叉樹的遍歷先序遍歷：ABDEGHCFIJ33二叉樹的遍歷如果一棵樹的先序遍歷序列是ABDEGHCFIJ，中序遍歷序列是DBGEHACIJF，畫出這棵樹并寫出后序序列。如果一棵樹的中序遍歷序列是BDACFE后序遍歷序列是DBFECA二叉樹的遍歷如果一棵樹的先序遍歷序列是ABDEGHCFIJ，34二叉樹的遍歷1、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是A

B

D

G

C

E

F

H，中序遍歷的結(jié)點(diǎn)訪問順序是D

G

B

A

E

C

H

F，則后序遍歷的結(jié)點(diǎn)訪問順序是：2、已知一棵二叉樹的中根序列和后根序列分別為B

D

C

E

A

F

H

G和D

E

C

B

H

G

F

A，試畫出這棵二叉樹。

二叉樹的遍歷1、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是A

B

D

35二叉樹的遍歷二叉樹的遍歷36查找查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。順序查找順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都必須使用順序查找。如果線性表有序，但采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則也必須使用順序查找。查找查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。37查找二分查找(折半查找)二分查找法只適用于順序存儲(chǔ)的有序表。先確定待查目標(biāo)元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當(dāng)查找區(qū)間縮小到0也沒有找到目標(biāo)元素為止。查找過程中，給定值首先和處于待查區(qū)間"中間位置"的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到"前半個(gè)區(qū)間"或"后半個(gè)區(qū)間"之后繼續(xù)進(jìn)行查找。查找二分查找(折半查找)38折半查找二分查找折半查找二分查找39排序 排序是指將一個(gè)無序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲(chǔ)的線性表為排序?qū)ο螅诔绦蛟O(shè)計(jì)語言中就是一維數(shù)組。排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。排序 排序是指將一個(gè)無序序列整理成按值遞增或遞減(本章均采用40快速排序基本思想：從線性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移動(dòng)到前面，將前面大于T的元素移動(dòng)到后面，將線性表分為兩個(gè)部分(子表)，T放到分界線的位置，這個(gè)過程稱為線性表的分割，通過一次分割，就以T為分界將線性表分為兩個(gè)子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原則對(duì)子表繼續(xù)進(jìn)行分割，直到子表為空，則整個(gè)線性表有序?？焖倥判蚧舅枷耄簭木€性表中選取一個(gè)元素，設(shè)為T，將線性表后413168459023395412877631暫存樞軸記錄T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割過程313168459023395412877631暫存樞軸記錄T：42第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱43知識(shí)點(diǎn)歸納程序設(shè)計(jì)方法程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、方法和工具來支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。在程序設(shè)計(jì)中，通常采用“自頂向下，逐步求精”的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語言編寫的程序。知識(shí)點(diǎn)歸納程序設(shè)計(jì)方法44程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良好的程序設(shè)計(jì)風(fēng)格概括起來包括以下及格方面：源程序文檔化數(shù)據(jù)說明的方法語句的結(jié)構(gòu)輸入和輸出程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常45程序設(shè)計(jì)風(fēng)格源程序文檔化標(biāo)識(shí)符的命名程序的注釋序言性注釋功能性注釋程序的視覺組織數(shù)據(jù)的說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化說明語句中變量的安排有序化使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)風(fēng)格源程序文檔化46程序設(shè)計(jì)風(fēng)格語句結(jié)構(gòu)在一行內(nèi)只寫一條語句程序編寫應(yīng)優(yōu)先考慮清晰性除非對(duì)效率有特殊要求，程序編寫要做到清晰第一，效率第二首先要保證程序正確，然后才要求提高速度避免使用臨時(shí)變量而使程序的可讀性下降避免不必要的轉(zhuǎn)移盡可能使用庫函數(shù)避免使用復(fù)雜的條件語句盡量減少使用“否定”條件的條件語句數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化要模塊化，使模塊功能盡可能單一化利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性從數(shù)據(jù)出發(fā)構(gòu)造程序不要修補(bǔ)不好的程序，要重寫編寫程序設(shè)計(jì)風(fēng)格語句結(jié)構(gòu)47程序設(shè)計(jì)風(fēng)格輸入和輸出對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性檢查輸入項(xiàng)的各種重要組合的合法性輸入格式要簡單，以使輸入的步驟和操作盡可能簡單輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式應(yīng)允許缺省值輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。程序設(shè)計(jì)風(fēng)格輸入和輸出48結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。逐步求精。對(duì)復(fù)雜的問題，應(yīng)設(shè)計(jì)一些子目標(biāo)過渡，逐步細(xì)化。模塊化。一個(gè)復(fù)雜問題肯定是有若干簡單問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。嚴(yán)格限制GOTO語句的使用。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則49結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，并且具有如下特點(diǎn)：單入口、單出口、結(jié)構(gòu)中無死循環(huán)，程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一50面向?qū)ο蟪绦蛟O(shè)計(jì)

面向?qū)ο蠓椒ǖ幕靖拍?.對(duì)象、類和屬性在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問題域中某個(gè)實(shí)體的抽象。每個(gè)對(duì)象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義。類是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，描述了屬于該類的所有對(duì)象的性質(zhì)。2.方法方法有稱為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可為其他對(duì)象使用。面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ幕靖拍?1面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方法的一個(gè)重要特征。指一個(gè)類(子類)直接使用另一個(gè)類(父類)的所有屬性和方法。它可以減少相似類的重復(fù)說明，從而體現(xiàn)一般性和特殊性的原則。4.多態(tài)性：多態(tài)性可以用“一個(gè)對(duì)外界面，多個(gè)內(nèi)部實(shí)現(xiàn)”來表示?？梢酝ㄟ^方法重載和方法重寫來實(shí)現(xiàn)多態(tài)。重載指一個(gè)類中可以有多個(gè)具有相同名稱的方法，由傳遞給它們的不同個(gè)數(shù)和類型的參數(shù)來決定執(zhí)行那個(gè)方法。重寫指子類可以重新實(shí)現(xiàn)父類的某些方法，使其具有自己的特征。多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，提高了軟件的可重用性和可擴(kuò)充性。5.消息：面向?qū)ο笙到y(tǒng)中的對(duì)象之間是通過消息機(jī)制彼此相互合作的，消息是一個(gè)對(duì)象與另一個(gè)對(duì)象之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息。面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方法的一個(gè)重要特征52面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護(hù)性好面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象53第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

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)試。

第三章軟件工程基礎(chǔ)考試大綱54知識(shí)點(diǎn)歸納軟件定義和特點(diǎn)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。計(jì)算機(jī)軟件具有如下特點(diǎn)：軟件是一種邏輯實(shí)體，具有抽象性軟件生產(chǎn)沒有明顯的制造過程軟件在運(yùn)行、使用期間不存在磨損、老化問題軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性軟件復(fù)雜性高，成本昂貴軟件開發(fā)涉及諸多社會(huì)因素知識(shí)點(diǎn)歸納軟件定義和特點(diǎn)55軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題，包括：軟件需求的增長得不到滿足軟件開發(fā)成本和進(jìn)度無法控制軟件質(zhì)量難以保證軟件不可維護(hù)或可維護(hù)性低軟件成本不斷提高軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長。軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的56軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于計(jì)算機(jī)軟件定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的三要素方法工具過程軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于57軟件工程過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。它包括兩方面含義：1.軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動(dòng)。通常包括四種基本活動(dòng)：P(Plan)：軟件規(guī)格說明D(Do)：軟件開發(fā)C(Check)：軟件確認(rèn)A(Action)：軟件演進(jìn)2.從軟件開發(fā)的觀點(diǎn)看，軟件工程過程是使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，在活動(dòng)結(jié)束時(shí)將輸入(用戶需求)轉(zhuǎn)化為輸出(軟件產(chǎn)品)。軟件工程過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資58軟件生命周期軟件從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用的過程稱為軟件的生命周期。一般包括以下幾個(gè)階段：可行性研究與計(jì)劃制定需求分析軟件設(shè)計(jì)軟件實(shí)現(xiàn)軟件測(cè)試運(yùn)行和維護(hù)軟件生命周期軟件從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用的過程稱為59軟件工程目標(biāo)與原則軟件工程的目標(biāo)是在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產(chǎn)品。為達(dá)到上述目標(biāo)，在軟件開發(fā)的過程中，必須遵循軟件工程的基本原則：抽象信息隱蔽模塊化局部化確定性一致性完備性可驗(yàn)證性軟件工程目標(biāo)與原則軟件工程的目標(biāo)是在給定成本、進(jìn)度的前提下，60軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具對(duì)過程和方法提供自動(dòng)或半自動(dòng)的支持。當(dāng)這些工具被集成起來使得一個(gè)工具產(chǎn)生的信息可以被另外一個(gè)工具使用時(shí)，一個(gè)支持軟件開發(fā)的系統(tǒng)就建立起來了，稱為計(jì)算機(jī)輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個(gè)軟件工程數(shù)據(jù)庫(包含了有關(guān)分析、設(shè)計(jì)、程序構(gòu)造和測(cè)試的重要信息)從而創(chuàng)建了一個(gè)軟件開發(fā)環(huán)境。軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具對(duì)過程和方法提供自動(dòng)或61結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法大多使用自頂向下、逐層分解的系統(tǒng)分析方法來定義系統(tǒng)需求。在結(jié)構(gòu)化分析的基礎(chǔ)上，完成系統(tǒng)的規(guī)格說明，建立系統(tǒng)的一個(gè)自頂向下的任務(wù)分析模型。結(jié)構(gòu)化分析方法是一種建模技術(shù)，模型的核心是數(shù)據(jù)辭典，它描述了所有在目標(biāo)系統(tǒng)中使用和生成的數(shù)據(jù)對(duì)象。結(jié)構(gòu)化分析常用的工具：數(shù)據(jù)流圖(DFD):描述數(shù)據(jù)在系統(tǒng)中如何被傳送或變換以及描述如何對(duì)數(shù)據(jù)流進(jìn)行變換的功能，用于功能建模。數(shù)據(jù)字典判定樹判定表結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法大多使用自頂向下、逐層分解的系統(tǒng)62數(shù)據(jù)流圖數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，它從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入系統(tǒng)到從系統(tǒng)輸入的移動(dòng)變換過程。數(shù)據(jù)流圖的基本元素外部實(shí)體數(shù)據(jù)流處理(加工)數(shù)據(jù)存儲(chǔ)數(shù)據(jù)流圖數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，它從數(shù)據(jù)傳遞和加工63數(shù)據(jù)字典數(shù)據(jù)字典是關(guān)于數(shù)據(jù)的信息的集合，對(duì)數(shù)據(jù)流圖中的各個(gè)元素進(jìn)行完整的定義和說明。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構(gòu)成系統(tǒng)的邏輯模型。數(shù)據(jù)字典通常包含的信息有：名稱、別名、何處使用、如何使用、內(nèi)容描述以及補(bǔ)充信息等。數(shù)據(jù)字典數(shù)據(jù)字典是關(guān)于數(shù)據(jù)的信息的集合，對(duì)數(shù)據(jù)流圖中的各個(gè)元64軟件需求軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發(fā)進(jìn)度需求等。需求分析應(yīng)交付的主要文檔是軟件需求規(guī)格說明書(SRS)。軟件需求軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需65結(jié)構(gòu)化設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)就是采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分以及個(gè)成分之間的內(nèi)部聯(lián)系的技術(shù)。也就是說，結(jié)構(gòu)化設(shè)計(jì)是這樣一個(gè)過程：它決定用哪些方法把哪些部分聯(lián)系起來，才能解決好某個(gè)具體的有清楚定義的問題。從工程管理的角度看，軟件設(shè)計(jì)分兩步完成：1.概要設(shè)計(jì)，即總體設(shè)計(jì)。將軟件需求轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)和軟件的系統(tǒng)結(jié)構(gòu)。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖(StructureChart)。2.詳細(xì)設(shè)計(jì)：即過程設(shè)計(jì)。通過對(duì)結(jié)構(gòu)表示進(jìn)行細(xì)化，得到軟件詳細(xì)的數(shù)據(jù)結(jié)構(gòu)和算法。過程設(shè)計(jì)常用的工具有：程序流程圖、N-S圖、PAD圖、過程設(shè)計(jì)語言PDL(偽碼)。結(jié)構(gòu)化設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)就是采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成66軟件測(cè)試定義：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。一個(gè)好的測(cè)試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例。一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。測(cè)試不能表明軟件中不存在錯(cuò)誤，它只能說明軟件中存在錯(cuò)誤。軟件測(cè)試定義：67測(cè)試技術(shù)與方法綜述從是否需要執(zhí)行被測(cè)試軟件的角度，可將測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。靜態(tài)測(cè)試主要包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。動(dòng)態(tài)測(cè)試是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程，或者說，是根據(jù)軟件開發(fā)的各個(gè)階段的規(guī)格說明和程序的內(nèi)部結(jié)構(gòu)而精心設(shè)計(jì)的一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過程。測(cè)試技術(shù)與方法綜述從是否需要執(zhí)行被測(cè)試軟件的角度，可將測(cè)試分68測(cè)試技術(shù)與方法綜述按照功能劃分，可將軟件測(cè)試分為黑盒測(cè)試和白盒測(cè)試。黑盒測(cè)試將測(cè)試對(duì)象看作一個(gè)黑盒，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求規(guī)格說明，檢查程序的功能是否符合它的功能說明。這種測(cè)試又稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。白盒測(cè)試把測(cè)試對(duì)象看作一個(gè)透明的盒子，利用程序內(nèi)部的邏輯機(jī)構(gòu)及有關(guān)信息，設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序的所有邏輯路徑進(jìn)行測(cè)試。通過在不同點(diǎn)檢查程序的狀態(tài)，確定實(shí)際的狀態(tài)是否與預(yù)期的一致。這種測(cè)試又稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。測(cè)試技術(shù)與方法綜述按照功能劃分，可將軟件測(cè)試分為黑盒測(cè)試和白69軟件測(cè)試的實(shí)施軟件測(cè)試按四個(gè)步驟進(jìn)行：單元測(cè)試：對(duì)軟件設(shè)計(jì)的最小單位－模塊進(jìn)行正確性的測(cè)試，其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。集成測(cè)試：是測(cè)試和組裝軟件的過程，它是在把模塊按照設(shè)計(jì)要求組裝起來的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。確認(rèn)測(cè)試：任務(wù)是驗(yàn)證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測(cè)試：將通過確認(rèn)測(cè)試的軟件，作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支持軟件、數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)境中對(duì)其進(jìn)行一系列的集成測(cè)試和確認(rèn)測(cè)試。軟件測(cè)試的實(shí)施軟件測(cè)試按四個(gè)步驟進(jìn)行：70程序調(diào)試程序調(diào)試的任務(wù)是診斷和修正程序中的錯(cuò)誤。調(diào)試的方法：強(qiáng)行排錯(cuò)法回溯法原因排除法程序調(diào)試程序調(diào)試的任務(wù)是診斷和修正程序中的錯(cuò)誤。71第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)考試大綱1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(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ù)庫規(guī)范化理論。

4.數(shù)據(jù)庫設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)考試大綱72知識(shí)點(diǎn)歸納數(shù)據(jù)庫的定義1.長期存放在計(jì)算機(jī)內(nèi)，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲(chǔ)，具有較小的冗余度、較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性。2.數(shù)據(jù)庫是由一個(gè)互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的。知識(shí)點(diǎn)歸納數(shù)據(jù)庫的定義73數(shù)據(jù)庫管理系統(tǒng)(DBMS)數(shù)據(jù)庫管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應(yīng)用程序的集合。因此，數(shù)據(jù)庫管理系統(tǒng)也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義和檢查數(shù)據(jù)庫的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS提供了相應(yīng)的語言：數(shù)據(jù)定義語言(DDL)數(shù)據(jù)操縱語言(DML)數(shù)據(jù)控制語言(DCL)數(shù)據(jù)庫管理系統(tǒng)(DBMS)數(shù)據(jù)庫管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和74數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)是由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。數(shù)據(jù)庫系統(tǒng)的特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)是由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員75數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶的數(shù)據(jù)視圖外模式：又稱為用戶模式，是每個(gè)用戶的局部數(shù)據(jù)描述，用戶的數(shù)據(jù)視圖內(nèi)模式：又稱為物理模式，是數(shù)據(jù)庫物理存儲(chǔ)結(jié)構(gòu)和物理存取方法的描述二級(jí)映射概念模式到內(nèi)模式的映射外模式到概念模式的映射數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式76數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示和操作提供一個(gè)抽象的框架。數(shù)據(jù)模型描述的內(nèi)容包括三部分：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型：概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征77實(shí)體聯(lián)系(ER)模型概念模型是面向現(xiàn)實(shí)世界的，其出發(fā)點(diǎn)是有效地模擬顯示世界，給出數(shù)據(jù)的概念化結(jié)構(gòu)。實(shí)體聯(lián)系模型是一種廣泛使用的概念模型，該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化為實(shí)體、聯(lián)系和屬性等幾個(gè)基本概念，并用ER圖直觀地表示出來。實(shí)體聯(lián)系(ER)模型概念模型是面向現(xiàn)實(shí)世界的，其出發(fā)點(diǎn)是有效78ER模型的基本概念實(shí)體：概念世界中的基本單位，它們是客觀存在且能相互區(qū)別的事物。凡具有共性的實(shí)體可以組成一個(gè)集合稱為實(shí)體集。屬性：屬性用來描述實(shí)體的特征。一個(gè)實(shí)體可以有多個(gè)屬性，每個(gè)屬性可以有值，一個(gè)屬性的取值范圍稱為該屬性的值域。聯(lián)系：聯(lián)系反映概念世界中的實(shí)體集之間存在的一定關(guān)系。一對(duì)一聯(lián)系(1:1)一對(duì)多聯(lián)系(1:M)多對(duì)多聯(lián)系(M:N)ER模型的基本概念實(shí)體：概念世界中的基本單位，它們是客觀存在79ER圖ER圖是實(shí)體聯(lián)系模型的直觀圖形表示。實(shí)體用矩形表示，并在矩形中標(biāo)明實(shí)體的名稱。屬性用標(biāo)有屬性名稱的橢圓表示，而且必須用線將屬性與其所屬的實(shí)現(xiàn)相連。關(guān)系用標(biāo)明關(guān)系名稱的菱形表示，關(guān)系的名稱一般是動(dòng)詞。關(guān)系將相關(guān)的實(shí)體連接在一起并在實(shí)體旁標(biāo)注關(guān)系的基數(shù)。

ER圖ER圖是實(shí)體聯(lián)系模型的直觀圖形表示。80關(guān)系模型1.關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)在用戶觀點(diǎn)下，關(guān)系模型中數(shù)據(jù)的邏輯結(jié)構(gòu)是一張二維表，它由行和列組成。在關(guān)系數(shù)據(jù)庫管理系統(tǒng)中，數(shù)據(jù)的外部視圖就是關(guān)系或表的集合。關(guān)系數(shù)據(jù)庫中，每一種關(guān)系都有唯一的名稱。關(guān)系模型1.關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)81關(guān)系模型的基本概念屬性：關(guān)系中的每一列都稱為屬性，每一個(gè)屬性表示了其下數(shù)據(jù)的含義。表中的每一列在關(guān)系范圍內(nèi)有唯一的名稱。元組：關(guān)系中的行稱為元組。元組定義了一組屬性值。主碼：表中的某個(gè)屬性組，它可以唯一確定一個(gè)元組。域：屬性的取值范圍。分量：元組中的一個(gè)屬性值。關(guān)系模式：對(duì)關(guān)系的描述。關(guān)系名（屬性1，屬性2，…，屬性n）例如：學(xué)生（學(xué)號(hào)，姓名，年齡，性別，系，年級(jí)）關(guān)系模型的基本概念屬性：關(guān)系中的每一列都稱為屬性，每一個(gè)屬性82關(guān)系的基本性質(zhì)元組的個(gè)數(shù)是有限的。列是同質(zhì)的，即每一列中的分量是同一類型的數(shù)據(jù)，來自同一個(gè)域。不同的列可以出自同一個(gè)域，稱其中的每一列為一個(gè)屬性，不同的屬性要給予不同的屬性名。列的順序無所謂，即列的次序可以任意交換。任意兩個(gè)元組不能完全相同。行的順序無所謂，即行的次序可以任意交換。分量必須取原子值，即每一個(gè)分量都必須是不可分的數(shù)據(jù)項(xiàng)。關(guān)系的基本性質(zhì)元組的個(gè)數(shù)是有限的。83關(guān)系模型2.關(guān)系操縱關(guān)系模型的數(shù)據(jù)操縱即建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除及修改四種操作。3.關(guān)系模型的約束實(shí)體完整性約束參照完整性約束用戶自定義完整性約束關(guān)系模型2.關(guān)系操縱84關(guān)系模型的基本運(yùn)算查詢選擇、投影、連接、并、交、差數(shù)據(jù)更新插入、刪除、更新關(guān)系操作的特點(diǎn)集合操作方式，即操作的對(duì)象和結(jié)果都是集合。關(guān)系模型的基本運(yùn)算查詢85關(guān)系操作：插入、刪除、更新關(guān)系操作：插入、刪除、更新86關(guān)系操作：選擇選擇操作：應(yīng)用于一個(gè)關(guān)系并產(chǎn)生一個(gè)新關(guān)系，新關(guān)系中的元組是元關(guān)系中元組的子集。選擇操作根據(jù)要求從原關(guān)系中選擇部分元組，屬性的數(shù)量保持不變。關(guān)系操作：選擇選擇操作：應(yīng)用于一個(gè)關(guān)系并產(chǎn)生一個(gè)新關(guān)系，新關(guān)87關(guān)系操作：投影投影：用于一個(gè)關(guān)系并產(chǎn)生一個(gè)新關(guān)系，新關(guān)系中的屬性是原關(guān)系中屬性的子集。投影操作中元組的數(shù)量保持不變。關(guān)系操作：投影投影：用于一個(gè)關(guān)系并產(chǎn)生一個(gè)新關(guān)系，新關(guān)系中的88關(guān)系操作：連接連接：基于共有屬性將兩個(gè)關(guān)系組合。關(guān)系操作：連接連接：基于共有屬性將兩個(gè)關(guān)系組合。89關(guān)系的操作(集合操作：并、交、差)關(guān)系的操作(集合操作：并、交、差)90數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)的基本任務(wù)是根據(jù)用戶對(duì)象的信息需求、處理需求和數(shù)據(jù)的支持環(huán)境設(shè)計(jì)出數(shù)據(jù)模式。數(shù)據(jù)庫的設(shè)計(jì)通常分為幾個(gè)階段：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)。數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)的基本任務(wù)是根據(jù)用戶對(duì)象的信息需求、處理91數(shù)據(jù)庫設(shè)計(jì)需求分析：通過詳細(xì)調(diào)查現(xiàn)實(shí)世界要處理的對(duì)象，充分了解原系統(tǒng)的工作概況，明確用戶的各種需求，然后在此基礎(chǔ)上確定新系統(tǒng)的功能。概念設(shè)計(jì)：目的是分析數(shù)據(jù)間內(nèi)在語義關(guān)聯(lián)，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)庫的抽象模型。方法有以下兩種：集中式模式設(shè)計(jì)法視圖集成設(shè)計(jì)法數(shù)據(jù)庫設(shè)計(jì)需求分析：通過詳細(xì)調(diào)查現(xiàn)實(shí)世界要處理的對(duì)象，充分了92數(shù)據(jù)庫設(shè)計(jì)邏輯設(shè)計(jì)：主要工作是將ER圖轉(zhuǎn)換成指定的RDBMS中的關(guān)系模式，并利用規(guī)范化理論對(duì)邏輯數(shù)據(jù)模型進(jìn)行優(yōu)化。ER圖中的實(shí)體和聯(lián)系都可以表示成關(guān)系，ER圖中的屬性也可以轉(zhuǎn)換成關(guān)系的屬性。物理設(shè)計(jì)：主要目標(biāo)是對(duì)數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度及有效利用存儲(chǔ)空間。數(shù)據(jù)庫設(shè)計(jì)邏輯設(shè)計(jì)：主要工作是將ER圖轉(zhuǎn)換成指定的RDBMS93數(shù)據(jù)庫管理數(shù)據(jù)庫的建立數(shù)據(jù)庫的調(diào)整數(shù)據(jù)庫的重組數(shù)據(jù)庫安全性控制與完整性控制數(shù)據(jù)庫的故障恢復(fù)數(shù)據(jù)庫監(jiān)控?cái)?shù)據(jù)庫管理數(shù)據(jù)庫的建立94演講完畢，謝謝觀看！演講完畢，謝謝觀看！95全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)96第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱 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.樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱97知識(shí)點(diǎn)歸納算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。嚴(yán)格來說，一個(gè)算法必須具有以下五個(gè)主要特征：可行性確定性有窮性輸入輸出綜上，所謂算法，是一組嚴(yán)格定義運(yùn)算順序的規(guī)則，而且每一個(gè)規(guī)則都是有效且明確的，此順序?qū)⒃谟邢薜拇螖?shù)終止。知識(shí)點(diǎn)歸納算法的基本概念98算法的基本概念算法的組成要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法的控制結(jié)構(gòu)算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸減半遞推回溯法算法的基本概念算法的組成要素99算法的復(fù)雜度算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量算法優(yōu)劣的量度。1.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)。算法的時(shí)間量度記作：T(n)=O(f(n))，表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱為算法的(漸進(jìn))時(shí)間復(fù)雜度。算法的復(fù)雜度算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量100算法的復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？

任何一個(gè)算法都是由一個(gè)“控制結(jié)構(gòu)”和若干“原操作”組成的，因此一個(gè)算法的執(zhí)行時(shí)間可以看成是所有原操作的執(zhí)行時(shí)間之和

∑(原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間)

則算法的執(zhí)行時(shí)間與所有原操作的執(zhí)行次數(shù)之和成正比。從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法時(shí)間復(fù)雜度的依據(jù)。這種衡量效率的辦法所得出的不是時(shí)間量，而是一種增長趨勢(shì)的量度。它與軟硬件環(huán)境無關(guān)，只暴露算法本身執(zhí)行效率的優(yōu)劣。

算法的復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？

任何一個(gè)算法都101算法的復(fù)雜度算法的空間復(fù)雜度算法的空間負(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作：S(n)=O(g(n))，其中n為問題的規(guī)模，表示隨問題規(guī)模的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。算法的復(fù)雜度算法的空間復(fù)雜度102數(shù)據(jù)結(jié)構(gòu)利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)103數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描104數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容是指在存儲(chǔ)空間中使用一個(gè)存儲(chǔ)結(jié)點(diǎn)來存儲(chǔ)一個(gè)數(shù)據(jù)元素，在存儲(chǔ)空間中建立各存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)，來表示數(shù)據(jù)元素之間的邏輯關(guān)系。常見的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器105線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表、棧、隊(duì)列、線性鏈表等）在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)（樹、二叉樹和圖等）非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹和圖都屬于非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表、棧、隊(duì)列、線性鏈表等）106線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：

(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個(gè)數(shù)n定義為線性表的表長；n=0時(shí)的線性表被稱為空表。稱i為ai在線性表中的位序。線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：107線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元108線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加一個(gè)新結(jié)點(diǎn)。一般情況下，要在第i(1≤i≤n)個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入到第i項(xiàng)。刪除運(yùn)算是指撤銷結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)。一般情況，要?jiǎng)h除第i(1≤i≤n)個(gè)元素，要從第i+1個(gè)元素開始，直到第n個(gè)元素，共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加109棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進(jìn)先出的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和110棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。棧的操作入棧：在棧頂位置插入一個(gè)新元素，棧頂指針top加1。退棧：取出棧頂元素并賦值給一個(gè)指定的變量，棧頂指針top減1。取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間111棧如果某棧的入棧順序是ABCDEF，則出棧順序不可能是哪個(gè)（）A、DCEFBAB、ABCDEFC、EDFCABD、CBAEDF棧如果某棧的入棧順序是ABCDEF，則出棧順序不可能是哪個(gè)（112隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱為退隊(duì)。隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(113循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。循環(huán)隊(duì)列初始狀態(tài)為空，即front=rear=m。入隊(duì)操作時(shí)，rear加1，若rear=m+1，則置rear=1；退隊(duì)操作時(shí)，front加1，若front=m+1，則置front=1。在循環(huán)隊(duì)列為空或?yàn)闈M時(shí)，均有front=rear，因此需要設(shè)置標(biāo)志s進(jìn)行區(qū)分，定義s=0表示隊(duì)列為空，s=1表示隊(duì)列非空。循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏114單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以連續(xù)，也可以不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需要存儲(chǔ)其后繼元素的存儲(chǔ)位置信息(指針域)。指針域中存儲(chǔ)的信息稱為指針或鏈，N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于結(jié)點(diǎn)中只包含一個(gè)指針域，故稱為單鏈表。單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以115單鏈表通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的地址，稱為頭指針。整個(gè)鏈表的存儲(chǔ)必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，其指針域?yàn)榭铡捂湵硗ǔＲ詥捂湵碇械谝粋€(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的116單鏈表的插入和刪除單鏈表的插入和刪除117雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。HEAD…∧…∧HEAD…HEAD雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)118樹及其基本概念樹是一種簡單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹，并且稱為根的子樹。集合為空的樹簡稱為空樹；樹中的元素稱為結(jié)點(diǎn)。樹及其基本概念樹是一種簡單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元119樹的主要術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。葉節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。雙親、孩子和兄弟：結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱為兄弟。層次：結(jié)點(diǎn)的層次從根開始定義，根為第一層，根的孩子為第二層。深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。樹的主要術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。120二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。二叉樹是另一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或121二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）性質(zhì)3對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則：n0=n2+1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-1122滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(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)。完全二叉樹除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為[log2n]+1。從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹

ADCBEF滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)123二叉樹的基本性質(zhì)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[log2n]+1）的結(jié)點(diǎn)按層序（從第1層到第[log2n]+1層，每層從左到右）從1起開始編號(hào)，則對(duì)任一編號(hào)為i的結(jié)點(diǎn)(1≤i≤n)，則:

(1)如果i=1，則編號(hào)為i的結(jié)點(diǎn)是二叉樹的根，無雙親；如果i>1，則其雙親結(jié)點(diǎn)parent(i)的編號(hào)是[i/2]。

(2)如果2i>n，則編號(hào)為i的結(jié)點(diǎn)無左孩子（編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編號(hào)是2i。

(3)如果2i+1>n，則編號(hào)為i的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)的編號(hào)是結(jié)點(diǎn)2i+1。

二叉樹的基本性質(zhì)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉124二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲(chǔ)左右子樹根節(jié)點(diǎn)的存儲(chǔ)位置，即指針。L(i)V(i)R(i)LchildvalueRchild二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三125二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)126二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由"根結(jié)點(diǎn)"、"左子樹"和"右子樹"三部分構(gòu)成，則遍歷二叉樹的操作可分解為"訪問根結(jié)點(diǎn)"、"遍歷左子樹"和"遍歷右子樹"三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進(jìn)行。

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二127二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA二叉樹的遍歷先序遍歷：ABDEGHCFIJ128二叉樹的遍歷如果一棵樹的先序遍歷序列是ABDEGHCFIJ，中序遍歷序列是DBGEHACIJF，畫出這棵樹并寫出后序序列。如果一棵樹的中序遍歷序列是BDACFE后序遍歷序列是DBFECA二叉樹的遍歷如果一棵樹的先序遍歷序列是ABDEGHCFIJ，129二叉樹的遍歷1、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是A

B

D

G

C

E

F

H，中序遍歷的結(jié)點(diǎn)訪問順序是D

G

B

A

E

C

H

F，則后序遍歷的結(jié)點(diǎn)訪問順序是：2、已知一棵二叉樹的中根序列和后根序列分別為B

D

C

E

A

F

H

G和D

E

C

B

H

G

F

A，試畫出這棵二叉樹。

二叉樹的遍歷1、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是A

B

D

130二叉樹的遍歷二叉樹的遍歷131查找查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。順序查找順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都必須使用順序查找。如果線性表有序，但采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則也必須使用順序查找。查找查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。132查找二分查找(折半查找)二分查找法只適用于順序存儲(chǔ)的有序表。先確定待查目標(biāo)元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當(dāng)查找區(qū)間縮小到0也沒有找到目標(biāo)元素為止。查找過程中，給定值首先和處于待查區(qū)間"中間位置"的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到"前半個(gè)區(qū)間"或"后半個(gè)區(qū)間"之后繼續(xù)進(jìn)行查找。查找二分查找(折半查找)133折半查找二分查找折半查找二分查找134排序 排序是指將一個(gè)無序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲(chǔ)的線性表為排序?qū)ο?，在程序設(shè)計(jì)語言中就是一維數(shù)組。排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。排序 排序是指將一個(gè)無序序列整理成按值遞增或遞減(本章均采用135快速排序基本思想：從線性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移動(dòng)到前面，將前面大于T的元素移動(dòng)到后面，將線性表分為兩個(gè)部分(子表)，T放到分界線的位置，這個(gè)過程稱為線性表的分割，通過一次分割，就以T為分界將線性表分為兩個(gè)子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原則對(duì)子表繼續(xù)進(jìn)行分割，直到子表為空，則整個(gè)線性表有序?？焖倥判蚧舅枷耄簭木€性表中選取一個(gè)元素，設(shè)為T，將線性表后1363168459023395412877631暫存樞軸記錄T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割過程313168459023395412877631暫存樞軸記錄T：137第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計(jì)。

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱138知識(shí)點(diǎn)歸納程序設(shè)計(jì)方法程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、方法和工具來支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。在程序設(shè)計(jì)中，通常采用“自頂向下，逐步求精”的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語言編寫的程序。知識(shí)點(diǎn)歸納程序設(shè)計(jì)方法139程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良好的程序設(shè)計(jì)風(fēng)格概括起來包括以下及格方面：源程序文檔化數(shù)據(jù)說明的方法語句的結(jié)構(gòu)輸入和輸出程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常140程序設(shè)計(jì)風(fēng)格源程序文檔化標(biāo)識(shí)符的命名程序的注釋序言性注釋功能性注釋程序的視覺組織數(shù)據(jù)的說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化說明語句中變量的安排有序化使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)風(fēng)格源程序文檔化141程序設(shè)計(jì)風(fēng)格語句結(jié)構(gòu)在一行內(nèi)只寫一條語句程序編寫應(yīng)優(yōu)先考慮清晰性除非對(duì)效率有特殊要求，程序編寫要做到清晰第一，效率第二首先要保證程序正確，然后才要求提高速度避免使用臨時(shí)變量而使程序的可讀性下降避免不必要的轉(zhuǎn)移盡可能使用庫函數(shù)避免使用復(fù)雜的條件語句盡量減少使用“否定”條件的條件語句數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化要模塊化，使模塊功能盡可能單一化利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性從數(shù)據(jù)出發(fā)構(gòu)造程序不要修補(bǔ)不好的程序，要重寫編寫程序設(shè)計(jì)風(fēng)格語句結(jié)構(gòu)142程序設(shè)計(jì)風(fēng)格輸入和輸出對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性檢查輸入項(xiàng)的各種重要組合的合法性輸入格式要簡單，以使輸入的步驟和操作盡可能簡單輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式應(yīng)允許缺省值輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。程序設(shè)計(jì)風(fēng)格輸入和輸出143結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。逐步求精。對(duì)復(fù)雜的問題，應(yīng)設(shè)計(jì)一些子目標(biāo)過渡，逐步細(xì)化。模塊化。一個(gè)復(fù)雜問題肯定是有若干簡單問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。嚴(yán)格限制GOTO語句的使用。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則144結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，并且具有如下特點(diǎn)：單入口、單出口、結(jié)構(gòu)中無死循環(huán)，程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一145面向?qū)ο蟪绦蛟O(shè)計(jì)

面向?qū)ο蠓椒ǖ幕靖拍?.對(duì)象、類和屬性在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問題域中某個(gè)實(shí)體的抽象。每個(gè)對(duì)象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義。類是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，描述了屬于該類的所有對(duì)象的性質(zhì)。2.方法方法有稱為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可為其他對(duì)象使用。面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ幕靖拍?46面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方法的一個(gè)重要特征。指一個(gè)類(子類)直接使用另一個(gè)類(父類)的所有屬性和方法。它可以減少相似類的重復(fù)說明，從而體現(xiàn)一般性和特殊性的原則。4.多態(tài)性：多態(tài)性可以用“一個(gè)對(duì)外界面，多個(gè)內(nèi)部實(shí)現(xiàn)”來表示。可以通過方法重載和方法重寫來實(shí)現(xiàn)多態(tài)。重載指一個(gè)類中可以有多個(gè)具有相同名稱的方法，由傳遞給它們的不同個(gè)數(shù)和類型的參數(shù)來決定執(zhí)行那個(gè)方法。重寫指子類可以重新實(shí)現(xiàn)父類的某些方法，使其具有自己的特征。多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，提高了軟件的可重用性和可擴(kuò)充性。5.消息：面向?qū)ο笙到y(tǒng)中的對(duì)象之間是通過消息機(jī)制彼此相互合作的，消息是一個(gè)對(duì)象與另一個(gè)對(duì)象之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息。面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方法的一個(gè)重要特征147面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護(hù)性好面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象148第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

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)試。

第三章軟件工程基礎(chǔ)考試大綱149知識(shí)點(diǎn)歸納軟件定義和特點(diǎn)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。計(jì)算機(jī)軟件具有如下特點(diǎn)：軟件是一種邏輯實(shí)體，具有抽象性軟件生產(chǎn)沒有明顯的制造過程軟件在運(yùn)行、使用期間不存在磨損、老化問題軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性軟件復(fù)雜性高，成本昂貴軟件開發(fā)涉及諸多社會(huì)因素知識(shí)點(diǎn)歸納軟件定義和特點(diǎn)150軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題，包括：軟件需求的增長得不到滿足軟件開發(fā)成本和進(jìn)度無法控制軟件質(zhì)量難以保證軟件不可維護(hù)或可維護(hù)性低軟件成本不斷提高軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長。軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的151軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于計(jì)算機(jī)軟件定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的三要素方法工具過程軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于152軟件工程過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。它包括兩方面含義：1.軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動(dòng)。通常包括四種基本活動(dòng)：P(Plan)：軟件規(guī)格說明D(Do)：軟件開發(fā)C(Check)：軟件確認(rèn)A(Action)：軟件演進(jìn)2.從軟件開發(fā)的觀點(diǎn)看，軟件工程過程是使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，在活動(dòng)結(jié)束