一、基本要求
掌握的知識點(diǎn)如下：
⑴ 線性表、順序表和鏈表。要求掌握線性表的概念，兩種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、優(yōu)缺點(diǎn)及兩種存儲(chǔ)結(jié)構(gòu)上的基本操作。
⑵ 棧與隊(duì)列。要求掌握棧和隊(duì)列的概念，順序棧、鏈棧的操作，棧的應(yīng)用，循環(huán)隊(duì)列、循環(huán)鏈隊(duì)列的操作。
⑶ 串的基本運(yùn)算和模式匹配。掌握串的基本運(yùn)算的含義，了解模式匹配算法和時(shí)間復(fù)雜度。
⑷ 多維數(shù)組和廣義表。掌握多維數(shù)組及特殊矩陣的地址公式，廣義表的運(yùn)算和存儲(chǔ)。
⑸ 樹和二叉樹。樹、二叉樹的定義、術(shù)語,二叉樹的性質(zhì)、存儲(chǔ)、遍歷、應(yīng)用,線索二叉樹的概念，樹與二叉樹的關(guān)系。
⑹ 圖的存儲(chǔ)及其操作。掌握圖的定義、術(shù)語，圖的存儲(chǔ)，圖的遍歷、圖的操作（最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑）概念。
⑺ 表和樹的查找。
掌握表和樹查找的概念、平均比較次數(shù)，二叉排序樹和平衡二叉樹的插入、刪除，了解B-樹的定義。
⑻ Hash技術(shù)。掌握哈希表構(gòu)造、解決沖突的方法及哈希表的查找。
⑼ 排序算法。掌握直接插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序和希爾排序算法和時(shí)間復(fù)雜度，了解基數(shù)排序、外排序的概念和算法。
二、基本內(nèi)容
第一章 數(shù)據(jù)結(jié)構(gòu)與算法概念
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)DS=(A,R)，其中A是數(shù)據(jù)元素的非空有限集合，R是定義在A上關(guān)系的非空有限集合。結(jié)構(gòu)就是元素之間的關(guān)系。
算法：算法就是解決問題的方法和步驟。
算法的時(shí)間復(fù)雜度：算法中語句重復(fù)執(zhí)行次數(shù)（或稱語句頻度）或算法中基本操作次數(shù)，一般用數(shù)量級符號○來描述。
抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型ADT=(A,R,P)，其中A是數(shù)據(jù)元素的非空有限集合，R是定義在A上關(guān)系的非空有限集合，P是(A，R)上非空的基本操作集合。
【例1-1】 求表2-1中程序段的各語句的語句頻度和時(shí)間復(fù)雜度。
表2-1 語句頻度和時(shí)間復(fù)雜度計(jì)算
語句
語句頻度
說明
for(i=0;i<N;I++)< SPAN>
n+1
當(dāng)i=n時(shí)，跳出for循環(huán)，故加1
for(j=0;j<I;J++)< SPAN>
即：
a[i][j]=x++;
時(shí)間復(fù)雜度T(n)為所有語句頻度之和，即T(n)=n+1+2 =
當(dāng)n→∞時(shí)， 所以時(shí)間復(fù)雜度T(n)=○(n2)
第二章 線性表
線性表的定義：線性表是n(n≥0)個(gè)元素的有限序列，當(dāng)n=0，則稱為空表；當(dāng)n>0時(shí)，線性表通常表示為（a1 ，a2 ，．．．，an），其中a1無前驅(qū)，an無后繼，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)和一個(gè)后繼。
線性表的存儲(chǔ)：線性表有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。
l 線性表的操作：主要操作有初始化表、判表空、求表長、查找、插入和刪除元素等。線性表的存儲(chǔ)結(jié)構(gòu)不同，具體的操作實(shí)現(xiàn)就不同，如表2-2所示。
表2-2 線性表的兩種存儲(chǔ)結(jié)構(gòu)的基本操作特點(diǎn)
順序存儲(chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
靜態(tài)數(shù)組
動(dòng)態(tài)數(shù)組
類
型
定
義
#define ArSize 10
typedef struct {
ElemType elem[ArSize];
int length;} SqList;
typedef struct {
Elemtype *elem;
int length, ArSize;
}sqList;
typedef struct node
{ElemType data;
struct node*next;
}LNode;
初
始
化
表
void initList(SqList *L)
{L->length=0;}
void initList(sqList *L, int n)
{L->elem=(ElemType*)malloc(
n*sizeof(ElemType));
L->ArSize=n;L->length=0;}
LNode *initLK( )
{LNode *head;
head=NULL;
return head;}
查
找
由于第i個(gè)元素ai的存儲(chǔ)位置LOC(ai)=LOC(a1)+(i-1)×d，所以能隨機(jī)查找任一個(gè)元素，時(shí)間復(fù)雜度為O(1)
只能進(jìn)行順序查找，查找一個(gè)元素平均比較次數(shù)為(n+1)/2
插
入
刪
除
插入、刪除時(shí)大量結(jié)點(diǎn)要移動(dòng)，在等概率下插入、刪除一個(gè)元素平均移動(dòng)結(jié)點(diǎn)的次數(shù)分別是n/2和(n-1)/2。
插入、刪除時(shí)只要修改相關(guān)的指針即可，時(shí)間復(fù)雜度都為O(1)
【例2-1】在非空的雙鏈表中刪除指針p所指向的結(jié)點(diǎn)。雙鏈表的結(jié)點(diǎn)形式如圖2-1(a)所示,刪除p的操作步驟如圖2-1(b)所示。
圖2-1中（1）為p->front->next=p->next;(2)為p->next->front=p->front 。
【例2-2】在非空的雙鏈表中指針p所指向的結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)q。插入q的操作步驟如圖2-2所示。
圖2-2中（1）為q->next=p; (2)q->front=p->front;
(3)p->front->next=q; (4)p->front=q
注意：步驟（3）與（4）的順序不能顛倒。
第三章棧和隊(duì)列
3.1 棧
l 棧的定義:棧是一種只能在表的某一端（首端）進(jìn)行操作的線性數(shù)據(jù)結(jié)構(gòu)。棧的操作主要有進(jìn)棧和出棧，因?yàn)橹荒茉谀骋欢诉M(jìn)棧出棧，所以必定是先進(jìn)后出的（FILO或LIFO）。
l 棧的存儲(chǔ)結(jié)構(gòu)：有順序棧（靜態(tài)數(shù)組或動(dòng)態(tài)數(shù)組）和鏈棧。
l 棧的操作：初始化棧、進(jìn)棧、出棧，通過棧頂指針（top）來操作如表2-3所示。
表2-3 順序棧和鏈棧的操作
靜態(tài)數(shù)組棧
動(dòng)態(tài)數(shù)組棧
鏈棧
類型定義
#define SSize 10
typedef struct {
ElemType elem[SSize];
int top;}SqSNode;
Typedef struct{
ElemType *elem,*top;
int SSize;
}DSNode;
typedef struct node
{ElemType data;
struct node*next;
}LSNode;
進(jìn)棧
SqSNode s;
s.elem[s.top++]=e;
DSNode s;
*s.top++=e;
LSNode *top,*p;
p=new LSNode;p->data=e; p->next=top;top=p;
出棧
e=s.elem[--s.top];
e=*--s.top;
p=top;e=p->data;
top=top->next;delete(p)
棧空
s.top==0
s.top==s.elem
top==NULL
棧滿
s.top==SSize
s.top==s.elem+s.SSize
空間分配失敗p==NULL
l 棧的應(yīng)用舉例：表達(dá)式求值和遞歸的實(shí)現(xiàn)。
【例3-1】算術(shù)表達(dá)式a+b*c/(d-e)-f的逆波蘭式為abc*de-/+f-;
【例3-2】已知下列算法
void p(int n)
{ if (n>1 &&n%2==1) p(n-1);
printf(“%2d”,n);
if (n>1 &&n%2==0) p(n-1);
}用p(5)調(diào)用的結(jié)果是：4 2 1 3 5
分析：當(dāng)遇到調(diào)用語句時(shí)將參數(shù)、返回地址進(jìn)棧；當(dāng)遇到函數(shù)結(jié)束時(shí)退棧返回。
3.2 隊(duì)列
l 隊(duì)列的定義：隊(duì)列是一種只能在表的尾端進(jìn)行插入操作，在首端進(jìn)行刪除操作的線性數(shù)據(jù)結(jié)構(gòu)。它是先進(jìn)先出（FIFO）的線性表。
l 隊(duì)列的存儲(chǔ)結(jié)構(gòu)：有順序隊(duì)列—循環(huán)隊(duì)列，設(shè)有首指針和尾指針；鏈隊(duì)列—一般在單循環(huán)鏈表上實(shí)現(xiàn)，只設(shè)尾指針，不設(shè)首指針稱循環(huán)鏈隊(duì)列。
隊(duì)列的操作：初始化隊(duì)列、進(jìn)隊(duì)、出隊(duì)，通過隊(duì)列的首指針front和尾指針rear實(shí)現(xiàn)操作如表2-4所示。
表2-4 循環(huán)隊(duì)列和循環(huán)鏈隊(duì)列的操作
循環(huán)隊(duì)列
循環(huán)鏈隊(duì)列
類型定義
#define QSize 10
typedef struct {
ElemType elem[QSize];
int front,rear;}SqQNode;
typedef struct node
{ElemType data;
struct node*next;
}LQNode;
進(jìn)隊(duì)
SqQNode Q;
Q.rear=(Q.rear+1)% QSize;
Q.elem[Q.rear]=e;
LQNode *rear,*p;
p=new LQNode; p->data=e; p->next=rear->next; rear->next=p; rear=p;
出隊(duì)
Q.front=(Q.front+1)% QSize;
e=Q.elem[Q.front];
p=rear->next; e=p->data;(無頭鏈表)
rear->next=p->next;delete(p)；
隊(duì)空
Q.front==Q.rear
rear==NULL
隊(duì)滿
Q.front==(Q.rear+1)%QSize
空間分配失敗p==NULL
【例3-3】設(shè)循環(huán)隊(duì)列Q，則當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)是：
(Q.rear-Q.front+ QSize)%QSize.
第四章 串
l 串、子串的定義：串是有限個(gè)字符組成的序列。子串是串中任意長度的連續(xù)字符構(gòu)成的序列。
l 串的運(yùn)算：兩個(gè)串的聯(lián)接、比較，串的賦值，求串長，插入子串，刪除子串和模式匹配。串的模式匹配算法有樸素的模式匹配算法和KMP算法等，設(shè)主串s、長度為m，子串t、長度為n，匹配算法如表2-5所示。
表2-5 模式匹配算法
樸素的模式匹配
KMP算法
若s[i]==t[j]，則i++；j++;
若s[i]==t[j]，則i++；j++;
若s[i]!=t[j]，則i=i-j+2；j=1;
若s[i]!=t[j]，則 j=next[j];i不動(dòng)
時(shí)間復(fù)雜度T（m,n）=○(mn)
時(shí)間復(fù)雜度T(m,n)=○(m+n)
其中
【例4-1】已知主串s=”ABBABA”,子串t=”ABA”,求用樸素的模式匹配算法查找子串t的比較次數(shù)。
解：用樸素的模式匹配算法需要進(jìn)行8次比較，子串位置是4。
【例4-2】求子串t=”ABCABCACAB”的next值。
解： j: 1 2 3 4 5 6 7 8 9 10
t[j]: A B C A B C A C A B
f[j]: 0 0 0 1 2 3 4 0 1 2
next[j]: 0 1 1 1 2 3 4 5 1 2
第五章數(shù)組和廣義表
l 數(shù)組的定義：n維數(shù)組Ab1b2…bn ,A中的每個(gè)元素A[j1, j2,…,jn]其中1≤ji≤bi,1為每一維的下界，bi為第i維的上界。
l 數(shù)組的存儲(chǔ)
l
【例5-1】已知三維數(shù)組Amnp,將A以行序?yàn)橹餍虼鎯?chǔ)在首地址為loc(A[1,1,1])的內(nèi)存空間中，每個(gè)元素占L個(gè)單元，則數(shù)組A中任意一個(gè)元素的地址為
loc(A[i,j,k])= loc(A[1,1,1])+((i-1)*n*p+(j-1)*p+k-1)*L
若以列序?yàn)橹餍颍瑒tloc(A[i,j,k])= loc(A[1,1,1])+((k-1)*m*n+(j-1)*m+i-1)*L
【例5-2】已知對稱陣Ann, 以行序?yàn)橹餍虼鎯?chǔ)A的下三角陣部分，內(nèi)存首地址為loc(A[1,1])，每個(gè)元素占L個(gè)單元，則下三角陣中任意一個(gè)元素的地址為
loc(A[i,j])=
【例5-3】已知上三角矩陣Ann 以行序?yàn)橹餍虼鎯?chǔ)在內(nèi)存首地址為loc(A[1,1])，每個(gè)元素占L個(gè)單元，則上三角陣中任意一個(gè)元素的地址為
loc(A[i,j])= loc(A[1,1])+((2n-i+2)*(i-1)/2+(j-i))*L 當(dāng)1≤i≤j時(shí)
【例5-4】 已知廣義表LS=((a,(b)),(c)),LS深度為3（括號的重?cái)?shù)），求頭Head(LS)=(a,(b)),求尾Tail(LS)=((c)).
【例5-5】已知四行七列的稀疏矩陣M=
，其三元組表為（(1,3,6),(2,2,3),(2,6,8),(4,1,5),(4,6,7)）。
【例5-6】已知廣義表LS=((a),(b,c)),廣義表的結(jié)點(diǎn)結(jié)構(gòu)如圖2-3 所示，LS的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖2-4 所示。
第六章樹和二叉樹
6．1 二叉樹
l 二叉樹的定義：二叉樹是由一個(gè)特定的結(jié)點(diǎn)（無前驅(qū)）稱為根和兩個(gè)互不相交的左子樹、右子樹組成，其中左子樹，右子樹本身是二叉樹。
l
l 線索二叉樹：二叉樹用二叉鏈表存儲(chǔ)時(shí)，當(dāng)二叉樹有n個(gè)結(jié)點(diǎn)時(shí)，則有n+1個(gè)指針域?yàn)榭?，可以利用這些空指針域存放某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種二叉樹就稱為線索二叉樹。在線索二叉樹中用得較多的是中序線索二叉樹，即樹中任意結(jié)點(diǎn)p，若p左指針域空，則其左指針域指向p的中序前趨;若p右指針域空，則其右指針域指向p的中序后繼。
l 哈夫曼樹（Huffman）：哈夫曼樹又稱最優(yōu)二叉樹。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最小的二叉樹。其中：
其中n表示葉子結(jié)點(diǎn)的數(shù)目，Wi和li分別表示葉子結(jié)點(diǎn)ki 的權(quán)值和根到ki 之間的路徑長度。
6．2 樹和森林
l 樹的定義：樹是由一個(gè)特定的結(jié)點(diǎn)（無前驅(qū)）稱為根和m(m>0)個(gè)互不相交的樹（稱為子樹）組成，其中當(dāng)m=0時(shí)稱為空樹。
l
l
l 樹轉(zhuǎn)換為二叉樹：樹用孩子兄弟表示法表示后即為二叉樹了。
l
【例6-1】圖2-5所示樹與二叉樹的區(qū)別，二叉樹的子樹有左右之分。
【例6-2】圖2-6所示滿二叉樹和完全二叉樹。
【例6-3】完全二叉樹的順序存儲(chǔ)如圖2-7所示。
【例6-4】n個(gè)結(jié)點(diǎn)的二叉樹用二叉鏈表存儲(chǔ)，那么有n+1個(gè)空指針，因?yàn)閚個(gè)結(jié)點(diǎn)共有2n個(gè)指針空間，其中n-1個(gè)指向孩子結(jié)點(diǎn)。
【例6-5】對于圖2-8所示的二叉樹，它的
前序遍歷序列為：ABEDHCFG
中序遍歷序列為：EDBHACGF
后序遍歷序列為：DEHBGFCA
層次遍歷序列為：ABCEHFDG
【例6-6】對于圖2-9所示的二叉樹，其中序線索二叉樹如圖2-10所示。
【例6-7】假設(shè)通信的電文僅有a,b,c,d,e五個(gè)字母組成，字母在電文中出現(xiàn)的次數(shù)分別是8，2，5，4，5。用哈夫曼算法構(gòu)造的哈夫曼樹過程如圖2-11所示。
哈夫曼樹中從根到每個(gè)葉子結(jié)點(diǎn)都有一條唯一的路徑，對路徑上的各分支約定左分支表示‘0’碼，右分支表示‘1’碼，則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支的碼組成的字符串作為該葉子結(jié)點(diǎn)的編碼，這就是哈夫曼編碼。為上述五個(gè)字母設(shè)計(jì)的哈夫曼編碼如圖2-12所示。
【例6-8】對于圖2-13的樹T，它的孩子兄弟表示法如圖2-14所示，即將樹T轉(zhuǎn)換為二叉樹了。
【例6-9】圖2-13中樹T的前序遍歷序列為：ABEFCDG, 后序遍歷序列為：EFBCGDA。而圖2-14中的二叉樹的前序遍歷序列為：ABEFCDG, 中序遍歷序列為：EFBCGDA。這個(gè)例子驗(yàn)證了樹和樹轉(zhuǎn)換為二叉樹的前序遍歷序列相同；樹的后序與二叉樹的中序相同。
第七章 圖
7.1 圖的定義：圖G＝（V，E），其中V是頂點(diǎn)（結(jié)點(diǎn)）的有窮非空集合，E是V中頂點(diǎn)的序偶組成的有窮集，這些序偶稱為邊。
7.2 基本術(shù)語
l鄰接點(diǎn)：，若存在一條邊<Vi,vj>，則在無向圖中稱vi和vj互為鄰接點(diǎn)，在有向圖中稱vj是vi 的鄰接點(diǎn)。
l 完全圖：圖G中任意兩點(diǎn)都鄰接，稱該圖為完全圖。無向完全圖有n（n-1）／2條邊,有向完全圖有n（n-1）條邊。
l 度、入度和出度：無向圖中頂點(diǎn)v依附(關(guān)聯(lián))的邊數(shù)稱為v的度。對于有向圖，頂點(diǎn)V的度分為入度和出度，v的入度是邊的箭頭指向v的入邊數(shù)目；v的出度是箭頭離開v的出邊數(shù)目。有關(guān)度的結(jié)論有圖中所有結(jié)點(diǎn)度數(shù)之和等于圖的邊數(shù)的兩倍。
l 連通和連通圖：在無向圖G中．若從頂點(diǎn)vi到vj有路徑，則稱vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱G連通圖。
l連通分量：無向圖G中的極大連通子圖稱為圖G的連通分量。
l 強(qiáng)連通圖和強(qiáng)連通分量：在有向圖G中，若任意兩個(gè)頂點(diǎn)vi和vj都連通，即從vi到vj存在路徑，從vj到vi也存在路徑,則稱該圖是強(qiáng)連通圖。有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。
l 網(wǎng)：在一個(gè)圖中，每條邊可以標(biāo)上具有某種含義的數(shù)值，該數(shù)值稱為該邊的權(quán)。邊帶權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)。
l 生成樹：連通圖G有n個(gè)頂點(diǎn)，取G中n個(gè)頂點(diǎn)，取連接n個(gè)頂點(diǎn)的n-1條邊所得的子圖稱為G的生成樹。滿足此定義的生成樹可能有多棵，即生成樹不唯一。
7.3 圖的存儲(chǔ)結(jié)構(gòu)
l 鄰接矩陣：鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)圖G=（V，E）有n個(gè)頂點(diǎn)，則G的鄰接矩陣是一個(gè)n階方陣：
A[i][j]=
若圖是帶權(quán)(w)圖,則：
A[i][j]=
l 鄰接表：鄰接表就是對圖中的每個(gè)頂點(diǎn)ki建立一個(gè)單鏈表，把與ki相鄰接的頂點(diǎn)放在一個(gè)鏈表中。
7.4 圖的遍歷
l 深度優(yōu)先搜索遍歷(DFS)：首先訪問指定的起始頂點(diǎn)v，然后選取與v鄰接的未被訪問的任意一個(gè)頂點(diǎn)w，訪問之，再選取與w鄰接的未被訪問的任一頂點(diǎn)，訪問之。重復(fù)進(jìn)行如上的訪問，當(dāng)?shù)竭_(dá)一個(gè)所有鄰接頂點(diǎn)都被訪問過時(shí)，則依次退回到最近被訪問過的頂點(diǎn)，若它還有鄰接頂點(diǎn)未被訪問過，從這些未被訪問過的頂點(diǎn)中取其中的一個(gè)頂點(diǎn)開始重復(fù)上述的訪問過程，直到所有的頂點(diǎn)都被訪問過為止。
l 廣度優(yōu)先搜索遍歷(BFS)：首先訪問指定的起始頂點(diǎn)v，然后選取與v鄰接的全部頂點(diǎn)w1,w2,...,wt,再依次訪問與w1,w2,...,wt鄰接的全部頂點(diǎn)（已被訪問的頂點(diǎn)除外），再從這些被訪問的頂點(diǎn)出發(fā)，逐次訪問與它們鄰接的全部頂點(diǎn)（已被訪問的頂點(diǎn)除外）。依次類推，直到所有頂點(diǎn)都被訪問過為止。
l 深度優(yōu)先生成樹和廣度優(yōu)先生成樹：在對具有n個(gè)頂點(diǎn)的連通圖進(jìn)行遍歷時(shí)，要訪問圖中的所有頂點(diǎn)，在訪問n個(gè)頂點(diǎn)過程中一定經(jīng)過n-1條邊，由深度優(yōu)先遍歷和廣度優(yōu)先遍歷所經(jīng)過的n-1條邊是不同的，通常把由深度優(yōu)先遍歷所經(jīng)過的n-1條邊和n個(gè)頂點(diǎn)組成的圖形就稱為深度優(yōu)先生成樹。而由廣度優(yōu)先遍歷所經(jīng)過的n-1條邊和n個(gè)頂點(diǎn)組成的圖形就稱為廣度優(yōu)先生成樹。
7.5 最小生成樹
l 定義：生成樹中邊權(quán)之和定義為樹權(quán)，在圖的所有生成樹中樹權(quán)最小的那棵生成樹就是最小生成樹。
l 最小生成樹的算法：普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法，Prim算法的時(shí)間復(fù)雜度為O(n2),它適用于稠密圖，而Kruskal算法的時(shí)間復(fù)雜度為O(elog2e), 它適用于稀疏圖。
7.6 拓?fù)渑判?div style="height:15px;">
l 拓?fù)渑判蚓褪菍σ粋€(gè)有向無環(huán)圖（AOV網(wǎng)）中的各頂點(diǎn)排成一個(gè)具有前后次序的線性序列。
l 拓?fù)渑判虻姆椒ǎ涸趫D中始終找無前趨（入度為零）的頂點(diǎn)，找到無前趨的頂點(diǎn)輸出并將其每個(gè)后繼頂點(diǎn)的前趨數(shù)（入度數(shù)）減1，重復(fù)上述過程直至所有頂點(diǎn)都輸出或無頂點(diǎn)可輸出。只要圖是無環(huán)的，一定能輸出所有的頂點(diǎn)，否則說明有向圖存在環(huán)。算法的時(shí)間復(fù)雜度為O(n+e)。
7.7 關(guān)鍵路徑
l 帶權(quán)有向圖（AOE網(wǎng)）中從源點(diǎn)(表示工程開始)到匯點(diǎn)(表示工程結(jié)束)的路徑長度最長的路徑稱為關(guān)鍵路徑。關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng),只要提高關(guān)鍵路徑上的活動(dòng)的速度就能縮短整個(gè)工程的工期。
7.8 最短路徑
l 最短路徑是圖中兩個(gè)頂點(diǎn)之間的最短距離或最便宜的交通費(fèi)用或途中所需的時(shí)間最少的問題。要找出最短路徑方法很多。常用經(jīng)典算法Dijkstra算法來求從一個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑。
l
【例7-1】已知圖G如圖2-15所示從v0出發(fā)深度優(yōu)先遍歷序列是v0 v1 v2 v3 v7 v4 v5 v6或v0 v3 v2 v7 v1 v4 v5 v6 等，從v0出發(fā)廣度優(yōu)先遍歷序列：v0 v1 v3 v4 v2 v5 v6 v7或v0 v4 v3 v1 v6 v5 v2 v7等。
【例7-2】對于圖2-15所示無向圖，從v0出發(fā)深度優(yōu)先遍歷生成樹和廣度優(yōu)先遍歷生成樹如圖2-16所示。
【例7-3】用Prim算法構(gòu)造的最小生成樹的過程如圖2-17所示。
【例7-4】用Kruskal算法構(gòu)造的最小生成樹的過程如圖2-18所示。
【例7-5】假設(shè)某專業(yè)中的六門課程的前修后繼之間的關(guān)系如圖2-19所示,課程的教學(xué)安排次序?yàn)椋篶1、c3、c2、c5、c4、c6?；騝1、c2、c3、c5、c4、c6。這就是拓?fù)渑判蛐蛄?，方法是將圖中的無前驅(qū)的結(jié)點(diǎn)輸出，若有多個(gè)無前驅(qū)的結(jié)點(diǎn)，則用?；蜿?duì)列暫存無前驅(qū)的結(jié)點(diǎn)，然后依次輸出并將后件的前驅(qū)數(shù)減一。
【例7-6】已知AOE網(wǎng)如圖2-20（a）所示，其中頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的數(shù)值表示活動(dòng)需要的時(shí)間，關(guān)鍵路徑如圖2-20（b）所示。
2-22 有向圖的鄰接矩陣
【例7-7】有向圖G如圖2-21所示，G的鄰接矩陣如圖2-22所示：
從源點(diǎn)v0到各終點(diǎn)的最短路徑值、路徑和Dijkstra算法的動(dòng)態(tài)執(zhí)行過程如圖2-23所示：
輸出結(jié)果為：
v0到v2：v0→v2 距離10
v0到v4：v0→v4 距離30
v0到v3：v0→v4→v3 距離50
v0到v5：v0→v4→v3→v5 距離60
v0到v1：無路徑 距離∞
第九章查找
9.1 查找概念
9.2 靜態(tài)查找表上的查找方法：
9.3 動(dòng)態(tài)查找表的查找
1．二叉搜索(排序)樹
l 定義：非空的二叉排序樹中的任意結(jié)點(diǎn)K，若k有左子樹，則左子樹中的每個(gè)結(jié)點(diǎn)的值都小于k的值；若k有右子樹，則右子樹中的每個(gè)結(jié)點(diǎn)的值都大于等于k的值。（注意：k是指樹中的每個(gè)結(jié)點(diǎn)）
l 查找：將待查元素與二叉排序樹的根比較，若相等，則查找成功；若待查元素小于根，則在左子樹中找；若待查元素大于根，則在右子樹中找；重復(fù)這樣的查找過程直至找到（查找成功）或子樹空（查找不成功）止。
l 插入：先查找插入位置，然后新結(jié)點(diǎn)掛在從根到插入位置這條路徑的末端。
l 刪除：先查找到被刪元素，①若被刪元素是葉子，則直接刪除；②若被刪結(jié)點(diǎn)是單支（被刪結(jié)點(diǎn)只有左子樹或只有右子樹）結(jié)點(diǎn)，則將單支的子樹掛到被刪結(jié)點(diǎn)的父結(jié)點(diǎn)上即從樹上斷開了被刪結(jié)點(diǎn)；③若被刪結(jié)點(diǎn)是雙支（被刪結(jié)點(diǎn)有左子樹又有右子樹）結(jié)點(diǎn)，則將左子樹掛到被刪結(jié)點(diǎn)的中序后繼的左邊或?qū)⒂易訕鋻斓奖粍h結(jié)點(diǎn)的中序前驅(qū)的右邊，這樣變成刪單支結(jié)點(diǎn)如情況②所述操作。
2．平衡二叉樹（AVL樹）
l 定義：對于非空的平衡二叉樹中的任意結(jié)點(diǎn)K，K的左子樹和右子樹的深度之差的絕對值不超過1。注意：k是指樹中的每個(gè)結(jié)點(diǎn)。
l 插入：在平衡二叉排序樹中插入結(jié)點(diǎn)，然后檢查是否因插入結(jié)點(diǎn)而破壞平衡，若是，則找出其中最小的不平衡二叉樹，按如圖2-24所示情況進(jìn)行調(diào)整。
圖2-24中結(jié)點(diǎn)的值為該結(jié)點(diǎn)的平衡值，陰影結(jié)點(diǎn)的平衡值為1或0或-1。
3． B_樹
l B_樹定義：一棵m階B_樹，或是空樹，或是滿足下列特性的m叉樹：
①樹中每個(gè)結(jié)點(diǎn)最多有m棵子樹；
②若根不是葉結(jié)點(diǎn)，則至少有兩棵子樹；
③除根外的每個(gè)非終端結(jié)點(diǎn)至少有 棵子樹；
④所有非終端結(jié)點(diǎn)中都包含下列數(shù)據(jù)信息：
（n,A0,K1,A1,K2,A2，…，Kn,An）
其中Ki(i=1,2, …,n)為關(guān)鍵字且由小到大有序排列，Ai(i=0,1, …,n)為指向子樹根的指針，且指針Ai-1 所指子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki, An 所指結(jié)點(diǎn)的關(guān)鍵字均大于Kn, n為結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目( )。
⑤所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息(看作外部結(jié)點(diǎn)或查找失敗結(jié)點(diǎn))。
一棵 3 階B_樹如圖2-25所示。
3 階B_樹也稱2-3樹。
l B_樹的查找：類似二叉排序樹的查找，首先在根結(jié)點(diǎn)包含的關(guān)鍵字中查找，若找到則成功返回；否則根據(jù)待查的關(guān)鍵字在相應(yīng)的子樹中繼續(xù)查找，直至查找成功或查找失敗。
l B_樹的插入：B_樹的結(jié)點(diǎn)插入只在底層進(jìn)行，先查找插入位置，在底層某個(gè)位置中插入結(jié)點(diǎn)，若該結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)不超過m-1，則插入完成；否則進(jìn)行結(jié)點(diǎn)的“分裂”處理。“分裂”就是把結(jié)點(diǎn)中處于中間位置上的關(guān)鍵字取出插到父結(jié)點(diǎn)中，并以該結(jié)點(diǎn)為分界線，把原結(jié)點(diǎn)分成兩個(gè)結(jié)點(diǎn)，對父結(jié)點(diǎn)再進(jìn)行關(guān)鍵字個(gè)數(shù)判斷，“分裂”過程可能一直持續(xù)到樹根。
l B_樹的刪除：先找到被刪結(jié)點(diǎn)，若被刪結(jié)點(diǎn)不在底層，則用底層的后繼（或前驅(qū)）替代，然后再刪后繼（或前驅(qū)），若被刪結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目小于 則進(jìn)行“合并”，否則刪除完成。
4．哈希表及其查找
l 哈希表：設(shè)哈希函數(shù)H(Key),結(jié)點(diǎn)的存儲(chǔ)方法為：H(關(guān)鍵字)=存儲(chǔ)位置，即關(guān)鍵字作為函數(shù)的自變量，函數(shù)值解釋為存儲(chǔ)位置，按這種方法得到的存儲(chǔ)結(jié)構(gòu)圖稱為哈希表。
l 解決沖突的方法：當(dāng)哈希函數(shù)H(Key)不是一對一函數(shù)時(shí)則產(chǎn)生沖突，沖突即兩個(gè)不同結(jié)點(diǎn)占同一存儲(chǔ)空間。常見的處理沖突的方法有：
①開放地址法：
Hi=(H(Key)+di)%M i=1,2,…，M-1
其中H(Key)為哈希函數(shù)；M為哈希表的長度；di為增量序列。
當(dāng)di=1，2，3，…，M-1時(shí)稱為線性探測再散列。
當(dāng)di=12，-12，22，-22，…，±k2(k≤M/2)時(shí)稱為二次探測再散列。
在發(fā)生沖突時(shí)順序地到存儲(chǔ)區(qū)的下一個(gè)單元進(jìn)行探測。
②鏈地址法：每個(gè)結(jié)點(diǎn)增加一個(gè)鏈域，鏈域指向沖突結(jié)點(diǎn)。
【例9-1】已知關(guān)鍵字序列 4,7,9,10,15,21,33,48,52,61。寫出用二分查找方法查找關(guān)鍵字52的比較次數(shù)并寫出等概率的平均查找長度。
解：序列長度為10，求任意結(jié)點(diǎn)的查找次數(shù)可以用如圖2-26所示的判定樹描述。
從判定樹可得查找52的比較次數(shù)為3次，ASL= =2.9
【例9-2】畫出有序序列長度為15的判定樹。
解：15個(gè)元素的判定樹如圖2-27所示：
圖中的數(shù)字為序列的關(guān)鍵字所在序列中的下標(biāo)。
【例9-3】從空的二叉排序樹開始依次插入29，20，35，8，15，39，28。畫出該二叉排序樹并計(jì)算平均查找長度。
span style='mso-ignore:vglayout;;z-index:23;margin-left:192px;margin-top:0px;width:160px;height:178px'解：二叉排序樹如圖2-28所示：
ASL= =2.57
【例9-4】在如圖2-29所示二叉排序樹中刪除結(jié)點(diǎn)20和35的過程。
【例9-5】從空的平衡樹中依次插入5，7，9，50，25，37，30。畫出建平衡二叉樹的過程。
解：建平衡二叉樹的過程如圖2-30所示。
【例9-6】從空的2-3樹開始依次插入20，30，50，52，60，68，70，畫出建立2-3樹的過程。并畫出刪除50和68后的2-3樹狀態(tài)。
解：2-3樹的建立過程如圖2-31所示，刪除50，68后的B_樹狀態(tài)如圖2-32所示。
圖中每個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)數(shù)省略了。
【例9-7】已知一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51），哈希函數(shù)為H(key)=key%13,用線性探測再散列法解決沖突，畫出哈希表并求平均查找長度。
解：哈希表如圖2-33所示，平均查找長度ASL=
【例9-8】對于例2.37的關(guān)鍵字序列用鏈地址法解決沖突的哈希表如圖2-34所示, 平均查找長度ASL=
第十章排序
10.1 排序的基本概念
排序：將無序序列調(diào)整為有序序列。
穩(wěn)定性：若待排序記錄中有相同關(guān)鍵字，排序后相同關(guān)鍵字的相對位置發(fā)生變化，則稱該排序是不穩(wěn)定的；
內(nèi)部排序：指待排序記錄全部存放在內(nèi)存中進(jìn)行排序的過程。
外部排序：指待排序的數(shù)量很大，以至內(nèi)存不能放下全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。
1．簡單排序
（1）直接插入排序
基本思想：將無序序列中從第二個(gè)開始的每個(gè)元素依次插入到有序序列中，當(dāng)序列有n個(gè)元素時(shí)，則進(jìn)行n-1次插入。
l 算法：
void insertsort(int r[ ],int n)
/*將數(shù)組r[1]～r[n]中的n個(gè)整數(shù)按非遞減有序方式進(jìn)行直接插入排序*/
{int i,j; for(i=2;i<=n;i++)
if ( r[i]<R[I-1])< SPAN> {r[0]=r[i];j=i-1;
do{ r[j+1]=r[j];j--; } while (r[0]<R[J]);< SPAN>
r[j+1]=r[0];
}
}
l 穩(wěn)定性：穩(wěn)定的算法分析：如表2-6所示
表2-6 直接插入排序算法的時(shí)間復(fù)雜度分析
直接插入排序
最好情況
最差情況
一般情況
比較次數(shù)
n-1 次
次
○(n2)
移動(dòng)次數(shù)
0次
次
○(n2)
時(shí)間復(fù)雜度
○(n)
○(n2)
○(n2)
（2）冒泡排序
基本思想：小的往上冒方法：從無序序列的最后元素開始往前兩兩比較，第一次冒出最小元素，第二次在剩余的結(jié)點(diǎn)序列中冒出第二小的，這樣共要冒出n-1個(gè)小的數(shù)。（也可以用大的往下沉方法）
l 算法：
void bubblesort(int r[ ],int n)
/*將數(shù)組r[0]～r[n-1]中的n個(gè)整數(shù)按非遞減有序方式進(jìn)行冒泡排序*/
{int i,j,tag,temp;
for(i=0;i<N-1;I++)< SPAN>
{ tag=0;for(j=n-1;j>=i+1;j--)
if(r[j]<R[J-1])< SPAN>{temp=r[j];r[j]=r[j-1];r[j-1]=temp;tag=1;}
if(tag==0) break;
}
}
l 穩(wěn)定性：穩(wěn)定的
l 算法分析：如表2-7所示
表2-7 冒泡排序算法的時(shí)間復(fù)雜度分析
冒泡排序
最好情況
最差情況
一般情況
比較次數(shù)
n-1 次
次
○(n2)
移動(dòng)次數(shù)
0次
次
○(n2)
時(shí)間復(fù)雜度
○(n)
○(n2)
○(n2)
（3）簡單選擇排序
l 基本思想：第一次從無序序列中選出第一小的元素，然后從剩余的結(jié)點(diǎn)序列中選出第二小的元素，這樣共選出n-1小的數(shù)。
l 算法：
void selectsort(int r[ ],int n)
/*將數(shù)組r[0]～r[n-1]中的n個(gè)整數(shù)按非遞減有序方式進(jìn)行選擇排序*/
{int i,j,k,temp;
for(i=0;i<N-1;I++)< SPAN>
{k=i;
for(j=i+1;j<N;J++)< SPAN>
if(r[j]< SPAN>
if(i!=k){ temp=r[i];r[i]=r[k];r[k]=temp;}
}
}
l 穩(wěn)定性：不穩(wěn)定的
l 算法分析：如表2-8所示
表2-8 簡單選擇排序算法的時(shí)間復(fù)雜度分析
簡單選擇排序
最好情況
最差情況
一般情況
比較次數(shù)
次
次
○(n2)
移動(dòng)次數(shù)
0次
3(n-1)次
○(n)
時(shí)間復(fù)雜度
○(n2)
○(n2)
○(n2)
3．先進(jìn)的排序
（1）希爾排序
希爾排序是直接插入排序方法的改進(jìn)，基本思想是：先將整個(gè)待排序列分割成若干子序列（或稱組），然后對各個(gè)子序列分別進(jìn)行直接插入排序。待整個(gè)序列中的元素基本有序時(shí)，再對整個(gè)序列進(jìn)行一次直接插入排序。具體做法是：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把序列分成d1個(gè)子序列，將所有間隔距離為d1的元素放在同一子序列中，在各個(gè)子序列中進(jìn)行直接插入排序，然后取第二個(gè)增量d2<D1,重復(fù)上述分組和排序，依次類推，直至所取的增量di=1為止，即所有元素在同一組中進(jìn)行直接插入排序。
希爾排序中元素是跳躍式移動(dòng)的，所以是不穩(wěn)定的。盡管希爾排序中調(diào)用了多次直接插入排序，但初始子序列較短，花得時(shí)間不會(huì)太多，后面序列基本有序，花得時(shí)間接近直接插入排序的最好時(shí)間，所以希爾排序的時(shí)間復(fù)雜度接近○(nlog2n)。
（2）快速排序
l 算法思想：選取序列的第一個(gè)結(jié)點(diǎn)，以它的關(guān)鍵字和序列中所有其它結(jié)點(diǎn)的關(guān)鍵字比較，將所有關(guān)鍵字較它小的結(jié)點(diǎn)放在它之前，將所有關(guān)鍵字較它大的結(jié)點(diǎn)放在它之后，則經(jīng)過這樣的一趟排序后，可按該結(jié)點(diǎn)所在位置為界，將序列分成兩部分，然后再分別對這兩部分重復(fù)上述過程，直至每一部分只剩一個(gè)結(jié)點(diǎn)為止。
l 排序過程：
25 84 21 47 15 27 68 35 20
20 15 21 25 47 27 68 35 84
15 20 21 25 35 27 47 68 84
15 20 21 25 27 35 47 68 84
l 算法：
void quicksort(node r[ ],int L,int R)
{int i,j;
if(L<R)< SPAN> { i=L;j=R;r[0]=r[i];
do{while (r[j].key>=r[0].key && i<>
if (i
while (r[i].key<=r[0].key && i<>
if (i
}while (i!=j);
r[i]=r[0];
quicksort(r, L, i-1); quicksort(r, i+1, R);
}
}
l 穩(wěn)定性：不穩(wěn)定的
l 算法分析：一般情況下的時(shí)間復(fù)雜度為O(nlog2n)，最壞情況下的時(shí)間復(fù)雜度O(n2)。
（3）堆排序
l 堆的定義：n個(gè)元素的關(guān)鍵字序列{ K1,K2,…，Kn},當(dāng)且僅當(dāng)所有關(guān)鍵字都滿足下列關(guān)系式時(shí)稱為堆： (稱為小根堆) 或 (稱為大根堆) 其中 1≤i≤n/2 。
l 堆排序的算法思想：首先將序列按堆的定義建成堆（如大根堆），從而堆頂?shù)年P(guān)鍵字最大，將堆頂與堆末交換，這樣得到了最大數(shù)，并把末元素從堆中去掉，然后再將堆頂調(diào)整為堆，從而堆頂為次大數(shù)，得到了次大數(shù)。如此反復(fù)進(jìn)行，直到堆中只剩一個(gè)元素止，此時(shí)數(shù)組的元素為遞增（或非遞減）有序序列。
l 算法：
void heapsort(int r[ ], int n)
/*將數(shù)組r[0]～r[n-1]中的n個(gè)整數(shù)按非遞減有序方式進(jìn)行堆排序*/
{int i,t;
for(i=n/1-1;i>0;i--)
heapadjust(r,i,n-1);
for(i=n-1;i>0;i--)
{t=r[0];r[0]=r[i];r[i]=t; heapadjust(r , 0, i-1);}
}
void heapadjust(int r[ ],int s,int m)
/*使r[s] ～r[m]為大根堆*/
{int i,j,t;
t=r[s];
for(j=2*s+1;j<=m;j=2*j+1)
{if (j<M&&R[J]<R[J+1])J++;< SPAN>
if(t>=r[j])break;
r[s]=r[j];s=j;
}
r[s]=t;
}
l 穩(wěn)定性：不穩(wěn)定的
l 算法分析：堆排序的最好、最差情況下的時(shí)間復(fù)雜度都為O(nlog2n)。
（4）歸并排序
l 算法思想：將兩個(gè)或多個(gè)有序序列合并成一個(gè)新的有序序列。
l 穩(wěn)定性：穩(wěn)定的
l 算法分析：歸并排序的最好、最差情況下的時(shí)間復(fù)雜度都為O(nlog2n)。
（5）基數(shù)排序
l 算法思想：基數(shù)排序是按組成關(guān)鍵字各個(gè)數(shù)位的值進(jìn)行排序的，具體做法是：根據(jù)基數(shù)r（若關(guān)鍵字是十進(jìn)制，則r=10）設(shè)置r個(gè)口袋（0～r-1），對關(guān)鍵字的第T位的值分配到相應(yīng)的口袋中，當(dāng)所有關(guān)鍵字分配完，則從0號～r-1號的次序進(jìn)行收集，若最大關(guān)鍵字有d位，則上述過程重復(fù)d次。T可以從最高有效位開始，也可以從最低有效位開始。
l 排序過程：如表2-9、表2-10所示
關(guān)鍵字序列：52，18，17，5，8，7，25
表2-9 基數(shù)排序的個(gè)位分配
口袋
0
1
2
3
4
5
6
7
8
9
個(gè)位分配
52
5
25
17
7
18
8
個(gè)位收集：52，5，25，17，7，18，8
表2-10 基數(shù)排序的十位分配
口袋
0
1
2
3
4
5
6
7
8
9
十位分配
5
7
8
17
18
25
52
十位收集：5，7，8，17，18，25，52
l 穩(wěn)定性：穩(wěn)定的
l 算法分析：基數(shù)排序的平均時(shí)間復(fù)雜度為O(d×(n+r))。
【例10-1】 給出一個(gè)例子說明簡單選擇排序是不穩(wěn)定的。
解：關(guān)鍵字序列如下：
5，5，4，7，2
2，5，4，7，5
2，4，5，7，5
2，4，5，5，7
帶下劃線的是后一個(gè)相同關(guān)鍵字。
【例10-2】判斷序列(100,70,33,65,24,56,48,92,86,33)是否為大根堆，如果不是，則把它調(diào)整為堆。
解：(100,70,33,65,24,56,48,92,86,33)不是堆，調(diào)整為大根堆：（100，92，56，86，33，33，48，65，70，24）
4．外排序
外排序就是對大型文件的排序，待排序的記錄存放在外存上，在排序過程中，內(nèi)存只存儲(chǔ)文件的一部分記錄，整個(gè)排序過程需要進(jìn)行多次的內(nèi)外存間的數(shù)據(jù)交換。
常用的外排序方法是歸并排序，先將文件中的記錄分段分別讀入內(nèi)存，用內(nèi)部排序方法分別進(jìn)行排序形成一個(gè)一個(gè)歸并段，然后用某種歸并方法進(jìn)行一趟一趟地歸并，使文件的有序段逐漸加長，直至整個(gè)文件歸并為一個(gè)有序段為止。
三、重點(diǎn)習(xí)題解析
本章重點(diǎn)內(nèi)容是棧，隊(duì)列，二叉樹性質(zhì)及遍歷，圖的存儲(chǔ)及遍歷，二分查找，二叉排序樹，哈希表和內(nèi)部排序。本節(jié)給出相關(guān)習(xí)題的討論。
本章難點(diǎn)內(nèi)容是：時(shí)間復(fù)雜度計(jì)算，串模式匹配中的next函數(shù)，平衡二叉樹，B_樹，算法設(shè)計(jì)方法等
(一)判斷題
從下列各題敘述中分別選出5條正確的敘述。
1． ①順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。
②順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。
③鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。
④散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。
⑤散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。
⑥負(fù)載因子（裝填因子）是散列法的一個(gè)重要參數(shù)，它反映散列表的裝滿程度。
⑦棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。
⑧用二叉鏈表法存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。
⑨用相鄰矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。
⑩鄰接表法只能用于有向圖的存儲(chǔ)，而相鄰矩陣法對于有向圖的存儲(chǔ)都適用。
2． ①二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對一般的樹則無此限制，因此二叉樹是樹的特殊情形。
②當(dāng)k≥1時(shí)，高度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。
③用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。
④線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)。
⑤將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹。
⑥一棵含有n個(gè)結(jié)點(diǎn)的完全二叉樹，它的高度是 。
⑦在二叉樹中插入結(jié)點(diǎn)，該二叉樹便不再是二叉樹。
⑧采用二叉鏈表作樹的存貯結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是一樣的
⑨哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。
⑩用一維數(shù)組存貯二叉樹時(shí)，總是以前序遍歷順序存貯結(jié)點(diǎn)。
3． ①一棵二叉樹的層次遍歷方法只有前序法和后序法兩種。
②在哈夫曼樹中，葉結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)個(gè)數(shù)多1。
③完全二叉樹一定是平衡二叉樹。
④在二叉樹的前序序列中，若結(jié)點(diǎn)u在結(jié)點(diǎn)v之前，則u一定是v的祖先。
⑤在查找樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。
⑥樹的后序序列和其對應(yīng)的二叉樹的后序序列的結(jié)果是一樣的。
⑦對B_樹刪除某一關(guān)鍵字值時(shí)，可能會(huì)引起結(jié)點(diǎn)的分裂。
⑧在含有n個(gè)結(jié)點(diǎn)的樹中，邊數(shù)只能是n-1條。
⑨最佳查找樹就是檢索效率最高的查找樹。
⑩中序遍歷二叉鏈表存儲(chǔ)的二叉樹時(shí)，一般要用堆棧；中序遍歷檢索二叉樹時(shí)，也必須使用堆棧。
4． ①m階B_樹每一個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)都小于等于m。
②m階B_樹每一個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)都大于等于 。
③m階B_樹具有k個(gè)后件的非葉子結(jié)點(diǎn)含有k—1個(gè)鍵值。
④m階B_樹的任何一個(gè)結(jié)點(diǎn)的左右子樹的高度都相等。
⑤中序遍歷一棵查找樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。
⑥用指針的方式存儲(chǔ)一棵有n個(gè)結(jié)點(diǎn)的二叉樹，最少要n+1個(gè)指針。
⑦任一查找樹的平均查找時(shí)間都小于用順序查找同樣結(jié)點(diǎn)的線性表的平均查找時(shí)間。
⑧平衡樹一定是豐滿樹。
⑨已知樹的前序遍歷并不能唯一地確定這棵樹，因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個(gè)。
⑩不使用遞歸，也可以實(shí)現(xiàn)二叉樹的前序、中序及后序遍歷。
n 判斷題答案：
1．④⑥⑦⑧⑨ 2．③④⑥⑧⑨ 3．②③⑧⑨⑩ 4．①③④⑤⑩
（二）填空題
1．算法好壞主要從 和 方面來衡量。
2．算術(shù)表達(dá)式a+b/(c+d)′f的逆波蘭式是______________。
3．在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列Q[0…M-1]，頭尾指針分別是front和rear，判斷隊(duì)空的條件為________，判斷隊(duì)滿的條件為_________。
4．設(shè)二維數(shù)組a[10][10] 是對稱陣，現(xiàn)將a中的上三角（含對角線）元素以行為主序存儲(chǔ)在首地址為2000的存儲(chǔ)區(qū)域中，每個(gè)元素占3個(gè)單元，則元素a[6][7]的地址為________。
5．廣義表( (a,b),(c) )的表頭是 ，表尾是 。
6．假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點(diǎn)數(shù)為______個(gè)，樹的深度為_____，樹的度為______。
7．在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有______個(gè)。
8．一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為_______，最大深度為_______。
9．對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，對應(yīng)二叉鏈表中指針總數(shù)為______個(gè)，其中______個(gè)用于指向孩子結(jié)點(diǎn)，______個(gè)指針空閑著。
10．某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是 。
11．有一棵50個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)有 個(gè)。
12．設(shè)有一稀疏圖G，則G采用_______________存儲(chǔ)較省空間。
13．如果無向圖G有n個(gè)頂點(diǎn)，那么G的一棵生成樹有且僅有 條邊。
14．如果無向圖G有n個(gè)頂點(diǎn)、e條邊且用鄰接矩陣進(jìn)行存儲(chǔ)，那么深度優(yōu)先遍歷圖G的時(shí)間復(fù)雜度為 。
15．假定對線性表（38，25，74，52，48）進(jìn)行散列存儲(chǔ)，采用H（K）=K%7作為散列函數(shù)，若分別采用線性探測法和鏈接法處理沖突，則對各自散列表進(jìn)行查找的平均查找長度分別為____和______。
16．在待排序的元素序列基本有序的前提下，效率最高的排序方法是___________。
17．對于一個(gè)具有n個(gè)結(jié)點(diǎn)的序列，如果采用插入排序,所須的最大比較次數(shù)是______?
所須的最大移動(dòng)次數(shù)是______?
18．設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用________排序法。
19．對于一個(gè)具有n個(gè)元素序列如果采用快速排序,那么所須的最少比較次數(shù)是_______;所須的最大比較次數(shù)是_______且此序列為 序列。
20．將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是 ，最多的比較次數(shù)是 。
n 填空題答案：
1. 時(shí)間復(fù)雜度、空間復(fù)雜度 2.abcd+/f′+
3. 隊(duì)空條件front==rear;隊(duì)滿條件front==（rear+1）%M
4. 上三角的地址公式loc(a[i][j])=loc(a[0][0])+(((2n-i+1)*i/2+(j-i))×L 注意0≤i,j≤9,所以a[6][7]的地址為2138
5. 表頭是(a,b)，表尾是 ((c)) 6. 10,4,3
7. m叉樹中的葉子數(shù)=1+ 所以有6個(gè)葉子
8. 最小深度 =5 最大深度是18 9. 2n, n-1, n+1
10. 畫出二叉樹后得gdbaehfca
11. 完全二叉樹的葉結(jié)點(diǎn)數(shù)= n為結(jié)點(diǎn)數(shù)，所以有25個(gè)葉結(jié)點(diǎn)
12. 鄰接表 13. n-1條邊
14. ○（n2） 15. 2 , 1.2
16.插入排序和冒泡排序 17.(n+2)(n-1)/2 , (n+4)(n-1)/2
18.堆排序 19.nlog2n ,n(n-1)/2, 有序
20．當(dāng)一個(gè)有序表的元素都比另一有序表的元素都?。ɑ蚨即螅r(shí)比較次數(shù)最少為n。最多比較次數(shù)為2n-1。
（三）簡答題
1．簡述順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)
答：順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)無需為表示元素間的邏輯關(guān)系而增加額外的指針空間；可以隨機(jī)存取表中的任一元素。缺點(diǎn)是必須事先進(jìn)行空間分配，表的容量難以擴(kuò)充；插入和刪除操作時(shí)需移動(dòng)大量結(jié)點(diǎn)，效率較低。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)點(diǎn)的存儲(chǔ)采用動(dòng)態(tài)存儲(chǔ)，表的容量很容易擴(kuò)充；插入和刪除操作方便，不必移動(dòng)結(jié)點(diǎn)，只要修改結(jié)點(diǎn)中的指針即可。缺點(diǎn)是每個(gè)結(jié)點(diǎn)中需要有指針空間，比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小；只能進(jìn)行順序查找結(jié)點(diǎn)。
2．鏈表中為何要引入頭結(jié)點(diǎn)？
答：鏈表進(jìn)行插入和刪除操作時(shí)要判斷是否在鏈表的首端操作，若在第一結(jié)點(diǎn)前插入新結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)則會(huì)引起首指針head值的改變；否則head的值不會(huì)改變。在鏈表前加一個(gè)頭結(jié)點(diǎn)（只用指針域指向鏈表的首結(jié)點(diǎn)）就避免了兩種情況的判斷，使程序設(shè)計(jì)簡單了，程序的結(jié)構(gòu)更清楚。
2． 簡述由二叉樹的前序、中序和后序遍歷序列確定二叉樹
答：在三種遍歷序列中，前序序列和中序序列、中序序列和后序序列能唯一確定一棵二叉樹，因?yàn)榍靶蛐蛄谢蚝笮蛐蛄心艽_定二叉樹的根結(jié)點(diǎn)而中序序列能確定根的左、右子樹。前序序列和后序序列不能唯一確定一棵二叉樹，但注意樹的先根序列和后根序列能唯一的確定該樹，因?yàn)闃涞暮蟾蛄芯褪嵌鏄涞闹行蛐蛄小?div style="height:15px;">
答：當(dāng)待排序的序列為有序序列時(shí)快速排序的效率很低，蛻變?yōu)槊芭菖判蛄?，為了避免這種情況，選序列的首元素為樞軸元素（或稱基準(zhǔn)元素）改為選序列的首元素、中間元素和末元素三個(gè)元素中中間大的元素為基準(zhǔn)元素（簡單的就用中間元素為基準(zhǔn)），這可大大改善快速排序的性能。例如：
