山東大學(xué)《數(shù)據(jù)結(jié)構(gòu)(雙語(yǔ))》【考試資料及題庫(kù)】數(shù)據(jù)結(jié)構(gòu) 課程重難點(diǎn)分析及考試方向預(yù)判

數(shù)據(jù)結(jié)構(gòu)課程重難點(diǎn)分析及考試方向預(yù)判

本文檔以課程復(fù)習(xí)綱要為藍(lán)本，進(jìn)行重難點(diǎn)分析及相關(guān)考試方向

預(yù)判，其中☆為一級(jí)要求，口為二級(jí)要求，△為三級(jí)要求，單獨(dú)出題

以［S］表示，混合出題以［M］表示，所有頁(yè)碼標(biāo)注均為英文課本。

Chapter0引論（僅作提綱使用）

a）數(shù)據(jù)結(jié)構(gòu)的表示

二維矩陣、棧、隊(duì)列邏輯表示

數(shù)組、單鏈表、雙鏈表存儲(chǔ)表示

b）數(shù)據(jù)邏輯結(jié)構(gòu)的分類(lèi)

一位數(shù)組、隊(duì)列、棧線性結(jié)構(gòu)

圖和樹(shù)多元關(guān)系遞歸定義動(dòng)態(tài)結(jié)構(gòu)

c）數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的分類(lèi)

數(shù)組順序存儲(chǔ)

鏈表與樹(shù)鏈?zhǔn)酱鎯?chǔ)

d）要求

1可以給出ADT及其相關(guān)描述

（2可以給出C++代碼）

本書(shū)五大重點(diǎn)：

1線性表（單鏈表）的表示和基本操作

2矩陣（稀疏矩陣等特殊矩陣）的表示和基本操作

3二叉樹(shù)及其搜索樹(shù)的的表示、定義及基本操作以及AVL、B、B+

的擴(kuò)展理解

4堆與優(yōu)先隊(duì)列的表示、基本操作和相關(guān)應(yīng)用

5圖論基本定義以及相關(guān)算法（最小生成樹(shù)x2、單源最短路徑xl、

全局最短路徑xl）

Ch叩ter1C++

要求范圍：類(lèi)定義方法、遞歸程序定義、new使用、友元函數(shù)

考試要求：盡量使用C++進(jìn)行描述與實(shí)現(xiàn)

重難點(diǎn)分析：

模板類(lèi)、引用聲明、const的使用（包括引用的const定義、函數(shù)返回

const的定義）

考點(diǎn)分析：

[MD]C++面向?qū)ο蟮某绦蛟O(shè)計(jì)（包括模板類(lèi)、引用等）

Chapter2程序性能評(píng)估

a）測(cè)度分類(lèi)

時(shí)間復(fù)雜度空間復(fù)雜度

b）時(shí)間復(fù)雜性

知道。（n）0（n）S（n）的理論定義，即上界、下界、精確界；

要求：估計(jì)簡(jiǎn)單算法的時(shí)間復(fù)雜性、找出最壞與期望時(shí)間復(fù)雜性

c）空間復(fù)雜性

理基本存儲(chǔ)單元關(guān)于n的逼近漸進(jìn)函數(shù)

d）排序要求

i.基于比較的排序：

1.內(nèi)排序：冒泡、快速、插入、堆、歸并

2.外排序：贏者樹(shù)排序

ii.基于儲(chǔ)存的排序：桶排序與基數(shù)排序（穩(wěn)定排序）

重難點(diǎn)分析：

1常見(jiàn)排序算法三種時(shí)間復(fù)雜性、空間復(fù)雜性以及穩(wěn)定性表

注：本部分收納后面的所有排序種類(lèi)，即后面的排序重點(diǎn)在此一并

列出，后面即不在混合列出，方便復(fù)習(xí)。

（注：前半部分為比較排序，后半部分為非比較排序）

Avera

NameBestWorstMemoryStableMethodOthernotes

ge

Quicksortis

usuallydone

inplacewith

0(log(77))

stackspace.

typica

Most

1

implementati

in-pla

onsare

cesort

lognunstable,as

onisnot

QuicksorPartition!stable

nlogrnlog工n2average,stable

tngin-place

worst*

partitioning

caseis77.stable

ismore

versio

complex.

ns

Naive

exist

variantsuse

an0(z?)space

arrayto

storethe

partition.

Highly

paredleiizab

le(upto

0(log(/?))

usingthe

Three

Depends1-Hungarian's

therexplanationAlgorithmor

Merge

nlogrnlogmlog?,neededj.YesMergingmore

sort

worstpractically,

caseis71Cole，s

parallel

mergesort)

for

processing

largeamounts

ofdata.

Heapsortnloginlogr.nlogi1NoSelection

0(z?+d),

Insertio

n77.22YesInsertionwhere/isthe

nsortn1

numberof

Avera

Name1BestWorstMemoryStableMethodOthernotes

ge

inversions

Stablewith

0(n)extra

Selectio

222NoSelectionspace,for

nsortnnn1

exampleusing

lists.~

Bubble「Tinycode

n22vYesExchanging.

sortnn1size

Whenusinga

Binary...self-balanci

n77logr.nlogrnYesTInsertion..

ireesoringbinary

searchIree

Tourname

nlogmlogrn~Selection

ntsoot

N

NameBest.AverageWorstMemoryStable?Notes

2k

Assumesuniform

Bucket

distributionof

sori

2YesNoelementsfromthe

(uniformn+kn?kn-k

domaininthe

keys)[6]

array.—

ristherangeof

numberstobe

Bucket

sortvvsorted.Ifr=

YesYes。(幾)

(integern-\-rn-1-rn+r

keys)thenAvgRT二。(九)

in

ristherangeof

numberstobe

CountingVcqV”sorted.Ifr=S)

YesYes

sortn4-rn+rn+r

thenAvgRT=°(〃)

N

NameBestAverageWorstMemoryStable?Notes

2*

LSDRadix_k_k⑹⑺

—n?77，?nYesNo

Sortdd

Stableversionuses

MSDRadixkkanexternalarrayof

—n?n-YesNo

