在一般的計算機系統(tǒng)中，基本的運算和操作有以下4

第1章數(shù)據(jù)結(jié)構(gòu)與算法類：算大運算、邏輯運算、關(guān)系運算和數(shù)據(jù)傳輸。

（2）算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序

通過對部分考生的調(diào)查以及對近年真題的總結(jié)分析，

稱為算法的控制結(jié)構(gòu)。

筆試部分經(jīng)常考察的是算法復(fù)雜度、數(shù)據(jù)結(jié)構(gòu)的概念、棧、

描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、

二叉樹的遍歷、二分法杳找，讀者應(yīng)對此部分進行重點學(xué)

算法描述語言等。一個算法一般都可■以用順序、選擇、循環(huán)

習(xí)。

3種基本控制結(jié)構(gòu)組合而成.

具體重點學(xué)習(xí)知識點：

考點2算法復(fù)雜度

1.算法的概念、算法時間復(fù)雜度及空間復(fù)雜度的概念

2.數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輯結(jié)構(gòu)及物理結(jié)構(gòu)的定義考試鏈接：

3.棧的定義及其運算、線性鏈表的存儲方式考點2在筆試考試中，是一個經(jīng)常考察的內(nèi)容，在筆試考試中出現(xiàn)

4.樹與二叉樹的概念、二叉樹的基本性質(zhì)、完全二叉的幾率為70%,重要是以選擇的形式出現(xiàn)，分值為2分，此考點為重點識

樹的概念、二叉樹的遍歷記內(nèi)容，淡者還應(yīng)當(dāng)識記算法時間復(fù)雜度及空間復(fù)雜度的榻念。

5.二分查找法1.算法的時間復(fù)雜度

6.冒泡排序法算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。

同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程

算法序進行編譯，或者在不同的計穿機上運營，效率均不同。這

表白使月絕對的時間單位衡量算法的效率是不合適的。撇開

考點1算法的基本概念

這些與計算機硬件、軟件有關(guān)的因素，可以認(rèn)為一個特定算

考試鏈接：

法〃運營工作量〃的大小，只依賴于問題的規(guī)模（通常用整數(shù)

考點1在卷試考試中考核的幾率為30%,重要是以填空題的形式出現(xiàn),

n表達），它是問題規(guī)模的函數(shù)。即

分值為2分，此考點為識記內(nèi)容，讀者還應(yīng)當(dāng)了解算法中對數(shù)據(jù)的基本運

算法的工作量=f（ri）

算。

2.算法的空間復(fù)雜度

計算機解題的過程事'丈上是在‘文行某種算法，這種弊

算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空

法稱為計算機算法。

間。

1.算法的基本特性：可行性、擬定性、有窮性、擁有足一個算法所占用的存儲空間涉及算法程序所占的空間、輸入

的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的

夠的情報。額外空間。其中額外空間涉及算法程序執(zhí)行過程中的工作單

元以及其種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。假如額外空間

2.算法的基本要素：

量相對子問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。

在許多實際問題中，為了減少算法所占的存儲空間，通常

（1）算法中對數(shù)據(jù)的運算和操作

采用壓縮存儲技術(shù)，以便盡展減少不必要的額外空間。

一個算法由兩種基本要素組成：一是對數(shù)據(jù)對象的運

疑難解答：算法的工作量用什么來計算？

算和操作；二是算法的控制結(jié)構(gòu)。

算法的工作量用算法所執(zhí)行的基本運算次數(shù)來計算，而算法所執(zhí)行的后件關(guān)系，一般用二元組來表達。

基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量才（n）,其中n是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為

問題的規(guī)模。數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系也許與

邏輯關(guān)系不同，因此，為了表達存放在計算機存儲空間中

考點3數(shù)據(jù)結(jié)構(gòu)的定義

的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的

考試鏈接：

存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放

考點3在算試考試中，是一個經(jīng)?？疾斓膬?nèi)容，在冬試考試中出現(xiàn)

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

的幾率為70隊重要是以逸擇的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表達成多種存儲結(jié)

容，讀者還應(yīng)當(dāng)識記數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的概念。

構(gòu)，常月的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。而采

數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，重要研究和討論以

用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)解決的效率是不同的。因此，在

下三個方面：

進行數(shù)據(jù)解決時，選擇合適的存儲結(jié)構(gòu)是很重要的。

<1）數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系，

