全國計算機二級考試公共基礎知識30248.doc

1、全國計算機二級考試公共基礎知識(全)第一章數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)過對部分考生的調(diào)查以及對近年真題的總結(jié)分析筆試部分經(jīng)?？疾榈淖闼惴◤碗s度、數(shù)據(jù)結(jié)構(gòu)的概念棧二叉樹的遍歷、二分法直找.讀者應對此部分進行蛋點學習。詳細幣:點學習知識點：1 算法的概念.算法時間復雜度及空間復雜度的概念2.數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輸結(jié)構(gòu)及物理結(jié)構(gòu)的定義3.棧的定義及其運算、線性鏈表的存儲方式4.樹與二叉樹的概念、二叉樹的基本性質(zhì)、完全二叉樹的概念、二艾樹的遍歷5.二分查找法6.冒泡排序法1.1 算法考點 i 算法的基本概念考試鏈接：考點 1 在筆試考試中考核的兒率為 30%,主耍是以填空題的形式出現(xiàn)，分值為 2 分，此考點為識

2、記內(nèi)容讀者還應該了牌算法中對數(shù)據(jù)的基本運算。il 傅機解題的過程實際上足在實施某種算法，這科算法稱為汁妹機算法。1.算法的雄木特征：可行性、確定性.有窮性.擁有足夠的情報。2.算法的基本翌素：(1算法中對數(shù)據(jù)的運算和操作一個算法由兩種基木要索組成：一是對數(shù)據(jù)對荻的運算和操作；二是算法的控制結(jié)構(gòu)。在般的計算機系統(tǒng)中基本的運算和操作有以下4 類：算術(shù)運克、邏輯運算-關(guān)系運算和數(shù)據(jù)傳輸。(2)算法的控制結(jié)構(gòu)：算法中備操作 z 間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。描述算法的工具通常冇傳統(tǒng)流程圖、ns 結(jié)構(gòu)化流程圖、算法描述語言等。一個算法般都可以川順序、選擇、循環(huán)3 種基木控制結(jié)構(gòu) 組合而成?？键c 2 算

3、法刃雜度考試鏈接：考點 2 在筆試考試中，是一個經(jīng)?？紪说膬?nèi)容在筆試考試中出現(xiàn)的兒率為70%,主耍是以選擇的形式出現(xiàn)，分值為 2 分，此考點為重 點識記內(nèi)容，讀者還應該識記算法時間復雜度及空間復雜度的概念。1.算法的時間復雜度算法的時間復雜度是指執(zhí)行算法所需要的計算工作呈。同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率血不同。這表明使用絕對的時間單 位衡 j1 算法的效率是不合適的。撇開這些與計算機硬件、軟件有關(guān)的因素，可以認為一個特定算法運行工作咼的大小，只依賴于問題的 規(guī)模（通常用整數(shù)n 表示），它是問題規(guī)模的函數(shù)。即算法的工作 ft=f （n）2

4、算法的空間口雜度算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包插算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額 外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)裁結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則 稱該算法是原地工作的。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術(shù)，以便盡雖減少不必要的額外空間。疑難解答：算法的工作地用什么來計算？算法的工作雖用算法所執(zhí)行的基本運算次數(shù)來計算，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f （n），其中 n 是問題的規(guī)

5、模。1.2 數(shù)據(jù)結(jié)構(gòu)的基木概念考點 3 數(shù)據(jù)結(jié)構(gòu)的定義考試鏈接：考點 3 在筆試考試中，是一個經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的兒率為 70%,主要是以選擇的形式出現(xiàn)，分值為 2 分，此考點為識 記內(nèi)容，讀者還應該識記數(shù)據(jù)的邏供結(jié)構(gòu)和存儲結(jié)構(gòu)的概念。數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主耍研究和討論以下三個方面：（1）數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2） 在對數(shù)據(jù)元索進行處理時，各數(shù)據(jù)元索在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3） 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。數(shù)據(jù)：是對客觀事物的符號表示，在計算機科學中是扌旨所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元索

