數據結構與演算法知識點

① 計算機二級c語言知識點

2017計算機二級c語言知識點精選

計算機二級C語言考試內容是什麼?為幫助大家更好備考3月計算機考試，我為大家分享計算機C語言二級考試知識點如下：

第一章 數據結構與演算法

1.1 演算法

1.演算法的基本概念

(1) 概念：演算法是指一系列解決問題的清晰指令。

(2) 4個基本特徵：可行性、確定性、有窮性、擁有足夠的情報。

(3) 兩種基本要素：對數據對象的運算和操作、演算法的控制結構(運算和操作時問的順序)。

(4) 設計的基本方法：列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。

2.演算法的復雜度

(1) 演算法的時間復雜度：執行演算法所需要的計算工作量。

(2) 演算法的空間復雜度：執行演算法所需的內存空間。

1.2 數據結構的基本概念

數據結構指相互有關聯的數據元素的集合，即數據的組織形式。其中邏輯結構反映數據元素之間邏輯關系;存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式，有順序存儲、鏈式存儲、索引存儲和散列存儲4種方式。

數據結構按各元素之間前後件關系的復雜度可劃分為：

(1) 線性結構：有且只有一個根節點，且每個節點最多有一個直接前驅和一個直接後繼的非空數據結構。

(2) 非線性結構：不滿足線性結構的數據結構。

1.3 線性表及其順序存儲結構

1.線性表的基本概念

線性結構又稱線性表，線性表是最簡單也是最常用的一種數據結構。

2.線性表的順序存儲結構

元素所佔的存儲空間必須連續。

元素在存儲空間的位置是按邏輯順序存放的。

3.線性表的插入運算

在第i個元素之前插入一個新元素的步驟如下：

步驟一：把原來第n個節點至第i個節點依次往後移一個元素位置。

步驟二：把新節點放在第i個位置上。

步驟三：修正線性表的節點個數。

在最壞情況下，即插入元素在第一個位置，線性表中所有元素均需要移動。

4.線性表的刪除運算

刪除第i個位置的元素的步驟如下：

步驟一：把第i個元素之後不包括第i個元素的n-i個元素依次前移一個位置;

步驟二：修正線性表的結點個數。

1.4 棧和隊列

1.棧及其基本運算

(1) 基本概念：棧是一種特殊的線性表，其插入運算與刪除運算都只在線性表的一端進行，也被稱為「先進後出」表或「後進先出」表。

棧頂：允許插入與刪除的一端。

棧底：棧頂的另一端。

空棧：棧中沒有元素的棧。

(2) 特點。

棧頂元素是最後插入和最早被刪除的元素。

棧底元素是最早插入和最後被刪除的元素。

棧有記憶作用。

在順序存儲結構下，棧的插入和刪除運算不需移動表中其他數據元素。

棧頂指針top動態反映了棧中元素的變化情況

(3) 順序存儲和運算：入棧運算、退棧運算和讀棧頂運算。

2.隊列及其基本運算

(1) 基本概念：隊列是指允許在一端進行插入，在另一端進行刪除的線性表，又稱「先進先出」的線性表。

隊尾：允許插入的一端，用尾指針指向隊尾元素。

排頭：允許刪除的一端，用頭指針指向頭元素的前一位置。

(2) 循環隊列及其運算。

所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間。

入隊運算是指在循環隊列的隊尾加入一個新元素。

當循環隊列非空(s=1)且隊尾指針等於隊頭指針時，說明循環隊列已滿，不能進行人隊運算，這種情況稱為「上溢」。

退隊運算是指在循環隊列的隊頭位置退出一個元素並賦給指定的變數。首先將隊頭指針進一，然後將排頭指針指向的元素賦給指定的變數。當循環隊列為空(s=0)時，不能進行退隊運算，這種情況稱為「下溢」。

1.5 線性鏈表

在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。

在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用於存放數據元素值，稱為數據域;另一部分用於存放指針，稱為指針域。其中指針用於指向該結點的前一個或後一個結點(即前件或後件)。

1.6 樹和二叉樹

1.樹的基本概念

樹是簡單的非線性結構，樹中有且僅有一個沒有前驅的節點稱為「根」，其餘節點分成m個互不相交的有限集合T1，T2，…，T}mm，每個集合又是一棵樹，稱T1，T2，…，T}mm為根結點的子樹。

