一估蹄、單純的數(shù)據(jù)結(jié)構(gòu)
1.棧和隊列共同特點：只允許在端點處插入和刪除元素
2.線性表：
順序存儲結(jié)構(gòu)：查找快O(1)偷遗，增刪慢O(n)向楼，好處是便于查找
鏈式存儲結(jié)構(gòu)：查找慢O(n)兰吟，增刪快O(1)。鏈表內(nèi)存中可用的存儲單元的地址可以是連續(xù)的也可以是不連續(xù)的套鹅。好處是便于插入和刪除操作。
程撸考：
單鏈表中，增加頭結(jié)點的目的：方便運算的實現(xiàn)
循環(huán)鏈表的優(yōu)點：從表中任一結(jié)點出發(fā)都能訪問到整個鏈表菱魔。
非空的循環(huán)單鏈表head的尾結(jié)點（p指向）滿足：p->next=head
線性表：除了第一個和最后一個元素留荔，其余每個元素有且只有一個直接前驅(qū)和直接后繼。
線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的澜倦，且各元素的存儲順序也是任意的聚蝶。
與單向鏈表相比，雙向鏈表的優(yōu)點之一是：更容易訪問相鄰結(jié)點藻治。
3.數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示
數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結(jié)構(gòu)
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關系的復雜程度碘勉，一般將數(shù)據(jù)結(jié)構(gòu)分為：線性結(jié)構(gòu)和非線性結(jié)構(gòu)
4.棧：是先進后出的線性表
數(shù)據(jù)結(jié)構(gòu)中具有記憶功能的是棧。
由兩個棧共享一個存儲空間的好處：節(jié)省存儲空間桩卵，降低上溢發(fā)生的機率验靡。
棧的基本運算：入棧雏节、退棧與讀棧頂元素
5.隊列：先進先出的線性表
遞歸算法一般用隊列實現(xiàn)
隊列的基本運算：入隊和出隊胜嗓。
6.線性結(jié)構(gòu)：其特點是數(shù)據(jù)元素之間存在一對一的線性關系。線性結(jié)構(gòu)擁有兩種不同的存儲結(jié)構(gòu)钩乍，即順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)辞州。
線性表、隊列寥粹、棧屬于線性結(jié)構(gòu)变过。但隊列和棧是受限的線性結(jié)構(gòu)。
二叉樹屬于非線性數(shù)據(jù)結(jié)構(gòu)
7涝涤、樹：
在第n層的二叉樹上總節(jié)點數(shù)最多是2^n-1
深度為n的滿二叉樹媚狰，葉子節(jié)點個數(shù)為2^(n-1)
完全二叉樹的總結(jié)點數(shù)為N，N為奇數(shù)阔拳，則葉子節(jié)點數(shù)位（N+1）/2哈雏；N為偶數(shù)，則葉子節(jié)點數(shù)位N/2
8衫生、串的長度是：串中所含字符的個數(shù)
9.圖：
10裳瘪。常用的存儲結(jié)構(gòu)：順序、鏈接罪针、索引等存儲結(jié)構(gòu)
11彭羹、數(shù)組和鏈表的區(qū)別。（很簡單泪酱，但是很撑梢螅考还最，記得要回答全面）
C++語言中可以用數(shù)組處理一組數(shù)據(jù)類型相同的數(shù)據(jù)，但不允許動態(tài)定義數(shù)組的大小毡惜，即在使用數(shù)組之前必須確定數(shù)組的大小拓轻。而在實際應用中，用戶使用數(shù)組之前無法確定數(shù)組的大小经伙，只能夠?qū)?shù)組定義成足夠大小扶叉，這樣數(shù)組的空間可能不被使用，從而造成內(nèi)存空間的浪費帕膜。鏈表是一種常見的數(shù)據(jù)組織形式枣氧，他采用動態(tài)分配內(nèi)存的形式實現(xiàn)。需要時可以用new分配內(nèi)存空間垮刹，不需要時用delete將已分配的空間釋放达吞，不會造成內(nèi)存空間的浪費。
從邏輯結(jié)構(gòu)上來看荒典，數(shù)組必須實現(xiàn)定于固定的長度酪劫，不能適應數(shù)據(jù)動態(tài)增減的情況，即數(shù)組的大小一旦定義就不能改變寺董。當數(shù)據(jù)增加是契耿，可能超過原先定義的元素的個數(shù)；當數(shù)據(jù)減少時螃征，造成內(nèi)存浪費搪桂；鏈表動態(tài)進行存儲分配，可以適應數(shù)據(jù)動態(tài)地增減的情況盯滚，且可以方便地插入踢械、刪除數(shù)據(jù)項。
從內(nèi)存存儲的角度看魄藕；數(shù)組從棧中分配空間（用new則在堆上創(chuàng)建）内列，對程序員方便快速，但是自由度斜陈省话瞧；鏈表從堆中分配空間，自由度大但是申請管理比較麻煩寝姿。
從訪問方式類看交排，數(shù)組在內(nèi)存中是連續(xù)的存儲，因此可以利用下標索引進行訪問饵筑；鏈表是鏈式存儲結(jié)構(gòu)埃篓，在訪問元素時候只能夠通過線性方式由前到后順序的訪問，所以訪問效率比數(shù)組要低根资。
二架专、數(shù)據(jù)結(jié)構(gòu)與算法：
（一）排序算法：
1同窘、插入排序：
直接插入排序：從后往前找合適的位置，直接插入
二分插入排序：用二分法找合適的位置部脚，插入
希爾排序：
2想邦、選擇排序：
簡單選擇排序：每次選最小的或者最大的換到第一位
堆排序：二叉樹然后換換
3、交換排序：
冒泡排序：比較兩個相鄰的數(shù)之間的關系與排序要求是否一致委刘，不一致則交換
快速排序：每輪以第一個數(shù)作為基準丧没，從后往前找比基準小的數(shù)，進行交換钱雷，再從前往后找比基準大的數(shù)進行交換，直到基準所在的位置前面的數(shù)都比他小吹零，后面的數(shù)都比他大罩抗。
4、歸并排序：已經(jīng)排好序的2個或以上的數(shù)組再進行歸并排序
5灿椅、基數(shù)排序：所有數(shù)值統(tǒng)一為同樣的數(shù)位長度套蒂，數(shù)位較短的前面補0，從最低位開始排序到最高位茫蛹。
最基本的是冒泡排序操刀，選擇排序，插入排序要可以很快地用代碼實現(xiàn)婴洼。這些主要考察你的實際編碼能力骨坑。堆排序，歸并排序柬采，快速排序這些算法需要熟悉主要思想欢唾，和需要注意的細節(jié)地方。
（二）查找算法：
二分查找
圖之深度優(yōu)先與廣度優(yōu)先：
深度優(yōu)先：從某個頂點v出發(fā)粉捻，首先訪問該頂點礁遣，然后依次從它的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到肩刃。 若此時尚有其他頂點未被訪問到祟霍，則另選一個未被訪問的頂點作起始點，重復上述過程盈包，直至圖中所有頂點都被訪問到為止沸呐。
無向圖的深度優(yōu)先：
ADBDFGE
有向圖的深度優(yōu)先：
ABCEDFG
廣度優(yōu)先：又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索"，簡稱BFS呢燥。
從圖中某頂點v出發(fā)垂谢，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點疮茄，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問滥朱，直至圖中所有已被訪問的頂點的鄰接點都被訪問到根暑。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點徙邻，重復上述過程排嫌，直至圖中所有頂點都被訪問到為止。
無向圖的廣度優(yōu)先：
ACDFBGE
有向圖的廣度優(yōu)先：
ABCEFDG
注意缰犁！:1淳地、同層的則按字母順序優(yōu)先；2帅容、如果是從鄰接圖演變的颇象，鄰接圖是有順序的，按那個順序并徘。
148遣钳、求圖的拓撲序列（只有有向圖有）：找出圖中無前驅(qū)節(jié)點的節(jié)點，依次輸出刪去麦乞。一個圖的拓撲序列可以有多種蕴茴。
深度優(yōu)先和拓撲序列可以判斷出一個有向圖是否有環(huán)。
