數(shù)據(jù)結(jié)構(gòu)-期末復(fù)習(xí)

數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)主要知識(shí)點(diǎn)算法的時(shí)間復(fù)雜度計(jì)算方法單鏈表堆棧和隊(duì)列的概念和應(yīng)用串的概念和應(yīng)用樹的概念和應(yīng)用圖的概念和應(yīng)用查找和排序數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第1頁。算法滿足以下性質(zhì):

(1)輸入性(2)輸出性(3)有限性

(4)確定性(5)可執(zhí)行性算法設(shè)計(jì)滿足以下目標(biāo):

(1)正確性(2)可讀性(3)健壯性

(4)高時(shí)間效率(5)高空間效率算法的時(shí)間復(fù)雜度計(jì)算方法數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第2頁。常見的時(shí)間復(fù)雜度表示：O(1)，O(n)，O(n2)，O(n3)，O(lbn)，O(lgn)算法時(shí)間復(fù)雜度定義:T(n)=O(f(n)),當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對(duì)所有的n(n≥n0)滿足T(n)≤c×f(n)。T（n）為算法的基本語句執(zhí)行次數(shù)，稱為時(shí)間復(fù)雜度，隨n增大與f（n）增長(zhǎng)接近相同，級(jí)，用O(f（n）)表示其復(fù)雜度即可稱同一個(gè)數(shù)量。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第3頁。推導(dǎo)大O階的方法:(1)用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。(2)在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。(3)如果最高階項(xiàng)在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)最后得到的結(jié)果就是大O階數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第4頁。例1求和算法，求1+2+3………..+99+100=5050。inti,sum=0,n=100;//執(zhí)行了1次for(i=1;i<=n;i++)//執(zhí)行n+1次{sum=sum+i;//執(zhí)行n次}printf(“%d”,sum);//執(zhí)行了1次

該算法一共執(zhí)行了1+n+1+n+1=2n+3次在求時(shí)間復(fù)雜度的時(shí)候我們忽略頭尾循環(huán)判斷的開銷，只需要分析影響一個(gè)算法時(shí)間復(fù)雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時(shí)間復(fù)雜度為

T(n)=O(n)稱為線性階注意：分析這類算法的復(fù)雜度關(guān)鍵是分析循環(huán)結(jié)構(gòu)的運(yùn)行情況數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第5頁。例2求和算法，求1+2+3………..+99+100=5050。intsum=0,n=100;//執(zhí)行了1次sum=(1+n)*n/2//執(zhí)行1次printf(“%d”,sum);//執(zhí)行了1次

該算法一共執(zhí)行了1+1+1=3次在求時(shí)間復(fù)雜度的時(shí)候只需要分析影響一個(gè)算法時(shí)間復(fù)雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時(shí)間復(fù)雜度為

T(n)=O(1)稱為常數(shù)階注意：不管這個(gè)常數(shù)是多少，我們都記做O(1)，而不是O(3)。

數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第6頁。例3求和算法，求1+2+3………..+99+100+…….=inti,j,x=0,sum=0,n=100;//執(zhí)行了1次for(i=1;i<=n;i++){for(j=1;j<=n;j++){x++;//執(zhí)行n*n次sum=sum+x;}}printf(“%d”,sum);//執(zhí)行了1次

在求時(shí)間復(fù)雜度的時(shí)候我們忽略頭尾循環(huán)判斷的開銷，只需要分析影響一個(gè)算法時(shí)間復(fù)雜度的主要部分即可，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)：該算法的時(shí)間復(fù)雜度為

T(n)=O(n2)稱為平方階注意：循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)的次數(shù)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第7頁。例1-3設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個(gè)n階矩陣相乘運(yùn)算算法的時(shí)間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本語句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本語句2}該算法的時(shí)間復(fù)雜度為

T(n)=O(n3)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第8頁。

例1-4設(shè)n為如下算法處理的數(shù)據(jù)個(gè)數(shù)，求如下算法的時(shí)間復(fù)雜度。

