数据结构知识点汇总
1、用鏈表表示線性表的優(yōu)點(diǎn)是（便于插入和刪除操作）
2、單鏈表中，增加頭結(jié)點(diǎn)的目的是（方便運(yùn)算的實(shí)現(xiàn)）
3、棧和隊(duì)列的共同特點(diǎn)是（只允許在端點(diǎn)處插入和刪除元素）
4、棧通常采用的兩種存儲結(jié)構(gòu)是（線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)）
5、隊(duì)列具有（先進(jìn)先出）的特征，棧具有（后進(jìn)先出）的特征。
6、鏈表（插入和刪除不需要移動元素，但是無法隨機(jī)訪問任一元素）
7、循環(huán)鏈表的主要優(yōu)點(diǎn)是（從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表）
8、線性表（除了第一個和最后一個元素外，其余每個元素都有一個直接前驅(qū)和直接后繼）
9、線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是（隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)）
10、深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為（16）。其共有（31）個結(jié)點(diǎn)。
? ? ? ?設(shè)一棵完全二叉樹共有699個結(jié)點(diǎn)。則該二叉樹的葉子結(jié)點(diǎn)數(shù)為（350）個。?
? ? ? ? ? ? ?#完全二叉樹總的結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2；若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2。
11、具有3個結(jié)點(diǎn)的二叉樹有（5）種形態(tài)。 #高度為2層的是：根-左-右。高度為3層的是：根-左-左、根-左-右、根-右-右、根-右-左。
12、一棵二叉樹中有3個葉子結(jié)點(diǎn)，有8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（13）個。
? ? ? #葉子結(jié)點(diǎn)數(shù)n0與度為2的結(jié)點(diǎn)數(shù)n2的關(guān)系是：n0＝n2＋1，所以度為2的結(jié)點(diǎn)個數(shù)為3-1=2。所以總的結(jié)點(diǎn)數(shù)為 n=n0+n1+n2, 8+2+3=13.
13、已知二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（cedba）。#過程見文章：點(diǎn)擊打開鏈接
14、已知二叉樹的前序遍歷序列是abdgcefh,中序遍歷序列是dgbaechf,它的前序遍歷序列是（gdbehfca）。
15、算法是指（解決方案的準(zhǔn)確而完整的描述）。
16、算法由（順序、選擇、循環(huán)）控制結(jié)構(gòu)組合而成。
17、算法的時間復(fù)雜度是指（算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)）。
18、算法的空間復(fù)雜度是指（執(zhí)行過程中所需要的存儲空間）。
19、算法分析的目的是（分析算法的效率以求改進(jìn)）。
20、數(shù)據(jù)的存儲結(jié)構(gòu)是指（數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示）。
21、數(shù)據(jù)的邏輯結(jié)構(gòu)是指（反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)）。
22、根據(jù)數(shù)據(jù)結(jié)構(gòu)中各元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分為（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）。
線性結(jié)構(gòu)一般是首無前驅(qū)，尾無后繼，中間元素有唯一的前驅(qū)和后繼。主要有：列表、鏈表、隊(duì)列、棧。
非線性結(jié)構(gòu)主要有1、沒有對應(yīng)關(guān)系的 集合。2、一對多關(guān)系的 樹。3、多對多關(guān)系的 圖。
23、（隊(duì)列，循環(huán)隊(duì)列，順序表）不具有記憶功能，（棧）具有記憶功能。
24、遞歸算法一般需要用（棧）來實(shí)現(xiàn)。
#在遞歸算法的運(yùn)行過程中，需要利用棧來保存其運(yùn)算結(jié)果、參數(shù)和返回地址等。
25、算法的五個基本特征是：可行性，確定性，和擁有足夠的情報
有限性：算法在執(zhí)行有限步后必須終止。
確定性：算法的每個步驟都需要精確地定義，嚴(yán)格地、無歧義的運(yùn)行。
輸入：算法在運(yùn)行之前賦給它的量。
輸出：算法運(yùn)行結(jié)束時的結(jié)果。
可行性：算法原則上能夠精準(zhǔn)地運(yùn)行，而且人們用紙和筆做有限次運(yùn)算后即可完成。
26、由兩個棧共享一個存儲空間的好處是（節(jié)省存儲空間，降低上溢發(fā)生的概率）。
為了不發(fā)生上溢錯誤，就必須給每個棧分配一個足夠大的存儲空間。但實(shí)際中，很難準(zhǔn)確地估計(jì)，若每個棧都分配過大的存儲空間，勢必造成系統(tǒng)空間緊張；若讓多個棧共用一個足夠大的連續(xù)存儲空間，則可利用棧的動態(tài)特性使它們的存儲空間互補(bǔ)
27、需要打印機(jī)輸出數(shù)據(jù)時，一般將打印作業(yè)放在一個（隊(duì)列）中。
28、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由?p?所指向） ，滿足（p->next=head?）。
29、與單鏈表相比，雙向鏈表的優(yōu)點(diǎn)是（更容易訪問相鄰結(jié)點(diǎn)）。
30、
31、N個頂點(diǎn)的連通圖中邊的條數(shù)至少為（N-1）條。#將所有頂點(diǎn)連成一條線即可
32、N個頂點(diǎn)的強(qiáng)連通圖中邊的條數(shù)至少為（N）條。#將所有頂點(diǎn)連成一條圈
33、對長度為n的線性表進(jìn)行順序查找，最壞情況下需要比較（N）次。
34、最簡單的交換排序是（冒泡排序）。
35、對長度為n的線性表進(jìn)行順序冒泡排序，最壞情況下需要比較（n(n-1)/2）次。
? ? ? ? #一共比較n-1遍，第1遍需要比較n-1次，第1遍需要比較n-2次,........最后一遍需要比較1次。是一個等差序列，對其進(jìn)行求和即可。
36、在序列基本有序的情況下，效率最高的方法是（A） #如果將插入排序換為冒泡排序，則選冒泡排序
? ? ? ? ?A．插入排序 ??B．選擇排序 ??C．快速排序 ??D．堆排序
? ? ? ??插入排序通過數(shù)據(jù)元素的交換來逐步消除線性表中的逆序，所以比較的次數(shù)與初始排列次序有關(guān)，在待排序的元素序列基本有序的前提下，效率最高。而選擇排序和堆排序的比較次數(shù)與初始排列次序無關(guān)。快速排序雖然與初始排列次序有關(guān)，但在待排序的元素序列基本有序的前提下，效率低于插入排序。
37、希爾排序?qū)儆?#xff08;插入類排序），堆排序?qū)儆?#xff08;選擇類排序）。
38、在下列幾種排序方法中，要求內(nèi)存量最大的是（D）.
?
? ? ? ? A．插入排序 ?B．選擇排序 ?C．快速排序 ?D．歸并排序
? ? ? ??快速排序的基本思想是，通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中，從而得到一個新的序列；選擇排序的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面(這是它應(yīng)有的位置)，然后對剩下的子表采用同樣的方法，直到表空為止；歸并排序是將兩個或兩個以上的有序表組成合成一個新的序列表。
39、已知數(shù)據(jù)表 A中每個元素距其最終位置不遠(yuǎn)，為節(jié)省時間， 應(yīng)采用（直接插入排序）。
40、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的( 數(shù)據(jù)元素 )的集合。
41、數(shù)據(jù)元素之間的任何關(guān)系都可以用 (前驅(qū)和后繼) 關(guān)系來描述。
42、順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在 (物理位置) 相鄰的存儲單元中。
43、棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。
44、隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)和退隊(duì)。
45、在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計(jì)算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為 (可利用棧) .
46、棧和隊(duì)列通常采用的存儲結(jié)構(gòu)分別是 鏈?zhǔn)酱鎯晚樞虼鎯Α?/p>
47、當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于對頭指針時， 說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 (上溢)?
48、當(dāng)循環(huán)隊(duì)列為空時， 不能進(jìn)行退隊(duì)運(yùn)算， 這種情況稱為 (下溢)。
49、在一個容量為 25 的循環(huán)隊(duì)列中， 若頭指針 front=16 ， 尾指針 rear=9 ， 則該循環(huán)隊(duì)列中共有 18 個元素。 ? ? ? ?注： 當(dāng) rear<front 時， 元素個數(shù)＝總?cè)萘?#xff0d;（ front －rear ）；?當(dāng) rear>front 時，元素個數(shù)＝ rear －front 。
50、判斷一個鏈表是否存在環(huán)：點(diǎn)擊打開鏈接
? ? ? ??單鏈表中元素的反轉(zhuǎn)：點(diǎn)擊打開鏈接
? ? ? ? 判斷兩個數(shù)組中是否有相同的數(shù)字：點(diǎn)擊打開鏈接
? ? ? ? 從一個子序列中找出其最大子序列的和：點(diǎn)擊打開鏈接
? ? ? ? 按單詞反轉(zhuǎn)字符串：點(diǎn)擊打開鏈接
? ? ? ? 刪除數(shù)組中重復(fù)的元素：點(diǎn)擊打開鏈接
?
1、數(shù)組和鏈表的區(qū)別
? ? ? 數(shù)組不允許動態(tài)地定義其大小，只能夠?qū)⑵涠x成足夠大小，這樣可能會造成空間的浪費(fèi)。
? ? ? 數(shù)組在內(nèi)存中是順序的存儲，可以以O(shè)(1)時間查找元素，但是需要O(n)時間插入和刪除元素（因?yàn)槠浜竺娴脑囟夹枰苿?#xff09;。
? ? ? 鏈表可以動態(tài)地定義其大小。其在內(nèi)存中是鏈?zhǔn)降拇鎯?#xff0c;訪問元素是需要從頭開始向后順序訪問，所以需要O(n)時間查找元素；如果在所需位置直接插入或刪除元素，需要O(1)時間，如果在需要先找到所需位置再插入或刪除元素，需要O(n)時間。
2、鏈表的基本操作：反轉(zhuǎn)，是否存在環(huán)，循環(huán)鏈表點(diǎn)擊打開鏈接和雙向鏈表點(diǎn)擊打開鏈接的查找、插入、刪除操作。
3、棧的入棧和出棧：點(diǎn)擊打開鏈接，隊(duì)列的入隊(duì)和出隊(duì)：點(diǎn)擊打開鏈接
4、二叉樹的基礎(chǔ)知識：點(diǎn)擊打開鏈接及其三種遍歷（遞歸和非遞歸實(shí)現(xiàn)）：點(diǎn)擊打開鏈接
5、圖的基礎(chǔ)知識：點(diǎn)擊打開鏈接
6、常用散列函數(shù)和沖突消解機(jī)制：點(diǎn)擊打開鏈接
?
7、排序算法中基本的冒泡排序、選擇排序、插入排序需要很快地用代碼實(shí)現(xiàn)。堆排序、歸并排序、快速排序需要掌握其主要思想，并熟悉常用排序算法的時間和空間復(fù)雜度，及其應(yīng)用范圍：
? ? (1) 當(dāng)數(shù)據(jù)規(guī)模較小時，直接采用直接插入排序或直接選擇排序。
? ??(2) 當(dāng)數(shù)據(jù)已經(jīng)基本有序時，可以用直接插入排序或冒泡排序。
? ? (3) 當(dāng)數(shù)據(jù)規(guī)模較大時，可以用快速排序。當(dāng)記錄隨機(jī)分布時，快速排序的平均時間最短。當(dāng)最壞情況時，其時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)。
? ???(4) 堆排序所需的輔助空間比快排少，但這兩種方法都不穩(wěn)定。
? ? ?(5) 歸并排序既可以用于內(nèi)部排序，也可以用于外部排序，是一種穩(wěn)定的算法。
8、能熟練寫出二分查找的程序。
9、熟悉算法的思想：貪心算法，動態(tài)規(guī)劃，分治算法。
?
?
參考：https://www.cnblogs.com/houjun/p/4896268.html
總結(jié)
- 上一篇： 软文发布时标题怎么写，这几点值得注意！
- 下一篇： “抛弃 Gmail！”