6、：是數(shù)據(jù)的基木單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)對彖：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏軻結(jié)構(gòu)是對數(shù)據(jù)元索 z 間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元索的集介和定義在此集合屮的若干關(guān)系來表示。數(shù)據(jù)的邏輯 結(jié)構(gòu)有兩個要素：-是數(shù)據(jù)元素的集合，通常記為 d；二是 d 上的關(guān)系，它反映了數(shù)據(jù)元索之間的前后件關(guān)系，通常記為 r。 個數(shù)據(jù)結(jié)構(gòu)可以後示成b= （d. r）其中 b 表示數(shù)據(jù)結(jié)構(gòu)。為了反映 d 中各數(shù)據(jù)元索之間的前后件關(guān)系，一般用二元組來表示。數(shù)據(jù)的邏軻結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。由于數(shù)抵元索在計算機存儲

7、空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此.為了義示存放在計算機存儲空間中的各數(shù)據(jù)元素 z 間的邏輯 關(guān)系（即前后件關(guān)系，在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅耍存放各數(shù)據(jù)元素的信息，還需耍存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。-種數(shù)據(jù)的邏輯結(jié)構(gòu)根弟需耍可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)冇順序、鏈接、索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，其 數(shù)據(jù)處理的效率是不同的。因此.在進行數(shù)據(jù)處理時.選擇合適的存儲結(jié)構(gòu)是很重耍的?？键c 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu)考試鏈接：考點 4 在筆試考試中，雖然說不是考試經(jīng)?？紪说膬?nèi)容，但讀者還是對此考點有所了解，在筆試考試中出現(xiàn)的兒率為 30%,主要是以填 空題出現(xiàn)的形式出現(xiàn)，分

8、值為 2 分，此考點為識記內(nèi)容。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，-般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果-個非空的數(shù)據(jù) 結(jié)拘滿足下列兩個條件：（1） 有且只有一個根結(jié)點；（2） 每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)劣結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應是線性結(jié)構(gòu)。如果-個數(shù)據(jù)結(jié)構(gòu) 不是線性結(jié)構(gòu).則稱之為菲線性結(jié)構(gòu)。疑難解答：空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)？一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這耍根據(jù)具體情況來確定。如果對該數(shù)據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)則 來處理的，則屬于線性結(jié)構(gòu)

9、；否則屬于菲線性結(jié)構(gòu)。1.3 棧及線性鏈表考點 5 棧及其基本運算考試鏈接：考點 5 在筆試考試中，是一個必考的內(nèi)容，在筆試考試中出現(xiàn)的兒率為 100%,主要是以選擇的形式出現(xiàn)，分值為 2 分，此考點為重點學 握內(nèi)容，讀若應該掌握棧的運算，1.棧的基木概念棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元索時稱為空棧。棧頂元 素總是后被插入的元索，從而也是嚴先被刪除的元縈；棧底元素總是最先彼插入的元素，從而也是最后才能被刪除的元索。棧是按觀先 進后出或后進先出”的原則組織數(shù)據(jù)的。2.棧的順序存儲及其運算用一維數(shù)組 s （1： m）作為棧的順序存儲

10、空間，其中 m 為最大容呈。在棧的順序存儲空間 s （1：m）中，s （bottom）為棧底元索，s （top）為棧頂元索。iop=0 表示?？?；iop-m 表示棧滿。棧的基本運算有三種：入棧、退找與讀棧頂元索。（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂扌旨針加一（即 top 加 i）,然后將新元索插入到棧頂折針指向的 位迓。當棧頂指針已經(jīng)指向存儲空間的最后一個位迓時，說明棧空間已満，不可能再進行入棧操作。這種情況稱為棧上滯錯誤。（2）退棧運算：退棧是指収出棧頂元索并賦給一個指定的變就。首先將棧頂元素（棧頂指針指向的元索）賦給一個指定的變就，然后將 棧頂指針減一（即 lo