for(i=1;i<=n;i=2*i)printf(“i=%d\n”，i)；解:設(shè)基本語句的執(zhí)行次數(shù)為T(n),有2T(n)≤n,即有T(n)≤lbn。所以該算法的時(shí)間復(fù)雜度為T(n)=O(lbn)。稱為對(duì)數(shù)階數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第9頁。例1-5:下邊的算法是用冒泡排序法對(duì)數(shù)字a中的n個(gè)整數(shù)類型的數(shù)據(jù)元素(a[0]~a[n-1])，從小到大進(jìn)行排序，求該算法的時(shí)間復(fù)雜度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第10頁。解:該算法基本語句執(zhí)行次數(shù)與原始數(shù)據(jù)序列大小情況有關(guān)系，此時(shí)，按最壞情況統(tǒng)計(jì)。設(shè)基本語句的執(zhí)行次數(shù)為T(n),最壞情況下有

T(n)≈n+4*n2/2因 T(n)≈n+2*n2≤c*

n2,其中c為常數(shù)，所以該算法的時(shí)間復(fù)雜度為

T(n)=O(n2)。

算法的時(shí)間復(fù)雜度是衡量一個(gè)算法好壞的重要指標(biāo)。一般來說，具有多項(xiàng)式時(shí)間復(fù)雜度的算法，是可接受、可實(shí)際使用的算法;具有指數(shù)時(shí)間復(fù)雜度的算法，是只有當(dāng)n足夠小時(shí)才可使用的算法。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第11頁。例1-6下面的算法是在一個(gè)有n個(gè)數(shù)據(jù)元素的數(shù)組a中刪除第i個(gè)位置的數(shù)組元素，要求當(dāng)刪除成功時(shí)數(shù)組元素個(gè)數(shù)減1，求該算法的時(shí)間復(fù)雜度。其中數(shù)組下標(biāo)從0至n-1。intDelete(inta[],int&n,inti){intj;if(i<0||i>=n)return0;//刪除位置錯(cuò)誤，失敗返回for(j=i+1;j<n;j++)a[j-1]=a[j];//順次移位填補(bǔ)n--;//數(shù)組元素個(gè)數(shù)減1return1;//刪除成功返回}數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第12頁。解:該算法與要?jiǎng)h除元素位置i有關(guān)，此時(shí)一般按i所有取值情況下的平均執(zhí)行次數(shù)來統(tǒng)計(jì)。假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的,設(shè)Pi為刪除第i個(gè)位置上數(shù)據(jù)元素的概率，則有Pi=1/n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有因T(n)=E≤(n+1)/2≤

c*n,其中c為常數(shù)，所以該算法的等概率平均時(shí)間復(fù)雜度為

T(n)=O(n)。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第13頁。插入效率：刪除效率：順序表操作的效率分析數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第14頁。單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動(dòng)數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個(gè)數(shù)操作的時(shí)間復(fù)雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第15頁。1、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。

A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)。

B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)。C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。

2、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（）。A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

B.數(shù)據(jù)結(jié)構(gòu)。

C.數(shù)據(jù)的邏輯結(jié)構(gòu)。D.數(shù)據(jù)元素之間的關(guān)系。CA習(xí)題練習(xí)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第16頁。3、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的

（）結(jié)構(gòu)。A．邏輯

B．存儲(chǔ)C．邏輯和存儲(chǔ) D．物理4、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)（）。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)元素的類型C．?dāng)?shù)據(jù)元素之間的關(guān)系

D．?dāng)?shù)據(jù)的存儲(chǔ)方法5、在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮（）。A．各結(jié)點(diǎn)的值如何。

B．結(jié)點(diǎn)個(gè)數(shù)的多少。C．對(duì)數(shù)據(jù)有哪些運(yùn)算。

D．所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。ACA數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第17頁。6、算法分析的目的是（），算法分析的兩個(gè)主要方面是（）。（1） A．找出數(shù)據(jù)結(jié)構(gòu)的合理性。

B．研究算法中的輸入和輸出的關(guān)系。

C．分析算法的效率以求改進(jìn)。

D．分析算法的易讀性和文檔性。（2） A．空間復(fù)雜度和時(shí)間復(fù)雜度。

B．正確性和簡(jiǎn)明性。

C．可讀性和文檔性。

D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性。CA數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第18頁。7、下面程序段的時(shí)間復(fù)雜度是

。

s＝0；

for（i＝0；i＜n；i＋＋）

for（j＝0；j＜n；j＋＋）

s＋＝B[i][j]；

sum＝s；8、下面程序段的時(shí)間復(fù)雜度是

。

