全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)講義全

1、全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義目錄第一章 數(shù)據(jù)結(jié)構(gòu)與算法 11.1 算法 11.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 21.3 線性表及其順序存儲(chǔ)結(jié)構(gòu) 31.4 棧和隊(duì)列 41.5 線性鏈表 51.6 樹(shù)與二叉樹(shù) 71.7 查找技術(shù) 1.0.1.8 排序技術(shù) 1.1.本章應(yīng)考點(diǎn)撥 1.2.第二章 程序設(shè)計(jì)基礎(chǔ) 1.32.1 程序設(shè)計(jì)風(fēng)格 1.3.2.2 結(jié)構(gòu)化程序設(shè)計(jì)（面向過(guò)程的程序設(shè)計(jì)方法） 1.42.3 面向?qū)ο蟮某绦蛟O(shè)計(jì) 1.5.本章應(yīng)考點(diǎn)撥 1.6.第三章 軟件工程基礎(chǔ) 1.73.1 軟件工程基本概念 1.7.3.2 結(jié)構(gòu)化分析方法 2.0.3.3 結(jié)構(gòu)化設(shè)計(jì)方法 2.1.3.4 軟件測(cè)

2、試 2.5.3.5 程序的調(diào)試 2.8.本章應(yīng)考點(diǎn)撥 2.9.第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 3.04.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 3.0.4.2 數(shù)據(jù)模型 3.4.4.3 關(guān)系代數(shù) 3.8.4.4 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟 4.0.本章應(yīng)考點(diǎn)撥 4.0.第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話(huà)說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種 描述。* :算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。2、算法的基本特征（1）可行性。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿(mǎn)意的結(jié)果。（2）確定性。每一條指令的含義明確，無(wú)二義性。并且在任何條件下，算法只有唯一的一條執(zhí)

3、行路徑，即相同的輸入只能得出相同的輸出。（3） 有窮性。算法必須在有限的時(shí)間完成。有兩重含義，一是算法中的操作步驟為有限個(gè)， 二是每個(gè)步驟都能在有限時(shí)間完成。（4 ）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)， 不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)， 算法將無(wú)法執(zhí)行或執(zhí)行有錯(cuò)。一般說(shuō)來(lái)，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提 供的情報(bào)不夠時(shí)，算法可能無(wú)效。* :綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，

4、且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1 ）算法時(shí)間復(fù)雜度是旨執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基-本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。（2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1 ）表示數(shù)據(jù)元素的信息；2 ）表示各數(shù)據(jù)元素之間的前后件關(guān)系。（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)

5、構(gòu)有順序、索引等。1）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯 關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)。2 ）存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的 指針字段表示的。由此得到的存儲(chǔ)表示稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3 ）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。* :數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。（3 ）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的

6、運(yùn)算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外， 還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中， 對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn),并簡(jiǎn)稱(chēng)為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二 元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。(1 )線性結(jié)構(gòu)非空的數(shù)據(jù)結(jié)構(gòu))條件:1 )有且只有一個(gè)根結(jié)點(diǎn)；2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。* :常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。(2)非線性結(jié)構(gòu)：不滿(mǎn)足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。* :常見(jiàn)的非線性結(jié)構(gòu)

7、有樹(shù)、二叉樹(shù)和圖等。1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n >0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元 素的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度。線性表可以為空表。2、 線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：(1 )線性表中所有元素所占的存儲(chǔ)空間是 連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。* :由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰.的，且前件元素一

8、定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。3、順序表的插入、刪除運(yùn)算(1)順序表的插入運(yùn)算：在一般情況下，要在第(1 E <n)個(gè)元素之前插入一個(gè)新元素時(shí)， 首先要從最后一個(gè)(即第n個(gè))元素開(kāi)始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移 動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第 i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后,線性表的長(zhǎng)度就增加了 1。* :順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。(2)順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i (1 Ewn)個(gè)元素時(shí)，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共n-i個(gè)元素依

9、次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長(zhǎng)度就減小了 1。* :進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n-1）/2個(gè)元素。插入、刪除運(yùn)算不方便。1.4棧和隊(duì)列1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性.表。在棧中，允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與刪除的另一端稱(chēng)為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照先進(jìn)后出”或后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算：1 ）插入元素稱(chēng)為入棧運(yùn)算；2）刪除元素稱(chēng)為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線性表類(lèi)

10、似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)行插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front ）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是 先 進(jìn)先出”或 后進(jìn)后出”的線性表。隊(duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的* :循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front1.5線性鏈表1、線性

11、表順序存儲(chǔ)的缺點(diǎn)：(1 )插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中， 插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素；(2)線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充；(3)線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。2、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針來(lái)實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱(chēng)為數(shù)據(jù)域；另一部分用于存放指針，稱(chēng)為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示：datanext數(shù)據(jù)域指針域(a)結(jié)點(diǎn)結(jié)構(gòu)H

12、EAD a |_ a21an-1anA(b) 個(gè)非空的線性鏈表示意圖線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類(lèi)型。在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域， 由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱(chēng)為左指針，指向其前件結(jié)點(diǎn)；另一個(gè)稱(chēng)為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱(chēng)為雙向鏈表，如下圖所示:左指針數(shù)據(jù)域右指針Aa1aA3 、線性鏈表的基本運(yùn)算 （1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。* ：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不 會(huì)出現(xiàn)“上溢”現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。* ：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。（3）將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。（4）將一個(gè)線性鏈表按要求進(jìn)行分解。（5）逆轉(zhuǎn)線性鏈表。（6）復(fù)制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。* ：線性鏈表不能隨機(jī)存取。4 、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中， 其插入與刪除的運(yùn)算雖然比較方便， 但還存在一個(gè)問(wèn)題， 在運(yùn)算過(guò)程中對(duì)于 空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮， 使空表與非空表的運(yùn)算不統(tǒng)一。 為了克服線性鏈 表的這個(gè)缺點(diǎn)，可以