Sortdd(1.sizentoholdallof

thebins

In-Place,k/d

MSDRadixkk

七2dNoNorecursionlevels,2'1

Sortn-3n?3

dadforcountarray

2Q(n)O(n)@(n)的理論定義，即上界、下界、精確界，并可以

對(duì)簡(jiǎn)單的程序進(jìn)行時(shí)間復(fù)雜性和空間復(fù)雜性估算

考點(diǎn)分析：

[$☆]排序算法的考查，題型可以涉及問(wèn)答題、選擇題、編程題方向,

考查范圍涉及各排序算法的穩(wěn)定性、時(shí)間復(fù)雜性空間復(fù)雜性的比較問(wèn)

答、選擇正確或者是直接完成一個(gè)排序算法的實(shí)現(xiàn)。

[MQ]程序或程序塊的時(shí)間復(fù)雜性判定，題型涉及問(wèn)答題、編程題

方向，主要考查對(duì)給定程序塊或者自定義程序的整體復(fù)雜度分析，特

別是在精確界情況下的分析（即判定上界與下界同時(shí)需要在同一個(gè)多

項(xiàng)式階次下）。

Chapter3數(shù)據(jù)表示

a）線性表的兩種表示方法（公式化、鏈?zhǔn)交?/p>

要求：C++的表示與基本操作（search/insert/delete）

能用圖與程序描述與實(shí)現(xiàn)

***指針的使用和insertdelete的輔助指針實(shí)現(xiàn)

b）鏈表函數(shù)功能擴(kuò)展

appenditeratorreversealternatemerge

c）循環(huán)鏈表與雙向鏈表的結(jié)構(gòu)與實(shí)現(xiàn)

1）利弊分析

2）空滿判斷

3）哨兵節(jié)點(diǎn)的使用

d）Chain的表示與實(shí)現(xiàn)

1）模板類(lèi)的替換與使用

2）擴(kuò)展至LinkedWDigraph

e）桶排序與基數(shù)排序

O（n）的時(shí)間復(fù)雜性、算法的整數(shù)受限性

。并查集（了解）

unionfind

重難點(diǎn)分析：

1線性表的表示及擴(kuò)展（Linearlist&Chain）

主要在于兩種表示方法的書(shū)面表述和代碼表述,主要考慮的是數(shù)據(jù)表

示的基本操作insertsearch（含行nd）delete三種基本操作

這樣總計(jì)有6個(gè)重點(diǎn)方法需要掌握，另有3個(gè)擴(kuò)展方法，以下列出框

架。

注：請(qǐng)注意鏈?zhǔn)奖硎镜氖孜补?jié)點(diǎn)的額外判定問(wèn)題，可以參見(jiàn)課本程序

33-3.5以及3.10-3.17,。

另外需要考慮的是chain的迭代器表示，需要掌握Initialize>next

兩個(gè)方法。

template<classT>〃數(shù)組表示

classLinearList{

public:

LinearList(intMaxListSize=10);//constructor

?LinearList。{delete[]element;}//destructor

boolIsEmptyOconst{returnlength==0;)

intLength()const{returnlength;}

boolFind(intk,T&x)const;

//returnthek*thelementoflistinvariablex

intSearch(constT&x)const;//returnpositionofx

AbstractList<T>&Delete(intk,T&x);

//deletek'thelementoflistandreturninx

AbstractList<T>&Insert(intk,constT&x);

//insertxjustafterk'thelement

voidOutput(ostream&out)const;

private:

intlength;

intMaxSize;

T.element;〃dynamican,ay

)；

template<classT>〃鏈表表示請(qǐng)注意輔助指針

classChain{

friendChainIterator<T>;

public:

Chain(){first=0;}

?Chain。；

boolIsEmptyOconst{returnfirst==0;}

intLength()const;

boolFind(intk,T&x)const;

intSearch(constT&x)const;

Chain<T>&Delete(intk,T&x);

Chain<T>&Insert(intk,constT&x);

Chain<T>&Reverse();

voidZero(){first=0;}

voidErase();//deleteallnodes

Chain<T>&Append(constT&x);

voidOutput(ostream&out)const;

Chain<T>&Merge(Chain<T>&A,Chain<T>&B);

private:

ChainNode<T>"first,//pointertofirstnode

*last;//pointertolastnode

)；

template<classT>〃迭代器

classChainiterator{

public:

T*Initialize(constChain<T>&c)

{location=c.first;

if(location)return&location->data;

return0;}

T*Next()

{if(!location)return0;

location=location->link;

if(location)return&location->data;

return0;)

private:

ChainNode<T>^location;

)；

2循環(huán)鏈表與雙向鏈表

1）與普通鏈表不同的是這里增添了更多的指針元素，具體說(shuō)來(lái)：

循環(huán)鏈表在尾節(jié)點(diǎn)處的link節(jié)點(diǎn)指向了first節(jié)點(diǎn)；

雙向鏈表在每個(gè)節(jié)點(diǎn)處增加了prev節(jié)點(diǎn)；

而雙向循環(huán)鏈表是二者兼有之，為了簡(jiǎn)化操作，在其中設(shè)置了一個(gè)空

的哨兵節(jié)點(diǎn)（dummy節(jié)點(diǎn)），里面不存有數(shù)值，是為了方便鏈表的操

作設(shè)置的，其后繼為頭結(jié)點(diǎn)，前驅(qū)為尾節(jié)點(diǎn)。

2）對(duì)于它們的空滿判定：

空：循環(huán)或雙向鏈表是x.first=0,雙向循環(huán)鏈表是哨兵前后均指向

自身。

滿：循環(huán)和雙向是nomem判定，但是查找是Iink==first判定為查找

結(jié)束標(biāo)志。

3）利弊分析：每種操作相對(duì)方便，但是復(fù)雜度提高。

3穩(wěn)定排序與并查集

此部分的排序部分請(qǐng)參見(jiàn)第二章的相關(guān)內(nèi)容,并查集部分只需要作了

解目標(biāo)，union/find的概念理解即可。

考點(diǎn)分析：

線性表的考查，考題類(lèi)型涉及選擇、問(wèn)答、讀程、寫(xiě)程所有

題型，考查范圍為對(duì)于選擇、問(wèn)答考查關(guān)于各個(gè)方法的復(fù)雜度問(wèn)題,

讀程序一般會(huì)和圖論混合考查鏈?zhǔn)降木W(wǎng)絡(luò)表示,寫(xiě)程序會(huì)考查基本線

性表尤其是鏈表的基本操作表示，屬于本書(shū)五大重點(diǎn)之一，需要高度

掌握。

[S口]循環(huán)及雙向鏈表的考查，考題類(lèi)型涉及選擇及問(wèn)答，考查范圍

是和普通鏈表的比較（包括復(fù)雜度的比較和操作難度以及具體實(shí)現(xiàn)差

異的比較），兩種特殊鏈表的搜索終點(diǎn)確定，空表判定等等。

