數據結構復習指導教學課件

數據結構復習指導數據結構復習指導數據結構復習指導數據結構復習指導第1章緒論掌握內容：基本術語：數據、數據元素、數據對象、數據結構、抽象數據類型、順序存儲結構和鏈式存儲結構。算法：5個特性、時間復雜度和空間復雜度的含義與估算。時間復雜度O(n)表示隨著數據規(guī)模n的不斷增長，算法執(zhí)行時間將以線性的速度增長。時間復雜度：O(n)、O(nlogn)、O(n2)抽象數據類型與數據結構的定義區(qū)別在于

。

數據的邏輯結構是從邏輯關系上描述數據，它與數據的

無關，是獨立于計算機的。().TheRunningTimeofthefollowingprogramfragmentis

O(n3)

.Sum=0;for(inti=0;i<N;i++)for(j=0;j<i;j++){Sum++;}for(i=0;i<N;i++)for(j=0;j<N*N;j++){A[i][j]=i*j;}(1).Arrangethefollowingorderexpressions,2N,100N,logN,10,N1/2,N2,N4,NlogN,bygrowthratefromslowesttofastest:

10<logN<N1/2<100N<NlogN<N2<N4<2N(2).Foreachofthefollowingpairsoffunctions,(B)satisfiestherelationshipf(n)=Q(g(n)): (A)f(n)=2n*logn,g(n)=logn+10n

(B)f(n)=6logn2,g(n)=logn+5 (C)f(n)＝log2n,g(n)=100logn

(D)f(n)=4n, g(n)=5n第2章線性表知道線性表定義、各基本操作的含義存儲形式：順序存儲結構與鏈式存儲結構順序存儲結構的特點：1.邏輯結構與物理結構一致；2.屬于隨機存取方式缺點：插入、刪除元素需要移動，平均約一半的元素鏈式存儲結構的特點：1.邏輯結構與物理結構不一致；2.屬于順序存取方式順序表和有序表順序表：線性表采用順序存儲結構表示有序表：內容按從小到大排列的線性表算法：在有序表中插入一個元素使其仍有序在給定位置插入一個元素注意：不要采用書上使用指針確定元素位置的方式，而用下標形式，可提高可讀性。鏈表不特殊說明，均帶頭結點算法：在有序鏈表中插入一個結點，使其仍保持有序給定元素位置，插入或刪除相應結點正序或逆序創(chuàng)建鏈表注意：*對循環(huán)鏈表操作時，尾部的判斷

*雙向鏈表的插入、刪除結點

*刪除結點一定要釋放空間在頭指針為head且表長大于1的單鏈表中，指針p指向表中某個結點，若p->next->next=head，則正確的說法是（）。A.p指向頭結點B.p指向尾結點C.*p的直接后繼是頭結點D.*p的直接后繼是尾結點有序的順序表與無序的順序表相比，其操作優(yōu)勢是（）。A.刪除快B.插入快C.生成快 D.查找快在長度為n的順序表中第i個元素(1in)之前插入元素時，需向后移動元素個數是

。sps->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

pp->prior->next=p->next;p->next->prior=p->prior;deletep;(1).Insinglylinkedlisteachnodehasapointer

nextpointingtothenextlinknode.Nowwewanttoremovethenodeafterthenodepointedtobypointerxfromthelist,theremovednodebepointedtobypointerp,whichofoperationsequencesbelowiscorrect(A) (A)p=x->next;x->next=x->next->next;deletep; (B)p=x->next;x=x->next;deletep; (C)p=x->next;x=x->next->next;deletep; (D)p=x->next;x->next=x;deletep;第3章棧和隊列棧和隊列的定義，操作特點棧的應用：*會寫出遞歸執(zhí)行過程*深度（縱向）遍歷*正、反向操作*表達式、背包隊列：按層遍歷注意：順序隊列都應該使用循環(huán)隊列。

棧的典型題判回文、表達式括號配對情況假設入棧順序為1234，則下列不可能出現(xiàn)的出棧序列為：

4321342112343412僅允許在同一端進行插入刪除的線性表稱為

。設元素15，25，35和45入隊，然后三個元素出隊，此時留在隊列里的元素是

。若已知一個棧的入棧序列是1,2,…,n.其出棧序列為p1,p2,…,pn(表示1,2,…,n的一個排列)。若p1=n，則pi為（）。A.iB.n-iC.n-i+1D.不確定第4章樹與二叉樹基本概念樹與森林：定義、存儲結構（雙親、孩子鏈表、孩子兄弟）二叉樹：定義、性質、存儲結構、遍歷、完全二叉樹樹、森林與二叉樹之間的關系，相互轉換構造赫夫曼樹與算法有關的典型例題給定一棵二叉樹的先序和中序（后序和中序）遍歷序列，構造對應的二叉樹通過二叉樹，獲得對應的樹的相關信息按層遍歷二叉樹/樹利用某種遍歷序列，對二叉樹進行某種操作三序遍歷的遞歸算法在一棵度為3的樹中，度為3的結點個數為2，度為2的結點個數為1，則度為0的結點個數為()。A.4B.5 C.6 D.7已知一棵完全二叉樹中共有768個結點，則該樹中共有384個葉子結點。在一棵高度為h的滿三叉樹中，結點的總數是多少？寫出計算的步驟和結果。答：30+31+32+...+3h-1=3h-1由五個分別帶權值為9，2，5，7，14的葉子結點構成哈夫曼樹，寫出該樹的帶權路徑長度并示明計算的步驟。已知樹T的先根序列為ABCDEFGHIJKL，后根遍歷序列為CBFGEHDKJLIA，請畫出樹T。設高度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為（）。

