二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法

二級(jí)基礎(chǔ)知識(shí)第一章數(shù)據(jù)結(jié)構(gòu)與算法全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第1頁(yè)。1.1算法一、算法的概念解決問(wèn)題準(zhǔn)確而完整的描述。特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。要素：對(duì)數(shù)據(jù)運(yùn)算操作（算術(shù)、邏輯）通過(guò)指令序列程序來(lái)實(shí)現(xiàn)、算法的控制結(jié)構(gòu)（執(zhí)行順序）。算法設(shè)計(jì)方法：列舉法：列舉所有可能歸納法：從特殊到一般二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第2頁(yè)。遞推：從條件到結(jié)論遞歸：函數(shù)的自調(diào)用減半遞推：中間分冶回溯:反證二、算法復(fù)雜度1、時(shí)間復(fù)雜度（工作量）平均性態(tài)（平均值）；最壞情況（最大值）2、空間復(fù)雜度（資源）內(nèi)存資源二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第3頁(yè)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念研究數(shù)據(jù)結(jié)構(gòu)——邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、運(yùn)算的實(shí)現(xiàn)1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)元素及元素間的關(guān)系，B=(D,R)存儲(chǔ)結(jié)構(gòu)：內(nèi)存中的存放形式線性與非線性結(jié)構(gòu)：有且僅有一個(gè)根結(jié)點(diǎn)；一個(gè)前件，一個(gè)后件只有一個(gè)根結(jié)點(diǎn)不是線性結(jié)構(gòu)二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第4頁(yè)。1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表：連續(xù)順序存儲(chǔ)，邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致。插入運(yùn)算：插入點(diǎn)起所有元素后移刪除運(yùn)算：刪除點(diǎn)后所有元素前移二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第5頁(yè)。1.4棧和隊(duì)列1、棧只有一個(gè)出入口僅有一個(gè)元素寬度的巷道， 先進(jìn)后出入棧、退棧、讀棧頂元素2、隊(duì)列一個(gè)出口一個(gè)入口僅有一個(gè)元素寬度的巷道，先進(jìn)先出隊(duì)列移動(dòng)，循環(huán)標(biāo)志s0空入隊(duì)；上溢、退隊(duì)；下溢二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第6頁(yè)。1.5線性鏈表線性表的缺點(diǎn)：插入刪除上的復(fù)雜性、空間的連續(xù)性（預(yù)留、不夠）結(jié)點(diǎn)：元素+指針Head---a1*a2---a2*a3…annull雙鏈表?xiàng)Ｅc隊(duì)列的鏈表實(shí)現(xiàn)鏈表的插入刪除改變前后元素的指針指向，可以不改變位置循環(huán)鏈表：增加一個(gè)表頭結(jié)點(diǎn)數(shù)據(jù)不定,最后一指針指向表頭二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第7頁(yè)。1.6樹(shù)與二叉樹(shù)1、樹(shù)層次結(jié)構(gòu)根結(jié)點(diǎn)、葉子結(jié)點(diǎn)、子結(jié)點(diǎn)、深度（層數(shù)）、節(jié)點(diǎn)的度（分叉數(shù)）了解表達(dá)式的樹(shù)表示2、二叉樹(shù)分叉數(shù)少于等于2（左右子樹(shù)）,一個(gè)根節(jié)點(diǎn)是二叉樹(shù)性質(zhì)A、k層節(jié)點(diǎn)少于2^(k-1)B、m深度的樹(shù)節(jié)點(diǎn)總數(shù)為2^m-1二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第8頁(yè)。C、度為2的比度為0節(jié)點(diǎn)多一個(gè)d、節(jié)點(diǎn)為n，則深度為int(log2N)+13、滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)不缺枝完全二叉樹(shù)：僅缺右子樹(shù)注意完全二叉樹(shù)節(jié)點(diǎn)編號(hào)間關(guān)系4、二叉樹(shù)的存儲(chǔ)采用雙鏈表二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第9頁(yè)。5、二叉樹(shù)的遍歷遍歷：不重復(fù)訪問(wèn)所有結(jié)點(diǎn)前序：根、左、右中序：左、根、右后序：左、右、根注意從上到下均按上述順序例1.33b左前：abdhiejkcflg；中:hdibjekalfcg后:hidjkeblfgca二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第10頁(yè)。1.7查找技術(shù)1、順序查找無(wú)序表、鏈表2、二分法查找有序表，最多l(xiāng)og2N次二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第11頁(yè)。1.8排序技術(shù)1、交換類排序A、昌泡法排序前后順序交換改變逆序n(n-1)/2B、快速排序法取一個(gè)中點(diǎn)兩邊與中點(diǎn)比較交換2、插入類排序A、簡(jiǎn)單插入排序從第一個(gè)開(kāi)始小的插在前n(n-1)/2B、希爾排序法分成若于子序列排序后減少子序列個(gè)數(shù)。二級(jí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法全文共13頁(yè)，當(dāng)前為第12頁(yè)。3、選擇類排序法A