父節點：每一個節點只有一個前件，無前件的節點只有一個，稱為樹的根結點(簡稱樹的根)。

子節點：每～個節點可以後多個後件，無後件的節點稱為葉子節點。

樹的度：所有節點最大的度。

樹的深度：樹的最大層次。

2.二叉樹的定義及其基本性質

(1) 二叉樹的定義：二叉樹是一種非線性結構，是有限的節點集合，該集合為空(空二叉樹)或由一個根節點及兩棵互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹，其中滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個特點：

二叉樹可為空，空的二叉樹無節點，非空二叉樹有且只有一個根結點;

每個節點最多可有兩棵子樹，稱為左子樹和右子樹。

(2) 二叉樹的基本性質。

性質1：在二叉樹的第k層上至多有2k-1個結點(k≥1)。

性質2：深度為m的二叉樹至多有2m-1個結點。

性質3：對任何一棵二叉樹，度為0的結點(即葉子結點)總是比度為2的結點多一個。

性質4：具有n個結點的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數部分。

3.滿二叉樹與完全二叉樹

(1) 滿二叉樹：滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。滿二叉樹在其第i層上有2i-1個結點。

從上面滿二叉樹定義可知，二叉樹的每一層上的結點數必須都達到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個結點。

(2) 完全二叉樹：完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。

如果—棵具有n個結點的深度為k的二叉樹，它的每—個結點都與深度為k的滿二叉樹中編號為1～n的結點——對應。

3.二叉樹的存儲結構

二叉樹通常採用鏈式存儲結構，存儲節點由數據域和指針域(左指針域和右指針域)組成。二叉樹的鏈式存儲結構也稱二叉鏈表，對滿二叉樹和完全二叉樹可按層次進行順序存儲。

4.二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中所有節點，主要指非空二叉樹，對於空二叉樹則結束返回。二叉樹的遍歷包括前序遍歷、中序遍歷和後序遍歷。

(1) 前序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。前序遍歷描述為：若二叉樹為空，則執行空操作;否則①訪問根結點;②前序遍歷左子樹;③前序遍歷右子樹。

(2) 中序遍歷。

中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。中序遍歷描述為：若二叉樹為空，則執行空操作;否則①中序遍歷左子樹;②訪問根結點;③中序遍歷右子樹。

(3) 後序遍歷。

後序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。後序遍歷描述為：若二叉樹為空，則執行空操作;否則①後序遍歷左子樹;②後序遍歷右子樹;③訪問根結點。

1.7 查找技術

(1) 順序查找：在線性表中查找指定的元素。

(2) 最壞情況下，最後一個元素才是要找的元素，則需要與線性表中所有元素比較，比較次數為n。

(3) 二分查找：二分查找也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制，它要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可)排列。對長度為n的有序線性表，在最壞情況下，二分查找法只需比較log2n次。

1.8 排序技術

(1) 交換類排序法。

冒泡排序：通過對待排序序列從後向前或從前向後，依次比較相鄰元素的排序碼，若發現逆序則交換，使較大的元素逐漸從前部移向後部或較小的元素逐漸從後部移向前部，直到所有元素有序為止。在最壞情況下，對長度為n的線性表排序，冒泡排序需要比較的次數為n(n-1)/2。

快速排序：是迄今為止所有內排序演算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準(一般取第一個元素)，通過一趟排序，將待排元素分為左右兩個子序列，左子序列元索的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。最壞情況下，即每次劃分，只得到一個序列，時間效率為O(n2)。

(2) 插人類排序法。

簡單插入排序法：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。在最壞情況下，即初始排序序列是逆序的情況下，比較次數為n(n-1)/2，移動次數為n(n-1)/2。

希爾排序法：先將整個待排元素序列分割成若干個子序列(由相隔某個「增量」的元素組成的)分別進行直接插入排序。待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。

(3) 選擇類排序法。

簡單選擇排序法：掃描整個線性表。從中選出最小的元素。將它交換到表的最前面;然後對剩下的子表採用同樣的方法，直到子表空為止。最壞情況下需要比較n(n-1)/2次。