[MZk]對(duì)于等價(jià)類(lèi)，也就是并查集的考查，考題類(lèi)型涉及選擇、問(wèn)答,

考查范圍是對(duì)其基本操作，也就是find和union的描述的解釋?zhuān)?/p>

及一些簡(jiǎn)單的優(yōu)化方法的描述。

Ch叩ter4數(shù)組與矩陣

a）arrayIDarray2D的ADT與C++標(biāo)準(zhǔn)表示

b）matrix的行主映射與列主映射以及邏輯位置與映射函數(shù)

c）matrix的ADT與C++標(biāo)準(zhǔn)表示

d）特殊矩陣存儲(chǔ)（對(duì)稱(chēng)、上下、稀疏）及映射函數(shù)

e）稀疏矩陣的鏈表表示與圖的鄰接鏈表表示的異同點(diǎn)

重難點(diǎn)分析：

1一維/二維數(shù)組的基本表示

主要考查的是在數(shù)組條件下的數(shù)組基本構(gòu)架和一些基本運(yùn)算的構(gòu)建，

包括常見(jiàn)的加減乘除單目或多目運(yùn)算，由于已經(jīng)有最基本的動(dòng)態(tài)指針

數(shù)組實(shí)現(xiàn)，實(shí)際這種考查難度不高。

程序請(qǐng)參見(jiàn)：程序4.1-4.11都有基本描述，難度低，不再贅述。

2矩陣的基本表示以及運(yùn)算實(shí)現(xiàn)及邏輯位置確定

注：以下的所有矩陣表示的外部參數(shù)輸入的起點(diǎn)是1,但內(nèi)部使用數(shù)

組從0開(kāi)始，所以會(huì)有一個(gè)對(duì)應(yīng)關(guān)系。

這部分主要在于將二維矩陣轉(zhuǎn)換成矩陣，并實(shí)現(xiàn)矩陣乘法，當(dāng)然事實(shí)

不會(huì)這么簡(jiǎn)單。在課本中，我們使用一維數(shù)組實(shí)現(xiàn)了整個(gè)矩陣，那么，

我們需要考慮映射關(guān)系：即行主映射與列主映射。

行主映射的對(duì)應(yīng)關(guān)系為：element[(i-l)*cols+j-l]

列主映射的對(duì)應(yīng)關(guān)系為：element[(i-l)*rows+i-ll

當(dāng)然其物理本質(zhì)依然是由指針聲明的動(dòng)態(tài)一維數(shù)組。

具體程序可以參看程序4.12-4.15

3特殊矩陣的映射與表示

總體原則：在進(jìn)行插入及刪除及改變的操作時(shí)請(qǐng)判定是否越界，因?yàn)?/p>

在此特殊矩陣基本都已一維數(shù)組存儲(chǔ)，除稀疏矩陣的鏈表表示法。

1)對(duì)角矩陣m[i][i]=e[i]

2)三對(duì)角矩陣m[i+l][i]=e[i-2]m[i][i]=e[n+i-2]m[i][i+l]=e[2*n+i-2]

3)三角矩陣

下三角矩陣m[i][j]=e[i*(i-l)/2+j-l]

上三角矩陣m[i][j]=e[(j-l)*j/2+i-l]

4）稀疏矩陣［數(shù)組表示］

分為三個(gè)一維數(shù)組分開(kāi)表示，分別記錄rowcolumnvalue

實(shí)質(zhì)上將矩陣虛級(jí)化,有些運(yùn)算對(duì)數(shù)組表示的稀疏矩陣影響不大,

但是對(duì)于矩陣的轉(zhuǎn)置會(huì)比較高的要求，具體說(shuō)來(lái)實(shí)現(xiàn)的方式是按列對(duì)

每列進(jìn)行首元素及每列元素?cái)?shù)量標(biāo)記方便轉(zhuǎn)置時(shí)的標(biāo)注與轉(zhuǎn)換（因

為，轉(zhuǎn)置后變?yōu)閷?shí)際列優(yōu)先），接下來(lái)讀入行的方式將每個(gè)列的數(shù)據(jù)

依次讀入，讀后列下標(biāo)的映射位置后移，循環(huán)完成轉(zhuǎn)置。

而對(duì)于加法操作，需要進(jìn)行判定，分單邊有值，雙邊有值，雙邊和

為。等3個(gè)類(lèi)型，分開(kāi)操作，難度不大不再贅述。

程序參看4.17-4.25

5）稀疏矩陣［鏈表表示］

實(shí)際是由不等長(zhǎng)二維鏈表實(shí)現(xiàn)，即由一個(gè)一維（行列雙向）鏈表,

行向連綴本行的元素，列向連綴首列元素，從而實(shí)現(xiàn)一個(gè)二維鏈表。

關(guān)于其轉(zhuǎn)置的實(shí)現(xiàn)，使用的是桶排序的思路，具體見(jiàn)程序4.28-4.30

3稀疏矩陣的鏈表表示和后面圖的鄰接鏈表表示的異同點(diǎn)

相同點(diǎn)：兩個(gè)的物理結(jié)構(gòu)基本相同，是由行列雙向鏈表實(shí)現(xiàn)的不等

長(zhǎng)二維鏈表。

不同點(diǎn)：

1）兩者意義不同，一個(gè)表示有值，不是0,另一個(gè)表示的是之間有

連接而不是沒(méi)有直接通路；

2）稀疏矩陣的要求更加松散，稀疏矩陣對(duì)于全零行可以直接省略行

標(biāo)識(shí)，而對(duì)于圖來(lái)說(shuō)，即使其為孤立點(diǎn)，也不能刪除這個(gè)點(diǎn)的列向表

示，故圖鄰接鏈表的首列表示也常用一維數(shù)組。

考點(diǎn)分析：

[S/MZM一維二維數(shù)組的考查，涉及的題型有選擇、問(wèn)答，當(dāng)然這一

部分滲透于每個(gè)題型，難度不大，而且后矩陣部分重疊，考查要求較

低。

[S/M口]矩陣的考查，一般涉及的內(nèi)容包含矩陣的映射關(guān)系、矩陣的

表示與實(shí)現(xiàn)，涉及的題型包括選擇、問(wèn)答、讀程序等，這個(gè)方面的考

查滲透亦比較寬泛，對(duì)于選擇問(wèn)答一般考查映射關(guān)系與基礎(chǔ)實(shí)現(xiàn)，而

對(duì)于讀程序題會(huì)考查表示與實(shí)現(xiàn)的相關(guān)問(wèn)題，另外直接的考查一般被

包含在我們的特殊矩陣考查中。

[§☆]特殊矩陣的考查，一般的涉及的內(nèi)容包括三角矩陣、對(duì)角矩陣

與稀疏矩陣的考查，特別是稀疏矩陣的考查，考查的是映射關(guān)系與具

體實(shí)現(xiàn)方法，因?yàn)閷?duì)于特殊矩陣而言，一維實(shí)現(xiàn)需要很高技巧性，所

