全國計算機二級考試VFP知識點小椴

2021-09-19 22:27:58 字數 3471 閱讀 1875

國家二級公共基礎知識考試要點

第一章資料結構與演算法

1.1 演算法

演算法:是指解題方****而完整的描述。

1.1 演算法

演算法:是指解題方****而完整的描述。

演算法不等於程式,也不等計算機方法,程式的編制不可能優於演算法的設計。

演算法的基本特徵:是一組嚴謹地定義運算順序的規則,每乙個規則都是有效的,是明確的,此順序將在有限的次數下終止。特徵包括:

(1)可行性;

(2)確定性,

(3)有窮性,

(4)擁有足夠的情報。

演算法的基本要素:一是對資料物件的運算和操作;二是演算法的控制結構。

指令系統:乙個計算機系統能執行的所有指令的集合。

基本運算和操作包括:算術運算、邏輯運算、關係運算、資料傳輸。

演算法的控制結構:順序結構、選擇結構、迴圈結構。

演算法基本設計方法:列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。

演算法複雜度:演算法時間複雜度和演算法空間複雜度。

演算法時間複雜度是指執行演算法所需要的計算工作量。

1.2 資料結構的基本基本概念

資料結構研究的三個方面:

(1)資料集合中各資料元素之間所固有的邏輯關係,即資料的邏輯結構;*

(2)在對資料進行處理時,各資料元素在計算機中的儲存關係,即資料的儲存結構;[2007.9 ]

(3)對各種資料結構進行的運算。

如:2007.9: (6)下列敘述中正確的是 [1.2]

a)資料的邏輯結構與儲存結構必定是一一對應的

b)由於計算機儲存空間是向量式的儲存結構,因此,資料的儲存結構一定是線性結構

c)程式語言中的陣列一般是順序儲存結構,因此,利用陣列只能處理線性結構

d)以上三種說法都不對

資料結構是指相互有關聯的資料元素的集合。

資料的邏輯結構包含:線性表、棧、佇列、二叉樹、圖

(1)表示資料元素的資訊;

(2)表示各資料元素之間的前後件關係。

資料的儲存結構有順序、鏈結、索引等。

線性結構條件:陣列、線性表、棧、佇列

(1)有且只有乙個根結點;

(2)每乙個結點最多有乙個前件,也最多有乙個後件。

非線性結構:不滿足線性結構條件的資料結構。二叉樹、圖

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

線性表由一組資料元素構成,資料元素的位置只取決於自己的序號,元素之間的相對位置是線性的。

在複雜線性表中,由若干項資料元素組成的資料元素稱為記錄,而由多個記錄構成的線性表又稱為檔案。

非空線性表的結構特徵:

(1)且只有乙個根結點a1,它無前件;

(2)有且只有乙個終端結點an,它無後件;

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

線性表的順序儲存結構具有以下兩個基本特點:

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

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

ai的儲存位址為:adr(ai)=adr(a1)+(i-1)k,,adr(a1)為第乙個元素的位址,k代表每個元素佔的位元組數。

順序表的運算:插入、刪除。要進行大量的資料移動 (詳見14--16頁)

1.4 棧和佇列

棧是限定在一端進行插入與刪除的線性表,允許插入與刪除的一端稱為棧頂,不允許插入與刪除的另一端稱為棧底。

棧的操作原則按照「先進後出」(filo)或「後進先出」(lifo)組織資料,棧具有記憶作用。用top表示棧頂位置,用bottom表示棧底。

棧的基本運算:(1)插入元素稱為入棧運算;(2)刪除元素稱為退棧運算;(3)讀棧頂元素是將棧頂元素賦給乙個指定的變數,此時指標無變化。

佇列是指允許在一端(隊尾)進入插入,而在另一端(隊頭)進行刪除的線性表。rear指標指向隊尾,front指標指向隊頭。

佇列是「先進先出」(fifo)或「後進後出」(lilo)的線性表。

佇列運算包括(1)入隊運算:從隊尾插入乙個元素;(2)退隊運算:從隊頭刪除乙個元素。