即數(shù)據(jù)的邏輯結(jié)構(gòu)；考點4線性結(jié)構(gòu)與非線性結(jié)構(gòu)

（2）在對數(shù)據(jù)元素進行解決時，各數(shù)據(jù)元素在計算機考試鏈接：

中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；考點4在筆試考試中，雖然說不是考試經(jīng)?？疾斓膬?nèi)容，但讀者還

（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。是對此考點有所了解，在邕試考試中出現(xiàn)的兒率為30隊重要是以填空題

數(shù)據(jù)：是對客觀事物的符號表達，在計算機科學(xué)中是出現(xiàn)的彩民出現(xiàn)，分值為2分，此考點為識記內(nèi)露.

指所有能輸入到計算機中并被計算機程序解決的符號的總根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜限

稱.度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機程序中通常作構(gòu)。假如一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：

為一個整體進行考慮和解決。（1）有且只有一個根結(jié)點；

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的（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ù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，

它可以用一個數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)疑難解答：空的數(shù)據(jù)結(jié)構(gòu)於線性結(jié)構(gòu)還足非線性結(jié)構(gòu)？

系來表達。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根

合，通常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元素之間的據(jù)具體情況來擬定。假如對該數(shù)據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)則來

前后件關(guān)系，通常記為R。一個數(shù)據(jù)結(jié)構(gòu)可以表達成解決的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。

B=（D,R）

1.3棧及線性鏈表

其中B表達數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前

考點5棧及其基本運算考點6線性鏈表的基本概念

考試飪接：考試鏈接：

考點5在邕試考試中，是一個必考的內(nèi)容，在筆,試考試中出現(xiàn)的幾考點6在苣試考試中出現(xiàn)的幾率為30丸魚要是以選擇的形式出現(xiàn)，

率為100$,重要是以選擇的形式出現(xiàn)，分值為2分，此考點為重點掌握內(nèi)分值為2分，此考點為識記內(nèi)容。重點識記結(jié)點的組成。

容，讀者應(yīng)當(dāng)掌握棧的運算。在鏈?zhǔn)酱鎯Ψ绞街?，?guī)定每個結(jié)點由兩部分組成：一部

1.棧的基本概念分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放

棧是限定只在一端進行插入與刪除的線性表，通常稱指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后

插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元一個結(jié)點（即前件或后件）。

素時稱為空淺。棧頂元素總是后被插入的元素，從而也是最鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒磉_線性結(jié)構(gòu)，也可用于表達

先被刪除的元素；棧底元素總是最先被插入的元素，從而也非線性結(jié)構(gòu)。

是最后才干被刪除的元素。棧是按照〃先進后出"或〃后進先（1）線性鏈表

出”的原則組織數(shù)據(jù)的。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。

2.棧的順序存儲及其運算在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)立兩個指

用一維數(shù)組S（1：m）作為棧的順序存儲空間，其中m為針，一人稱為左指針，用以指向其前件結(jié)點；另一個稱為右

最大容量。指針，月以指向其后件結(jié)點。這樣的表稱為雙向鏈表。

在棧的順序存儲空間S（1：m）+,S（bottom）為棧底（2）帶鏈的棧

棧乜是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。帶鏈的棧可

元素，S（top）為棧頂元素。lop=（）表達?？?；top=m表達棧

以用來收集計算機存儲空間中所有空閑的存儲結(jié)點，這種

曬。帶鏈的棧稱為可運用棧。

棧的基本運算有三種：入棧、退棧與讀棧頂元素。

疑難解答：在鏈?zhǔn)浇Y(jié)構(gòu)中，存儲空間位置關(guān)系與邏輯關(guān)系是什

（1）入棧運算：入棧運算是指在棧頂位置插入一個新

元素。一方面將棧頂指針加一（即top加1）,然后將新元素么？

插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間

的最后一個位置時，說明棧空間已滿，不也許再進行入棧

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)

操作。這種嘴況稱為棧〃上溢”錯誤。

（2）退棧運算：退棧是指取出棧頂元素并賦給一個指點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之

定的變量。一方面將棧頂元素（棧頂指針指向的元素）賦給

一個指定的變量，然后將棧頂指針減一（即top減1）。當(dāng)棧間的邏輯關(guān)系是由指針域來擬定的。

頂指針為0時，說明?？眨豢蛇M行退棧操作。這種情況稱