以也是本書(shū)的五大重點(diǎn)之一，需要重點(diǎn)掌握。

[S口]鏈?zhǔn)较∈杈仃嚺c圖論相關(guān)，一般涉及的內(nèi)容包括鏈?zhǔn)较∈杈仃?/p>

與圖論鄰接鏈表的比較，考查題型一般只會(huì)涉及問(wèn)答題類(lèi)型，但是需

要對(duì)此有清晰的理解。

Chapter5棧(LIFO)

a)棧的定義與ADT

b)棧的自定義描述(C++&ADT)

c)棧的存儲(chǔ)實(shí)現(xiàn)：一位數(shù)組及鏈表

棧的操作實(shí)現(xiàn)：adddelete

d)棧的應(yīng)用：括號(hào)配對(duì)、前后綴表達(dá)式等等

重難點(diǎn)分析：

1棧的基本描述與自定義描述及其操作實(shí)現(xiàn)

對(duì)于棧的基本描述由于并不常見(jiàn)也不實(shí)用所以不作為考查對(duì)象，主

要是理解自定義的棧的描述及其實(shí)現(xiàn)。其中需要實(shí)現(xiàn)的方法有空棧判

定、滿棧判定、棧的推入、棧的彈出即add&delete。另外其實(shí)現(xiàn)方

法也有數(shù)組和鏈表兩種表示方法，具體框架如下。

template<classT>

classStack{

//LIFOobjects

public:

Stack(intMaxStackSize=10);

-Stack(){delete[]stack;}

boolIsEmptyOconst{returntop==-1;)

boolIsFull()const{returntop==MaxTop;}

TTop()const;

Stack<T>&Add(constT&x);

Stack<T>&Delete(T&x);

private:

inttop;//currenttopofstack

intMaxTop;//maxvaluefortop

T*stack;//elementarray

)；

template<classT>

classLinkedStack{

public:

LinkedStack(){top=0;}

?LinkedStack。；

boolIsEmptyOconst{returntop==0;}

boolIsFull()const;

TTop()const;

LinkedStack<T>&Add(constT&x);

LinkedStack<T>&Delete(T&x);

private:

Node<T>*top;//pointertotopnode

)；

具體程序可見(jiàn)程序5.25.4

2堆棧的應(yīng)用

包括括號(hào)匹配、前后綴表達(dá)式互換、圖的DFS等。認(rèn)知到堆棧的真

正應(yīng)用于計(jì)算機(jī)的遞歸實(shí)現(xiàn)中，知道hanoi的實(shí)現(xiàn)也是堆棧。具體而

言括號(hào)匹配的掌握實(shí)際被包含于前后綴表達(dá)式轉(zhuǎn)換中,而前后綴表達(dá)

式轉(zhuǎn)換請(qǐng)參閱實(shí)驗(yàn)指導(dǎo)書(shū)，在其中有完整而詳盡的描述。

考點(diǎn)分析：

[S口]由于堆棧在很大程度上和遞歸有等價(jià)關(guān)系，而為了明確不混亂,

遞歸的內(nèi)容包括DFS不算為堆棧的考查范圍。這樣堆棧由于難度一

般，考點(diǎn)混合度較小，只需掌握基本的實(shí)現(xiàn)與定義即可?？碱}類(lèi)型涉

及選擇、問(wèn)答、讀程序，寫(xiě)程序可能會(huì)出小的實(shí)現(xiàn)(和隊(duì)列一起)，

考查的內(nèi)容也僅僅涉及基本的實(shí)現(xiàn)即pop/push,那么整體難度一般。

[S/M口]堆棧的應(yīng)用，作為堆棧的衍生類(lèi)型，整體要求也是一般，涉

及題型一般仍然是選擇、問(wèn)答，一般考查的是這些的算法描述，同樣

難度重要度一般。

Chapter6隊(duì)列(FIFO)

a)隊(duì)列的定義與ADT

b)隊(duì)列的形式化描述(C++&ADT)

c)隊(duì)列的存儲(chǔ)實(shí)現(xiàn)：一位數(shù)組及鏈表

隊(duì)列的操作實(shí)現(xiàn)：adddelete

隊(duì)列的優(yōu)劣判定

循環(huán)隊(duì)列的空滿判定

d)鏈表隊(duì)列的add、delete的實(shí)現(xiàn)

表頭、表尾的依據(jù)

e)隊(duì)列的應(yīng)用：BFS

重難點(diǎn)分析：

1隊(duì)列的形式化描述和實(shí)現(xiàn)

對(duì)于隊(duì)列基本的形式化表示方法即被常用，與棧類(lèi)似，其考查的是

隊(duì)列的基本操作add和delete,即出隊(duì)與入隊(duì)，另外還需要關(guān)注的是

隊(duì)列的優(yōu)劣判定與空滿判定；當(dāng)然還需要關(guān)注的是一類(lèi)特別的隊(duì)列循

環(huán)隊(duì)列的判定；另外其實(shí)現(xiàn)方法也有數(shù)組和鏈表兩種表示方法，具體

框架如下。

classQueue)

//FIFOobjects

public:

Queue(intMaxQueueSize=10);

?Queue。{delete[]queue;}

boolIsEmptyOconst{returnfront==rear;}

boolIsFull()const{return(

((rear+1)%MaxSize==front)?1:0);}

TFirst()const;//returnfrontelement

TLast()const;//returnlastelement

Queue<T>&Add(constT&x);

Queue<T>&Delete(T&x);

private:

intfront;//onecounterclockwisefromfirst

intrear;//lastelement

intMaxSize;//sizeofarrayqueue

T*queue;//elementarray

)；

template<classT>

classLinkedQueue{

friendostream&operator?

(ostream&,constLinkedQueue<T>&);

friendistream&operator?

(istream&,LinkedQueue<T>&);

public:

LinkedQueue(){front=rear=0;}//constructor

-LinkedQueue(){Erase();}

boolIsEmptyOconst

{return((front)?false:true);}

boolIsFullOconst;

TFirst()const;//returnfirstelement

TLast()const;//returnlastelement

LinkedQueue<T>&Add(constT&x);

LinkedQueue<T>&Delete(T&x);

intSize()const;

private:

Node<T>.front;//pointertofirstnode

Node<T>*rear;//pointertolastnode

voidErase();//deleteallnodes

)；