for（i＝0；i＜n；i＋＋）

for（j＝0；j＜m；j＋＋）

A[i][j]＝0；9、下面程序段的時(shí)間復(fù)雜度是

。

i＝0；

while（i＜＝n）

i＝i*2；O（n2）O（n*m）

O（log2n）數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第19頁。pa0a1an-1∧…h(huán)eaddatanextx∧s(a)插入前pa0a1an-1∧…h(huán)eaddatanextx∧s(b)插入后1).在帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較核心操作語句為：p=head；s->next=p->next;p->next=s;注：兩條語句順序不能顛倒，即“先勾右鏈，再勾左鏈”單鏈表數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第20頁。2).刪除帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)pa0a1an-1∧…h(huán)eaddatanext核心操作語句為：p=head；s=p->next;*x=s->datap->next=p->next->next;free(s);數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第21頁。3).在不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)a0a1an-1∧…h(huán)eadx∧s(a)插入前a0a1an-1∧…h(huán)eadxs(b)插入后核心操作語句為：s->next=head;head=s;數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第22頁。4).在不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素前插入結(jié)點(diǎn)pai-1a0aian-1∧…h(huán)eaddatanextxs…×核心操作語句為：s->next=p->next;p->next=s;數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第23頁。5).刪除不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)a0a1an-1∧…h(huán)eaddatanext×6).刪除不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素結(jié)點(diǎn)pai-1a0aian-1∧…h(huán)eaddatanext…×ai+1核心操作語句為：s=head->next;head=head->next;free(s);核心操作語句為：s=p->next;*x=s->datap->next=p->next->next;free(s);數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第24頁。1、在帶頭結(jié)點(diǎn)的單鏈表head中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行的核心代碼是（

）。s->next=p；p->next=s；

s->next=p->next；p->next=s；C.s->next=p->next；p=s；

D.p->next=s；s->next=p；2、在帶頭結(jié)點(diǎn)的單鏈表head中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的核心代碼是（

）。p->next=p->next->next；

p=p->next；p->next=p->next->next；C.p->next=p->next；

D.p=p->next->next；習(xí)題練習(xí)BA數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第25頁。4、單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了（

）。使單鏈表至少有一個(gè)結(jié)點(diǎn)。

標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置。C.方便運(yùn)算的實(shí)現(xiàn)。

D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)。5、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（

）。A.head==NULL B.head->Next==NULL

C.head->next==head D.head!=NULLCB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第26頁。6、已知head為帶頭結(jié)點(diǎn)的單鏈表，p為其中非首元的結(jié)點(diǎn)，分別寫出以下操作的序列：（1）將s結(jié)點(diǎn)插入p結(jié)點(diǎn)之后；（2）刪除p的直接后繼結(jié)點(diǎn)；（3）刪除尾元結(jié)點(diǎn)；s->Next=p->Next;p->Next=s;q=p->Next;p->Next=p->Next->Next;free(q);p=head;While(p->Next->Next!=NULL)p=p->Next;q=p->Next;p->Next=p->Next->Next;free(q);數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第27頁。堆棧和隊(duì)列的基本概念和應(yīng)用堆棧的數(shù)據(jù)元素及邏輯關(guān)系與線性表完全相同，但是操作受限。(1)定義:限定只能在固定一端進(jìn)行插入和刪除操作的線性表。特點(diǎn)：后進(jìn)先出。故又稱后進(jìn)先出表(2)允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。隊(duì)列的基本概念堆棧的基本概念(1)定義:只能在表的一端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作的線性表（又稱先進(jìn)先出表）。一個(gè)隊(duì)列的示意圖如下：a0a1a2…an-1隊(duì)頭隊(duì)尾隊(duì)尾插入隊(duì)頭刪除數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第28頁。1、有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）。543612 B.453126C.346521 D.2341562、一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.23415B.54132C.23145D.154323、

某堆棧的輸入序列為a,b，c，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（）。a，c，b，d B.b,c，d，aC.c，d，b，a D.d,c，a，b習(xí)題練習(xí)CBD數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第29頁。5、棧和隊(duì)列的共同點(diǎn)是（）。A．都是先進(jìn)后出。

B．都是先進(jìn)先出。C．只允許在端點(diǎn)處插入和刪除元素。

