數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)點(diǎn)必備

1、數(shù)據(jù)結(jié)構(gòu)與方法1、算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)2、算法的基本運(yùn)算和操作：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸3、算法的基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)（重復(fù)）結(jié)構(gòu)4、算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法5、算法的復(fù)雜度主要包括：時(shí)間復(fù)雜度、空間復(fù)雜度6、算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量7、算法的空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間8、數(shù)據(jù)結(jié)構(gòu)主要研究：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算9、數(shù)據(jù)結(jié)構(gòu)研究的目的：提高數(shù)據(jù)處理的效率10、數(shù)據(jù)處理的效率：數(shù)據(jù)處理的速度、減少處理過(guò)程中占用計(jì)算機(jī)

2、的存儲(chǔ)空間11、數(shù)據(jù)處理：指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算12、數(shù)據(jù)元素：指在數(shù)據(jù)處理中，每一個(gè)需要處理的對(duì)象都可以抽象成數(shù)據(jù)元素13、數(shù)據(jù)結(jié)構(gòu)：指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示14、數(shù)據(jù)的邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，兩要素：數(shù)據(jù)元素的集合、數(shù)據(jù)元素在集合上的關(guān)系15、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式，常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等16、數(shù)據(jù)結(jié)構(gòu)的圖形表示中每個(gè)元素加上方框成為結(jié)點(diǎn)17、數(shù)據(jù)結(jié)構(gòu)一般分為：線性結(jié)構(gòu)、非線性結(jié)構(gòu)18、線性結(jié)構(gòu)滿(mǎn)足：有且僅有一個(gè)根結(jié)點(diǎn)、每個(gè)結(jié)點(diǎn)最多有一個(gè)前件和后件、在一個(gè)線性結(jié)構(gòu)中插入和刪除任何一

3、個(gè)結(jié)點(diǎn)后還是線性結(jié)構(gòu)19、線性表定義：線性表是由n個(gè)數(shù)據(jù)元素a1、a2、a3、a4an組成的一個(gè)有限序列，表中每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且僅有一個(gè)前件，除了最后一個(gè)外，有且僅有一個(gè)后件20、非線性表的特征：有且只有一個(gè)根節(jié)點(diǎn)a1，它無(wú)前件、有且只有一個(gè)終結(jié)點(diǎn)an，它無(wú)后件、除了第一個(gè)和最后一個(gè)外，其他所有結(jié)點(diǎn)只有一個(gè)前件和一個(gè)后件21、線性表的長(zhǎng)度：線性表中的結(jié)點(diǎn)的個(gè)數(shù)n成為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，成為空表22、線性表的順序存儲(chǔ)的特點(diǎn)：所有元素所占的存儲(chǔ)空間是連續(xù)的、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序一次存放的23、線性表的隨機(jī)存取地址計(jì)算公式：ADD(ai)=ADD(a1)+(i-1

4、)*k24、線性表的主要操作：插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)25、棧的定義：棧是限定在一端進(jìn)行插入和刪除的線性表，它按照“先進(jìn)后出，后進(jìn)先出”的原則組織數(shù)據(jù)26、棧的順序存儲(chǔ)：在程序設(shè)計(jì)語(yǔ)言中，一般一維數(shù)組S（1：m）作為棧的順序存儲(chǔ)空間，其中m為棧的最大容量27、棧的基本運(yùn)算：入棧、退棧、讀棧頂元素28、入棧運(yùn)算：首先將棧頂指針（top）加1，然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說(shuō)明棧空間已滿(mǎn)，稱(chēng)為“上溢”錯(cuò)誤29、退棧運(yùn)算：首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針（top）減1。當(dāng)棧頂指針為0時(shí)，說(shuō)明?？?，成為“下溢”錯(cuò)

5、誤30、隊(duì)列的定義：隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它按照“先進(jìn)先出”的原則組織數(shù)據(jù)31、循環(huán)隊(duì)列：在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用32、循環(huán)隊(duì)列空的狀態(tài)：s=0，且front=rear=m循環(huán)隊(duì)列滿(mǎn)的狀態(tài)：s=1，且front=rear33、循環(huán)隊(duì)列的基本運(yùn)算：入隊(duì)、退隊(duì)34、入隊(duì)運(yùn)算：同樣隊(duì)列滿(mǎn)時(shí)發(fā)生“上溢”錯(cuò)誤35、退隊(duì)運(yùn)算：同樣隊(duì)列空時(shí)發(fā)生“下溢”錯(cuò)誤36、線性鏈表的基本概念：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)37、線性鏈表的存儲(chǔ)結(jié)構(gòu)：線性鏈表的每個(gè)結(jié)點(diǎn)中

6、數(shù)據(jù)域存放數(shù)據(jù)元素的值，指針域存放好后件結(jié)點(diǎn)的存儲(chǔ)地址38、雙向鏈表的存儲(chǔ)結(jié)構(gòu)：雙向鏈表的存儲(chǔ)結(jié)構(gòu)比線性鏈表的存儲(chǔ)結(jié)構(gòu)多出一個(gè)指針域，它用來(lái)存放前面的存儲(chǔ)地址39、棧的鏈?zhǔn)浇Y(jié)構(gòu)：棧的鏈?zhǔn)浇Y(jié)構(gòu)基本上和線性鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)相同。只是線性鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的頭指針變成了棧的鏈?zhǔn)浇Y(jié)構(gòu)的棧頂指針40、隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)：隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)和線性鏈表的存儲(chǔ)結(jié)構(gòu)基本相同。只是隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)保持有兩個(gè)指針：一個(gè)指向隊(duì)列頭的頭指針，一個(gè)指向隊(duì)列尾的尾指針41、線性鏈表的主要運(yùn)算：插入、刪除、合并、分解、逆轉(zhuǎn)、復(fù)制、排列、查找42、線性鏈表的特點(diǎn)43、樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)的類(lèi)型：根結(jié)點(diǎn)、父結(jié)點(diǎn)、子結(jié)點(diǎn)、葉子結(jié)點(diǎn)44、結(jié)點(diǎn)的度：

7、一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)成為結(jié)點(diǎn)的度45、樹(shù)的度：在所有結(jié)點(diǎn)中最大的度數(shù)46、樹(shù)的深度：樹(shù)的最大層，也就是樹(shù)的高度47、子樹(shù)：子結(jié)點(diǎn)構(gòu)成的樹(shù)48、二叉樹(shù)的特點(diǎn)：一是非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，二是每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)49、二叉樹(shù)的性質(zhì)：在二叉樹(shù)的第k層上，最多有2的（k-1）次方個(gè)結(jié)點(diǎn) 深度為m的二叉樹(shù)最多有2的m次方減1個(gè)結(jié)點(diǎn) 在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè) 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2(n)+1，其中l(wèi)og2(n)表示log2(n)的整數(shù)部分50、滿(mǎn)二叉樹(shù)定義：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)51、完全二叉樹(shù)定義：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上缺少右邊的若干結(jié)點(diǎn)52：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：L（i）左指針域R（i）右指針域V（i）數(shù)據(jù)域53：二叉樹(shù)的遍歷集中用到了遞歸的思