堆排序的方法：首先將一個無序序列建成堆;然後將堆頂元素(序列中的最大項)與堆中最後一個元素交換(最大項應該在序列的最後)。不考慮已經換到最後的那個元素，只考慮前n-1個元素構成的子序列，將該子序列調整為堆。反復做步驟②，直到剩下的子序列空為止。在最壞情況下，堆排序法需要比較的次數為0(nlog2n)

第二章 程序設計基礎

2.1 程序設計方法與風格

(1)設計方法：指設計、編制、調試程序的方法和過程，主要有結構化程序設計方法、軟體工程方法和面向對象方法。

(2)設計風格：良好的'設計風格要注重源程序文檔化、數據說明方法、語句的結構和輸入輸出。

2.2 結構化程序設計

1.結構化程序設計的原則

結構化程序設計強調程序設計風格和程序結構的規范化，提倡清晰的結構。。

(1)自頂向下：即先考慮總體，後考慮細節;先考慮全局目標，後考慮局部目標。

(2)逐步求精：對復雜問題，應設計一些子目標做過渡，逐步細化。

(3)模塊化：把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊;

(4)限制使用GOT0語句。

2.結構化程序的基本結構與特點

(1)順序結構：自始至終嚴格按照程序中語句的先後順序逐條執行，是最基本、最普遍的結構形式。

(2)選擇結構：又稱為分支結構，包括簡單選擇和多分支選擇結構。

(3)重復結構：又稱為循環結構，根據給定的條件，判斷是否需要重復執行某一相同的或類似的程序段。

結構化程序設計中，應注意事項：

(1)使用程序設計語言中的順序、選擇、循環等有限的控制結構表示程序的控制邏輯。

(2)選用的控制結構只准許有一個人口和一個出口。

(3)程序語言組成容易識別的塊，每塊只有一個入口和一個出口。

(4)復雜結構應該用嵌套的基本控制結構進行組合嵌套來實現。

(5)語言中所沒有的控制結構，應該採用前後一致的方法來模擬。

(6)盡量避免GOT0語句的使用。

2.3 面向對象的程序設計

面向對象方法的本質是主張從客觀世界固有的事物出發來構造系統，強調建立的系統能映射問題域。

對象：用來表示客觀世界中任何實體，可以是任何有明確邊界和意義的東西。

類：具有共同屬性、共同方法的對象的集合。

實例：一個具體對象就是其對應分類的一個實例。

消息：實例間傳遞的信息，它統一了數據流和控制流。

繼承：使用已有的類定義作為基礎建立新類的定義技術。

多態性：指對象根據所接受的信息而作出動作，同樣的信息被不同的對象接收時有不同行動的現象。面向對象程序設計的優點：與人類習慣的思維方法一致、穩定性好、可重用性好、易於開發大型軟體產品、可維護性好。

第三章 軟體工程基礎

3.1 軟體工程基本概念

1.軟體的定義與特點

(1)定義：軟體是指與計算機系統的操作有關的計算機程序、規程、規則，以及可能有的文件、文檔和數據。

(2)特點。

是邏輯實體，有抽象性。

生產沒有明顯的製作過程。

運行使用期間不存在磨損、老化問題。

開發、運行對計算機系統有依賴性，受計算機系統的限制，導致了軟體移植問題。

復雜性較高，成本昂貴。

開發涉及諸多社會因素。

2.軟體的分類

軟體可分應用軟體、系統軟體和支撐軟體3類。

(1)應用軟體是特定應用領域內專用的軟體。

(2)系統軟體居於計算機系統中最靠近硬體的一層，是計算機管理自身資源，提高計算機使用效率並為計算機用戶提供各種服務的軟體。

(3)支撐軟體介於系統軟體和應用軟體之間，是支援其它軟體的開發與維護的軟體。

3.軟體危機與軟體工程

軟體危機指在計算機軟體的開發和維護中遇到的一系列嚴重問題。軟體工程是應用於計算機軟體的定義、開發和維護的一整套方法、工具、文檔、實踐標准和工序，包括軟體開發技術和軟體工程管理。

4.軟體生命周期

軟體產品從提出、實現、使用維護到停止使用的過程稱為軟體生命周期。

在國家標准中，軟體生命周期劃分為8個階段①軟體定義期：包括問題定義、可行性研究和需求分析3個階段。②軟體開發期：包括概要設計、詳細設計、實現和測試4個階段。③運行維護期：即運行維護階段。

