內(nèi)容簡介

為了幫助考生順利通過全國計算機等級考試，我們根據(jù)全國計算機等級考試最新公告、考試大綱以及相關(guān)考

試用書，精心編寫制作了全國計算機等級考試“二級公共基礎(chǔ)知識”輔導系列：

1.全國計算機等級考試《二級公共基礎(chǔ)知識》【教材精講+真題解析】講義與視頻課程112小時高清視頻】

2.全國計算機等級考試《二級公共基礎(chǔ)知識》題庫【歷年真題+章節(jié)題庫+模擬試題】

3.全國計算機等級考試《二級公共基礎(chǔ)知識》專用教材【考綱分析+考點精講+真題演練+強化習題】

本書主要包括以下兩部分內(nèi)容：

I.教材精講【含12小時視頻講解】。遵循“二級公共基礎(chǔ)知識考試大綱（2018版）”的考察要求及指定

參考教材和相關(guān)法律法規(guī)，名師高清視頻深入剖析考試大綱，全面講解教材重點難點內(nèi)容，幫助學員鞏固知識,

梳理邏輯，輕松應(yīng)考。

2.真題解析。精選歷年考試真題，每道真題均提供詳盡答案解析。學員可以熟悉真題的考試特點，鞏固知

識點并測試自己的水平。

視頻講解教師簡介

全國計算機等級考試輔導（二級）

公共基礎(chǔ)知識

網(wǎng)授精講班

主講教師：趙亮

趙痙，畢業(yè)于中科院研究生院的計算機科學與技術(shù)專業(yè)。常年從事計算機學科的研究和教學，有較強的專業(yè)

知識和教學能力，能夠根據(jù)學科特點，深入淺出的講解課程內(nèi)容，使學生快速理解掌握，達到教學目標。

授課掙點：親和力強，課堂氛圍輕松，授課思路明朗，能夠讓枯燥的知識形象生動，幫助學員輕松掌握核心

知識點，深受廣大學員喜愛。

教材精講部分［視頻講解I

考試形式

1.公共基礎(chǔ)知識不單獨考試，與其他二級科目組合在一起，作為二級科目考核內(nèi)容的一部分。

2.考試方式為上機考試，10道選擇題，占10分。

知識點分布

I.數(shù)據(jù)結(jié)構(gòu)與算法

2.程序設(shè)計基礎(chǔ)

3.軟件工程基礎(chǔ)

4.數(shù)據(jù)庫設(shè)計基礎(chǔ)

大綱基本要求

1.掌握算法的基本概念。

2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作，

3.掌握基本排序和查找算法。

4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。

5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)的能力。

6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。

第1章數(shù)據(jù)結(jié)構(gòu)與算法［視頻講解］

1.算法的基本概念；算法復雜度的概念和意義(時間復雜度與空間復雜度)。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示：線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。

4.棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算,

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。

6.樹的基本概念；二義樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法(交換類排序，選擇類排序，插入類排序)。

1.1算法

一、算法的基本概念

1.算法的定義

算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的一種描述。

【注意】算法不等于程序，也不等于計算方法。

2.算法的基本特征

(1)可行性(Effectiveness)：算法中的每一個步驟必須能夠?qū)崿F(xiàn)，執(zhí)行的結(jié)果要能夠達到預期的目的。

(2)確定性(Definiteness)：算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋或多義

性。

(3)有窮性(Fineness)：算法必須能在有限的時間(合理的時間)內(nèi)做完，即算法必須能在執(zhí)行有限個步

驟之后終止。

(4)擁有足夠的情報：輸入是否足夠并正確，輸出是否合理,初始狀態(tài)是否正確。

二、算法設(shè)計基本方法

I.列舉法

(1)基本思想

根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的?/p>

(2)特點

簡單，方便用計算機進行大量列舉；情況較多時，工作量將會很大。

<3)使用

將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律，進行分類，減少列舉量。

【例1】今有雞母一，值錢三；雞翁一，值錢二；雞雛一，值錢半。凡百錢買百雞，問雞母、雞翁、雞雛各