為棧的〃下溢〃錯誤。1.4樹與二叉樹

（3）讀枝頂元素：讀棧頂元素是指將棧頂元素賦給一

個指定的變量。這個運算不刪除棧頂元素，只是將它賦給一

考點7樹與二叉樹及其基本性質(zhì)

個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為。時，說明

棧空，讀不到棧頂元素。

考試鏈接：

考點7在苣試考試中，是一個必考的內(nèi)容，在名試考試中出現(xiàn)的幾率

小技巧：棧是按照“先進后出"或"后進先出”的原則組織數(shù)據(jù),

為100%,重要是以選擇的形式出現(xiàn)，花時也有出現(xiàn)在填空題中，分值為2

但是出棧方式有多種選擇，在考題中經(jīng)?？疾旄鞣N不同的出棧方式。

分，此考點、為重點掌握內(nèi)容。重點識記樹及二叉樹的性質(zhì)。

點）總是比度為2的結(jié)點多一個。

誤區(qū)警示：

性質(zhì)4：具有n個結(jié)點的二叉樹，其深度至少為[log2n]

滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應(yīng)當(dāng)+1,其口[log2n]表達取log2n的整數(shù)部分。

注意兩者的區(qū)別。

小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還

1.樹的基本概念

是后序遍歷，：叉樹的葉子結(jié)點的先后順序都是不變的。

樹（tree）是一種簡樸的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，每

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

一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只

滿二叉樹是指這樣的一種二叉樹：除最后一層外，每

有一個，稱為樹的根結(jié)點。每一個結(jié)點可以有多個后件，它

一層上的所有結(jié)點都有兩個子結(jié)點。在滿二叉樹中，每一層

們稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。

上的結(jié)點數(shù)都達成最大值，即在滿二叉樹的第k層上有2k-1

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

個結(jié)點，且深度為m的滿二叉樹有2m—1個結(jié)點。

的度。葉子結(jié)點的度為0。在樹中，所有結(jié)點中的最大的度

完全二又樹是指這樣的二叉樹：除最后一層外，每一層

稱為樹的度。

上的結(jié)點數(shù)均達成最大值；在最后一層上只缺少右邊的若干

2.二義樹及其基本性質(zhì)

結(jié)點。

（1）二叉樹的定義

對于完全二叉樹來說，葉子結(jié)點只也許在層次最大的

二又樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個特

兩層上已現(xiàn)：對于任何一個結(jié)點，若其右分支下的子孫結(jié)點

，占、、、?.

的最大層次為P,則其左分支下的子孫結(jié)點的最大層次或為

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

P,或為p+1。

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

完全二叉樹具有以下兩個性質(zhì)：

左了?樹和右了樹。

性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為[logzn]+1。

由以上特點可以看出，在二叉樹中，每一個結(jié)點的度

性質(zhì)6:設(shè)完全二又樹共有n個結(jié)點。假如從根結(jié)點開始，

最大為2,即所有子樹（左子樹或右子樹）也均為二叉樹，而

按層次（每一層從左到右）用自然數(shù)1,2,……，n給結(jié)點

樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。此外，二叉樹中

進行編號，則對于編號為k（k=l,2,……，n）的結(jié)點有以

的每個結(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹

下結(jié)論：

中,一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有

①若k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>l,

右子樹而沒有左子樹。當(dāng)一-個結(jié)點既沒有左子樹也沒有右子

則該結(jié)點的父結(jié)點編號為INT（k/2）o

樹時，該結(jié)點即為葉子結(jié)點。

②若2kWn,則編號為k的結(jié)點的左子結(jié)點編號為2k：否

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

則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。

二叉樹具有以下幾個性質(zhì)：

③若2k+lWn,則編號為k的結(jié)點的右子結(jié)點編號為

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

2k+l；否則該結(jié)點無右子結(jié)點。

點；

性質(zhì)2:深度為m的二叉樹最多有2m-1個結(jié)點；考點8二叉樹的遍歷

性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)

考試鏈接:只能用順序查找。

考點8在近試考試中考核幾率為30$,分值為2分，讀者應(yīng)當(dāng)他熟掌

考點10二分法查找

握各種遍歷的具體算法，能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果。

考試鏈接：

在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷

考點10在苣試考試中考核幾率為30%,一般出現(xiàn)填空題中，分值為2

右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的順序，二