A.2h B.2h-1C.2h+1 D.h+1

設a、b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的條件是（）。

A.a在b右方B.a是b的祖先

C.a在b左方D.a是b的子孫假設通訊電文使用的字符集為{a，b，c，d，e，f}，各字符在電文中出現(xiàn)的頻率分別為：0.34，0.05，0.12，0.23，0.08和0.18，試為該字符集設計Huffman編碼，并計算對應Huffman樹的帶權路徑長WPL（要求樹中左孩子結點的權值小于右孩子結點的權值，且左分支以0編碼，右分支以1編碼）。Huffman樹：該樹的帶權路徑長度WPL=對于給定的正整數x，設計一遞歸算法，在由正整數為結點數據域值的一棵二叉排序樹中，找出最接近且又小于x的值（要求：寫明算法思想，語句加注釋，畫出你跟蹤算法的數據模型。數據類型按常規(guī)定義，無須另加說明）。voidsearch(BiTreeT,intx,int&pre){if(T){search(T->lchild,x,pre);if(T->data<x){pre=T->data;search(T->rchild,x,pre);}}}(4).Ifweuseaseriesofnumbers:40,30,50,20,60,10,80,70tobuiltaBinarySearchTree，thentheresultofthetreeofpostodertraversalis

.10203070806050403.ThePre-ordertraversalofabinarytreeis12345678,andtheIn-orderenumerationis24351687.(1)Drawthisbinarytree(2)WhatisthePost-orderenumerationofthetree?:453287614.BuildtheHuffmancodingtreeforthefollowingsetoflettersandweights:A D M C E X P20 10 3 8 14 2 6(1)BuildingtheHuffmancodingtree.(2)Encodethestring“MADE"intoHuffmancodes;(3)DecodetheHuffmancodestream:10000110101Note:WhenbuildingtheHuffmantree,youshouldkeeptheconditionthattheleftsub-treehaslessweight.Andusinga0toindicatetheleftbranchanda1toindicatetherightbranch第5章圖有向圖：弧、入/出度、有向完全圖無向圖：邊、度、無向完全圖存儲結構（鄰接/十字/多重—適用場合）圖遍歷算法（牢記）最小生成樹（算）、拓撲排序（算）、關鍵路徑、一頂點到其余各頂點的最短路徑（按算法手工走給定例子）圖的連通性典型題目深度或廣度優(yōu)先遍歷能夠完成拓撲排序的圖一定是一個

有向無環(huán)圖

。

n個頂點的無向連通圖至少有

n-1條邊。已知一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是

統(tǒng)計第i列中1的數目。設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某頂點vi相關的所有弧的時間復雜度是A.O(n) B.O(e) C.O(n+e) D.O(n*e)在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數為

n*n-2*e。已知一個無向圖的頂點集為{a,b,c,d,e},其鄰接矩陣如下所示：

01001

10010000110110110110(1)畫出該圖的圖形；(2)根據此鄰接矩陣，從頂點b出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應遍歷的頂點序列。

Acompletedirectedgraphofnverticeshas

n*(n-1)

edges.

第6章內部排序插入排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數排序：手工排序每趟過程各種排序方法的適用場合、時間復雜度快速排序、堆排序的算法在下列排序方法中，平均時間性能為O(nlogn)且空間性能最好的是（）。A.快速排序B.堆排序C.歸并排序D.基數排序堆排序在最壞的情況下的時間復雜度是()。A.O(log2n) B.O(log2n2) C.O(nlog2n) D.O(n2)用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進行排序時，如果元素序列前幾趟的變化情況如下：84，47，68，35，15，27，21，25，20（第一趟）68，47，27，35，15，20，21，25，84（第二趟）47，35，27，25，15，20，21，68，84（第三趟）35，25，27，21，15，20，47，68，84（第四趟）則所采用的排序方法是（）。

A.選擇排序 B.堆排序C.歸并排序 D.快速排序對關鍵字序列(72,87,61,23,100,15,7,60)進行堆排，結果應按關鍵字遞減次序排列。請寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。(5).Anarrayhaskeysas（30，20，18，50，25，28,15，40）,thearrayistobesortedbymergesort,afterthefirstroundmerge,theresultingkeyswillb