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

一、算法的基本概念算法是解題方案的準(zhǔn)確而完整的描述，它不等于程序，也不等計(jì)算方法。1．算法的基本特征可行性(effectiveness)

每一步要能實(shí)現(xiàn)

執(zhí)行的結(jié)果達(dá)到預(yù)期的目的確定性(definiteness)---非多義性有窮性(finiteness)擁有足夠的情報(bào)----輸入數(shù)據(jù)結(jié)構(gòu)與算法一、算法的基本概念2．算法的基本要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸算法的控制結(jié)構(gòu)順序選擇循環(huán)一、算法的基本概念3．算法設(shè)計(jì)基本方法列舉法（工作量大找規(guī)律分類優(yōu)化）歸納法（列舉少量找出一般關(guān)系可能是錯(cuò)的）遞推（也是歸納從初始條件逐次推出中間結(jié)果或最后結(jié)果）遞歸（也是歸納從算法本身到達(dá)遞歸邊界）減半遞推技術(shù)（分而治之規(guī)模減半重復(fù)減半）回溯法（試探八皇后問題）一、算法的基本概念算法的復(fù)雜度1.時(shí)間復(fù)雜度指執(zhí)行算法所需要的計(jì)算工作量算法工作量=f(n)n是問題的規(guī)模與下列因素?zé)o關(guān)：書寫算法的程序設(shè)計(jì)語言編譯產(chǎn)生的機(jī)器語言，代碼質(zhì)量機(jī)器執(zhí)行指令的速度算法工作量的分析方法：第一種情況：在同一個(gè)問題規(guī)模下，算法執(zhí)行所需的基本運(yùn)算次數(shù)可能與輸入有關(guān)（例如順序查找），可以用兩種方法分析算法工作量(1)平均性態(tài)

當(dāng)問題規(guī)模一定時(shí)，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一個(gè)特定的輸入時(shí)，用此方法分析工作量

A(n)=

pi是某個(gè)元素(x)出現(xiàn)的概率,ti

是在輸入某個(gè)元素(x)時(shí)所執(zhí)行的基本運(yùn)算次數(shù)n+1∑i=1piti(2)最壞情況復(fù)雜性

是指當(dāng)問題規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)

W(n)=max(ti)

W(n)比A(n)更有實(shí)用價(jià)值第二種情況：算法的計(jì)算工作量也可能與輸入無關(guān)（例如n階矩陣相乘），在所有可能的輸入下，算法所執(zhí)行的基本運(yùn)算次數(shù)是一定的，此時(shí)A(n)=W(n)2.空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間內(nèi)存空間包括：1）算法程序占用空間2）輸入的初始數(shù)據(jù)占用空間3）算法執(zhí)行中所需的額外空間二、數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)研究三個(gè)問題:(1)邏輯結(jié)構(gòu):數(shù)據(jù)集合中各元素之間所固有的邏輯關(guān)系(2)存儲(chǔ)結(jié)構(gòu):各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系(3)運(yùn)算:對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行運(yùn)算數(shù)據(jù)結(jié)構(gòu)研究的目的:(1)提高數(shù)據(jù)處理速度(2)節(jié)省存儲(chǔ)空間1.什么是數(shù)據(jù)結(jié)構(gòu)例如:無序表的順序查找和有序表的對(duì)分查找3516788543293321544616212933354346547885無序表:若查找的元素正好是第一個(gè),次數(shù)少若查找的元素是最后一個(gè)或查找的元素不在表中的情況,無序表有序表則次數(shù)多(1)數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素的信息(即數(shù)據(jù)元素的集合,記為D)和各數(shù)據(jù)元素之間的前后件關(guān)系(記為R)。與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無關(guān).記B為數(shù)據(jù)結(jié)構(gòu),則

B=(D,R)例如:一年四季的數(shù)據(jù)結(jié)構(gòu)表示為:

B=(D,R)

D={春,夏,秋,冬}

R={(春,夏),(夏,秋),(秋,冬)}