具體程序可見(jiàn)程序6.2-6.6

需要注意的是循環(huán)隊(duì)列的判定，其中空隊(duì)的判定是頭尾指針相同，滿

隊(duì)的判定是兩者在對(duì)Maxsize取模后fronf-rear^lo

鏈?zhǔn)疥?duì)列的頭尾依據(jù)依然有所區(qū)別，空是front指向空，滿是嘗試增

添節(jié)點(diǎn)返回異常視為已滿。

2隊(duì)列的應(yīng)用

主要提及的仍然是隊(duì)列在圖論的BFS上的應(yīng)用，BFS在相關(guān)的圖論

算法中使用也是比較多的，在這里不統(tǒng)一作介紹，將放在圖論處統(tǒng)一

介紹。

考點(diǎn)分析：

[M口]由于隊(duì)列在某種程度上與棧相似，是BFS的基礎(chǔ)，如不算相關(guān)

圖論問(wèn)題，難度不大?？碱}類(lèi)型涉及選擇、問(wèn)答、讀程序，寫(xiě)程序可

能會(huì)出小的實(shí)現(xiàn)(和堆棧一起)，考查的內(nèi)容也僅僅涉及基本的實(shí)現(xiàn)

即push/pop,那么整體難度一般。

[M口]隊(duì)列的應(yīng)用，考察的基本都是BFS相關(guān)應(yīng)用，涉及題型一般仍

然是選擇、問(wèn)答，一般考查的是這些的算法描述，同樣難度重要度一

般。

Chapter7跳表(△)與hash

a)sortedChain

b)Skiplist

c)Hash的基本的思想

常用hash函數(shù)

hash表的基本表示(openaddressing/linkedrepresentation)

hash表的方法實(shí)現(xiàn)：search/insert/delete

hash的沖突處理

重難點(diǎn)分析：

1明確了對(duì)跳表的無(wú)要求性

2Hash的基本表示、實(shí)現(xiàn)與沖突處理

首先應(yīng)該明確哈希函數(shù)實(shí)際上大空間數(shù)據(jù)到小空間存儲(chǔ)空間的

映射，常用的哈希函數(shù)包括理想哈希和線性開(kāi)放選址兩類(lèi)，在這

種下物理實(shí)現(xiàn)是數(shù)組，開(kāi)放選址使用的是取模操作，如遇沖突就

進(jìn)行逐位后移尋找插入位置，當(dāng)然理想哈希幾乎不考，但是需要

注意的是其方法實(shí)現(xiàn)包括查找、插入和刪除是比較重要的，程序

可參考7.11-7.15,以下給出鏈?zhǔn)絟ash的框架。

classhashChains:publicdictionary<K,E>

public:

hashChains(inttheDivisor=11)

-hashChains(){delete[]table;}

boolempty()const{returndSize==0;}

intsize()const{returndSize;}

pair<constK,E>*find(constK&theKey)const

{returntable[hash(theKey)%divisor].find(theKey);}

voidinsert(constpair<constK,E>&thePair)

voiderase(constK&theKey)

{table[hash(theKey)%divisorJ.erase(theKey);}

voidoutput(ostream&out)const；

protected:

sortedChain<K,E>*table;//hashtable

hash<K>hash;//mapstypeKtononnegativeinteger

intdSize;//numberofelementsinlist

intdivisor;//hashfunctiondivisor

考點(diǎn)分析：

[S口]作為非重點(diǎn)部分，我們只需要掌握散列表的基礎(chǔ)即可，既包括

表示與實(shí)現(xiàn),也包括特色的沖突處理,但是要求與難度實(shí)際上都不高,

涉及題型一般會(huì)涉及選擇、問(wèn)答，考查問(wèn)題為散列表實(shí)現(xiàn)的復(fù)雜度分

析、一些實(shí)現(xiàn)與沖突處理細(xì)節(jié)等。

Chapter8二叉樹(shù)及其他樹(shù)

a）樹(shù)的定義、基本術(shù)語(yǔ)

根、樹(shù)的高度、孩子、雙親、葉子、頂點(diǎn)的度

b）二叉樹(shù)及基本術(shù)語(yǔ)

根、左子樹(shù)、右子樹(shù)、空樹(shù)、滿二叉樹(shù)（一維數(shù)組存儲(chǔ)）、完全二叉樹(shù)（一維數(shù)組存儲(chǔ)）

c）數(shù)學(xué)表達(dá)式的二叉樹(shù)表示

d）二叉樹(shù)的性質(zhì)

e）二叉樹(shù)的存儲(chǔ)（線性、鏈表）&C++表示

0動(dòng)態(tài)存在結(jié)構(gòu)：

遞歸編程、三種遍歷方式、樹(shù)的高度計(jì)算

以上的編程實(shí)現(xiàn)

g）其他樹(shù)（森林）的二叉樹(shù)表示

利用二叉樹(shù)表示集合與集合操作的實(shí)現(xiàn)

重難點(diǎn)分析：

1樹(shù)和二叉樹(shù)的基本定義與術(shù)語(yǔ)

主要掌握此段的各種術(shù)語(yǔ)，包括樹(shù)的相關(guān)術(shù)語(yǔ)（根、樹(shù)的高度、孩子、雙

親、葉子、頂點(diǎn)的度）、二叉樹(shù)的相關(guān)術(shù)語(yǔ)（根、左子樹(shù)、右子樹(shù)、空樹(shù)、滿二叉

樹(shù)、完全二叉樹(shù)），對(duì)其可以有文字上和圖形表示上的理解，而這些屬于

記憶內(nèi)容在這里不再贅述。

2二叉樹(shù)的性質(zhì)（需要掌握實(shí)質(zhì)及證明）［8.3節(jié)］

1）n元素的二叉樹(shù)有n-1條邊

2）高為h的二叉樹(shù)，有至少h至多2/1個(gè)節(jié)點(diǎn)

3）節(jié)點(diǎn)數(shù)為n的二叉樹(shù)，樹(shù)的高度至多為n,高度至少為廠log2

（n+1）-|

4）節(jié)點(diǎn)數(shù)為n的完全二叉樹(shù)，對(duì)于標(biāo)號(hào)為i的節(jié)點(diǎn)，有以下三個(gè)性

質(zhì)成立；

-）i=l此節(jié)點(diǎn)為根節(jié)點(diǎn)

i>l此節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)為［i/2］