迴圈佇列:s=0表示佇列空,s=1且front=rear表示佇列滿

空間的計算:若rear>front : rear-front

rear<=front :空間數+rear-front

[2008.9]、書後習題

1.5 線性鍊錶

資料結構中的每乙個結點對應於乙個儲存單元,這種儲存單元稱為儲存結點,簡稱結點。

結點由兩部分組成:(1)用於儲存資料元素值,稱為資料域;(2)用於存放指標,稱為指標域,用於指向前乙個或後乙個結點。

在鏈式儲存結構中,儲存資料結構的儲存空間可以不連續,各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致,而資料元素之間的邏輯關係是由指標域來確定的。

鏈式儲存方式即可用於表示線性結構,也可用於表示非線性結構。

線性鍊錶,head稱為頭指標,head=null(或0)稱為空表,如果是兩指標:左指標(llink)指向前件結點,右指標(rlink)指向後件結點。

線性鍊錶的基本運算:查詢鍊錶順序查詢,陣列隨機查詢 、插入、刪除。

1.6樹是一種簡單的非線性結構,所有元素之間具有明顯的層次特性。

在樹結構中,每乙個結點只有乙個前件,稱為父結點,沒有前件的結點只有乙個,稱為樹的根結點,簡稱樹的根。每乙個結點可以有多個後件,稱為該結點的子結點。沒有後件的結點稱為葉子結點。

在樹結構中,乙個結點所擁有的後件的個數稱為該結點的度,所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

二叉樹的特點:(1)非空二叉樹只有乙個根結點;(2)每乙個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。

二叉樹的基本性質:

(1)在二叉樹的第k層上,最多有2k-1(k≥1)個結點;

(2)深度為k的二叉樹最多有2k-1個結點;

(3)度為0的結點(即葉子結點)總是比度為2的結點多乙個;【2007.9】

(4)具有n個結點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分;

(5)具有n個結點的完全二叉樹的深度為[log2n]+1;

(6)設完全二叉樹共有n個結點。如果從根結點開始,按層序(每一層從左到右)用自然數1,2,….n給結點進行編號(k=1,2….n),有以下結論:

① 若k=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點編號為int(k/2);

② 若2k≤n,則編號為k的結點的左子結點編號為2k;否則該結點無左子結點(也無右子結點);

③ 若2k+1≤n,則編號為k的結點的右子結點編號為2k+1;否則該結點無右子結點。

滿二叉樹是指除最後一層外,每一層上的所有結點有兩個子結點,則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。

完全二叉樹是指除最後一層外,每一層上的結點數均達到最大值,在最後一層上只缺少右邊的若干結點。

二叉樹儲存結構採用鏈式儲存結構,對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。

二叉樹的遍歷:

(1)(先根)前序遍歷(dlr),首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;

全國計算機等級考試二級VFP考試知識點總匯

資料是指儲存在某一種 上能夠識別的物理符號。資料的概念包括兩個方面 其一是描述事物特性的資料內容 其二是儲存在某一種 上的資料形式。資料形式可以是多種多樣的。資料處理是指將資料轉換成資訊的過程。從資料處理的角度而言,資訊是一種被加工成特定形式的資料,這種資料形式對於資料接收者來說是有意義的。資料處理...

全國計算機vfp知識點最全

21 多某個關係進行選擇,投影或聯接運算的結果仍然是乙個關係。22 visual foxpro的3種基本操作方式為命令方式 選單方式和程式方式。23 實體是客觀存在並且可以區別的事物,實體集是同類實體的集合。24 資料庫系統是由資料庫集合 計算機硬體系統 資料庫管理員 資料庫管理系統和使用者5部分組...

全國計算機等級考試二級VFP講解

第一部分 vfp資料庫基礎 佔考試筆試分值2至4分,一般是1至2道題 vfp是目前微機上優秀的資料庫管理系統軟體之一,在具體學習vfp之前,我們首先學習資料庫的基本概念和關聯式資料庫設計的基礎知識,這是我們學習vfp的必要前提條件。3.1資料庫基礎知識 3.1.1計算機資料管理的發展 1.資料與資料...