11、p 減 1）。當棧頂指針為 0 時，說明?？眨豢蛇M行退找操作。這種悄況稱為棧的下溢錯誤。（3） 讀棧頂元索：険棧頂元索是指將棧頂元索賦給一個指定的變量。這個運算不刪除棧頂元素,只是將它賦給一個變量，因此棧頂指針 不會改變。當棧頂扌旨針為 0 時，說明?？眨x不到棧頂元素。小技巧：棧是按照先進后出或”后進先出的原則組織數(shù)據(jù).但是出棧方式有多種選擇.在考題中經(jīng)?？疾楦鞣N不同的出棧方式?？键c 6 線性鏈表的基本概念考試鏈接：考點 6 在筆試考試中出現(xiàn)的幾率為 30%,主翌是以選擇的形式岀現(xiàn)，分值為 2 分，此考點為識記內(nèi)容。重點識記結(jié)點的組成。在鏈式存儲方式中，耍求每個結(jié)點由兩部分組成：一部分用于

12、存放數(shù)蟹元索值.稱為數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。其 中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件。鏈式存儲方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。（1） 線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。在某些應用中，對線性鏈表中的每個結(jié)點設置兩個指針,一個稱為左指針,用以指向其前件結(jié)點:另-個稱為右指針,用以指向其后件 結(jié)點。這樣的表稱為雙向鏈表。（2） 帶鏈的棧棧也是線性表，也可以采用鏈式存儲結(jié)構(gòu)。帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。疑難解答:在徒式結(jié)構(gòu)中，存儲空間位置關(guān)系與邏輯關(guān)系是什么？在鏈式存儲結(jié)構(gòu)中.存儲數(shù)據(jù)結(jié)

13、構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元索 z 間的邏輯關(guān)系是由指針域來確定的。1.4 樹與二叉樹 考點 7 樹與二叉樹及其基本性質(zhì)考試鏈接：考點 7 在筆試考試中,是一個必考的內(nèi)容，在筆試考試中出現(xiàn)的兒率為 100%,主要是以選擇的形式出現(xiàn),有時也有出現(xiàn)在填空題中，分 值為 2 分，此考點為覓點掌握內(nèi)客。重點識記樹及二叉樹的性質(zhì)。課區(qū)警示：滿二叉樹也是完全二叉樹.而完全二叉樹一般不是滿二叉樹。應該注意二者的區(qū)別。1、樹的基本概念樹（tree）是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個稱為樹的根

14、結(jié)點。每一個結(jié)點可以有多個后件，它們稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，-個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。葉子結(jié)點的度為0 在樹中，所有結(jié)點中的最大的度稱為樹的度。2、二叉樹及其基本性質(zhì)（1）二叉樹的定義二叉樹是-種很有用的非線性結(jié)構(gòu)，具有以下兩個特點：非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多冇兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。由以上持點可以看出，在二叉樹中，每一個結(jié)點的度最大為 2,即所有子樹（左子樹或右子樹）也均為二叉樹.而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。另外，二叉樹中的每個結(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結(jié)點可以只有左子

15、樹而沒有右 子樹，也可以只有右子樹而沒有左子樹。當一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點即為葉子結(jié)點。（2） 二叉樹的基木性質(zhì)二叉樹具有以下兒個性質(zhì)：性質(zhì) 1：在二叉樹的第 k 層上，最冬有 2k-l （kl）個結(jié)點：性質(zhì) 2：深度為 m 的二叉樹垠多有 2m-1 個結(jié)點：性質(zhì) 3：在任意-棵二叉樹中，度為 0 的結(jié)點（即葉子結(jié)點）總是比度為 2 的結(jié)點多一個。性質(zhì) 4：具有 n 個結(jié)點的二叉樹，其深度至少為（log2n） +1,其中（iog2n）表示取 log2n 的整數(shù)部分。小技巧：在二叉樹的遍歷中.無論是前序遍歷中序遍歷還是后序遍歷二義樹的葉子結(jié)點的先后順序都是不變的。3、滿二叉樹與

16、完全二叉樹滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。在満二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第 k 層上有 2kl 個結(jié)點，且漆度為 m 的滿二叉樹有 2m-1 個結(jié)點。完全二叉樹是指這樣的二艾樹：除鍛后一層外.每一層上的結(jié)點數(shù)均達到最大值；在晟后一層上只缺少右邊的若干結(jié)點。 對于完全二叉樹來說，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)：對于任何一個結(jié)點，若苴右分支下的子孫結(jié)點的最大層次為 p,則瓦左 分支下的子孫結(jié)點的呆大層次或為p,或為 p+i.完全二叉樹具有以下兩個性質(zhì)：性質(zhì) 5:具有 n 個結(jié)點的完全二叉樹的深度為（log2n） +1。