幾何？

假設(shè)買母雞I只、公雞J只、小雞KN。根據(jù)題意，粗略的列舉算法描述如下：

FOR1=0TO100STEP1DO

FORJ=0TO100STEP1DO

FORK=0TO100STEP1DO

【卜((l+J+K==100)AND(3*l+2勾+U.5*K==1UU.U))THEN

PRINTI,J,K

)

END

共有三層循環(huán)，每層循環(huán)各需要循環(huán)101次，大約為100萬次。

優(yōu)化后的算法

FOR1=0TO33STEPIDO

FORJ=0TO50-1.5*1STEP1DO

{

K=IOO-I-J

IF(3旬+2*J+0.5*K==100.0)THEN

PRINTI,J,K

}

END

共有兩層循環(huán)，循環(huán)次數(shù)為

33

^(51-1.57)^894

/=0

2.歸納法

(I)基本思想

通過列舉少量的特殊情況，經(jīng)過分析最后找出一般的關(guān)系。

(2)特點

歸納是?種抽象，即從特殊現(xiàn)象中找出??般關(guān)系。

(3)使用

由于在歸納的過程中不可能對所有的情況進行列舉。因此，最后由歸納得到的結(jié)論還只是?種猜測，還需要

對這種猜測加以必要的證明。實際上，通過精心觀察而得到的猜測得不到證實或最后證明猜測是錯的，也是常有

的事。

3.遞推

(I)基本思想

從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。

(2)特點

本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果。

(3)使用

遞推算法在數(shù)值計算中是極為常見的。但是，對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。

4.遞歸

(1)基本思想

為了降低問題的復雜程度，將問題逐層分解，最后歸結(jié)為一些最簡單的問題，這種將問題逐層分解的過程,

實際上并沒有對問題進行求解，而只是當解決r最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜

合。

(2)特點

結(jié)構(gòu)清晰，可讀性強。

(3)使用

遞歸在可計算性理論和算法設(shè)計中占有很重要的地位。

(4)分類

直接遞歸(自己調(diào)用自己)和間接遞歸(P調(diào)用Q,Q又調(diào)用P)。

【例2】編寫一個過程，對于輸入的參數(shù)n,依次打印輸出自然數(shù)1到n。

非遞歸算法：

wrt(intn)

(

FORk=lTOnSTEPIDOPRINTk

RETURN

)

遞歸算法：

wrtl(intn)