用二元組表示數(shù)據(jù)元素之間的前后件關(guān)系(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式注意:各數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置關(guān)系與它們的邏輯關(guān)系不一定是相同的.

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有：

順序

鏈接

索引

2、數(shù)據(jù)結(jié)構(gòu)的圖形表示例1:一年四季春夏秋冬結(jié)點(diǎn)

例2:家庭成員父親

兒子女兒

有向箭頭前件指向后件例3:用圖形表示數(shù)據(jù)結(jié)構(gòu)B=(D,R)D={d1,d2,d3,d4,d5,d6,d7}R={(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}d1d2d3d7d4d6d5

根結(jié)點(diǎn)(無前件)終端結(jié)點(diǎn)(葉子結(jié)點(diǎn)無后件)內(nèi)部結(jié)點(diǎn)3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)（1）線性結(jié)構(gòu):有且只有一個(gè)根結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件注意:在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)該是線性結(jié)構(gòu)如:

ABCD將A刪除就不滿足了(2)非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)就是非線性結(jié)構(gòu)例如：家庭成員關(guān)系對(duì)非線性結(jié)構(gòu)的存儲(chǔ)與處理比線性結(jié)構(gòu)復(fù)雜得多三、線性表及其順序存儲(chǔ)結(jié)構(gòu)1、線性表的基本概念例如：一個(gè)N維向量、英文字母表、一年中的四季，一個(gè)一維數(shù)組等都是線性表，其中的每一個(gè)值都是線性表的一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）。此時(shí)的數(shù)據(jù)元素是一個(gè)簡單項(xiàng)。又如：一個(gè)學(xué)生表也是線性表，其中的每條記錄就是線性表的一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）。此時(shí)的數(shù)據(jù)元素是一個(gè)復(fù)雜項(xiàng)。2、線性表的順序存儲(chǔ)結(jié)構(gòu)兩個(gè)基本特點(diǎn):（1）線性表中所有元素所占存儲(chǔ)空間是連續(xù)的（2）線性表中所有元素在存儲(chǔ)空間中是按邏輯順序依次存放的2、線性表的順序存儲(chǔ)結(jié)構(gòu)線性表中每一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址ADR(ai)由該元素在線性表中的位置序號(hào)i唯一確定ADR(ai)=ADR(a1)+(i-1)k

k表示每個(gè)元素占用的字節(jié)數(shù)3、順序表的插入運(yùn)算（元素后移、上溢）291856633524314712345678910872918566335243147123456789101429871856633524314712345678910如再插入，將上溢1234567思考：在末尾插入一個(gè)元素，在表頭插入一個(gè)元素，在表中i位置處插入一個(gè)元素，表中其他元素移動(dòng)情況。結(jié)論：在線性表的存儲(chǔ)情況下，要插入一個(gè)元素，效率低；特別是在大表中，消耗的時(shí)間更多。4、順序表的刪除運(yùn)算2918566335243147123456789101856633524314712345678910185663352447123456789101256734思考：在末尾刪除一個(gè)元素，在表頭刪除一個(gè)元素，在表中i位置處刪除一個(gè)元素，表中其他元素移動(dòng)情況。結(jié)論：在線性表的存儲(chǔ)情況下，要?jiǎng)h除一個(gè)元素，效率低；特別是在大表中，消耗的時(shí)間更多。故：線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除運(yùn)算，比較適合小線性表或者其中元素不常變動(dòng)的線性表。四、棧和隊(duì)列1、棧（stack）及其基本運(yùn)算它是限定在一端進(jìn)行插入與刪除的線性表此端稱為棧頂，用指針top來指示；另一端不允許做任何操作，稱為棧底，用指針bottom來指示。所謂“先進(jìn)后出”表或者“后進(jìn)先出”表。插入一個(gè)元素稱為入棧，刪除一個(gè)元素成為退棧。棧示意圖an……a2a1入棧退棧棧頂top棧底bottom2、隊(duì)列（queue）及其運(yùn)算它是在一端（隊(duì)尾）插入，用尾指針rear指示；另一端（隊(duì)頭）刪除，用頭指針front指示的線性表。所謂“先進(jìn)先出”表或者“后進(jìn)后出”表往隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的隊(duì)頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。隊(duì)列示意圖ABCDEFfrontrear退隊(duì)入隊(duì)五、線性鏈表一個(gè)存儲(chǔ)單元對(duì)應(yīng)一個(gè)數(shù)據(jù)結(jié)點(diǎn)，這個(gè)存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。1、線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表數(shù)據(jù)域指針域存儲(chǔ)序號(hào)12…I…m線性鏈表的存儲(chǔ)空間數(shù)據(jù)域指針域V（i）NEXT(i)存儲(chǔ)序號(hào)i線性鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)nNull……h(huán)ead線性鏈表的邏輯結(jié)構(gòu)例：設(shè)線性表為（a1,a2,a3,a4,a5）,存儲(chǔ)空間有10個(gè)存儲(chǔ)結(jié)點(diǎn)，則存儲(chǔ)情況如圖：a29a11a410a35a50123456789103head物理狀態(tài)圖a1head線性鏈表的邏輯狀態(tài)圖a2a3a4a50319510以上是線性單鏈表，特點(diǎn)是：每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由它只能找到后件結(jié)點(diǎn)，而不能找到前件結(jié)點(diǎn)。為彌補(bǔ)此缺點(diǎn)，每個(gè)結(jié)點(diǎn)設(shè)兩個(gè)指針，即左指針（Llink）用來指向其前件；右指針(Rlink)用來指向其后件。此線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖：0DRLDRLD0…………h(huán)ead域中值為0，表示為空Null,即不指向任何結(jié)點(diǎn)2、帶鏈的棧AnAn-1A10Top…AnAn-1A10Top…An+1AnAn-1A10Top…入棧操作退棧操作3、帶鏈的隊(duì)列A1A2An0front…A1A2An…An+10A1A2An0…rearfrontrearrearfront入隊(duì)操作退隊(duì)操作六、樹與二叉樹1、樹的基本概念樹（tree）是一種非線性結(jié)構(gòu)。RKPQDBENOTCHXYSWZAMFGL根結(jié)點(diǎn)葉子結(jié)點(diǎn)根結(jié)點(diǎn)、父結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)結(jié)點(diǎn)的度、樹的度（后件個(gè)數(shù)）樹的深度（層次個(gè)數(shù)）子樹重要概念2、二叉樹及其基本性質(zhì)特點(diǎn)：（1）非空的二叉樹只有一個(gè)根結(jié)點(diǎn)（2）每個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹；沒有左右子樹的結(jié)點(diǎn)就是葉子結(jié)點(diǎn)