D．沒有共同點(diǎn)。6、以下（）不是隊(duì)列的基本運(yùn)算?A．從隊(duì)尾插入一個(gè)新元素。

B．從隊(duì)列中刪除第i個(gè)元素。C．判斷一個(gè)隊(duì)列是否為空。

D．讀取隊(duì)頭元素的值。CB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第30頁。7、順序循環(huán)隊(duì)列中判定隊(duì)列滿的條件為（

）。

A.rear==front B.count>0C.count>0&&rear==front

D.count>0||rear==front8、順序循環(huán)隊(duì)列中判定隊(duì)列空的條件為（

）。

A.rear==front B.count==0C.count>0&&rear==frontD.count>0||rear==frontCB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第31頁。9、輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為（）。A．push，pop，push，pop，push，pop

B．push，push，push，pop，pop，popC．push，push，pop，pop，push，pop

D．push，pop，push，push，pop，pop10、允許對(duì)隊(duì)列進(jìn)行的操作有（）。A．對(duì)隊(duì)列中的元素排序B．取出最近進(jìn)隊(duì)的元素C．在隊(duì)頭元素之前插入元素D．刪除隊(duì)頭元素11、對(duì)于循環(huán)隊(duì)列（）。A．無法判斷隊(duì)列是否為空B．無法判斷隊(duì)列是否為滿C．隊(duì)列不可能滿D．以上說法都不對(duì)BDD數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第32頁。12、若用一個(gè)大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。A．1和5

B．2和4

C．4和2

D．5和113、隊(duì)列的“先進(jìn)先出”特性是指（）。A．最早插入隊(duì)列中的元素總是最后被刪除。B．當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先。C．每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作。D．每次從隊(duì)列中刪除的總是最早插入的元素。DB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第33頁。１、串（又稱字符串）是由n(n≥0)個(gè)字符組成的有限序列。（它是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。）２、串長(zhǎng):串中字符的個(gè)數(shù)（n≥0）。３、空串:串中字符的個(gè)數(shù)為0時(shí)稱為空串。４、空格串:由一個(gè)或多個(gè)空格符組成的串。５、子串:串S中任意個(gè)連續(xù)的字符序列叫S的子串;S叫主串。６、子串位置:子串的第一個(gè)字符在主串中的序號(hào)(從0開始)。７、字符位置:字符在串中的序號(hào)(從0開始)。８、串相等:串長(zhǎng)度相等，且對(duì)應(yīng)位置上字符相等。（即兩個(gè)串中的字符序列一一對(duì)應(yīng)相等。）串的基本概念和應(yīng)用數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第34頁。35

1、現(xiàn)有以下4個(gè)字符串：a=“BEI” b=“JING”c=“BEIJING”d=“BEIJING”①他們各自的長(zhǎng)度？答：a是c和d的子串，在c和d中的位置都是0。②a是哪個(gè)串的子串？在主串中的位置是多少？答：a：3，b：4，c：7，d：8。③空串是哪個(gè)串的子串？a是不是自己的子串？答：空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。。子串個(gè)數(shù)問題？如：串S=“produce”，則S共多少個(gè)子串？長(zhǎng)為2,3的子串分別多少個(gè)？習(xí)題練習(xí)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第35頁。2、設(shè)S1=“DataStructureCourse”,S2=“Structure”,S3=“Base”，求（1）Length(S1);（2）Compare(S2,S3)；（3）Insert(S1,5,S3)；（4）Delete(S1,5,9);（5）SubString(S1,5,9,T)；（6）Search(S1,0,S2);（7）Replace(S1,0,S2,S3);36Length(S1)=21。返回值為1。輸出“DataBaseStructureCourse”。輸出“DataCourse”。輸出T=“Structure”。返回值為5。輸出“DataBaseCourse”。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第36頁。3、串的長(zhǎng)度是指（）。A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)4、串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符BB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第37頁。若干術(shù)語（要求:理解、認(rèn)識(shí)這些術(shù)語）ABCGEIDHFJFLK結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)(也可稱分支數(shù))。葉結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)，也稱作終端結(jié)點(diǎn)。

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，一棵樹中除葉結(jié)點(diǎn)外的所有結(jié)點(diǎn)都是分支結(jié)點(diǎn)。樹的基本概念和應(yīng)用數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第38頁。孩子結(jié)點(diǎn)：樹中某個(gè)結(jié)點(diǎn)的所有子樹的根結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙親結(jié)點(diǎn)：若樹中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個(gè)結(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)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)，根的層次為0，其它為雙親層次加1。樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第39頁。無序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的不要求區(qū)分次序，即左右顛倒后還是同一棵樹；（本章的“樹”）。