(

IF(n#))THEN

(

wrtl(n-l)PRINTn

)

RETURN

5.減半遞推技術(shù)

所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推”，是指重復“減半”的過程。

【例3】設(shè)方程f(x)=0在區(qū)間［a,b］上有實根，且f(a)與f(b)異號。利用二分法求該方程在區(qū)間［a,

用上的一個實根。

用二分法求方程實根的減半遞推過程如下：

(I)首先取給定區(qū)間的中點c=(a+b)/2o

(2)然后判斷f(后是否為0：

如果f(c)=0,則說明c即為所求的根，求解過程結(jié)束；

如果f(c)#0,則根據(jù)以下原則將原區(qū)間減半：

①若f(a)f(c)<0,則取原區(qū)間的前半部分；

②若f(b)f(c)<0,則取原區(qū)間的后半部分。

(3)最后判斷減半后的區(qū)間長度是否已經(jīng)很?。?/p>

①若|a-b|Vg,則過程結(jié)束，取(a+b)/2為根的近似值；

②若|a-則重復上述的減半過程。

6.回溯法

(1)基本思想

通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成

功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探。這種方法稱為回溯法。

(2)特點

在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。

對于這類問題，一種有效的方法是“試工

三、算法復雜度

主要包括時間復雜度和空間復雜度。

1.算法的時間復雜度

(1)定義

執(zhí)行算法所需要的計算工作量。

(2)衡量標準

通常用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運算次數(shù)還與問

題的規(guī)模有關(guān)。

綜上所述，算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的

函數(shù)，即算法的工作量=t(n)。

(3)存在問題

算法所執(zhí)行的基本運算次數(shù)還可能與特定的輸入有關(guān)，而實際上乂不可能將所有可能情況下算法所執(zhí)行的基

本運算次數(shù)都列舉出來。

(4)解決方法

①平均性態(tài)(AverageBehavior)

用各種特定輸入下的基本運算次數(shù)的加權(quán)平均值來度量算法的工作量：

A⑺=￡p(x?(x)

②最壞情況復雜性(Worst-CaseComplexity)

規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)：

W(〃)=max{/(x)}

2.算法的空間復雜度

【定義】執(zhí)行這個算法所需要的內(nèi)存空間。

(1)算法程序所占的空間：

(2)輸入的初始數(shù)據(jù)所占的存儲空間；

(3)算法執(zhí)行過程中所需要的額外空間。

【注意】

①如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。

②在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術(shù)，以便盡量減少不必要的額外

空間。

【考題1】算法的時間復雜度是指(

A.執(zhí)行算法程序所需要的時間

B.算法程序的長度

C.算法執(zhí)行過程中所需要的基本運算次數(shù)

D.算法執(zhí)行過程中所需要的所有運算次數(shù)

E.算法程序中的指令條數(shù)

【答案】C

【解析】算法的時間復雜度是指算法執(zhí)行過程中所需要的基本運算次數(shù)。執(zhí)行算法程序所需要的時間、算法

長度、指令條數(shù)等與時間復雜度沒有直接關(guān)系。

【考題2】算法的空間復雜度是指（）。

A.算法程序的長度

B.算法程序中的指令條數(shù)

C.算法程序所占的存儲空間

D.算法執(zhí)行過程中所需要的存儲空間

E.算法所處理的數(shù)據(jù)量

【答案】D

【解析】算法的空間復雜度是指算法執(zhí)行過程中所需要的存儲空間。算法程序的長度、指令條數(shù)、所處理的

數(shù)據(jù)量等與空間復雜度沒有直接關(guān)系。

1.2數(shù)據(jù)結(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)進行的運算。

討論以上問題的目的：

（I）提高數(shù)據(jù)處理的速度；

（2）盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。

一、什么是數(shù)據(jù)結(jié)構(gòu)

【定義】數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

數(shù)據(jù)元素具有廣泛的含義：

描述一年四季的季節(jié)名：春、夏、秋、冬

表示數(shù)值的各個數(shù)：18、11、35、23、16…

表示家庭成員的各成員名：父親、兒子、女兒

數(shù)據(jù)處理：對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數(shù)

據(jù)元素進行分析。

【注意】作為某種處理，其中的數(shù)據(jù)元素一般具有某種共同特征，一般情況下，在具有相同特征的數(shù)據(jù)元素

集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系，這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。

I.數(shù)據(jù)的邏輯結(jié)構(gòu)

（1）定義

反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息：

①表示數(shù)據(jù)元素的信息；

②表示各數(shù)據(jù)元素之間的前后性關(guān)系。

（2）數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：

一是數(shù)據(jù)元素的集合，通常記為D；

二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R；

即一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=（D,R）。

【例4】?年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成

B=（D,R）

D=｛春，夏，秋，冬｝

R=｛（春，夏），（夏，秋），（秋，冬）｝

2.數(shù)據(jù)的存儲結(jié)構(gòu)

定義：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。

【注意】

①各數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。

②在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

③常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。

④采用不同的存儲結(jié)構(gòu)，具數(shù)據(jù)處理的效率是不同的。

二、數(shù)據(jù)結(jié)構(gòu)的圖形表示

一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。

（1）對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為

結(jié)點；

（2）對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點，有時箭頭可省去。

圖M一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示圖（線性）

圖1-2家庭成員間關(guān)系數(shù)據(jù)結(jié)構(gòu)的圖形表示（樹型結(jié)構(gòu)）

【考題】下列敘述中正確的是（

A.線性表是線性結(jié)構(gòu)

B.棧與隊列是非線性結(jié)構(gòu)

C.循環(huán)鏈表是非線性結(jié)構(gòu)

D.二叉樹是線性結(jié)構(gòu)

【答案】A

【解析】選項A正確；選項B,棧和隊列都是線性結(jié)構(gòu)，二者區(qū)別是，棧只允許在一端插入和刪除，隊列

只允許在一端插入，在另一端刪除；選項C,循環(huán)鏈表是線性表的鏈式存儲結(jié)構(gòu)；選項D,二叉樹是一種典型的

非線性結(jié)構(gòu)。

三、線性結(jié)構(gòu)與非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性

結(jié)構(gòu)”

如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：

(1)有且只有一個根結(jié)點：

(2)每一個結(jié)點最多有一個前件，也最多有一個后件。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，線性結(jié)構(gòu)又稱線性表。

【注意】在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu),

則稱之為非線性結(jié)構(gòu)。

【考題】設(shè)數(shù)據(jù)集合為D={1,3,5,7,9},D上的關(guān)系為R。下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為非線性結(jié)

構(gòu)的是()。

A.R={(5,1),(7,9),(1,7),(9,3)}

B.R={(9,7),(L3),(7,I),(3,5)}

C.R={(1,9),(9,7),(7,5),(5,3)}

D.R={(I,3),(3,5),(5,9)}

【答案】D

【解析】如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：①有且只有一個根結(jié)點；②每一個結(jié)點最多有一個前

件，也最多有一個后件。則該數(shù)據(jù)垢構(gòu)為線性結(jié)構(gòu)。

選項A：5是根結(jié)點，5的后件是1,1的后件是7,7的后件是9,9的后件是3,故選項A是線性結(jié)構(gòu)；

選項B：9是根結(jié)點，9的后件是7,7的后件是1,1的后件是3,3的后件是5,故選項B是線性結(jié)構(gòu)；

選項C：1是根結(jié)點，1的后件是9,9的后件是7,7的后件是5,5的后件是3,故選項C是線性結(jié)構(gòu)：

選項D：I是根結(jié)點，1的后件是3,3的后件是5,5的后件是9,7也是根結(jié)點,沒有前件也沒有后件，線

性數(shù)據(jù)結(jié)構(gòu)第一個條件不滿足，故選項D是非線性結(jié)構(gòu)，即選項D正確。

1.3線性表及其順序存儲結(jié)構(gòu)

一、線性表的基本概念

線性表(LinearList)是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。如：一個n維向量、矩陣，學生情況登記表。

線性表是由n(n^O)個數(shù)據(jù)元素a”a?,…，組成的一個芍限序列，表中的每一個數(shù)據(jù)元素，除了第一

個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為(a,,

a2,ai，a?),其中％(i=l,2,n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點。

車空線性表有如下一些結(jié)構(gòu)特征：

(1)有且只有一個根結(jié)點山它無前件；

(2)有且只有一個終端結(jié)點加，它無后件；

(3)除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。

【說明】

①線性表中結(jié)點的個數(shù)n稱為線性表的長度。

②當n=0時，稱為空表。

二、線性表的順序存儲結(jié)構(gòu)

1.特點

（1）線性表中所有元素所占的存儲空間是連續(xù)的；

（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的

前面。

圖1-3線性表的順序存儲結(jié)構(gòu)

【注意】

①在程序設(shè)計語言中，通常定義一個一維數(shù)組來表示線性表的順序存儲空間。

②在用一維數(shù)組存放線性表時，該一維數(shù)組的長度通常要定義得比線性表的實際長度大一些，以便對線性表

進行各種運算，特別是插入運算。

2.線性表的相關(guān)操作

（I）插入：在線性表的指定位置處加入一個新的元素，

（2）刪除：在線性表中刪除指定的元素。

（3）查找：在線性表中查找某個（或某些）特定的元素。

（4）排序：對線性表中的元素進行整序（即線性表的）。

（5）分解：按要求將一個線性表分解成多個線性表。

（6）合并：按要求將多個線性表合并成一個線性表。

（7）復制：復制一個線性表。

（8）逆轉(zhuǎn):逆轉(zhuǎn)一個線性表。

三、順序表的插入運算

【例5】長度為8的線性表順序存儲在長度為10的存儲空間中。在第2個元素之前插入一個新元素87。然

后在線性表的第9個元素之前插入?個新元素14o

V（l：10）V（l：10）V（l：10）

129129129

叵］—218287287

356318318

463456456

535563563

624635635

731724724

847831831

9回一947914

10101047

（a）長度為8的線性表（b）插入元素87后的線性表（c）插入元素14后的線性表

圖1-4線性表在順序存儲結(jié)構(gòu)下的插入

線性表的存儲空間從1到m,線性表的長度為n（nWm）,插入的位置為i（i表示在第i個元素之前插入）。

線性表的插入操作如下：

第一步首先處理以下三種異常情況：

①當存儲空間已滿（即n=m）時為“上溢”錯誤，不能進行插入，算法結(jié)束；

②當i>n時，認為在最后一個元素之后插入；

③當i<l時，認為在第I個元素之前插入。

第二步從最后一個元素開始，直到笫i個元素，每一個元素往后移動一個位置。

第三步將新元素插入到第i個位置，線性表的長度加1。

四、順序表的刪除運算

【例6］長度為8的線性表順序存儲在長度為10的存儲空間中?，F(xiàn)在要求刪除線性表中的第1個元素。再

刪除線性表中的第6個元素。

V（l：10）V（l:io）V（I：10）

129118118

218256256

356363363

463435435

535524524

624631647

7317477

84788

999

101010

（a）長度為8的線性表（b）刪除兀素29后的線性表（c）刪除元素31后的線性表

S1-5線性表在順序存儲結(jié)構(gòu)下的刪除

線性表的存儲空間從1至Um,線性表的長度為n（n^m）,刪除的位置為i（表示刪除第i個元素）。線性表

的刪除操作如下：

第一步首先處理以下兩種異常情況：

①當線性表為空（即n=0）時錯誤，不能進行刪除，算法結(jié)束；

②當i<l或>1!時?，錯誤，不能進行刪除，算法結(jié)束。

第二步刪除線性表中的第i個元素。

第三步從第i+1個元素開始，直到最后一個元素，其中每一個元素均依次往前移動一個位置。線性表的長

度減小1。

1.4棧和隊列

一、棧及其基本運算

1.什么是棧

【定義】限定在一端進行插入與刪除的線性表

【說明】

①允許插入與刪除的一端稱為棧頂（指針top）,而不允許插入與刪除的另一端稱為棧底（指針bottom）。

②棧是按照“先進后出"（FILO）的原則組織數(shù)據(jù)。

③棧具有記憶作用。

④往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素（即刪除棧頂元素）稱為出棧運算.

人棧退棧

2.棧的順序存儲及其運算

圖1-7（a）是容量為10的棧順序存儲空間，棧中已有6個元素；圖1-7（b）與圖1-7（c）分別為入棧與退

棧后的狀態(tài)。

S（l：10）S（l：10）S（l：10）

101010

999

8top—?8Y8

77Xtop—>7X

top—>6F6F6F

5E5E5E

4D4D4D

3C3C3C

2B2B2B

rA

bottom—1bottom—?1Abottom—>1A

（a）有6個元素的棧（b）插入X與Y后的棧（c）退出一個元素后的棧

圖1-7棧在順序存儲結(jié)構(gòu)下的運算

（1）入棧運算

入棧運算是指在棧頂位置插入一個新元素。操作過程如下：

①首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后一個位置。如果是，則說明棧空間已滿，不可能再進行入

棧操作（這種情況稱為棧“上溢”錯誤），算法結(jié)束。

②然后將棧頂指針進一（即lop加1）。

③最后將新元素x插入棧頂指針指向的位置。

（2）退棧運算

退校運算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：

①首先判斷棧頂指針是否為0。如果是，則說明?？眨豢赡苓M行退棧操作（這種情況稱為?！跋乱纭卞e誤），

算法結(jié)束。

②然后將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量。

③最后將棧頂指針退一（即lop減1）。

（3）讀棧頂元素

讀棧頂元素是指將棧頂元素賦紿一個指定的變量。操作過程如下：

①首先判斷棧頂指針是否為0。如果是，則說明枝空，讀不到棧頂元素，算法結(jié)束。

②然后將棧頂元素賦給指定的變量y?

【注意】這個運算不刪除棧頂元素，只是將它的值賦給一個變量，因此，在這個運算中棧頂指針不會改變。

【考題】下列關(guān)于棧的敘述中正確的是（）。

A.在棧中只能插入數(shù)據(jù)

B.在棧中只能刪除數(shù)據(jù)

C.棧是先進先出的線性表

D.枝是先進后出的線性表

E.棧是一種非線性結(jié)構(gòu)

【答案】D

【解析】在棧中，只允許在棧頂一端進行插入和刪除，所以A、B錯誤；隊列是“先進先出”的線性表，棧

是“先進后出”的線性表，所以C、E錯誤，D正確。

二、隊列及其基本運算

1.什么是隊列

加入的元素總是插入到線性表的末尾，并且乂總是從線性表的頭部取出（刪除）元素。這種線性表稱為隊列。

【說明】

①允許插入的一端稱為隊尾（rear）,允許刪除的一端稱為隊頭（from）。

②在隊列中按照“先進先出”的原則進行操作。

退隊-ABCDEF一入隊

tT

frontrear

圖1-8具有6個元素的隊列示意圖

front—*

Afront—?front-?

在

Ccc

rear—>rear—>5D

rear—>E

(a)一個隊列(b)刪除一個元素后的隊列?插入元素E后的隊列

圖1-9隊列運算示意圖

【考題】下列關(guān)于隊列的敘述中正確的是()。

A.在隊列中只能插入數(shù)據(jù)

B.在隊列中只能刪除數(shù)據(jù)

C.隊列是先進先出的線性表

D.隊列是先進后出的線性表

【答案】C

【解析】在隊列中，只允許在一端進行插入，在另一端進行刪除，所以A、B錯誤；隊列是“先進先出”的

線性表，枝是“先進后出”的線性表，所以D錯誤，選擇C。

2.循環(huán)隊列及其運算

【定義】循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)

使用。

rear—?

front—>

圖1-10循環(huán)隊列存儲空間示意圖

月隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。

在實際使用循環(huán)隊列時，為了能區(qū)分隊列滿還是隊列空，通常還需增加一個標志s,s值的定義如下:

J0表示隊列空

11表示隊列非空

由此可以得出隊列空與隊列滿的條件如下:

隊列空的條件為s=0；

隊列滿的條件為s=I且front=rearn

Q（l：8）Q（l：8）Q（l：8）

88X8X

rear—*7F7F7F

6E6E6E

5D5D51）

4C4C4C

3B3B3B

2A2Afront—*2

front—>1front—?1Yrear—>IY

rear—?

（a）具有6個元素的循環(huán)隊列（b）加入X、Y后的循環(huán)隊列（c）退出一個元素后的循環(huán)隊列

圖1-11循環(huán)隊列運算示意圖

（I）入隊運算

入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。操作過程如下：

①首先判斷循環(huán)隊列是否滿。當循環(huán)隊列非空（S=l）且隊尾指針等于排頭指針時，說明循環(huán)隊列已滿，不

能進行入隊運算。這種情況稱為“上溢”。此時算法結(jié)束。

②然后將隊尾指針進?（即rear=rear+1）,并當rear=m+1時置rear=1?

③最后將新元素x插入隊尾指釬指向的位置，并且置循環(huán)隊列非空標志。

（2）退隊運算

退隊運算是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。操作過程如下：

①首先判斷循環(huán)隊列是否為空。當循環(huán)隊列為空（s=0）時，不能進行退隊運算。這種情況稱為“下溢”。

此時算法結(jié)束。

②然后將排頭指針進一（即front=fronl+1）,并當front=m4-1時置front=1。

③再將排頭指針指向的元素賦給指定的變量。

④最后判斷退隊后循環(huán)隊列是否為空。當fronl=rear時置循環(huán)隊列空標志（即s=0）。

【考題】設(shè)循環(huán)隊列為Q（I：m）,其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊與退隊運算后，front=

30,rear=IOo現(xiàn)要在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)為（）。

A.19

B.20

C.m—19

D.m—20

【答案】D

【解析】在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)，實際上就是求循環(huán)隊列中元素的個數(shù)。

元素的個數(shù)=（rear-front+m）modm=（10—30+m）modm=m—20,選項D正確。

1.5線性鏈表

一、線性鏈表的基本概念

【定義】線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。線性鏈表的數(shù)據(jù)結(jié)構(gòu)包括兩部分，一是數(shù)據(jù)元素的值，二是

數(shù)據(jù)元素之間的前后件關(guān)系。

存儲序號數(shù)據(jù)域指針域

V(i)NEXT(i)

圖1-12線性鏈表的一個存儲結(jié)點

為什么用線性鏈表？

（I）線性表順序存儲結(jié)構(gòu)存在的缺點：

①插入或刪除過程中需要移動大量的數(shù)據(jù)元素。

②出現(xiàn)線性表的存儲空間已滿，但還需要插入新的元素時，就會發(fā)生“上溢”錯誤。

③線性表的順序存儲結(jié)構(gòu)不便于存儲空間的動態(tài)分配。

（2）線性表鏈式存儲結(jié)構(gòu)存在的優(yōu)點：

在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)