二）2i>n此節(jié)點(diǎn)沒(méi)有左孩子否則孩子節(jié)點(diǎn)下標(biāo)為2i

三）2i+l>n此節(jié)點(diǎn)沒(méi)有右孩子否則孩子節(jié)點(diǎn)下標(biāo)為2i+l

3二叉樹(shù)的存儲(chǔ)

對(duì)于二叉樹(shù)的存儲(chǔ)實(shí)際分為一位數(shù)組存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種形式,因此

我們都需要掌握。但是需要注意的是，數(shù)組存儲(chǔ)的主要適用范圍是完

全二叉樹(shù)、滿二叉樹(shù)等數(shù)組使用密度相對(duì)較高的類(lèi)型，而對(duì)于我們的

普通二叉樹(shù)一般采用的形式是鏈?zhǔn)叫问?數(shù)組形式比較簡(jiǎn)潔是按層次

遍歷的方式進(jìn)行了標(biāo)號(hào)，方法同性質(zhì)4,鏈表形式在書(shū)中給出，可以

見(jiàn)程序8.1o

4二叉樹(shù)的遍歷及數(shù)學(xué)表達(dá)式的表示

這是二叉樹(shù)的重點(diǎn)，我們考慮到遍歷實(shí)際上有前序遍歷、中序遍歷、

后序遍歷、層次遍歷四類(lèi)，應(yīng)了解到四類(lèi)遍歷的實(shí)質(zhì)前三類(lèi)是遞歸或

者說(shuō)DFS,而后一類(lèi)可以說(shuō)是BFS即隊(duì)列實(shí)現(xiàn)。具體的程序請(qǐng)看

8.2-8.4以及8.7,另外需要注意的是visit函數(shù)的重寫(xiě)。

關(guān)于其數(shù)學(xué)表達(dá)式的表示，計(jì)算機(jī)操作層面使用的是堆棧，物理表示

層面使用的是二叉樹(shù)，所以也就是說(shuō)這個(gè)數(shù)學(xué)表達(dá)式的前中后序表示

是非常重要的，當(dāng)然要求一般局限于繪圖問(wèn)答，所有要求不算很高。

5二叉樹(shù)的各種操作實(shí)現(xiàn)

除了最基礎(chǔ)的定位根節(jié)點(diǎn)，合并樹(shù)、拆分樹(shù)，還有四個(gè)遍歷外，我們

實(shí)際上還有四個(gè)遍歷的輸出，當(dāng)然那個(gè)不難，主要考慮的是高度與節(jié)

點(diǎn)數(shù)的求法，各位可以參考8.9.3節(jié)與8.9.4節(jié)，用的是遞歸求極值和

遞歸求和的方法重寫(xiě)visit函數(shù)實(shí)現(xiàn)的。

6其他樹(shù)形結(jié)構(gòu)的二叉樹(shù)表示與在線等價(jià)類(lèi)

這一部分主要是考慮森林的二叉樹(shù)表示、多叉樹(shù)與二叉樹(shù)的轉(zhuǎn)換，以

及在線等價(jià)類(lèi)（并查集）的深入，關(guān)于并查集前面已經(jīng)描述，這里不

再贅述。關(guān)于多叉樹(shù)轉(zhuǎn)二叉樹(shù)的方案，主要抓住“左兒子右兄弟”的

原則，即最左邊的兒子變?yōu)樽髢鹤?，其右?cè)兄弟變?yōu)槠溆覂鹤?，依?/p>

遞推即可；而對(duì)于森林轉(zhuǎn)二叉樹(shù)，先把每棵樹(shù)轉(zhuǎn)化為二叉樹(shù)，然后進(jìn)

行左兒子右兄弟的操作，即兒子均放在左側(cè)，將其他樹(shù)變?yōu)槠溆易訕?shù),

即可變?yōu)槎鏄?shù)，反之亦然。

考點(diǎn)分析：

[S口]樹(shù)的定義及術(shù)語(yǔ)的考查，這部分的考查術(shù)語(yǔ)基礎(chǔ)考查，屬于記

憶性內(nèi)容，考題類(lèi)型涉及選擇、問(wèn)答，考查范圍涉及術(shù)語(yǔ)的定義、含

義，與圖的區(qū)別，與多叉樹(shù)的區(qū)別等等。

[S口]二叉樹(shù)的性質(zhì)考查，二叉樹(shù)的性質(zhì)以四個(gè)性質(zhì)為藍(lán)本，經(jīng)常會(huì)

涉及一些證明，考題類(lèi)型也限定在選擇與問(wèn)答方向，考查范圍對(duì)性質(zhì)

的理解的問(wèn)答，或者問(wèn)答式的簡(jiǎn)單相關(guān)推論證明。

[S/M口]二叉樹(shù)的存儲(chǔ)與簡(jiǎn)單實(shí)現(xiàn)，包括兩種存儲(chǔ)方式和求樹(shù)高等操

作，需要認(rèn)真閱讀相關(guān)代碼，理解要義，考題類(lèi)型一般涉及讀程序、

寫(xiě)程序兩類(lèi)，考查范圍比較廣，與二叉樹(shù)基本表示相關(guān)的都會(huì)考查。

[S/Mhid二叉樹(shù)的遍歷，這是一個(gè)重要部分，應(yīng)清楚理解四個(gè)遍歷的

實(shí)質(zhì)和操作方法，學(xué)會(huì)對(duì)Visit函數(shù)的重寫(xiě)，以及其衍生產(chǎn)物數(shù)學(xué)表

達(dá)式的理解，考題類(lèi)型為讀程序和寫(xiě)程序兩塊，考查范圍是其實(shí)現(xiàn)和

過(guò)程實(shí)現(xiàn)的具體理解。

[SZk]其他樹(shù)類(lèi)型和在線等價(jià)類(lèi)，這些都是需要理解地記憶的內(nèi)容，

要求僅僅是畫(huà)出，所以考題類(lèi)型基本定位于選擇與問(wèn)答，而考題內(nèi)容

定位于森林、多叉樹(shù)、二叉樹(shù)轉(zhuǎn)換等等。

Chapter9優(yōu)先隊(duì)列

a）最大堆最小堆的定義與ADT（實(shí)質(zhì)：完全二叉樹(shù)）

b）Heap的一維數(shù)組存儲(chǔ)、類(lèi)定義、基本操作

searchdeleteinsertInitialize（時(shí)間復(fù)雜性）

c）高度優(yōu)先左高樹(shù)（HBLT）的定義

d）堆排序?qū)崿F(xiàn)算法與程序

