全國計(jì)算機(jī)等級考試——二級公共基礎(chǔ)知識輔導(dǎo)講義?1
第一章?? 數(shù)據(jù)結(jié)構(gòu)與算法?1
第二章?? 程序設(shè)計(jì)基礎(chǔ)?7
第三章?? 軟件工程基礎(chǔ)?9
第四章?? 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)?16
第一章?? 數(shù)據(jù)結(jié)構(gòu)與算法
1.1 算法
1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。
*：算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。
2、算法的基本特征
（1）可行性。針對實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。
（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。
（4）擁有足夠的情報。算法中各種運(yùn)算總是要施加到各個運(yùn)算對象上，而這些運(yùn)算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情報時，此算法才是有效的；而當(dāng)提供的情報不夠時，算法可能無效。
*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。
3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。
（1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。
（2）算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念
1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。
2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題：
（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。
數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。
（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。
數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。
1）順序存儲。它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。
2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。
3）索引存儲：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。
*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。
（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。