系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

【說明】

①在線性鏈表中，用一個專門的指針HEAD指向線性鏈表中第?個數(shù)據(jù)元素的結(jié)點（即存放線性表中第一

個數(shù)據(jù)元素的存儲結(jié)點的序號）。線性表中最后一個元素沒有后件，因此，線性鏈表中最后一個結(jié)點的指針域為

空（用NULL或0表示），表示鏈表終止。

HEAD->數(shù)據(jù)］數(shù)據(jù)2數(shù)據(jù)nNULL

圖1-13線性鏈表的邏輯結(jié)構(gòu)

②在線性表的鏈式存儲結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，并且各結(jié)點在存儲空間中的位置關(guān)系與

邏輯關(guān)系也不一致。

③當HEAD=NULL（或0）時稱為空表。

V(i)NEXT(i)

9

a2

HEAD2

33%1

4

510

a4

6

7

8

95

100

a5

(a)線性域表的物理狀態(tài)

(b)線性鏈表的邏輯狀態(tài)

圖1-14線性鏈表例

1.雙向鏈表

對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針(Llink),用以指向其前件結(jié)點；另一個稱為右指

針(Rlink),用以指向其后件結(jié)點。

圖1-16帶鏈的棧

在實際應(yīng)用中，帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。

(b)在從可利用棧取得一個結(jié)點p