有序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹（本章的“二叉樹”）。森林：m（m≥0）棵樹的集合。二叉樹基本特點(diǎn)：①每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）；②左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹。二叉樹形態(tài)：二叉樹的所有結(jié)點(diǎn)的形態(tài)有五種：空、無左右子樹、只有左子樹、只有右子樹、左右子樹均存在。（形態(tài)只看形狀，不看具體結(jié)點(diǎn)元素值）分析：只有三個(gè)結(jié)點(diǎn)（假設(shè)分別為A,B,C）的二叉樹形態(tài)共有哪些情況？數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第40頁。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹稱為滿二叉樹。（所有的存在的層次上結(jié)點(diǎn)都滿）完全二叉樹：如果一棵深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)能夠與深度為k的順序編號(hào)的滿二叉樹從1到n標(biāo)號(hào)的結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹稱為完全二叉樹。（相對(duì)于深度相同

的滿二叉樹來說完全二叉樹只可能最后一層缺少最后面連

續(xù)的結(jié)點(diǎn)）如下圖所示滿二叉樹也是一棵特殊的完全二叉樹。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第41頁。BACEDFGHIJKLMNO(a)滿二叉樹BACEDFGHIJ(b)完全二叉樹問題:一個(gè)深度為h的完全二叉樹最多有多少個(gè)結(jié)點(diǎn)?最少有多少個(gè)結(jié)點(diǎn)?根結(jié)點(diǎn)深度為0。最多2(h+1)-1個(gè)，最少2h個(gè)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第42頁。二叉樹的性質(zhì)性質(zhì)1在一棵非空二叉樹的第i層上至多有2i個(gè)結(jié)點(diǎn)（i≥0）。（理解、記結(jié)論）性質(zhì)2深度為k的二叉樹至多有2k+1-1個(gè)結(jié)點(diǎn)。說明：深度k=-1，表示空二叉樹，沒有一個(gè)結(jié)點(diǎn)；深度k=0，表示只有一個(gè)根結(jié)點(diǎn)。（理解、記結(jié)論）性質(zhì)3具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為大于或等于lb(n+1)-1的最小整數(shù)。（要求會(huì)根據(jù)結(jié)點(diǎn)數(shù)求深度）如：20個(gè)結(jié)點(diǎn)的完全二叉樹深度為？答：2k-1<n<=2k+1-1，k=4數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第43頁。哈夫曼樹的基本概念

從A結(jié)點(diǎn)到B結(jié)點(diǎn)所經(jīng)過的分支序列叫做從A結(jié)點(diǎn)到B結(jié)點(diǎn)的路徑；從A結(jié)點(diǎn)到B結(jié)點(diǎn)所經(jīng)過的分支個(gè)數(shù)叫做從A結(jié)點(diǎn)到B結(jié)點(diǎn)的路徑長(zhǎng)度；從二叉樹的根結(jié)點(diǎn)到二叉樹中所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和稱作該二叉樹的路徑長(zhǎng)度。設(shè)二叉樹有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，定義從二叉樹的根結(jié)點(diǎn)到二叉樹中所有葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉結(jié)點(diǎn)權(quán)值的乘積之和稱作該二叉樹的帶權(quán)路徑長(zhǎng)度（WPL），即：WPL=

其中，wi為第i個(gè)葉結(jié)點(diǎn)的權(quán)值，li為從根結(jié)點(diǎn)到第i個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第44頁。1、已知一棵樹T=(D,R),D={A,B,C,D,E,F,G,H,I,J,K,L,M,N}；R={<I,M>,<I,N>,<E,I>,<B,E>,<B,D>，<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>}請(qǐng)畫出這棵樹，并回答以下問題：(1)哪個(gè)是根結(jié)點(diǎn)？

(2)哪些是葉子結(jié)點(diǎn)？(3)哪個(gè)是結(jié)點(diǎn)G的雙親？

(4)哪些是結(jié)點(diǎn)E的孩子？(5)哪些是E的兄弟？