RKDENOTBB只有根結(jié)點(diǎn)的二叉樹二叉樹的基本性質(zhì)

性質(zhì)1：在二叉樹的第K層上，最多有2k-1(k>=1)個(gè)結(jié)點(diǎn)。

性質(zhì)2：深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。（等比數(shù)列求和：S=a1(1-qn)

/(1-q)）

性質(zhì)3：在任意一棵二叉樹中，（出）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比（出）度為2的結(jié)點(diǎn)多一個(gè)。（所有的出度=所有入度+1）

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分。（由性質(zhì)2得出）滿二叉樹與完全二叉樹（1）滿二叉樹即除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是說，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。(即：除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)均有兩個(gè)子結(jié)點(diǎn))滿二叉樹非滿（2）完全二叉樹即除最后一層外，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

兩者關(guān)系：滿二叉樹也是完全二叉樹，反之則不一定。完全二叉樹的基本性質(zhì)

性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1（由性質(zhì)4得出）

性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每層從左到右）用自然數(shù)1，2，3，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)編號(hào)為k（k=1,2,3,…,n）的結(jié)點(diǎn)有以下結(jié)論：（1）若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為int(k/2)（2）若2k<=n,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）（3）若2k+1<=n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)

3、二叉樹的存儲(chǔ)結(jié)構(gòu)FCEDHGPAB4F6C90E2A08D0130H010P05G110B0BT二叉樹二叉鏈表的邏輯狀態(tài)iL(i)V(i)R(i)LchildRchildValue二叉樹存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)10P020A0346F9513G162C87811D090E510110B012130H0BT二叉鏈表的物理狀態(tài)4、二叉樹的遍歷（1）前序遍歷（DLR）

根左右（2）中序遍歷（LDR）

左根右（3）后序遍歷（LRD）

左右根例如：表達(dá)式（a+b）*d/2用下列邏輯結(jié)構(gòu)，采用前序遍歷就可以實(shí)現(xiàn)(a*b/d2+)七、查找技術(shù)1、順序查找從第一個(gè)元素開始，依次比較，若相等，則表示找到。這對(duì)于大表來說，效率較低。在最壞的情況下，順序查找需要比較n次。2、二分法查找此方法只適用于順序存儲(chǔ)的有序表。效率比順序查找高。對(duì)于長度為n的有序線性表，在最壞的情況下，二分法只需要比較log2n次，而順序查找需要比較n次。八、排序技術(shù)1、交換類排序（1）冒泡排序（相鄰元素比較）假設(shè)線性表的長度為n，在最壞情況下，需要比較的次數(shù)為n(n-1)/2（2）快速排序法（選取元素，不斷分割）2、插入類排序（1）簡單插入排序法（提取元素，插入有序表）將無序序列中的各元素（先保存到一個(gè)變量T中）依次插入到已經(jīng)有序的線性表。每一次比較后最多移掉一個(gè)逆序。因此其效率與冒泡法相同，在最壞情況下，需要比較的次數(shù)為n(n-1)/2（2）希爾排序法（先分割成子序列，再插入排序）將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序的過程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序完成。增量一般取ht=n/2k