圖1-17可利用棧及其運算

3.帶鏈的隊列

隊列也是線性表，也可以采用鏈式存儲結(jié)構(gòu)。

0

frontrear

(a)帶鏈的隊列

front

(b)在帶鏈的隊列中插入一個新結(jié)點

(C)在帶鏈的隊列中刪除一個結(jié)點

圖1-18帶鏈的隊列及其運算

二、線性鏈表的基本運算

線性鏈表的運算主要有以下幾個：

①插入：在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。

②刪除：在線性鏈表中刪除包含指定元素的結(jié)點。

③合并：將兩個線性鏈表按要求合并成一個線性鏈表。

④分解：將一個線性鏈表按要求進行分解。

⑤逆轉(zhuǎn)

⑥復制

⑦排序

⑧查找

1.在線性鏈表中查找指定元素

從頭指針指向的結(jié)點開始往后沿指針進行掃描，直到后面已沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為X為止。

因此，由這種方法找到的結(jié)點P有兩種可能：

①當線性鏈表中存在包含元素X的結(jié)點時，則找到的p為第?次遇到的包含元素X的前?個結(jié)點序號;

②當線性鏈表中不存在包含元素X的結(jié)點時，則找到的P為線性鏈表中的最后一個結(jié)點號。

2.線性鏈表的插入