分，考核比較多查找的比較次數(shù)，讀者應(yīng)當(dāng)具體掌握二分查找法的算法。

叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。

二分法只合用于順序存儲的，按非遞減排列的有序表，

（1）前序遍歷：先訪問根結(jié)點、然后遍歷左子樹，最后遍

歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，其方法如下：

然后遍歷左子樹，最后遍歷右子樹。

（2）中序遍歷：先遍歷左子樹、然后訪問根結(jié)點，最后遍設(shè)有序線性表的長度為n,被查找的元索為i,

歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，

然后訪問根結(jié)點，最后遍歷右子樹。（1）將i與線性表的中間項進行比較；

（3）后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪

問根結(jié)點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，（2）若i與中間項的值相等，則查找成功；

然后遍歷右子樹，最后訪問根結(jié)點。

（3）若i小于中間項，則在線性表的前半部分以相同的方法

查找；

（4）若i大于中間項，則在線性表的后半部分以相同的方法

疑難解答：樹與二叉樹的不同之處是什么？

杳找。

在二叉樹中，每一個結(jié)點的度最大為2,即所有子樹（左子樹或右子

疑難解答：二分查找法合用于哪種情況？

樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。

二分查找法只合用于順序存儲的有序表。在此所說的有序表是指

1.5查找技術(shù)線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相

等）。

考點9順序查找

這人過程一直進行到查找成功或于表長度為0為止。

考試鏈接：

對于長度為n的有序線性表，在最壞情況下，二分查找只需

考點9在卷試考試中考核幾率在30$,一般出現(xiàn)選擇題中，分值為2

要比較log2n次。

分，讀者應(yīng)當(dāng)具體掌握順序查找的算法。

查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元1.6排序技術(shù)

素。從線性表的第一個元素開始，依次將線性表中的元素與

考點11互換類排序法

被查找的元索相比較，若相等則表達查找成功；若線性表中

考試能接：

所有的元素都與被查找元素進行了比較但都不相等，則表

考點11屬于比較難的內(nèi)容，一般以選杼題的形式考察，考核幾率為

達查找失敗。

30%,分值約為2分，讀者應(yīng)當(dāng)純熟掌握幾種排序算法的基本過程。

在下列兩種情況下也只能采用順序查找：

冒泡排序法和快速排序法都屬于互換類排序法。

（1）假如線性表為無序表，則不管是順序存儲結(jié)構(gòu)還

（1）冒泡排序法

是鏈?zhǔn)酱鎯Y(jié)構(gòu)，只能用順序查找。

一方面，從表頭開始往后掃描線性表，逐次比較相鄰

（2）即使是有序線性表，假如采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也兩個元素的大小，若前面的元素大于后面的元素，則將它

們互換，不斷地將兩個相鄰元素中的大者往后移動，最后結(jié)構(gòu)和非線性結(jié)構(gòu)

最大者到了線性表的最后。C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D）動態(tài)

然后，從后到前掃描剩下的線性表，逐次比較相鄰兩結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

個元素的大小，若后面的元素小于前面的元素，則將它們解析：邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線性

互換，不斷地將兩個相鄰元素中的小者往前移動，最后最結(jié)構(gòu)表達數(shù)據(jù)元素之間為一對一的關(guān)系，非線性結(jié)構(gòu)表達

小者到了線喋表的最前面。數(shù)據(jù)元素之間為一對多或者多對一的關(guān)系，所以答案為B）。

對剩下的線性表反復(fù)上述過程，直到剩下的線性表變答案：B）

空為止，此時已經(jīng)排好序?！纠?】以下不是棧的基本運算。（考點5）

在最壞的情況下，冒泡排序需要比較次數(shù)為n（n-l）A）判斷棧是否為素空B）將棧

/2o置為空棧

（2）快速排序法C）刪除棧頂元素D）刪除

它的基本思想是：任取待排序序列中的某個元素作為基準(zhǔn)

棧底元素

（一般取第一個元素），通過一趟排序，將待排元素分為左

右兩個了序列，左了序列元素的排序碼均小丁或等丁基在解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），

元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序

碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對

有序。

棧的操作都是在棧頂進行的。

疑難解答：冒泡排序和快速排序的平均執(zhí)行時間分別是多少？

冒泡排序法的平均執(zhí)行時間是0（n2）,而快速排序法的平均執(zhí)行時間答案：D）

是0（nlog2n）?