17、性質(zhì) 6:設完全二叉樹共有 n 個結(jié)點。如果從根結(jié)點開始，按層次（每一層從左到右）用自然數(shù) 1, 2, ., n 給結(jié)點進行編號，則對于編號為 k （k=i, 2,，n）的結(jié)點有以下結(jié)論:若 k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點：若 kl則該結(jié)點的父結(jié)點編號為int （k/2） o若 2kn,則編號為 k 的結(jié)點的左子結(jié)點編號為 2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若 2k+ln,則編號為 k 的結(jié)點的右子結(jié)點編號為 2kh；否則該結(jié)點無右子結(jié)點?？键c 8 二叉樹的遍歷考試鏈接：考點 8 在筆試考試中考核兒率為 30%,分值為 2 分,讀者應該熟練掌握各種遙歷的具體算法，能由兩

18、種遍歷的結(jié)果推導另-種遍歷的結(jié) 果。在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷分為三類： 前序遍歷、中序遍歷和后序遍歷。（1） 前序適歷：先訪問根結(jié)點.然后遍歷左子樹.昴后遍歷右子樹；并且，在遍歷左.右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹. 報后遍歷右子樹。（2） 中庠遍歷：先遍歷左子樹、然后訪問根結(jié)點，最后遍歷右子樹；并且，在姻歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點, 最后遍歷右子樹。（3） 后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點；并且，在遍歷左.右子樹時，仍然先遍歷左子樹，然后遍歷右子樹, 最后

19、訪問根結(jié)點。疑難解答：樹與二叉樹的不同之處是什么？在二叉樹中，每一個結(jié)點的度最大為 2,即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。1.5 査找技術(shù)考點 9 順序查找考試鏈接：考點 9 在筆試考試中考核兒率在 30%,-般岀現(xiàn)選擇題中，分值為 2 分，讀者應該具體學握順序査找的算法。査找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找菜個指定的元索。從線性表的第一個元索開始依次將線性表中的元索與被査找的元索相比較, 若相等則農(nóng)示查找成功；若線性農(nóng)中所有的尤索都 9 被杳找尤索進行了比較但都不相等，則農(nóng)爪査找失敗 在下列兩種情況下也只能采川順序査找：（1） 如果線性農(nóng)為無序表

20、，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序査找。（2） 即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。考點 10 二分法查找考試鏈接：考點 10 在筆試考試中考核幾率為 30%, 般出現(xiàn)填空題中，分值為 2 分,考核比較多查找的比較次數(shù)，讀者應該具體慕握二分查找法的 算法。二分法只適用于順序存儲的,按非遞減排列的有序表,其方法如 f：設有序線性表的長度為 n,被査找的元索為 i.（1）將 i 與線性表的中間項進行比較；（2） 若 i 與中間項的值相等，則査找成功；（3）若 i 小于中間項，則在線性表的前半部分以相同的方法査找：（4） 若 i 大于中間項則在線性表的后半部分以相同的方法査找。疑難解答：二分查找法適用于哪種情況？二分査找法只適用于順序存儲的有序表。在此所說的有序表