對於將要參加計算機等級考試的考生來說,計算機等級考試的知識點輔導是非常重要的複習資料。以下是小編收集的資料庫技術知識資料結構的演算法,希望大家認真閱讀!
1、資料:資料的基本單位是資料元素。資料元素可由一個或多個數據項組成。資料項是資料的不可分割的最小單位
2、資料結構:資料的邏輯結構、資料的儲存結構、資料的運算
3、主要的資料儲存方式:順序儲存結構(邏輯和物理相鄰,儲存密度大)和鏈式儲存結構
順序儲存結構:
順序儲存計算公式 Li=L0+(i-1)×K 順序結構可以進行隨機存取;插人、刪除運算會引起相應節點的大量移動
鏈式儲存結構:a、指標域可以有多個,可以指向空,比比順序儲存結構的儲存密度小
b、邏輯上相鄰的節點物理上不一定相鄰。 c、插人、刪除等不需要大量移動節點
4、順序表:一般情況下,若長度為n的順序表,在任何位置插入或刪除的概率相等,元素移動的平均次數為n/2(插入)和(n-1)/2(刪除)。
5、連結串列:線性連結串列(單鏈表和雙向連結串列等等)和非線性連結串列
線性連結串列也稱為單鏈表,其每個一節點中只包含一個指標域,雙鏈表中,每個節點中設定有兩個指標域。(注意結點的'插入和刪除操作)
6、棧:“後進先出”(LIFO)表。棧的應用:表示式求解、二叉樹對稱序周遊、快速排序演算法、遞迴過程的實現等
7、佇列:“先進先出”線性表。應用:樹的層次遍歷
8、串:由零個或多個字元組成的有限序列。
9、多維陣列的順序儲存:
10、稀疏矩陣的儲存:下三角矩陣順序儲存
其他常見的儲存方法還有三元組法和十字連結串列法
11、廣義表:由零個或多個單元素或子表所組成的有限序列。廣義表的元素可以是子表,而子表的元素還可以是子表
12、樹型結構:非線性結構。常用的樹型結構有樹和二叉樹。
二叉樹與樹的區別:二叉樹不是樹的特殊情況,樹和二叉樹之間最主要的區別是:二叉樹的節點的子樹要區分左子樹和右子樹,即使在節點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。
13、樹(森林)與二叉樹之間的轉換(要會轉換)
14、二叉樹和樹的周遊(遍歷)
二叉樹的周遊主要有以下3種方式:前序法(NLR)、對稱序法(LNR)、後序法(LRN)
周遊樹和樹林:深度優先和按廣度優先兩種方式進行。深度優先方式又可分為按先根次序和按後根次序周遊
樹與二叉樹周遊之間的對應關係:按先根次序周遊樹正好與按前序法周遊樹對應的二叉樹等同,後根次序周遊樹正好與按對稱序法周遊對應的二叉樹等同
按廣度優先方式就是層次次序周遊
15、二叉樹的儲存和線索
二叉樹的儲存結構:二叉樹的llink一rlink法儲存表示
線索二叉樹:在有n個節點的二叉樹的且llink - rlink法儲存表示中,必定有n+1個空指標域
16、哈夫曼樹:一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。
17、查詢:
(1)順序查詢:平均查詢長度為(n +1 )/2次,時間複雜度為O(n)
(2)二分法查詢:線性表節點必須按關鍵碼值排序,且線性表是以順序儲存方式儲存的。查詢成功比較次數log2n,查詢失敗比較次數log2n+1
(3)分塊查詢:先是塊間查詢,然後塊內查詢。
(4)散列表(雜湊表Hash)的儲存和查詢:處理衝突的方法:開地址法(線性探測法)、拉鍊法等
負載因子(裝填因子)=表實際儲存的結點個數/表的最大能儲存結點個數(即表長)
二叉排序樹:每個結點左子樹的所有關鍵碼值都小於該結點關鍵碼值,右子樹所有結點關鍵碼值都大於該結點關鍵碼值。對稱周遊二叉排序樹,得到一個有序序列,時間複雜度O(log2n)
B樹和B+樹:M階樹,每個結點至多有M-1個關鍵碼,至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查詢,不適合順序查詢。B+樹適合順序查詢。
18、排序
直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序演算法要了解。
直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序,其他排序為穩定排序