習(xí)題練習(xí)數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第45頁。(6)哪些是F的兄弟？(7)結(jié)點(diǎn)N的層次是多少？(8)以結(jié)點(diǎn)C為根的子樹的深度是多少？

(9)該樹的深度是多少？

(10)該樹的度是多少？數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第46頁。2、某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為（）。A．3

B．2

C．4

D．53、對(duì)某二叉樹進(jìn)行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（

）。DBFEAC B.DFEBCA

C.BDFECA D.BDEFACCB數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第47頁。4、設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（

）。a在b的右方 B.a在b的左方

C.a是b的祖先 D.a是b的子孫5、若以{4,5,6,7,8}作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長(zhǎng)度為（）。A.67

B.68 C.69 D.70BC數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第48頁。6、樹最適合用來表示（）。有序數(shù)據(jù)元素。 無序數(shù)據(jù)元素。 C.元素之間具有分支層次關(guān)系的數(shù)據(jù)。

D.元素之間無聯(lián)系的數(shù)據(jù)。7、假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。C數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第49頁。8、已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。9、已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。畫出二叉樹的形態(tài)。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第50頁。10、設(shè)有如下圖所示的樹，要求：（1）將其轉(zhuǎn)換為二叉樹；（2）分別寫出該樹的先根遍歷序列和后根遍歷序列；（3）分別寫出轉(zhuǎn)換后的二叉樹的前序、中序以及后序遍歷序列。ABCDEFGHIJK數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第51頁。（1）完全圖：在有n個(gè)頂點(diǎn)的無向圖中，若有n(n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且只有一條邊，則稱此圖為無向完全圖；在有n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖。（2）鄰接結(jié)點(diǎn)：在無向圖G中，若（u,v）是E(G)中的一條邊，則稱u和v互為鄰接結(jié)點(diǎn)，并稱邊（u,v）依附于結(jié)點(diǎn)u和v；在有向圖G中，若＜u,v＞是E(G)中的一條邊，則稱結(jié)點(diǎn)u鄰接到結(jié)點(diǎn)v，結(jié)點(diǎn)v鄰接自結(jié)點(diǎn)u，并稱邊＜u,v＞和結(jié)點(diǎn)u和結(jié)點(diǎn)v相關(guān)聯(lián)。

圖的基本概念和應(yīng)用數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第52頁。（3）結(jié)點(diǎn)的度：結(jié)點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作TD(v)。有向圖中：結(jié)點(diǎn)的度=入度+出度。

即TD(v)=ID(v)+OD(v)思考：在無向圖中，所有頂點(diǎn)度的和是圖中邊數(shù)有何關(guān)系？答：所有頂點(diǎn)度的和是圖中邊數(shù)的2倍。有向圖中：所有出度和=入度和=邊總數(shù)（4）連通圖和強(qiáng)連通圖：在無向圖中，若從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj有路徑，則稱結(jié)點(diǎn)vi和結(jié)點(diǎn)vj是連通的。如果圖中任意一對(duì)結(jié)點(diǎn)都是連通的，則稱該圖是連通圖。在有向圖中，若對(duì)于任意一對(duì)結(jié)點(diǎn)vi和結(jié)點(diǎn)vj（vi≠vj）都存在路徑，則稱圖G是強(qiáng)連通圖。（5）最小連通子圖：G1包含G的全部結(jié)點(diǎn)，但只有G中足夠構(gòu)成連通圖的最少數(shù)目的邊，則G1稱為G的最小連通子圖數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第53頁。（6）生成樹：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹。有n個(gè)結(jié)點(diǎn)的連通圖的生成樹有n個(gè)結(jié)點(diǎn)和n-1條邊。

生成樹一般是對(duì)無向圖來討論。一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個(gè)頂點(diǎn)，并且有保持圖連通的最少的邊。若在生成樹中刪除一條邊就會(huì)使該生成樹因變成非連通圖而不再滿足生成樹的定義；若在生成樹中增加一條邊就會(huì)使該生成樹中因存在回路而不再滿足生成樹的定義；一個(gè)連通圖的生成樹可能有許多；有n個(gè)頂點(diǎn)的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)全文共65頁，當(dāng)前為第54頁。1、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。A．先序遍歷

B．中序遍歷C．后序遍歷 D．按層遍歷2、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A．先序遍歷 B．中序遍歷