(c)p插入到q之后

圖1-19線性鏈表的插入

3.線性鏈表的刪除

TOP0

<O將被刪除的結(jié)點p送回可利用棧后

圖1-20線性鏈表的刪除

二、循環(huán)鏈表

線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在?個問題，在運算過程中對于空表和對第一個結(jié)

點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。

I.循環(huán)鏈表的特點

（1）增加了表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點。循

環(huán)鏈表的頭指針指向表頭結(jié)點。

（2）循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)

成了一個環(huán)狀鏈。

HEAD

表頭結(jié)點

（a）非空循環(huán)漣表

HEAD-,

表頭結(jié)點

（b）空循環(huán)捱表

圖1-21循環(huán)鏈表的邏輯狀態(tài)

2.循環(huán)鏈表與線性單鏈表相比主要有以下兩個方面的優(yōu)點：

（1）在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點。線

性單鏈表做不到這一點。

（2）由于在循環(huán)鏈表中設(shè)置了?個表頭結(jié)點，因此，在任何情況下循環(huán)鏈表中至少有一個結(jié)點存在，從而

使空表與非空表的運算統(tǒng)一。

1.6樹與二叉樹

一、樹的基本概念

【定義】樹（Tree）是一種簡單的非線性結(jié)構(gòu)，樹中所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。