5.軟體工程的原則

軟體工程的原則包括：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。

3.2 結構化分析方法

需求分析的任務是發現需求、求精、建模和定義需求的過程，可概括為：需求獲取、需求分析、編寫需求規格說明書和需求評審。

1.常用的分析方法

結構化分析方法：其實質著眼於數據流，自頂向下，逐層分解，建立系統的處理流程。

面向對象分析方法。

2.結構化分析常用工具

結構化分析常用工具包括數據流圖、數字字典(核心方法)、判斷樹和判斷表。

(1)數據流圖：即DFD圖，以圖形的方式描繪數據在系統中流動和處理的過程，它只反映系統必須完成的邏輯功能。是一種功能模型。

符號名稱作用：

箭頭代表數據流，沿箭頭方向傳送數據的通道

圓或橢圓代表加工，輸入數據經加工變換產生輸出

雙杠代表存儲文件，表示處理過程中存放各種數據文件

方框代表源和潭，表示系統和環境的介面

(2)數據字典：結構化分析方法的核心。數據字典是對所有與系統相關的數據元素的一個有組織的列表。以及精確的、嚴格的定義，使得用戶和系統分析員對於輸入、輸出、存儲成分和中間計算結果有共同的理解。

(3)判定樹：使用判定樹進行描述時，應先從問題定義的文字描述中分清判定的條件和判定的結論，根據描述材料中的連接詞找出判定條件之問的從屬關系、並列關系、選擇關系，根據它們構造判定樹。

(4)判定表：與判定樹相似，當數據流圖中的加工要依賴於多個邏輯條件的取值，即完成該加工的一組動作是由於某一組條件取值的組合引發的，使用判定表比較適宜。

3.軟體需求規格說明書

軟體需求規格說明書是需求分析階段的最後成果，是軟體開發的重要文檔之一。

(1)軟體需求規格說明書的作用：①便於用戶、開發人員進行理解和交流;②反映出用戶問題的結構，可以作為軟體開發工作的基礎和依據;③作為確認測試和驗收的依據。

(2)軟體需求規格說明書的內容：①概述;②數據描述;③功能描述;④性能描述;⑤參考文獻;⑥附錄。

(3)軟體需求規格說明書的特點：①正確性;②無歧義性;③完整性;④可驗證性;⑤一致性;⑥可理解性;⑦可修改性;⑧可追蹤性。

3.3 結構化設計方法

1.軟體設計的基本概念和方法

軟體沒計是一個把軟體需求轉換為軟體表示的過程。

(1)基本原理：抽象、模塊化、信息隱藏、模塊獨立性(度量標准：耦合性和內聚性，高耦合、低內聚)。

(2)基本思想：將軟體設計成由相對獨立、單一功能的模塊組成的結構。

2.概要設計

(1)4個任務：設計軟體系統結構、數據結構及資料庫設計、編寫概要設計文檔、概要設計文檔評審。

(2)面向數據流的設計方法：數據流圖的信息分為交換流和事物流，結構形式有交換型和事務型。

3.詳細設計的工具

詳細設計的工具包括：

圖形工具：程序流程圖、N-S、PAD、HIPO。

表格工具：判定表。

語言工具：PDL(偽碼)。

3.4 軟體測試

1.目的

為了發現錯誤而執行程序的過程。

2.准則

所有測試應追溯到用戶需求。

嚴格執行測試計劃，排除測試的隨意性。

充分注意測試中的群集現象。

程序員應避免檢查自己的程序。

窮舉測試不可能。

妥善保存設計計劃、測試用例、出錯統計和最終分析報告。

3.軟體測試技術和方法

軟體測試的方法按是否需要執行被測軟體的角度，可分為靜態測試和動態測試，按功能分為白盒測試和黑盒測試。

(1)白盒測試：根據程序的內部邏輯設計測試用例，主要方法有邏輯覆蓋測試、基本路徑測試等。

(2)黑盒測試：根據規格說明書的功能來設計測試用例，主要診斷方法有等價劃分法、邊界值分析法、錯誤推測法、因果圖法等，主要用於軟體確認測試。

4.軟體測試的實施