e）Huffmancode的思想、huffmantree實(shí)現(xiàn)算法、對(duì)字符頻率表建立humnantree

重難點(diǎn)分析：

1堆的分類(lèi)定義及基本操作實(shí)現(xiàn)

首先注意到，堆實(shí)際上是分最大堆和最小堆兩種，也稱(chēng)大根堆和小

根堆，對(duì)于每個(gè)節(jié)點(diǎn)都有左右兒子（如果有的話）小于（或大于）父

節(jié)點(diǎn)的情況，并且其實(shí)質(zhì)是一個(gè)有序的完全的二叉樹(shù)。另外，我們需

要考慮的是其四個(gè)基本操作，當(dāng)然我們以課本的最大堆為例，分為搜

索、刪除、插入和初始化四個(gè)，搜索是針對(duì)完全有序的堆排序的結(jié)果

而言的，從根節(jié)點(diǎn)開(kāi)始向下遞歸尋找目標(biāo)值，當(dāng)然這個(gè)用的范圍并不

是很廣，主要需要考慮的是刪除與插入，刪除一般是刪除極值，也就

是取出根的值，并且將最后一個(gè)節(jié)點(diǎn)移動(dòng)至根節(jié)點(diǎn)位置，然后進(jìn)行堆

維護(hù)操作，而插入操作實(shí)際上就是把放在樹(shù)末尾，通過(guò)維護(hù)操作遞推

向上直到不滿足上升要求為止;初始化是將一個(gè)無(wú)序一維數(shù)組的前半

部分進(jìn)行逆向堆維護(hù)，這樣可以保證最后的變成堆的形態(tài)。程序可以

參見(jiàn)程序9.1-95另外需要注意的是復(fù)雜度問(wèn)題，前三個(gè)都是logn

的，后一個(gè)是n的，有證明請(qǐng)看課本。

2堆排序的實(shí)現(xiàn)與算法描述

堆排序算法是建立在建堆完成的基礎(chǔ)上的，那么其基礎(chǔ)就是

initialize方法，在建堆完成之后，堆排序相對(duì)顯得簡(jiǎn)單，做法是做類(lèi)

似刪除操作，將極值取出，那么取出n次之后，我們得到的就是一

個(gè)有序序列，正確性不再贅述，請(qǐng)讀者自己理解。具體代碼并未給出，

請(qǐng)各位在英文維基百科上查詢heapsort,即可得到相關(guān)代碼表示。而

且堆實(shí)質(zhì)也就是優(yōu)先隊(duì)列的一種實(shí)現(xiàn)形式。

3左高樹(shù)的定義及簡(jiǎn)單表述

作為本章的次要內(nèi)容，左高樹(shù)我們需要把握的是s、w兩個(gè)值的含

義，還有外部節(jié)點(diǎn)的定義，另外對(duì)實(shí)現(xiàn)相關(guān)的操作步驟需要有個(gè)基礎(chǔ)

了解。

4堆或優(yōu)先隊(duì)列的應(yīng)用：哈夫曼相關(guān)

考查的是哈夫曼樹(shù)、哈夫曼編碼等，我們需要了解其思想，并會(huì)實(shí)

現(xiàn)基本編碼。給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，

若帶權(quán)路徑長(zhǎng)度達(dá)到最小的樹(shù)稱(chēng)為哈夫曼樹(shù)，其帶權(quán)路徑長(zhǎng)度最短,

權(quán)值較大的結(jié)點(diǎn)離根較近，注意到結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)

到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積,而樹(shù)的帶權(quán)路徑長(zhǎng)度

規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，所以樹(shù)的帶權(quán)路徑長(zhǎng)度最

小即滿足要求，一般也不唯一，下面借用維基百科的描述來(lái)說(shuō)明一下

哈夫曼編碼：

在計(jì)算機(jī)數(shù)據(jù)處理中,霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)

字母）進(jìn)行編碼，其中變近編碼表是通過(guò)一種評(píng)估來(lái)源符號(hào)出現(xiàn)機(jī)率的方法得

到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編

碼，這便使編碼之后的字符串的平均長(zhǎng)度、期望值降低,從而達(dá)到無(wú)損壓縮數(shù)

據(jù)的目的。

例如，在英文中，e的出現(xiàn)機(jī)率最高，而z的出現(xiàn)概率則最低。當(dāng)利用霍夫曼編

碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)比特來(lái)表示，而z則可能花去25

個(gè)比特（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（皿）,

即8個(gè)比特。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。

倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度

提高無(wú)損壓縮的比例。

這也是我們實(shí)現(xiàn)霍夫曼編碼的原則，當(dāng)然僅需了解含義可以畫(huà)圖即

可，編碼參見(jiàn)維基百科哈夫曼樹(shù)部分。

考點(diǎn)分析：

"碗☆］堆的理解與實(shí)現(xiàn)以及其優(yōu)先隊(duì)列應(yīng)用，對(duì)于這部分實(shí)際上就

是對(duì)堆這種特殊樹(shù)的考查，在處理中一般考查的各種操作的實(shí)現(xiàn)，包

括查找、插入、刪除或者其他內(nèi)容，以及維護(hù)隊(duì)的性質(zhì)以及建堆操作,

雖然這些操作看似簡(jiǎn)單,可是實(shí)現(xiàn)需要一定要求,考試題型涉及選擇、

問(wèn)答、讀程序、寫(xiě)程序的所有題型，考查范圍涉及堆的各個(gè)方面的實(shí)

現(xiàn)，特別是初始化的實(shí)現(xiàn)，和它們的時(shí)間復(fù)雜性分析，是五大重點(diǎn)之

一，所以重點(diǎn)掌握是必要的。

"碗☆］堆排序及其實(shí)現(xiàn)，恰與前述的排序算法相似，這里對(duì)堆排序

進(jìn)行了詳盡而又充分的描述，作為綜合表現(xiàn)最優(yōu)秀的比較排序算法之

一，其實(shí)現(xiàn)步驟是很重要的，由于其建立在基本堆操作之上，所以堆

操作熟悉的情況下，才會(huì)掌握堆排序的實(shí)質(zhì)，考題類(lèi)型基本為問(wèn)答和

寫(xiě)程序，考點(diǎn)還是排序算法的實(shí)現(xiàn)和時(shí)間復(fù)雜性分析。

［§△］左高樹(shù)相關(guān)，我們需要考慮的是左高樹(shù)的幾個(gè)重要定義和基本

