二級vb公共基礎(chǔ)知識

1、全國計算機(jī)等級考試二級公共基礎(chǔ)知識全國計算機(jī)等級考試二級公共基礎(chǔ)知識第1頁，共12頁數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法一、一、基本概念：基本概念：數(shù)據(jù)數(shù)據(jù)(Data)(Data)：信息的載體，能夠被計算機(jī)識別、存儲和加工處理的物理符號。包括文：信息的載體，能夠被計算機(jī)識別、存儲和加工處理的物理符號。包括文本類型的數(shù)據(jù)本類型的數(shù)據(jù)(如：字母、數(shù)字、漢字如：字母、數(shù)字、漢字)和多媒體類型的數(shù)據(jù)和多媒體類型的數(shù)據(jù)(如：聲音、動畫、圖像如：聲音、動畫

2、、圖像)。數(shù)據(jù)元素數(shù)據(jù)元素(Data(DataElement)Element)：是數(shù)據(jù)的基本單位，有時也稱為元素、結(jié)點、頂點、記錄，：是數(shù)據(jù)的基本單位，有時也稱為元素、結(jié)點、頂點、記錄，可以有若干個數(shù)據(jù)項（字段、域、屬性）組成?？梢杂腥舾蓚€數(shù)據(jù)項（字段、域、屬性）組成。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（DataDataStructureStructure）：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其）：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。

3、其包括三個部分：包括三個部分：1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系2、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示。、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示。3、數(shù)據(jù)的運算（算法）：即對數(shù)據(jù)施加的操作、數(shù)據(jù)的運算（算法）：即對數(shù)據(jù)施加的操作數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：1、線性結(jié)構(gòu)：、線性結(jié)構(gòu)：特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點特征

4、是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點最多只有一個直接前趨和一個直接后繼。最多只有一個直接前趨和一個直接后繼。例：一維數(shù)組、鏈表、棧、隊列、串例：一維數(shù)組、鏈表、棧、隊列、串2、非線性結(jié)構(gòu)：、非線性結(jié)構(gòu)：特征是：一個結(jié)點可能有多個直接前趨和直接后繼。特征是：一個結(jié)點可能有多個直接前趨和直接后繼。例：多維數(shù)組、廣義表、樹、圖例：多維數(shù)組、廣義表、樹、圖數(shù)據(jù)的存儲結(jié)構(gòu)有以下基本存儲方法：數(shù)據(jù)的存儲結(jié)構(gòu)有以下基

5、本存儲方法：1、順序存儲方法：、順序存儲方法：該方法是將邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)該方法是將邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，一般通過數(shù)組來實現(xiàn)的。系由存儲單元的鄰接關(guān)系來體現(xiàn)，一般通過數(shù)組來實現(xiàn)的。2、鏈接存儲方法：、鏈接存儲方法：該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的該方法不要求邏輯上相鄰的結(jié)點在物理

6、位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。通過指針類型來實現(xiàn)的。指針字段表示的。通過指針類型來實現(xiàn)的。3、索引存儲方法：、索引存儲方法：該方法通常是在存儲結(jié)點信息的同時，還建立附加的索引表，索引表中的每一項稱為該方法通常是在存儲結(jié)點信息的同時，還建立附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是：關(guān)鍵字，地址。索引項，索引項的一般形式是：關(guān)鍵字，地址。4、散列存儲方法：、散列存儲方法：該方法的基本思想是根據(jù)結(jié)

7、點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，通過散列函數(shù)該方法的基本思想是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，通過散列函數(shù)實現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù)實現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù)算法的基本特征：算法的基本特征：1、可行性、可行性(Effectiveness)(Effectiveness)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。果。2、確定性

8、、確定性(Definiteness)(Definiteness)：算法中的每一個步驟都必須有明確的定義，不允許出現(xiàn)歧：算法中的每一個步驟都必須有明確的定義，不允許出現(xiàn)歧義性。義性。3、有窮性、有窮性(Finiteness)(Finiteness)：算法必須在有限時間內(nèi)做完，即必須在執(zhí)行有限個步驟之后：算法必須在有限時間內(nèi)做完，即必須在執(zhí)行有限個步驟之后終止。終止。時間復(fù)雜度：該算法執(zhí)行的時間耗費，它是該算法所求解問題規(guī)模時間復(fù)雜度：該算

