2017年計算機二級公共基礎知識
通過全國計算機二級的文章" target="_blank" >計算機二級考試是許多高校對其學生計算機能力的基本要求。以下是由小編整理關於計算機二級公共基礎知識的內容,希望大家喜歡!
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、交換類排序法:氣泡排序法、快速排序法