【例4】鏈表不具有的特點是。（考點6）

1.7例題詳解A）可隨機訪問任意?個結(jié)點B）

一、選擇題插入和刪除不需要移動任何元素

【例I】算法的時間復(fù)雜度取決于O（考點2）C）不必事先估計存儲空間D）

所需空間與其長度成正比

A）問題的規(guī)模B）待解決的

數(shù)據(jù)的初態(tài)解析：順序表可以隨機訪問任意一個結(jié)點，而鏈表必

C）問題的難度D）A）和B）須從第一個數(shù)據(jù)結(jié)點出發(fā)，逐個杳找每個結(jié)點。所以答案為

解析：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，在A）o

答奚：A）

同一個問題規(guī)模下，并且與輸入數(shù)據(jù)有關(guān)。即與輸入數(shù)據(jù)所

有的也許取宜范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)?！纠?】已知某二叉樹的后序遍歷序列是DACBE,

中序遍歷序列是DEBAC,則它的前序遍歷序列是

答案：D）

【例2】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)_。（考點8）

A）ACBEDB）DEABC

結(jié)構(gòu)提成______。（考點3）

C)DECABD)EDBAC

A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B）線性

解析：后序遍歷的順序是〃左子樹一右子樹一根結(jié)點〃；二、填空題

中序遍歷順序是〃左子樹一根結(jié)點一右子樹”；前序遍歷順序【例1】問題解決方案的對的而完整的描述稱為

是〃根結(jié)點一左子樹一右子樹〃。根據(jù)各種遍歷算法，不難得o（考點1）

出前序遍歷序列是EDBAC。所以答案為D）。解析：計算機解題的過程事實上是在實行某種算法，

答案：D）這種算法稱為計算機算法。

【例6】設(shè)有一個已按各元素的值排好序的線答案：算法

性表（長度大于2）,對給定的值k,分別用順序查【例2】一個空的數(shù)據(jù)結(jié)構(gòu)是按線性結(jié)構(gòu)解決的，則屬

找法和二分查找法查找一個與k相等的元素，比較于。（考點4）

的次數(shù)分別是s和b,在查找不成功的情況下，s和b解析：一個空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)或是非線性結(jié)構(gòu)，

的關(guān)系是_______o（考點9）要根據(jù)具體情況而定。假如對數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)

A）s=bB）s>bC）s<b來解決的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。

D）s2b答奚：線性結(jié)構(gòu)

解析：時于順序查找，查找不成功時和給定關(guān)鍵字比【例3】設(shè)樹T的度為4,其中度為1、2、3和4的

較的次數(shù)為二分查找查找不成功的關(guān)鍵字比較次數(shù)為結(jié)點的人數(shù)分別為4、2、1、1,則T中葉子結(jié)點的個數(shù)

[log2n]+1。當(dāng)n22時，顯然n+l>[log2n]+1。為o（考點7）

答案：B）解析：根據(jù)樹的性質(zhì)：樹的結(jié)點數(shù)等于所有結(jié)點的度

【洌7】在快速排序過程中，每次劃分，將被劃分與相應(yīng)的結(jié)點個數(shù)乘枳之和加1。

的表（或了表）提成左、右兩個了表，考慮這兩個了表，因此樹的結(jié)點數(shù)為1X4+2X2+3X1+4X1

下列結(jié)論一定對的的是o（考點11）+1=16。葉子結(jié)點數(shù)目等于樹結(jié)點總數(shù)減去度不為0的結(jié)

A）左、右兩個子表都已各自排好序點數(shù)之和，即16—（4+2+1+1）=8。

B）左邊子表中的元素都不大于右邊子表中的元素答案：8

C）左邊子表的長度小于右邊子表的長度【例4】二分法查找的存儲結(jié)構(gòu)僅限于______且是有序

D）左、右兩個子表中元素的平均值相等的。（考點10）

解析?：快速排序基本思想是：任取待排序表中的某個解析：二分查找，也稱折半查找，它是一種高效率的查找

元素作為基準(zhǔn)（一般取第一個元素），通過一趟排序，將待方法。但二分查找有條件限制：規(guī)定表必須用順序存儲結(jié)構(gòu),

排元素分為左右兩個子表，左子表元素的排序碼均小于或且表中元素必須按關(guān)鍵字有序（升序或降序均可）。

答案：順序存儲結(jié)構(gòu)

