二級演算法是什麼意思

① 計算機二級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.資料庫管理

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

② 計算機二級二叉樹演算法

1、二叉樹的概念

二叉樹是一種特殊的樹形結構，每個結點最多隻有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態。

2、二叉樹的性質

性質1 在二叉樹的第k層上，最多有2^(k-1)(k≥1）個結點。

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

性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個。

性質4 具有n個結點的二叉樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。

③ 計算機二級演算法

這正經文章寫的都太繁復了。可行性就是說能不能運行，就是這么簡單的意思。它的舉例過於抽象，可以換一個說法：比如你想用計算機里的畫圖畫圓，先按住滑鼠然後畫圈就能成，先畫圈後按住滑鼠就不成。由此說明一個軟體事務並不是做完了每一步就算是成功，先後順序（也就是演算法）是會影響到可行性的。

④ 計算機二級數據結構與演算法知識點

一、數據結構

（1）數據結構的基本概念

1、數據：數據是客觀事物的符號表示，是能輸入到計算機中並被計算程序識別和處理的符號的總稱，如文檔，聲音，視頻等。

2、數據元素：數據元素是數據的基本單位。

3、數據對象：數據對象是性質相同的數據元素的集合。

4、數據結構：是指由某一數據對象中所有數據成員之間的關系組成的集合。

（2）邏輯結構和存儲結構

1、數據結構可分為數據的邏輯結構和存儲結構。

1）數據的邏輯結構是對數據元素之間的邏輯關系的描述，與數據的存儲無關，是面向問題的，是獨立於計算機的。它包括數據對象和數據對象之間的關系。

2）數據的存儲結構也稱為數據的物理結構，是數據在計算機中的存放的方式，是面向計算機的，它包括數據元素的存儲方式和關系的存儲方式。

2、存儲結構和邏輯結構的關系：一種數據的邏輯結構可以表示成多種存儲結構即數據的邏輯結構和存儲結構不一定一一對應。

3、常見的存儲結構有：順序，鏈接，索引等。採用不同的存儲結構其數據處理的效率是不同的。

⑤ 計算機二級選擇題干貨（五）——數據結構和演算法

1、線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱後進先出表（Last In First Out）；隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表（First In First Out）。

2、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

3、棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱先進後出表（FILO-First In Last Out）。線性表可以順序存儲，也可以鏈式存儲，而棧是一種線性表，也可以採用鏈式存儲結構。

4、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

5、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

top=0表示棧空，top=50表示棧滿。入棧操作首先將top加1，然後將新元素插入到top指針指向的位置；退棧操作首先將top指針指向的元素賦給一個指定的變數，然後將top減1。棧頂指針top動態反映了棧中元素的變化情況。

6、棧是一種先進後出的線性表，棧實際上也是線性表，只不過是一種特殊的線性表。隊列是指允許在一端進行插入、而在另一端進行刪除的線性表，隊列是一種"先進先出"或"後進後出"的線性表

隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。它又稱為"先進先出"或"後進後出"的線性表，體現了"先來先服務"的原則。

7、帶鏈的隊列也是線性鏈表，在線性鏈表中指向線性表中的第一個結點的指針稱為頭指針，頭指針為NULL或0時稱為空表，指向隊尾元素的指針稱為尾指針。隊列在隊尾插入元素，稱為入隊運算；在隊頭刪除元素，稱為退隊運算。帶鏈隊列在開辟存儲空間時，可以按照存儲空間地址增大的方向開辟，也可以按照存儲空間地址減少的方向開辟。

8、所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第1個位置，形成邏輯上的環狀空間，供隊列循環使用。所以循環隊列還是屬於線性結構。循環隊列的頭指針front指向隊列的第一個元素的前一位置，隊尾指針rear指向隊列的最後一個元素，循環隊列的動態變化需要頭尾指針共同反映循環隊列的長度是：(sq.rear-sq.front+maxsize)%maxsize，所以循環隊列的長度是由隊頭和隊尾指針共同決定的

 在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。

 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就進一。每進行一次退隊運算，排頭指針就進一。當rear或front的值等於隊列的長度+1時，就將rear或front的值置為1。一般情況下，rear大於front，因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限之後又從數組的低端開始，此時，rear是小於front的。

循環隊列就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在實際應用中，隊列的順序存儲結構一般採用循環隊列的形式。因此，循環隊列不是隊列的一種鏈式存儲結構。循環隊列是一種存儲結構，因此循環隊列是一種物理結構，而不是邏輯結構。循環隊列是隊列的順序存儲結構，因此循環隊列是線性結構。

9、循環隊列不同於循環鏈表，循環隊列是順序存儲結構，循環鏈表是鏈式存儲結構。雙向鏈表是鏈式存儲結構，其中每個結點都有左指針和右指針，不同於二叉樹結點的左子樹指針和右子樹指針。非線性結構和線性結構是數據的邏輯結構，順序和鏈式是數據的存儲結構，例如二叉樹是非線性結構，也可以按照層序進行順序存儲。

10、非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後驅。常見的非線性結構有：樹（二叉樹等），圖（網等）。

11、由於二叉樹的存儲結構中每一個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表，二叉鏈表屬於非線性結構。

12、遍歷是指不重復的訪問所有結點。線性單鏈表每個結點只有一個指針域，由這個指針只能找到後件結點，但不能找到前件結點。雙向鏈表中的每個結點設置兩個指針，左指針指向其前件結點，右指針指向其後件結點。循環鏈表中增加了一個表頭結點，循環鏈表中的所有結點的指針構成了一個環狀鏈。二叉鏈表即二叉樹的鏈式存儲結構，每個存儲結點有兩個指針域，左指針域指向該結點的左子結點的存儲地址，右指針域指向該結點的右子結點的存儲地址。

13、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的;（2）線性表中各元素在存儲空間中是按邏輯順序依次存放的。

14、循環鏈表具有以下兩個特點：(1)在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。(2)循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

15、在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點。

16、根據二叉樹的性質：二叉樹第i（i≥1）層上至多有2i-1個結點。

17、所謂滿二叉樹是指這樣的一種二叉樹：除最後一層外，每層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m個結點。

18、在任意一顆樹中，結點總數=總分支數目+1

19、二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。本題中度為2的結點數為n，故葉子結點數為n+1個。

二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

20、在用完全二叉樹表示堆，樹中所有非葉子結點值均不小於其左右子樹的根結點值，因此，堆頂元素必為序列的n個元素中的最大項。

21、作為一個演算法，一般應具有以下幾個基本特徵。

 可行性

 確定性

 有窮性

擁有足夠的情報

22、計算機演算法是指解題方案的准確而完整的描述

演算法的有窮性，是指演算法必須在有限的時間內做完，即演算法必須能在執行有限個步驟之後終止。

23、希爾排序法的基本思想是：將整個無序序列分割成若干小的子序列分別進行插入排序。所以希爾排序法屬於插入類排序，但它對簡單插入排序做了很大的改進。

24、快速排序的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄繼續進行排序，以達到整個序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中，從而得到一個新的序列；選擇排序的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置），然後對剩下的子表採用同樣的方法，直到表空為止；歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表。

25、在單鏈表中，增加頭結點的目的是______。

頭結點不僅標識了表中首結點的位置，而且根據單鏈表（包含頭結點）的結構，只要掌握了表頭，就能夠訪問整個鏈表，因此增加頭結點目的是為了便於運算的實現。

26、演算法分析是指對一個演算法的運行時間和佔用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示。分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度，提高演算法的執行效率。

27、演算法是指解題方案的准確而完整的描述。但演算法不等於程序，也不等於計算方法。當然，程序也可以作為演算法的一種描述，但程序通常還需要考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統運行環境的限制。通常，程序的編制不可能優於演算法的設計。作為一個演算法，一般應具有可行性、確定性、有窮性、擁有足夠情報四個基本特徵。因此設計演算法時不僅僅要考慮結果的可靠性，即不僅考慮演算法結果的可行性，還要考慮步驟的確定性，時間和步驟的有窮性等。因此，演算法是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。

28、一個演算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是演算法的控制結構。因此設計演算法時不僅需要考慮數據結構的設計，還要考慮數據的操作和運算及各操作之間的執行順序。

29、在有向圖中，若任意兩個頂點都連通，則稱該圖是強連通圖，這樣的有向圖的形狀是環狀，因而至少應有n條邊。

30、當數據表A中每個元素距其最終位置不遠，說明數據表A按關鍵字值基本有序，在待排序序列基本有序的情況下，採用插入排序所用時間最少。

31、數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。

32、假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後掃描和n/2遍的從後往前掃描，需要比較次數為n(n-1)/2。快速排序法的最壞情況比較次數也是n(n-1)/2

（1）冒泡排序法：是一種最簡單的交換類排序法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要比較的次數為n(n-1)/2次。

 （2）簡單插入排序法：在簡單插入排序法中，每一次比較後最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。

 （3）簡單選擇排序法：對於長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然後將該最小的元素與子表中的第一個元素進行交換。簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。

 （4）堆排序法：堆排序的方法為：①首先將一個無序序列建成堆。②然後將堆頂元素（序列中的最大項）與堆中最後一個元素交換（最大項應該在序列的最後）。在最壞情況下，堆排序需要比較的次數為。

 假設線性表的長度為16，那麼冒泡排序、直接插入排序、簡單選擇排序都需要比較120次，而堆排序需要比較64次。

33、對於長度為n的線性表，在最壞的情況下，快速排序所需要的比較次數為n(n-1)/2；冒泡排序所需要的比較次數為n(n-1)/2；直接插入排序所需要的比較次數為n(n-1)/2；堆排序所需要的比較次數為。

34、在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次。

35、二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

二分法檢索要求線性表結點按關鍵值排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功；否則根據比較結果確定下一步在表的前半部分或後半部分繼續進行。二分法檢索的效率比較高，設線性表有n個元素，則最多的檢索次數為大於log2n(2為底數)的最小整數，最少的檢索次數為1。

36、一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。

37、順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素，鏈式存儲結構中各數據結點的存儲序號是不連續的，並且各結點在存儲空間中的位置關系與邏輯關系也不一致。兩者都可以存儲線性的、有序的邏輯結構，順序結構使用的是連續物理空間，鏈式結構可以使用零散的物理空間存儲，鏈式結構更靈活，不存在誰節約空間的說法

38、順序存儲結構中，數據元素存放在一組地址連續的存儲單元中，每個數據元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到，從而實現了隨機存取。對於鏈式存儲結構，要對某結點進行存取，都得從鏈的頭指針指向的結點開始，這是一種順序存取的存儲結構。

39、鏈式存儲結構克服了順序存儲結構的缺點：它的結點空間可以動態申請和釋放；它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。故鏈式存儲結構下的線性表便於插入和刪除操作。

40、線性表的順序存儲結構的存儲空間只用於存放結點數據，而鏈式存儲結構的存儲空間不僅要存放結點數據，還要存放數據的指針，所以線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構

41、在進行順序查找過程中，如果線性表中的第1個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次

42、對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較 次，而順序查找需要比較n次。二分法查找只適用於順序存儲的有序表，如果採用鏈式存儲結構，也只能用順序查找,所以，對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數為n

43、根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。

44、如果一個非空的數據結構滿足下列兩個條件：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

45、有一個以上根結點的數據結構肯定是非線性結構，循環鏈表、雙向鏈表是線性結構；線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。

46、在鏈表中，如果有兩個結點的同一個指針域的值相等，則該鏈表一定是非線性結構

47、線性表的鏈式存儲結構稱為線性鏈表，為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干位元組，通常稱這些小塊為存儲結點。每一個存儲結點分為兩部分：一部分用於存儲數據元素的值，稱為數據域；另一部分用於存放下一個數據元素的存儲序號，即指向後件的結點，稱為指針域。在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，以便用於存儲該元素的值，然後將存放新元素值的結點鏈接到線性表中指定的位置。在線性鏈表的插入過程中不發生數據無素移動的現象，只需改變有關結點的指針即可，從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結點，首先要在線性鏈表中找到這個結點，然後將要刪除結點放回到可利用棧。在線性鏈表中刪除一個元素後，不需要移動表的數據元素，只需改變被刪元素所在結點的前一個結點的指針域即可。因此，進行插入與刪除時，不需要移動表中的元素。

48、在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷和後序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

二叉樹的中序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

49、鏈表有線性鏈表，也有非線性鏈表。線性鏈表和二叉樹鏈表的結點都有兩個指針域，前者是線性結構，後者是非線性結構。線性單鏈表中的結點只有一個指針，葉子結點一般是對樹結構而言，樹結構是非線性結構，不是線性表。

50、演算法的復雜度主要包括時間復雜度和空間復雜度：演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度；演算法的時間復雜度是指執行演算法所需要的計算工作量，即演算法執行過程中所需要的基本運算次數，為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。二者沒有直接關系。

51、一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。一個演算法所佔用的存儲空間包括程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間相對於問題規模來說是常數，則稱該演算法是原地(in place)工作的。

52、我們通常用時間復雜度和空間復雜度來衡量演算法效率，演算法的時間復雜度是指執行演算法所需要的計算工作量；演算法所執行的基本運算次數與問題的規模有關，而一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間；一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構。

所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。

53、子程序調用是一種層次關系，子程序調用功能模塊，調用功能模塊的個數也不確定，可以是一個，也可以是多個。二叉樹是一種很有用的非線性結構，二叉樹不同於樹形結構。二叉樹具有以下兩個特點：①非空二叉樹只有一個根結點；②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。選項D規定每個結點只能有兩個後件。在子程序調用中，調用的功能模塊可以是多個，可以調用超過兩個功能模塊。

54、結構圖的深度表示控制的層數結構圖的深度表示控制的層數

55、數據結構是指反映數據元素之間關系的數據元素集合的表示。更通俗地說，數據結構是指帶有結構的數據元素的集合。所謂結構實際上就是指數據元素之間的前後件關系。線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，還要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。

⑥ 演算法是什麼意思

演算法，從字面意義上解釋，就是用於計算的方法，通過該這種方法可以達到預期的計算結果。目前，被廣泛認可的演算法專業咐渣敏定義是：演算法是模型分析的一組可行的，確定的，有窮的規則。通俗的說，演算法也可以理解為一個解題梁陸步驟，有一些基本運算和規定的順序構成。但是從計算機程序設計的角度看，演算法由一系列求解問題的指令構成，能根據規范的輸入，在有限的時間內獲得有效的輸出衡枝結果。演算法代表了用系統的方法來描述解決問題的一種策略機制。

完成同一件事的不同的演算法完成的時間和佔用的資源可能並不相同，這就牽扯到效率的問題。演算法的基本任務是針對一個具體的問題，找到一個高效的處理方法，從而完成任務。而這就是我們的責任了。

演算法的五個特徵：

一個典型的演算法一般都可以抽象出5個特徵：

有窮性：演算法的指令或者步驟的執行次數和時間都是有限的。

確切性：演算法的指令或步驟都有明確的定義。

輸入：有相應的輸入條件來刻畫運算對象的初始情況。

輸出：一個算應有明確的結果輸出。

可行性：演算法的執行步驟必須是可行的。