(考前必看)02142數(shù)據(jù)導(dǎo)購結(jié)論知識點總結(jié)
如果有幫到你記得三連哦?。。?/strong>
第一章知識點總結(jié)：
1.數(shù)據(jù)分為：①數(shù)據(jù) ②數(shù)據(jù)元素 ③數(shù)據(jù)項
2.數(shù)據(jù)項分為：① 字段 ②域
3.基本的數(shù)據(jù)組織形式：①圖 ②樹 ③集合 ④線性
4.具有指數(shù)階的算法是不可計算的，具有平方階的算法是高效率的
5.空間復(fù)雜度指：除輸入數(shù)據(jù)占用的存儲空間之外所需要的附加存儲空間大小
6.數(shù)據(jù)的主要存儲方式：①順序 ②單鏈 ③索引 ④散列
7.評價算價好壞的方面：①健壯性 ②易讀性 ③正確性 ④時空性
8.估算管閥空間復(fù)雜度，只需要分析輔助變量所占用的空間。
9.算法的時間復(fù)雜度是在給定輸入下的計算量。?
10.算法是求給定問題的處理步驟和執(zhí)行順序
11.數(shù)據(jù)的邏輯結(jié)構(gòu)：①圖②樹③集合④線性
第二章線性表知識點總結(jié)：
1.單循環(huán)鏈表為空的條件：head-next=head
2.頭指針：確定線性表中第一個結(jié)點的存儲位置
3.頭結(jié)點：鏈表的第一個結(jié)點
4.指針變量：存放地址的變量
5.首結(jié)點：頭指針指向的下一個結(jié)點
6.查詢多的情況下用鏈表，反之順序表。
7.線性表的實現(xiàn)：①順序?qū)崿F(xiàn) ②鏈接實現(xiàn)
8.順序表的插入：
9.順序表的刪除：
10.順序表的定位：
11.單鏈表的讀表元素：
12.單鏈表的插入：
這里是重點中的重點哦
13.單鏈表的刪除
這里是重點中的重點哦
14.單鏈表建表的三個方法
方法一
方法二
方法三
15.單鏈表刪除重復(fù)的結(jié)點：
16.線性表是一對一。
第三章棧隊列數(shù)組知識點總結(jié)：
1.隊列滿的條件：((CQ.rear+1)%maxsize==CQ.front)??
2.隊列空的條件：CQ.rear==CQ.front
3.數(shù)組采用的線性存儲結(jié)構(gòu)。
4.判斷隊列為空：
5.入隊列
6.鏈棧的進棧：
7.鏈棧的出棧：
8.順序棧的進棧：
9.順序棧的出棧：
10.對稀疏矩陣采用三元組是節(jié)省空間。
11.棧中允許進行插入和刪除的一端是棧頂
12.n^2元素可以壓縮存儲到n(n+1)/2個元素的一維數(shù)組中。
第四章樹和二叉樹知識點總結(jié)：
1.二叉樹的基本形態(tài)：①空二叉樹?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ②只有根結(jié)點的二叉樹?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ③只有根結(jié)點和左子樹的二叉樹?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ④只有根結(jié)點和右子樹的二叉樹?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ⑤只有根結(jié)點和左子樹、右子樹的二叉樹
2.一棵判定樹描述了一種分類方法
3.中序遍歷一顆二叉樹可以得到一個有序序列
4.一顆樹中所有結(jié)點的度的最大值稱為該樹的度。
5.深度為k的二叉樹之多有2^k-1的結(jié)點，二叉樹第i層至多有2^(i-1)和結(jié)點，n0=n2+1。
6.一棵樹結(jié)點最少為0稱為空樹。
7.滿二叉樹一定是完全二叉樹，反之。含有n個結(jié)點的二叉樹深度為[log2^n]+1
8.任意編號i的結(jié)點A有：i=1，A是根。2i>n,A左右孩子，2i+1>n,A無右孩子，否則為2i+1
第五章圖知識點總結(jié)：
1.一個具有N個頂點的無向完全圖的邊數(shù)是n(n-1)/2，一個具有n個頂點有向完全圖的弧數(shù)n(n-1)
2任何兩點之間都有邊的無向圖稱為無向完全圖。
3.任何沒有回路的無向圖可以排成一個拓?fù)渑判颉?/strong>
4.圖的定義：V：頂點的有窮非空集合 E：邊得集合（弧）
5.無向圖的(v,w)與(w,v)是同一條邊，有向圖的<v,w>與<w，v>是不同的兩條弧。
6.任何兩點之間有邊的無向圖稱為無向完全圖。
7.一個具有n個頂點的無向完全圖的邊數(shù)為n(n-1)/2。
8.一個具有n個頂點的有向完全圖的弧數(shù)為：n(n-1)。
9.頂點的度：? ?無向圖：例：v0——————v1? v0的度就是與它相關(guān)邊的數(shù)目也就是1(v0)
? ? ? ? ? ? ? ? ? ? ? ? 有向圖：以頂點V為終點的弧的數(shù)目稱為V的入度記作ID(V)
? ? ? ? ? ? ? ? ? ? ? ? 以頂點V為始點的弧的數(shù)目稱為V的出度記為OD(V)
? ? ? ? ? ? ? ? ? ? ? ? 有向圖中頂點V的度為出入度的和也就是D(V)=ID(V)+OD(V)
10.簡單路徑：不重復(fù)出現(xiàn)的路徑稱為簡單路徑
? ? ? ? ? ? 回路：第一個頂點和最后一個頂點相同的路徑稱為回路
? ? ??簡單回路：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)的回路
11.圖的遍歷方式：①深度優(yōu)先搜索(遞歸) ②廣度優(yōu)先搜索（有向圖和無向圖）
12.對于N的頂點的無向圖，所有生成樹有N-1條邊
13.構(gòu)造最小生成樹的兩種方法：
①Prim方法 思想：從v0出發(fā)找V0權(quán)值最小的相鄰邊Vn，再從Vn出找Vn的最小相鄰邊知道最后一個
②克魯斯科爾方法 思想：把一個圖初始化為只有n個頂點而無邊的非連通圖，那么每一個頂點就是一個連通分量
然后，在從邊的集合中找權(quán)值最小的連起來，重復(fù)此步驟直到所有頂點都在一個連通分量
14.拓?fù)渑判駻OV網(wǎng)中不允許有回路。（有向圖）
15.拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是O（n+e）。n是頂點e是弧的數(shù)目。
16.圖的應(yīng)用：①最小生成樹 ②單元最短路徑 ③拓?fù)渑判?/strong>
17.具有N個頂點的無向圖最多有N*(N+1)/2條邊。
18.無向圖的鄰接矩陣是對稱的。
19.有向圖的鄰接表實際是看頂點i的出度，而有向圖的逆鄰接表實際是看頂點i的入度。
第六章查找知識點總結(jié)：
1.查找表的邏輯結(jié)構(gòu)是集合。
2.完成拓?fù)渑判虻那疤崾茿OV中不允許出現(xiàn)回路
3.二次探測法缺點：不易探測整個散列表的所有空間
4.多重散列法不易產(chǎn)生堆積
5.散列函數(shù)的m一般取素數(shù)
6.完全避免堆積采用鏈地址法。
7.散列函數(shù)的p平常取接近表長的質(zhì)數(shù)
8.H(k1)=H(k2)這種現(xiàn)象是沖突，k1和k2是相對于H的同義詞。
第七章排序知識點總結(jié)：
1.直接插入排序的表長下標(biāo)從1開始。