圖1-22學校行政層次結(jié)構(gòu)樹

【說明】

①在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹口勺根結(jié)點，簡稱

為樹的根。

②在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。

③在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。

④在樹中，所有結(jié)點中的最大的度稱為樹的度。

⑤樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1。

⑥根結(jié)點在第1層。同一層上所有結(jié)點的所有子結(jié)點都在下一層。樹的最大層次稱為樹的深度。

樹在計算機中的存儲方式：

樹在計算機中通常用多重鏈表表示。多重鏈表中的每個結(jié)點描述了樹中對應(yīng)結(jié)點的信息，而每個結(jié)點中的鏈

域（指針域）個數(shù)將隨樹中該結(jié)點的度而定。

??

value(值)degree(?)link.link??linkn

圖1-23樹鏈表中的結(jié)點結(jié)構(gòu)

二、二又樹及其基本性質(zhì)

1.什么是二叉樹

二叉樹具有以下兩個特點：

①非空二叉樹只有一個根結(jié)點；

②每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。

【注意】在二叉樹中，每一個垢點的度最大為2。

回

（a）只有根結(jié)點的二叉樹（b）深度為4的二叉樹

圖1-24二叉樹例

2.二叉樹的基本性質(zhì)

【性質(zhì)1］在二叉樹的第k層上，最多有2廣1（k21）個結(jié)點。