軟體測試是保證軟體質量的重要手段，軟體測試是一個過程，其測試流程是該過程規定的程序，目的是使軟體測試工作系統化。

軟體測試過程分4個步驟，即單元測試、集成測試、驗收測試和系統測試。

單元測試是對軟體設計的最小單位——模塊(程序單元)進行正確性檢驗測試。

單元測試的目的是發現各模塊內部可能存在的各種錯誤。

單元測試的依據是詳細的設計說明書和源程序。

單元測試的技術可以採用靜態分析和動態測試。

3.5 程序的調試

(1)任務：診斷和改正程序中的錯誤。

(2)調試方法：強行排錯法、回溯法和原因排除法。

第四章 資料庫設計基礎

4.1 資料庫系統的基本概念

(1) 數據(Data)：描述事物的符號記錄。

(2) 資料庫(DataBase)：長期存儲在計算機內的、有組織的、可共享的數據集合。

(3) 資料庫管理系統的概念

資料庫管理系統(DataBase Management System，DBMS)是資料庫的機構，它是一種系統軟體，負責資料庫中的數據組織、數據操作、數據維護、數據控制及保護和數據服務等。為完成以上6個功能，DBMS提供了相應的數據語言;數據定義語言(負責數據的模式定義與數據的物理存取構建);數據操縱語言(負責數據的操縱);數據控制語言(負責數據完整性、安全性的定義)。資料庫管理系統是資料庫系統的核心，它位於用戶和操作系統之間，從軟體分類的角度來說，屬於系統軟體。

(4) 資料庫技術發展經歷了3個階段。

人工管理階段→文件系統階段→資料庫系統階段

(5) 資料庫系統的特點：集成性、高共享性、低冗餘性、數據獨立性、數據統一管理與控制等。

(6) 資料庫系統的內部機構體系：三級模式(概念模式、內模式、外模式)和二級映射(外模式/概念模式的映射、概念模式/內模式的映射)構成了資料庫系統內部的抽象結構體系。

4.2 數據模型

數據模型是數據特徵的抽象，從抽象層次上描述了系統的靜態特徵、動態行為和約束條件，描述的內容有數據結構、數據操作和數據約束。有3個層次：概念數據模型、邏輯數據模型和物理數據模型。

(1) E—R模型：提供了表示實體、屬性和聯系的方法。實體間聯系有「一對一」、「一對多」和「多對多」。

(2) E-R模型用E-R圖來表示。

(3) 層次模型：利用樹形結構表示實體及其之問聯系。其中節點是實體，樹枝是聯系，從上到下是一對多關系。

(4) 網狀模型：用網狀結構表示實體及其之間聯系。是層次模型的擴展。網路模型以記錄型為節點，反映現實中較為復雜的事物聯系。

(5) 關系模型：採用二維表(由表框架和表的元組組成)來表示，可進行數據查詢、增加、刪除及修改操作。關系模型允許定義「實體完整性」、「參照完整性」和「用戶定義的完整性」三種約束。

鍵(碼)：二維表中唯一能標識元組的最小屬性集。

候選鍵(候選碼)：二維表中可能有的多個鍵。

主鍵：被選取的一個使用的鍵。

4.3 關系代數

(1) 關系代數的基本運算：投影、選擇、笛卡爾積。

(2) 關系代數的擴充運算：交、連接與自然連接、除。

4.4 資料庫設計與管理

1.資料庫設計概述

基本思想：過程迭代和逐步求精。

方法：面向數據的方法和面向過程的方法。

設計過程：需求分析→概念設計→邏輯設計→物理設計→編碼→測試→運行→進→步修改。

2.資料庫設計的需求分析

需求收集和分析是資料庫設計的第一階段，常用結構化分析方法(自頂向下、逐層分解)和面向對象的方法，主要工作有繪制數據流程圖、數據分析、功能分析、確定功能處理模塊和數據間關系。

數據字典：包括數據項、數據結構、數據流、數據存儲和處理過程，是對系統中數據的詳盡描述。

3.資料庫的設計

(1) 資料庫的概念設計：分析數據問內在的語義關聯，以建立數據的抽象模型。

(2) 資料庫的邏輯設計：從E-R圖向關系模型轉換，邏輯模式規范化，關系視圖設計可以根據用戶需求隨時創建。實體轉換為元組，屬性轉換為關系的屬性，聯系轉換為關系。