實(shí)現(xiàn)方法，考題類(lèi)型集中于選擇或問(wèn)答，考題范圍基本為左高樹(shù)基礎(chǔ)

理解與實(shí)現(xiàn)原理。

［S口］哈夫曼相關(guān)，主要考查的是哈夫曼樹(shù)和哈夫曼編碼及自定義內(nèi)

容，考題類(lèi)型涉及寫(xiě)程序和選擇、問(wèn)答，需要考查的范圍基本是哈夫

曼的幾個(gè)相關(guān)定義，以及如何用字頻作為權(quán)重因子建立哈夫曼編碼,

（當(dāng)然需要先建立對(duì)應(yīng)的哈夫曼樹(shù)，再加權(quán)得到，）可能在考試中被

重點(diǎn)提及需要注意。

Chapter10競(jìng)賽樹(shù)（△）

贏者（輸者）樹(shù)的定義；

采用上述樹(shù)的排序算法思想描述

采用匾者樹(shù)實(shí)現(xiàn)外部排序的算法描述；

[SZk]此段已明確沒(méi)有重難點(diǎn)，也沒(méi)有重點(diǎn)考點(diǎn)。所以不再贅述，只

做了解即可。

Chapter11搜索樹(shù)

a）二叉搜索樹(shù)（☆）、AVL樹(shù)（平衡性）、B-樹(shù)（多叉樹(shù)、根節(jié)點(diǎn)的分裂與合并）、B+樹(shù)定

義

b）二叉搜索樹(shù)的表示與基本操作：

searchinsertdelete

c）AVL樹(shù)的性質(zhì)、平衡因子的定義、旋轉(zhuǎn)

d）B-/B+樹(shù)的定義表述

重難點(diǎn)分析：

1二叉搜索樹(shù)的定義、ADT表示及基本操作

對(duì)于二叉搜索樹(shù)其定義并不難理解，實(shí)質(zhì)仍然是一棵二叉樹(shù)，只不

過(guò)就像堆一樣，是一個(gè)有特性的二叉樹(shù)，其性質(zhì)是對(duì)于每一個(gè)節(jié)點(diǎn)，

左右兒子（若存在）其左兒子必在定義下的順序中（或普遍約定的順

序中）比父節(jié)點(diǎn)小，右兒子必比父節(jié)點(diǎn)大。如此構(gòu)成了一棵二叉搜索

樹(shù)。其ADT表示中涉及插入、刪除、查找三個(gè)基本操作，但因?yàn)槠?/p>

沒(méi)有優(yōu)化，復(fù)雜度變化程度大，樹(shù)的深度也差異很大，不過(guò)其期望復(fù)

雜度都是logn,最壞情況下均會(huì)到達(dá)n的水平。需要注意的是有一

個(gè)DBST類(lèi)，只不過(guò)要求很低，而且便于理解，在此不進(jìn)行贅述。

程序可以參見(jiàn)程序11.2-11.4,尤其需要注意刪除操作。

2AVL樹(shù)的定義、性質(zhì)及旋轉(zhuǎn)操作

AVL樹(shù)是一種經(jīng)過(guò)修正的二叉查找樹(shù)，具體說(shuō)來(lái)其實(shí)現(xiàn)了普通二叉

搜索樹(shù)的復(fù)雜度不穩(wěn)定問(wèn)題。通過(guò)途中修正旋轉(zhuǎn)實(shí)現(xiàn)整個(gè)樹(shù)的相對(duì)平

衡，具體說(shuō)來(lái)需要有以下性質(zhì)：

1)n個(gè)節(jié)點(diǎn)的AVL樹(shù)的高度是logn級(jí)別的

2)對(duì)于每一個(gè)值n,如果其n>=0,那么存在一棵AVL樹(shù)

3)一個(gè)n元素的AVL樹(shù)搜索時(shí)間復(fù)雜性是O(logn)

4)一個(gè)新元素插入原有n元素的AVL樹(shù)，時(shí)間復(fù)雜性是O(logn)

5)一個(gè)元素從原有n元素的AVL樹(shù)中刪除，時(shí)間復(fù)雜性是O(logn)

對(duì)于我們來(lái)說(shuō)，實(shí)際的要求是要理解這個(gè)數(shù)據(jù)結(jié)構(gòu)而不是代碼實(shí)現(xiàn),

也就是會(huì)用圖形表示這個(gè)AVL樹(shù),那么需要考慮的是AVL樹(shù)的自調(diào)

整問(wèn)題，也就是旋轉(zhuǎn)操作的實(shí)現(xiàn)，具體說(shuō)來(lái)分為插入調(diào)整與刪除調(diào)整

兩種，插入調(diào)整分為L(zhǎng)L、LR、RL、RR四種調(diào)整，刪除操作分為

RO、RI、R-1共三種調(diào)整，具體實(shí)現(xiàn)方式請(qǐng)參見(jiàn)課本圖表11.8-11.13,

另外注意調(diào)整的原則的一個(gè)重要參數(shù)：平衡因子，即左子樹(shù)深度減去

右子樹(shù)深度的值，當(dāng)這個(gè)值在插入刪除后出現(xiàn)了絕對(duì)值大于一的情

況，那么即需要調(diào)整。

3B-樹(shù)(包括m叉樹(shù))的定義、性質(zhì)及基本操作與樹(shù)的調(diào)整

(B+樹(shù)簡(jiǎn)介)

類(lèi)似于AVL樹(shù)，這也是一種二叉平衡搜索樹(shù)，我們需要基本了解m

叉樹(shù)的定義與性質(zhì)：

1)在對(duì)應(yīng)的m叉樹(shù)中，每個(gè)內(nèi)部節(jié)點(diǎn)最多有m個(gè)孩子并且含有1到m-1個(gè)元

素

2）每個(gè)含有p個(gè)元素的節(jié)點(diǎn)擁有p+1個(gè)孩子

3）考慮任何一個(gè)有p個(gè)元素的節(jié)點(diǎn)，節(jié)點(diǎn)的這p個(gè)元素按照嚴(yán)格升序排列，而

此點(diǎn)的P+1個(gè)孩子，第i個(gè)孩子應(yīng)該比第i-1號(hào)（如果存在）的元素大，而

比第i號(hào)元素（如果存在）小

這是一個(gè)m叉樹(shù)的基本定義，下面介紹基本操作，m叉樹(shù)實(shí)際上與

二叉樹(shù)類(lèi)似，實(shí)際上也是有查找、插入、刪除操作在內(nèi)的三個(gè)基本操

作