數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)教學(xué)課件

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)第1章緒論掌握內(nèi)容：基本術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。算法：5個(gè)特性、時(shí)間復(fù)雜度和空間復(fù)雜度的含義與估算。時(shí)間復(fù)雜度O(n)表示隨著數(shù)據(jù)規(guī)模n的不斷增長，算法執(zhí)行時(shí)間將以線性的速度增長。時(shí)間復(fù)雜度：O(n)、O(nlogn)、O(n2)抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的定義區(qū)別在于

。

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的

無關(guān)，是獨(dú)立于計(jì)算機(jī)的。().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章線性表知道線性表定義、各基本操作的含義存儲(chǔ)形式：順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：1.邏輯結(jié)構(gòu)與物理結(jié)構(gòu)一致；2.屬于隨機(jī)存取方式缺點(diǎn)：插入、刪除元素需要移動(dòng)，平均約一半的元素鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：1.邏輯結(jié)構(gòu)與物理結(jié)構(gòu)不一致；2.屬于順序存取方式順序表和有序表順序表：線性表采用順序存儲(chǔ)結(jié)構(gòu)表示有序表：內(nèi)容按從小到大排列的線性表算法：在有序表中插入一個(gè)元素使其仍有序在給定位置插入一個(gè)元素注意：不要采用書上使用指針確定元素位置的方式，而用下標(biāo)形式，可提高可讀性。鏈表不特殊說明，均帶頭結(jié)點(diǎn)算法：在有序鏈表中插入一個(gè)結(jié)點(diǎn)，使其仍保持有序給定元素位置，插入或刪除相應(yīng)結(jié)點(diǎn)正序或逆序創(chuàng)建鏈表注意：*對(duì)循環(huán)鏈表操作時(shí)，尾部的判斷

*雙向鏈表的插入、刪除結(jié)點(diǎn)

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

。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章棧和隊(duì)列棧和隊(duì)列的定義，操作特點(diǎn)棧的應(yīng)用：*會(huì)寫出遞歸執(zhí)行過程*深度（縱向）遍歷*正、反向操作*表達(dá)式、背包隊(duì)列：按層遍歷注意：順序隊(duì)列都應(yīng)該使用循環(huán)隊(duì)列。

棧的典型題判回文、表達(dá)式括號(hào)配對(duì)情況假設(shè)入棧順序?yàn)?234，則下列不可能出現(xiàn)的出棧序列為：

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

。設(shè)元素15，25，35和45入隊(duì)，然后三個(gè)元素出隊(duì)，此時(shí)留在隊(duì)列里的元素是

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

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

設(shè)a、b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是（）。

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

C.a在b左方D.a是b的子孫假設(shè)通訊電文使用的字符集為{a，b，c，d，e，f}，各字符在電文中出現(xiàn)的頻率分別為：0.34，0.05，0.12，0.23，0.08和0.18，試為該字符集設(shè)計(jì)Huffman編碼，并計(jì)算對(duì)應(yīng)Huffman樹的帶權(quán)路徑長WPL（要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值，且左分支以0編碼，右分支以1編碼）。Huffman樹：該樹的帶權(quán)路徑長度WPL=對(duì)于給定的正整數(shù)x，設(shè)計(jì)一遞歸算法，在由正整數(shù)為結(jié)點(diǎn)數(shù)據(jù)域值的一棵二叉排序樹中，找出最接近且又小于x的值（要求：寫明算法思想，語句加注釋，畫出你跟蹤算法的數(shù)據(jù)模型。數(shù)據(jù)類型按常規(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章圖有向圖：弧、入/出度、有向完全圖無向圖：邊、度、無向完全圖存儲(chǔ)結(jié)構(gòu)（鄰接/十字/多重—適用場合）圖遍歷算法（牢記）最小生成樹（算）、拓?fù)渑判颍ㄋ悖㈥P(guān)鍵路徑、一頂點(diǎn)到其余各頂點(diǎn)的最短路徑（按算法手工走給定例子）圖的連通性典型題目深度或廣度優(yōu)先遍歷能夠完成拓?fù)渑判虻膱D一定是一個(gè)

有向無環(huán)圖

。

n個(gè)頂點(diǎn)的無向連通圖至少有

n-1條邊。已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是

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

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

01001

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

Acompletedirectedgraphofnverticeshas

n*(n-1)

edges.

第6章內(nèi)部排序插入排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數(shù)排序：手工排序每趟過程各種排序方法的適用場合、時(shí)間復(fù)雜度快速排序、堆排序的算法在下列排序方法中，平均時(shí)間性能為O(nlogn)且空間性能最好的是（）。A.快速排序B.堆排序C.歸并排序D.基數(shù)排序堆排序在最壞的情況下的時(shí)間復(fù)雜度是()。A.O(log2n) B.O(log2n2) C.O(nlog2n) D.O(n2)用某種排序方法對(duì)線性表(25，84，21，47，15，27，68，35，20)進(jìn)行排序時(shí)，如果元素序列前幾趟的變化情況如下：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.快速排序?qū)﹃P(guān)鍵字序列(72,87,61,23,100,15,7,60)進(jìn)行堆排，結(jié)果應(yīng)按關(guān)鍵字遞減次序排列。請寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。(5).Anarrayhaskeysas（30，20，18，50，25，28,15，40）,thearrayistobesortedbymergesort,afterthefirstroundmerge,theresultingkeyswillb