【性質(zhì)2】深度為m的二叉樹最多有方一1個結(jié)點,即21「+22「+…+2m「=2m-L

【性質(zhì)3】在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。

【性質(zhì)4】具有n個結(jié)點的二叉樹，其深度至少為［log2n］+l,其中［logzn］表示取log2n的整數(shù)部分。

【考題1］在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（）。

A.32

B.31

C.16

D.15

【答案】C

【解析】葉子結(jié)點的個數(shù)=2<51）=16。

【考題2】設(shè)樹T的度為4,其中度為1,2,3,4的結(jié)點個數(shù)分別為4,2,1,1。則樹丁口的葉子結(jié)點數(shù)

為（）。

A.8

B.7

C.6

D.5

【答案】A

【解析】結(jié)點數(shù)為所有結(jié)點的度數(shù)之和加1，同時，注意到葉子結(jié)點的度數(shù)為0,則總結(jié)點數(shù)（設(shè)葉子結(jié)點

數(shù)為X）l*4+2*2+3*l+4*l+X*0+l=16,葉子結(jié)點數(shù)為X=16—4—2—1-1=8。

3.滿二叉樹與完全二叉樹

（1）滿二叉樹

【定義】滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。

【說明】在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2廣1個結(jié)點，且深

度為m的滿二叉樹有2m-l個結(jié)點。