等于基準(zhǔn)元素的排序碼，右子表的排序碼則大于基準(zhǔn)元素

的排序碼，然后分別對兩個子表繼續(xù)進行排序，直至整個

表有序。第2章程序設(shè)計基礎(chǔ)

答案：B）

通過對部分考生的調(diào)查以及對近年真題的總結(jié)分析,

筆試部分經(jīng)?？疾斓氖墙Y(jié)構(gòu)化程序設(shè)計的原則、面向?qū)ο蠓剑?）對象

法的基本概念，讀者應(yīng)對此部分進行重點學(xué)習(xí)。通常把對對象的操作也稱為方法或服務(wù)。

具體重點學(xué)習(xí)知識點：屬性即對象所包含的信息，它在設(shè)計對象時擬定，一

1.結(jié)構(gòu)化程序設(shè)計方法的四個原則般只能通過執(zhí)行對象的操作來改變。屬性值應(yīng)當(dāng)指的是純粹

2.對象、類、消息、繼承的概念、類與實例的區(qū)別

的數(shù)據(jù)值，而不能指對象。

操作描述了對象執(zhí)行的功能，若通過信息的傳遞，還

2.1結(jié)構(gòu)化程序設(shè)計

可認(rèn)為其他對象使用。

考點1結(jié)構(gòu)化程序設(shè)計的原則

對象具有如下特性：標(biāo)記惟一性、分類性、多態(tài)性、封

考試鏈接：

裝性、模塊獨立性。

考點1在邕試考試中出現(xiàn)的幾率為30%,重要是以選擇題的形式出現(xiàn),

分值為2分，此考點為識記內(nèi)容，讀者應(yīng)當(dāng)識記結(jié)構(gòu)化程序設(shè)計方法的四（2）類和實例

個重要原則。

類是具有共同屬性、共同方法的對象的集合。它描述了

20世紀(jì)70年代提出了“結(jié)構(gòu)化程序設(shè)計”的思想和方法。

結(jié)構(gòu)化程序設(shè)計方法引入了工程化思想和結(jié)構(gòu)化思想，使大屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其相

型軟件的開發(fā)和編程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計方

法的重要原則為：自頂向下、逐步求精、模塊化和限制使用應(yīng)類的一個實例。

goio語句。

類是關(guān)于對象性質(zhì)的描述，它同對象同樣，涉及一組

疑難解答：如何進行自頂向下設(shè)計方法？數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。

程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目的，（3）消息

后考慮局部目的；不要一開始就過多追求眾多的細節(jié)，先從最上層總消息是實例之間傳遞的信息，它請求對象執(zhí)行某一解

目的開始設(shè)計，逐步使問題具體化。決或回答某規(guī)定的信息，它統(tǒng)了卻據(jù)流和控制流。

2.2面向?qū)ο蟮某绦蛟O(shè)計一人消息由三部分組成：接受消息的對象的名稱、消息

標(biāo)記符（消息名）和零個或多個參數(shù)。

考點2面向?qū)ο蠓椒ǖ幕靖拍?/p>

（4）繼承

考試鏈接：

廣義地說，繼承是指可以直接獲得已有的性質(zhì)和特性，

考點2在筆試考試中，是一個經(jīng)?？疾斓膬?nèi)容，在筆試考試中出現(xiàn)的

而不必反復(fù)定義它們。

幾率為70舟,重要是以填空題的形式出現(xiàn)，分值為2分，此考點為重點識

繼承分為單繼承與多重繼承。單繼承是指，一個類只允

記內(nèi)容，讀者應(yīng)當(dāng)識記幾個基本要素的定義、對象的特性以及消息、繼承、

許有一人父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指，一個

類的定義。

類允許有多個父類。

誤區(qū)警示：

（5）多態(tài)性

當(dāng)使用“對象”這個術(shù)語時，既可以指一個具體的對象，也可以泛指

對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的

一般的對象，但是當(dāng)使用"實例"這個術(shù)語時，必須是指一個具體的對象。

對象接受時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。

面向?qū)ο蠓椒êw對象及對象屬性與方法、類、繼承、疑難解答：能舉一下現(xiàn)實中的對象及其屬性和操作嗎？

一輛汽車是一個對象，它包含了汽車的屬性（如顏色、型號等）

多態(tài)性幾個基本要素。

及其操作（如啟動、剎車等）。一個窗口是對