(3) 資料庫的物理設計：是數據在物理設備上的存儲結構與存取方法，目的是對資料庫內部物理結構作出調整並選擇合理的存取路徑，以提高速度和存儲空間。

4.資料庫管理

資料庫管理包括資料庫的建立、資料庫的調整、資料庫的重組、資料庫的安全性與完整性控制、資料庫故障恢復和資料庫的監控。

;

② 數據結構知識點總結

線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元里。是隨機存取的順序存儲結構。順序存儲指內存地址是一塊的，隨機存取指訪問時可以按下標隨機訪問，存儲和存取是不一樣的。

用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。鏈表中結點的邏輯次序和物孫畢帆理次序不一定相同。

隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。先進先出。

串(String)是零個或多個字元組成的有限序列。長度為零的串稱為空串(Empty String)，它不包含任何字元。通常將僅由一個或多個空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如「 」和「」分別表示長度為1的空白串和長度為0的空串。

串的表示和實現

數組和廣義表可看成是一種特殊的線性表，其特殊在於: 表中的元素本身也是一種線性表。內存連續。根據下標在O(1)時間讀/寫任何元素。
二維數組，多維數組，廣義表，樹，圖都屬於非線性結構

數組
數組的順序存儲：行優先順序；列優先順序。數組中的任一元素可以在相同的時間內存取，即順序存儲的數組是一個隨機存取結構。

關聯數組(Associative Array)，又稱映射（Map）、字典（ Dictionary）是一個抽象的數據結構，它包含著類似於(鍵，值)的有序對。 不是線性表。

廣義表
廣義表（Lists，又稱列表）是線性表的推廣。廣義表是n(n≥0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。若廣義表LS（n>=1)非空，則a1是LS的表頭，其餘元素組成的表(a2,…an)稱為LS的表尾。廣義表的元素可以是廣義表，也可以是原子，廣義表的元素也可以為空。表尾是指除去表頭後剩下的元素組成的表，表頭可以為表或單元素值。所以表尾不可以是單個元素值。

三個結論

考點

一種非線性結構。樹是遞歸結構，在樹的定義中又用到了樹的概念。

基本術語
1.樹結點：包含一個數據元素及若干指向子樹的分支；
2.孩子結點：結點的子樹的根稱為該結點的孩子；
3.雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；
4.兄弟結點：同一雙親的孩子結點；
5.堂兄結點：同一層上結點；
6.結點層次：根結點的層定義為1；根的孩子為第二層結點，依此類推；
7.樹的高（深）度：樹中最大的結點層
8.結點的度：結點子樹的個數，就是有幾個孩子
9.樹的度： 樹中最大的結點度。
10.葉子結點：也叫終端結點，是度為0的結點；
11.分枝結點：度不為0的結點（非終端結點）；
12.森林：互不相交的樹集合；
13.有序樹：子樹有序的樹，如：家族樹；
14.無序樹：不考慮子樹的順序；

二叉樹
二叉樹可以為空。二叉樹結點的子樹要區分左子樹和右子樹，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。
注意區分： 二叉樹、二叉查找樹/二叉排序數念樹/二叉搜索樹、二叉平衡(查找)樹

二叉樹遍歷
先序遍歷：根左右
中序遍歷：左根右
後序遍歷：左右根
層次遍歷：一維數組存儲二叉樹，總是以層次遍歷的順序存儲結點。層次遍歷應該藉助隊列。

二叉樹性質
1.在二叉樹的第 i 層上至多有2的i次冪-1個結點
2.深度為 k 的二叉樹上至多含 2的k次冪-1 個結點（k≥1）
3.樹與轉換後的二叉樹的關系：轉則雹換後的二叉樹的先序對應樹的先序遍歷；轉換後的二叉樹的中序對應樹的後序遍歷

