2017年計算機二級公共基礎知識

通過全國計算機二級考試是許多高校對其學生計算機能力的基本要求。以下是由小編整理關於計算機二級公共基礎知識的內容，希望大家喜歡!

1、算法：是指解題方案准確而完整的描述

2、算法的基本特徵：可行性、確定性、又窮性、擁有足夠的情報

3、算法設計基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法

4、用算法在執行過程中所需基本運算的執行次數來度量算法的工作量

5、插入類排序法：簡單插入排序法、希爾排序法

6、數據結構作為計算機的一門學科，主要研究和討論一下三個方面的問題：

(1)數據集合中各數據元素之間所固有的邏輯關係，即數據的邏輯結構

(2)在對數據進行處理時，各數據元素在計算機中的儲存關係，即數據的存儲結構

(3)對數據結構進行的運算

7、數據的邏輯結構：是指帶有結構的數據元素的集合

8、數據結構應包含(1)表示數據元素的信息

(2)表示各數據元素之間的前後件關係

9、所謂數據的邏輯結構，是指反應數據元素之間邏輯關係的數據結構

10、選擇類排序法：簡單選擇排序法、堆排序法

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

12、如果一個非空的數據結構滿足下列兩個條件

(1)有且只有一個根結點

(2)每一個結點最多有一個前件，也最多有一個後件則稱該數據結構為線性結構，又稱線性表

13、線性表是最簡單、最常用的一種數據結構

14、非線性表有以下結構特徵

(1)有且只有一個根結點a1，它無前件

(2)有且只有一個終結點An，它無後件

(3)除根結點與終結端外，其他所有結點有且只有一個前件，也有且只有一個後件， 線性表中結點的個數n稱為為線性表長度，當n=0時，稱為空表

15、線性表的順序存儲結構具有兩個基本特點

(1)線性表中所有元素所佔的存儲空間是連續的

(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放的

16、順序表的插入、刪除運算

17、棧：是限定在一端進行插入與刪除的線性表

18、棧是按照“先進後出”或“後進先出”的原則組織數據的，棧也被稱為“先進後出” 表或“後進先出”表

19、棧中的個數=bottom-top+1 (用值大的減值小的再加一)

Top=0表示棧空 top=m表示棧滿

支持子程序調用的數據結構是棧棧的基本運算有三種：入棧、退棧、與讀棧頂元素

20、隊列：是指允許在一端進行插入、而在另一端進行刪除的線性表

21、隊列稱為“先進先出”或“後進後出”的線性表

22、對列空與對列滿的條件：隊列空的條件為s=0，隊列滿的條件為s=1且ftont=rear

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

退隊運算、是指在循環隊列的排頭位置退出一個元素並賦給指定的變量

24、線性表的鏈式存儲式結構稱為線性鏈表、

25、(1)在線性鏈表中查找指定元素

(2)線性鏈表的插入、是指在鏈式存儲結構下的線性表中插入一個新元素

(3)線性鏈表的刪除、是指在鏈式存儲結構下的線性表中刪除包含指定元素的結點

26、樹是一種簡單的非線性結構

27、樹這種數據結構的基本特徵

(1)在樹結構中每一個結點只有一個前件，稱為父結點沒有前件的結點只有一個，稱 為樹的根結點，簡稱為樹的根。

(2)在樹結構中，每一個結點可以有多個後件，它們都稱為該結點的子結點。沒有後 件的結點稱為葉子結點

(3)在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0在 樹中，所有結點中的最大的度稱為樹的度

28、樹的最大層次稱為樹的深度

29、在樹中，以某結點的一個子結點為根構成的樹稱為該結點的`一顆子樹，葉子結點沒有子樹

30、二叉樹，是一種很有用的非線性結構

31、二叉樹的特點：(1)非空二叉樹只有一個根結點

(2)每一個結點最多有兩顆子樹，每一個結點的度最大為2

32、二叉樹的基本性質：(1)在二叉樹的第k層上，最多有2的k-1次方(k>=1)個結點

(2)深度為m的二叉樹最多有2的m次方-1個結點(深度為m的 二叉樹是指二叉樹共有m層)

(3)在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度 為2的結點多一個

(4)具有n個結點的二叉樹，其深度至少為【log2N】+1,其中【log2N】 表示取其整數部分

33、滿二叉樹與完全二叉樹(1)滿二叉樹：除最後一層外，每一層上的所有結點都有兩個 子結點

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

34、完全二叉樹的性質：(1)具有m個結點的完全二叉樹的深度為【log2N】+1

(2)設完全二叉樹共有n個結點

35、計算機中二叉樹通常採用鏈式存儲結構

36、二叉樹的遍歷：是指不重複地訪問二叉樹中的所有結點

(1)前序遍歷(2)中序遍歷(3)後序遍歷

37、二分法查找只適用於順序存儲的有序表。二分法查找只需要比較log2N次而順序查找需要比較n次

38、交換類排序法：冒泡排序法、快速排序法