(k=1,2,…,[log2n])其中n為待排序序列的長度。希爾排序?qū)τ诿總€(gè)子表仍然是插入排序，但是，在子表中每進(jìn)行一次比較就有可能移去整個(gè)線性表中的多個(gè)逆序，從而改善了排序性能。其效率與所選取的增量序列有關(guān)，如果選取上述增量，則在最壞情況下，需要比較次數(shù)為O（n1.5）3、選擇類排序（1）簡單選擇類排序（選擇，交換）掃描整個(gè)線性表，選取最小元素，交換到表的最前面；對(duì)剩下的子表采用同樣的方法，直到子表是空為止。最壞情況下，比較次數(shù)n(n-1)/2（2）堆排序軟件工程基礎(chǔ)一、軟件的生命周期指軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。

可行性研究需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測試使用維護(hù)退役定義階段開發(fā)階段維護(hù)階段二、結(jié)構(gòu)化分析方法1、需求分析2、分析工具

a.數(shù)據(jù)流圖（DFD）

b.數(shù)據(jù)字典（DD）c.判定樹

d.判定表3、軟件需求規(guī)格說明書（SRS）加工（轉(zhuǎn)換）數(shù)據(jù)流存儲(chǔ)文件（數(shù)據(jù)源）源，潭（系統(tǒng)之外的實(shí)體）三、結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)的基本原理（1）抽象（2）模塊化（3）信息隱蔽（4）模塊獨(dú)立性

a.內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度。一個(gè)模塊的內(nèi)聚性越強(qiáng)，那么其獨(dú)立性就越強(qiáng)。

b.耦合性：是模塊間互相連接的緊密程度。一個(gè)模塊與其他模塊的耦合性越強(qiáng),則其獨(dú)立性越弱。內(nèi)聚與耦合的關(guān)系：內(nèi)聚性越強(qiáng)那么耦合性就越弱。應(yīng)該做到高內(nèi)聚，低耦合。2、概要設(shè)計(jì)（1）基本任務(wù)：設(shè)計(jì)軟件的系統(tǒng)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)編寫概要設(shè)計(jì)文檔概要設(shè)計(jì)文檔評(píng)審（2）設(shè)計(jì)工具

a.結(jié)構(gòu)圖

b.數(shù)據(jù)流圖（變換型、事務(wù)型）（3）設(shè)計(jì)準(zhǔn)則（P66）3、詳細(xì)設(shè)計(jì)（1）基本任務(wù)：

a.為軟件結(jié)構(gòu)中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)。

b.用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。（2）設(shè)計(jì)工具

a.圖形工具：程序流程圖PFD，N-S，PAD，HIPOPAD:問題分析圖b.表格工具：判定表

c.語言工具：PDL（偽碼）HIPO圖(hierarchyplusinput-process-output)是IBM公司于70年代中期在層次結(jié)構(gòu)圖(structurechart)的基礎(chǔ)上推出的一種描述系統(tǒng)結(jié)構(gòu)和模塊內(nèi)部處理功能的工具(技術(shù))。HIPO圖由層次結(jié)構(gòu)圖和IPO圖兩部分構(gòu)成,前者描述了整個(gè)系統(tǒng)的設(shè)計(jì)結(jié)構(gòu)以及各類模塊之間的關(guān)系,后者描述了某個(gè)特定模塊內(nèi)部的處理過程和輸入/輸出關(guān)系。

HIP0圖一般由一張總的層次化模塊結(jié)構(gòu)圖和若干張具體模塊內(nèi)部展開的IPO圖組成,如圖3.13和圖3.14所示。圖3.13是一張有關(guān)修改庫存文件部分內(nèi)容模塊的層次模塊結(jié)構(gòu)圖。圖3.14是圖3.13中若干張模塊展開圖(I