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

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

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

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

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

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

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

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

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

9、法執(zhí)行的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。的函數(shù)。全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第3頁，共12頁先出的線性表，又稱為先出的線性表，又稱為LIFOLIFO表。表。棧的基本運(yùn)算有：棧的基本運(yùn)算有：棧的初始化、判棧空、判棧滿、進(jìn)棧、出棧等棧的初始化、判?？铡⑴袟M、進(jìn)棧、出棧等棧的存儲(chǔ)：棧的存儲(chǔ)：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)例：若進(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四、四、隊(duì)列：隊(duì)列：隊(duì)列隊(duì)列(Queue)(Queue)：也是一種運(yùn)算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一：也是一種運(yùn)算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一

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

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

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

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

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