一些概念
1.路徑：從一個祖先結點到子孫結點之間的分支構成這兩個結點間的路徑；
2.路徑長度：路徑上的分支數目稱為路徑長度；
3.樹的路徑長度：從根到每個結點的路徑長度之和。
4.結點的權：根據應用的需要可以給樹的結點賦權值；
5.結點的帶權路徑長度：從根到該結點的路徑長度與該結點權的乘積；
6.樹的帶權路徑長度=樹中所有葉子結點的帶權路徑之和；通常記作 WPL=∑wi×li
7.哈夫曼樹：假設有n個權值(w1, w2, … , wn)，構造有n個葉子結點的二叉樹，每個葉子結點有一個 wi作為它的權值。則帶權路徑長度最小的二叉樹稱為哈夫曼樹。最優二叉樹。

圖搜索->形成搜索樹
1.窮舉法
2.貪心法。多步決策，每步選擇使得構成一個問題的可能解，同時滿足目標函數
3.回溯法，根據題意，選取度量標准，然後將可能的選擇方法按度量標准所要求順序排好，每次處理一個量，得到該意義下的最優解的分解處理

無向圖
1.迴路或環：第一個頂點和最後一個頂點相同的路徑。
2.簡單迴路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路
3.連通：頂點v至v』 之間有路徑存在
4.連通圖：無向圖圖 G 的任意兩點之間都是連通的，則稱G是連通圖。
5.連通分量：極大連通子圖，子圖中包含的頂點個數極大
6.所有頂點度的和必須為偶數

有向圖
1.迴路或環：第一個頂點和最後一個頂點相同的路徑。
2.簡單迴路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路。
3.連通：頂點v至v』之間有路徑存在
4.強連通圖：有向圖G的任意兩點之間都是連通的，則稱G是強連通圖。各個頂點間均可達。
5.強連通分量：極大連通子圖
6.有向圖頂點的度是頂點的入度與出度之和。鄰接矩陣中第V行中的1的個數是V的出度
7.生成樹：極小連通子圖。包含圖的所有n個結點，但只含圖的n-1條邊。在生成樹中添加一條邊之後，必定會形成迴路或環。
8.完全圖：有 n(n-1)/2 條邊的無向圖。其中n是結點個數。必定是連通圖。
9.有向完全圖：有n(n-1)條邊的有向圖。其中n是結點個數。每兩個頂點之間都有兩條方向相反的邊連接的圖。
10.一個無向圖 G=(V,E) 是連通的，那麼邊的數目大於等於頂點的數目減一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向圖，那麼它是強連通圖的必要條件是邊的數目大於等於頂點的數目：|E|>=|V|，而反之不成立。沒有迴路的無向圖是連通的當且僅當它是樹，即等價於：|E|=|V|-1。

圖的鄰接矩陣和鄰接表

1.鄰接矩陣和加權鄰接矩陣

深度優先搜索利用棧
深度優先遍歷類似於樹的先序遍歷，是樹的先序遍歷的推廣

廣度優先遍歷
圖的廣度優先遍歷就類似於樹的層序遍歷

每次遍歷一個連通圖將圖的邊分成遍歷所經過的邊和沒有經過的邊兩部分，將遍歷經過的邊同圖的頂點構成一個子圖，該子圖稱為生成樹。因此有DFS生成樹和BFS生成樹。

生成樹是連通圖的極小子圖，有n個頂點的連通圖的生成樹必定有n-1條邊,在生成樹中任意增加一條邊，必定產生迴路。若砍去它的一條邊，就會把生成樹變成非連通子圖

最小生成樹：生成樹中邊的權值(代價)之和最小的樹。最小生成樹問題是構造連通網的最小代價生成樹。

Kruskal演算法 ：令最小生成樹集合T初始狀態為空，在有n個頂點的圖中選取權值最小的邊並從圖中刪去，若該邊加到T中有迴路則丟棄，否則留在T中；依次類推，知道T中有n-1條邊為止

Prim演算法： 它的基本思想是以頂點為主導地位，從起始頂點出發，通過選擇當前可用的最小權值邊把頂點加入到生成樹當中來：
1.從連通網路N={V,E}中的某一頂點U0出發，選擇與它關聯的具有最小權值的邊（U0,V）,將其頂點加入到生成樹的頂點集合U中。
2.以後每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(U,V),把它的頂點加入到集合U中。如此繼續下去，直到網路中的所有頂點都加入到生成樹頂點集合U中為止。

Prim演算法，Kruskal演算法和Dijkstra演算法都屬於貪心演算法