9、法執(zhí)行的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。的函數(shù)。全國計算機(jī)等級考試二級公共基礎(chǔ)知識全國計算機(jī)等級考試二級公共基礎(chǔ)知識第3頁，共12頁先出的線性表，又稱為先出的線性表，又稱為LIFOLIFO表。表。棧的基本運算有：棧的基本運算有：棧的初始化、判棧空、判棧滿、進(jìn)棧、出棧等棧的初始化、判?？铡⑴袟M、進(jìn)棧、出棧等棧的存儲：棧的存儲：順序存儲、鏈?zhǔn)酱鎯樞虼鎯?、鏈?zhǔn)酱鎯喝暨M(jìn)棧的輸入序列是例：若進(jìn)棧的輸入序列是A、B、C、D、E，

10、并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操，并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操作，則不可能出現(xiàn)的出棧序列是（作，則不可能出現(xiàn)的出棧序列是（）A、EDCBAEDCBAB、DECBADECBAC、DCEABDCEABD、ABCDEABCDE四、四、隊列：隊列：隊列隊列(Queue)(Queue)：也是一種運算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一：也是一種運算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一

11、段稱為隊頭端進(jìn)行刪除。允許刪除的一段稱為隊頭(Front)(Front)，允許插入的一段稱為隊尾，允許插入的一段稱為隊尾(Rear)(Rear)。（類似（類似于生活中的購物排隊）于生活中的購物排隊）。是一種先進(jìn)先出的線性表，又稱為。是一種先進(jìn)先出的線性表，又稱為FIFOFIFO表。表。隊列的基本運算：隊列的基本運算：隊列的初始化、判隊空、判隊滿、入隊、出隊隊列的初始化、判隊空、判隊滿、入隊、出隊隊列的存儲實現(xiàn)：隊列的存儲實現(xiàn)：順序存儲、

12、鏈?zhǔn)酱鎯樞虼鎯?、鏈?zhǔn)酱鎯阂粋€隊列的入隊序列是例：一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是，則隊列的輸出序列是（）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，1五、五、串：串：串(String)(String)：是零個或多個字符組成的有限序列。：是零個或多個字符組成的有限序列。串中所包含的字符個數(shù)稱為該串的長度。串中所包含的字符個數(shù)稱為該串的長度。串中任意個連續(xù)字符組成的子序列稱為該串的子串，

13、包含子串的串相應(yīng)地稱為主串串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串注：空串是任意串的子串，任意串是其自身的子串注：空串是任意串的子串，任意串是其自身的子串串有串常量、串變量之分：串有串常量、串變量之分：1、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。2、串變量其值是可以改變的。、串變量其值是可以改變的。串的基本運算：串的基本運算：求串長

14、、串復(fù)制、串聯(lián)接、串比較、字符定位、求串長、串復(fù)制、串聯(lián)接、串比較、字符定位、六、六、樹（非線性結(jié)構(gòu)）：樹（非線性結(jié)構(gòu)）：樹(Tree)(Tree)：是：是n(n=0)n(n=0)個結(jié)點的有限集個結(jié)點的有限集T，T(n=0)T(n=0)為空時稱為空樹，否則它滿足如下兩為空時稱為空樹，否則它滿足如下兩個條件：個條件：1、有且僅有一個特定的稱為根、有且僅有一個特定的稱為根(Root)(Root)的結(jié)點的結(jié)點2、其余的結(jié)點可分為、其余的結(jié)點可

15、分為m(m=0)m(m=0)個互不相交的子集個互不相交的子集T1T1，T2T2，…….…….，TmTm，其中每個子集，其中每個子集本身又是一棵樹，并稱其為根的子樹本身又是一棵樹，并稱其為根的子樹(Subtree)(Subtree)。在樹的樹形圖表示中，結(jié)點通常是用圓圈表示的，結(jié)點的名字一般是寫在圓圈旁邊，在樹的樹形圖表示中，結(jié)點通常是用圓圈表示的，結(jié)點的名字一般是寫在圓圈旁邊，有時亦可寫在圓圈內(nèi)。有時亦可寫在圓圈內(nèi)。度(Degree)(