【正文】 第1章 二級(jí)公共基礎(chǔ) 本章知識(shí)點(diǎn)11二級(jí)公共基礎(chǔ)的內(nèi)容主要包括數(shù)據(jù)結(jié)構(gòu)與算法、程序設(shè)計(jì)基礎(chǔ)、軟件工程基礎(chǔ)、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4個(gè)部分。 基本數(shù)據(jù)結(jié)構(gòu)與算法本部分的考試要點(diǎn)如下。（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)的圖形表示，線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的概念。（3）線(xiàn)性表的定義，線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。（4）棧和隊(duì)列的定義，棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。（5）線(xiàn)性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。（6）樹(shù)的基本概念，二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的前序、中序和后序遍歷。（7）順序查找與二分查找算法，基本排序算法（交換類(lèi)排序、選擇類(lèi)排序、插入類(lèi)排序）。1．算法的基本概念（1）算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系程序設(shè)計(jì)主要包括兩個(gè)方面，一是行為特性的設(shè)計(jì)，二是結(jié)構(gòu)特性的設(shè)計(jì)。行為特性的設(shè)計(jì)一般是指將解決問(wèn)題過(guò)程中的每一個(gè)細(xì)節(jié)準(zhǔn)確地加以定義，并將全部的解題過(guò)程用某種工具完整地描述出來(lái)。這一過(guò)程也稱(chēng)為算法的設(shè)計(jì)。結(jié)構(gòu)特性的設(shè)計(jì)是指為問(wèn)題的解決確定合適的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法之間有著密切的關(guān)系。特別是對(duì)于數(shù)據(jù)處理問(wèn)題，算法的效率通常與數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示有著直接的關(guān)系。（2）算法的基本特征所謂算法是指對(duì)解題方案準(zhǔn)確而完整的描述。對(duì)于一個(gè)問(wèn)題，如果可以通過(guò)一個(gè)計(jì)算機(jī)程序，在有限的存儲(chǔ)空間內(nèi)運(yùn)行有限長(zhǎng)的時(shí)間而得到正確的結(jié)果，則稱(chēng)這個(gè)問(wèn)題是算法可解的。但算法不等于程序，也不等于計(jì)算方法。當(dāng)然，程序也可以作為算法的一種描述，但程序通常還需考慮很多與方法和分析無(wú)關(guān)的細(xì)節(jié)問(wèn)題，這是因?yàn)樵诰帉?xiě)程序時(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制。算法實(shí)際上是一種抽象的解題方法，它具有動(dòng)態(tài)性。作為一個(gè)算法，一般應(yīng)具有以下幾個(gè)基本特征。① 能行性（Effectiveness）算法的能行性主要包括兩個(gè)方面。一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的，二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的。② 確定性（Definiteness）算法的確定性，是指算法中的每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩可的解釋?zhuān)膊辉试S有多義性。這一性質(zhì)也反映了算法與數(shù)學(xué)公式的明顯差別。③ 有窮性（Finiteness）算法的有窮性是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。因?yàn)椋绻粋€(gè)算法需要執(zhí)行千萬(wàn)年，也就失去了實(shí)用價(jià)值。④ 擁有足夠的情報(bào)一個(gè)算法是否有效，還取決于為算法所提供的情報(bào)是否足夠。通常，算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這是算法執(zhí)行的起點(diǎn)或是依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法本身也就無(wú)法執(zhí)行或?qū)е聢?zhí)行有錯(cuò)。一般來(lái)說(shuō)，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的，而當(dāng)提供的情報(bào)不夠時(shí)，算法并不有效。綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。（3）算法的基本要素一個(gè)算法通常由兩個(gè)基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。① 算法中對(duì)數(shù)據(jù)的運(yùn)算和操作每個(gè)算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。因此，計(jì)算機(jī)算法就是計(jì)算機(jī)能處理的操作所組成的指令序列。通常計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，稱(chēng)為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。計(jì)算機(jī)程序就是按解題要求從計(jì)算機(jī)指令系統(tǒng)中選擇合適的指令所組成的指令序列。② 算法的控制結(jié)構(gòu)一個(gè)算法的功能不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱(chēng)為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、NS結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。（4）算法設(shè)計(jì)的基本方法計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱(chēng)為計(jì)算機(jī)算法。常用的算法設(shè)計(jì)方法有如下幾種。① 列舉法列舉法的基本思想是根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰模男┦遣恍枰?。因此，列舉法常用于解決“是否存在”或“有多少種可能”等類(lèi)型的問(wèn)題，例如求解不定方程的問(wèn)題。列舉法的特點(diǎn)是算法比較簡(jiǎn)單，但當(dāng)列舉的可能情況較多時(shí)，執(zhí)行列舉算法的工作量將會(huì)很大。通常，在設(shè)計(jì)列舉算法時(shí)，要對(duì)實(shí)際問(wèn)題進(jìn)行詳細(xì)的分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律；或?qū)λ锌赡艿那闆r進(jìn)行分類(lèi)，引出一些有用的信息，就可以大大減少列舉量。列舉算法是計(jì)算機(jī)算法中的一個(gè)基礎(chǔ)算法。② 歸納法歸納法的基本思想是：通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。顯然，歸納法要比列舉法更能反映問(wèn)題的本質(zhì)，并且可以解決列舉量為無(wú)限的問(wèn)題。但是，從一個(gè)實(shí)際問(wèn)題中總結(jié)歸納出一般的關(guān)系，并不是一件容易的事情，尤其是要?dú)w納出一個(gè)數(shù)學(xué)模型更為困難。從本質(zhì)上講，歸納就是通過(guò)觀察一些簡(jiǎn)單而特殊的情況，最后總結(jié)出有用的結(jié)論或解決問(wèn)題的有效途徑。③ 遞推所謂遞推是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而得到確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關(guān)系式實(shí)際上是通過(guò)對(duì)實(shí)際問(wèn)題的分析與歸納而得到的，因此，遞推關(guān)系式往往是歸納的結(jié)果。④ 遞歸遞歸的基本思想是將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題為止。遞歸是一種很重要的算法設(shè)計(jì)方法。遞歸分為直接遞歸與間接遞歸兩種。⑤ 減半遞推技術(shù)解決實(shí)際問(wèn)題的復(fù)雜程度往往與問(wèn)題的規(guī)模有著密切的關(guān)系。因此，利用分治法解決這類(lèi)實(shí)際問(wèn)題是有效的。所謂分治法就是對(duì)問(wèn)題分而治之。工程上常用的分治法是減半遞推技術(shù)。所謂“減半”是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變。所謂“遞推”是指重復(fù)“減半”的過(guò)程。⑥ 回溯法在工程上，有些實(shí)際問(wèn)題卻很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟，并且也不能進(jìn)行無(wú)限的列舉。對(duì)于這類(lèi)問(wèn)題，一種有效的方法是“試”。通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解，若