Dijkstra演算法適用於邊權值為正的情況，如果邊權值為負數就才用另一種最短路演算法Bellman-Ford演算法。該演算法是指從單個源點到各個結點的最短路，該演算法適用於有向圖和無向圖。復雜度O(n^2)
Dijkstra演算法圖文詳解

若從一個連通圖中刪去任何一個頂點及其相關聯的邊，它仍為一個連通圖的話，則該連通圖被稱為 重（雙）連通圖。
若連通圖中的某個頂點和其相關聯的邊被刪去之後，該連通圖被分割成兩個或兩個以上的連通分量，則稱此頂點為 關節點。

沒有關節點的連通圖稱為雙連通圖
1.生成樹的根結點，有兩個或兩個以上的分支，則此頂點(生成樹的根)必為關節點；
2.對生成樹上的任意一個非葉「頂點」，若其某棵子樹中的所有「頂點」沒有和其祖先相通的回邊，則該「頂點」必為關節點

拓撲排序。在用鄰接表表示圖時,對有n個頂點和e條弧的有向圖而言時間復雜度為O(n+e)。一個有向圖能被拓撲排序的充要條件就是它是一個有向無環圖。

AOV網(Activity On Vertex)：用頂點表示活動，邊表示活動的優先關系的有向圖稱為AOV網。AOV網中不允許有迴路，這意味著某項活動以自己為先決條件。

拓撲有序序列：把AOV網路中各頂點按照它們相互之間的優先關系排列一個線性序列的過程。若vi是vj前驅，則vi一定在vj之前；對於沒有優先關系的點，順序任意。

拓撲排序：對AOV網路中頂點構造拓撲有序序列的過程。方法：

採用 深度優先搜索 或者 拓撲排序 演算法可以判斷出一個有向圖中是否有環（迴路）。
深度優先搜索只要在其中記錄下搜索的節點數n，當n大於圖中節點數時退出，並可以得出有迴路。若有迴路，則拓撲排序訪問不到圖中所有的節點，所以也可以得出迴路。廣度優先搜索過程中如果訪問到一個已經訪問過的節點，可能是多個節點指向這個節點，不一定是存在環。

拓撲演算法描述 ：

AOE網：帶權的有向無環圖，其中頂點表示事件，弧表示活動，權表示活動持續時間。在工程上常用來表示工程進度計劃。

常用哈希函數
1.直接定址法。
2.數字分析法。
3.平方取中法。
4.折疊法。
5.除留余數法。
6.隨機數法。

沖突解決
1.開放定址法：當發生沖突時，形成一個探查序列，沿此序列逐個地址探查，知道找到一個空位置，將發生沖突的記錄放到該地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函數，m哈希表長，di增量序列。

2.鏈地址法：將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，並用一維數組存放頭指針。

3.設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到Hash表中需要做n (n-1)/2次線性探測。如果使用二次探測再散列法將這n個關鍵字存入哈希表，至少要進行n (n+1)/2次探測
4.Hash查找效率：裝填因子=表中記錄數/表容量
5.開哈希表——鏈地址法；閉哈希表——開放地址法

B樹的查找
時間復雜度O(logn)

B樹的插入

例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15構建5階B樹

因為構建5階的B樹，所以每個節點的關鍵字個數范圍為[2,4]

插入11時，該節點的關鍵字個數超出范圍，進行分裂

之後直接插入4，8，13

當插入10時，節點關鍵字個數再次超出范圍

將子節點分裂

直接插入5，17，9，16，插入20

關鍵字個數超出范圍，進行分裂

繼續插入3

關鍵字個數超出范圍，進行分裂

繼續插入15

關鍵個數超出范圍，進行分裂

這時候根節點關鍵字個數也超出范圍，繼續分裂

B+的優點
1.單一節點存儲更多的元素，使得查詢的IO次數更少。
2.所有查詢都要查詢葉到葉子節點，查詢更加穩定
3.所有葉子節點形成有序鏈表，便於范圍查詢。

③ 資料庫技術知識數據結構的演算法

資料庫技術知識數據結構的演算法

對於將要參加計算機等級考試的考生來說，計算機等級考試的知識點輔導是非常重要的復習資料。以下是我收集的資料庫技術知識數據結構的演算法，希望大家認真閱讀!

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、排序

直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序演算法要了解。

直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序，其他排序為穩定排序

;