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

考試時(shí)間：第10周周日(5月7日)

九、十節(jié)18:00~19:40考試教室安排：考試方式：閉卷筆試考試成績＝卷面(80％)＋平時(shí)作業(yè)(20％)考試題型(參考）：1、判斷對錯(cuò)、選擇、填空2、綜合應(yīng)用3、算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)答疑安排：大黑樓A701或A718第十周周三(5月3日)上午9:00～11:30第十周周四(5月4日)下午1:30～4:00第一章緒言基本概念和術(shù)語（掌握）數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)結(jié)構(gòu)邏輯結(jié)構(gòu)與算法分析（掌握）算法定義算法特性：算法評價(jià)：–時(shí)間復(fù)雜度與空間復(fù)雜度第二章

線性表邏輯結(jié)構(gòu)（掌握）

結(jié)構(gòu)（掌握）結(jié)構(gòu)：結(jié)構(gòu)：順序鏈?zhǔn)建C單鏈表–雙向鏈表–循環(huán)鏈表–雙向循環(huán)鏈表–靜態(tài)鏈表（了解）基本操作（掌握）刪除查找應(yīng)用------一元多項(xiàng)式相加（掌握）時(shí)間復(fù)雜度第三章棧和隊(duì)列---操作受限的線性表?xiàng)Ｌ攸c(diǎn)（掌握）：FILO(LIFO)結(jié)構(gòu)（掌握）：順序棧與鏈?；静僮鳎ㄕ莆眨喝霔Ｅc出棧應(yīng)用（掌握）：回文、括號匹配、表達(dá)式求值中綴轉(zhuǎn)后綴隊(duì)列特點(diǎn)（掌握）：FIFO（LILO）結(jié)構(gòu)（掌握）：順序隊(duì)列鏈隊(duì)列循環(huán)隊(duì)列（掌握）基本操作（掌握）入隊(duì)出隊(duì)?wèi)?yīng)用（了解）：迷宮，優(yōu)先隊(duì)列等隊(duì)空、隊(duì)滿條件、元素個(gè)數(shù)、隊(duì)首隊(duì)尾指針第四章數(shù)組線性結(jié)構(gòu)結(jié)構(gòu)順序

結(jié)構(gòu)（掌握）

：次序約定（算法實(shí)現(xiàn)不要求）壓縮

（掌握）對稱矩陣對角矩陣三角矩陣稀疏矩陣算法：求轉(zhuǎn)置矩陣（了解）三元組表行邏輯 的順序表帶行指針向量的單鏈表鏈表第五章樹邏輯結(jié)構(gòu)：按分支關(guān)系定義的層次結(jié)構(gòu)定義（掌握）：深度、度、葉子等滿二叉樹、完全二叉樹二叉樹性質(zhì)（掌握）：5結(jié)構(gòu)樹（掌握）雙親表示法孩子表示法（孩子鏈表與多重鏈表）孩子兄弟表示法（二叉鏈表））二叉樹（掌握順序 結(jié)構(gòu)二叉鏈表三叉鏈表樹、森林與二叉樹轉(zhuǎn)換（掌握）遍歷按層次、先序、中序、后序遍歷遞歸（掌握）與非遞歸算法（了解）遍歷算法應(yīng)用（掌握）?由先序序列建立二叉鏈表?統(tǒng)計(jì)葉子結(jié)點(diǎn)?求二叉樹深度?已知先序和中序、后序和中序、層次和中序，構(gòu)造二叉樹應(yīng)用Huffman樹（掌握）–定義，WPL–構(gòu)造方法–有n個(gè)葉子結(jié)點(diǎn)的Huffman樹共有2n-1個(gè)結(jié)點(diǎn)–應(yīng)用?Huffman編碼與譯碼?最佳判定樹第六章

圖定義（掌握）：圖、有向圖、度、連通、完備圖等結(jié)構(gòu)鄰接矩陣（掌握）鏈表（了解）鄰接多重表（了解）遍歷：深度優(yōu)先與廣度優(yōu)先（掌握遍歷策略及算法）深度優(yōu)先生成樹、廣度度優(yōu)先生成樹鄰接表與逆鄰接表（掌握）

構(gòu)成特點(diǎn)(與頂點(diǎn)度關(guān)系)應(yīng)用（掌握求解過程，不要求寫算法）最小生成樹（Prim與Kruscal）拓?fù)渑判蜃疃搪窂剑―ijkstra）第七章查找靜態(tài)查找表順序查找（掌握）折半查找（掌握）分塊查找（了解）適用條件、比較、ASL動態(tài)查找表（了解）二叉排序樹–定義–構(gòu)造方法–生成、 、刪除與查找–中序遍歷二叉排序樹可得到結(jié)點(diǎn)有序序列判定樹哈希查找（掌握）定義、基本思想Hash函數(shù)構(gòu)造方法處理

方法哈希表構(gòu)造哈希查找過程與ASL第八章排序掌握排序的基本概念和性能分析方法，排序策略排序直接折半排序（掌握）排序（掌握）排序（了解）交換排序冒泡排序（掌握）快速排序（了解）選擇排序簡單選擇排序（掌握）堆排序（掌握，不考算法）歸并排序：2-路歸并排序（了解）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序（了解）排序方法思想每趟排序結(jié)果排序方法性能分析評價(jià)排序穩(wěn)定性本章"了解"的排序方法不要求掌握算法1、 環(huán)問題問題描述：設(shè)有為1，2，3……n的n個(gè)人順時(shí)針方向圍坐一圈，每人有一（正整數(shù)）。開始時(shí)給出一報(bào)數(shù)上限m，從 為1的人開始報(bào)數(shù)，報(bào)m的人出列；以后將出列者的作為新的m，從順時(shí)針方向緊挨著他的下一個(gè)人開始報(bào)數(shù)……直至所有人出列。試編算法，求出出列順序。要求：用不 結(jié)點(diǎn)的單向循環(huán)鏈表實(shí)現(xiàn)從鍵盤輸入n，m各人的 由計(jì)算機(jī)隨機(jī)產(chǎn)生(1~10的正整數(shù)，也可以自己指定)測試數(shù)據(jù)：假設(shè)m的初值為6；n=7，7個(gè)人的 依次是：3,1,7,2,4,8,4則出列的順序?yàn)?

6,1,4,7,2,3,5作業(yè)145964結(jié)構(gòu)ptail需要的變量：k：計(jì)數(shù)p:

指向當(dāng)前結(jié)點(diǎn)pre：指向p的前驅(qū)結(jié)點(diǎn)上機(jī)實(shí)現(xiàn)提示：①編制建立循環(huán)鏈表算法②編制結(jié)點(diǎn)輸出算法(帶輸入?yún)?shù)k)③編制主程序作業(yè)1pre環(huán)(Joseph

Circle)void

CreateCirList(CirList

&T,int

n)值(1~10)，建立帶尾指針的單循環(huán)鏈表T//

法：隨機(jī)產(chǎn)生n個(gè)元素的{ LNode*p,*rear;int

i;intc[

]={3,1,7,2,4,8,4};//srand(ti

LL));for(i=0;i<n;i++){p=(CirList)malloc(sizeof(LNode));p->data.num=i+1;ode=1+rand()%9;ode=c[i];//p->dp->dif(i==0)T=rear=p;else{rear->next=p;rear=p;}}rear->next=T;T=rear;}作業(yè)1void

OutputJSF(CirList

&T,intm){環(huán)出環(huán)順序及各自為:\n");LNode*p,*pre;int

i;printf("\npre=T;p=T->next;while(p->next!=

p)//表非空{(diào) for(i=1;i<m;i++)//報(bào)數(shù){pre=p;p=p->next;ode);}pre->next=p->next;//繞過結(jié)點(diǎn)p

printf("No:%d--Code:%d\n",p->data.num,p->dm=p->d ode;//出環(huán)

作為新的mfree(p);//

pp=pre->next;//p后移}printf("No:%d--Code:%d\n",p->data.num,p->dode);//最后一個(gè)出環(huán)作業(yè)1}2.

請編寫算法實(shí)現(xiàn)：(1)InsertAtHead()：從鍵盤讀入正整數(shù)n,再讀入n個(gè)升序整數(shù)，用頭插法建立帶表頭結(jié)點(diǎn)的降序單鏈表La；(2)InsertAtTail()：從鍵盤讀入正整數(shù)m,再讀入m個(gè)升序整數(shù)，用 法建立帶表頭結(jié)點(diǎn)的升序單鏈表Lb；(3)PrintList()：分別輸出顯示有序單鏈表La和Lb;(4)ReverseList()：將降序單鏈表La就地逆置成升序；

(5)MergeList()：將兩個(gè)升序單鏈表La和Lb合并成升序單鏈表Lc并輸出顯示；(6)

DelOdd()：將有序單鏈表Lc中數(shù)據(jù)域值為奇數(shù)的所有元素刪除，然后輸出顯示作業(yè)1創(chuàng)建結(jié)點(diǎn)單鏈表L13610^8typedef

int

ElemType;typedef

struct

LNode{

ElemType

data;struct

LNode

*next;}LNode,

*LinkList;作業(yè)1void

InsertAtTail(LinkList

&L,int

m,ElemType

b[])//

法:升序輸入m個(gè)元素的值，建立 結(jié)點(diǎn)的單鏈表Lb{LNode*p,*rear;int

i;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;rear=L;for(i=0;i<m;i++){p=(LinkList)malloc(sizeof(LNode));p->data=b[i];rear->next=p;rear=p;}rear->next=NULL;}創(chuàng)建結(jié)點(diǎn)單鏈表L875^2typedef

int

ElemType;typedef

struct

LNode{

ElemType

data;struct

LNode

*next;}LNode,

*LinkList;作業(yè)1void

InsertAtHead(LinkList

&L,int

n,ElemType

a[])//頭插法：升序輸入n個(gè)元素的值，建立 結(jié)點(diǎn)的單鏈表La{LNode*p;int

i;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=0;i<n;i++){p=(LinkList)malloc(sizeof(LNode));p->data=a[i];p->next=L->next;L->next=p;}}//顯示單鏈表中元素void

PrintList(LinkList

L){

LNode

*p;p=L->next;printf("H");while(p){printf("->%d",p->data);p=p->next;}printf("\n\n");}作業(yè)1//單鏈表就地逆置void

ReverseList(LinkList

&L){ LNode

*p,

*q;p=L->next;L->next=NULL;while

(p

!=

NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}作業(yè)1//合并La和Lb,得到Lcvoid

MergeList(LinkList

&La,

LinkList

&Lb,

LinkList

&Lc){ LNode*pa,*pb,*pc;pa=

La->next;pb

=

Lb->next;Lc

=

pc=La;while(

pa

&&

pb){ if(pa->data<=

pb->data){

pc->next

=pa;

pc=

pa;

pa=pa->next;

}else{

pc->next

=

pb;

pc

=pb;

pb=pb->next;

}}pc->next

=

pa?pa:pb;free(Lb);}作業(yè)1//刪除數(shù)據(jù)域值為奇數(shù)的所有元素

void

DelOdd(LinkList

&L){ LNode*p,*pre;pre=L;p=L->next;while(p){

if(p->data%2==1){pre->next=p->next;free(p);p=pre->next;}else{pre=p;p=p->next;}}}作業(yè)1作業(yè)2若進(jìn)棧序列為ABCD，請寫出全部可能的出棧序列和不可能的出棧序列?？赡艿某鰲Ｐ蛄校?14種)dcba

cdba

bacd

cbda

adcb

cbad

bdca

acdb

bcdaacbd

bcad

abdc

badc

abcd不可能的出棧序列：(10種)dbca

dbac

dabc

dacb

dcab

cabd

cdab

bdac

cadb

adbc循環(huán)隊(duì)列隊(duì)滿和隊(duì)空的判別條件。Q.front==Q.rear

Q.front=

=(

Q.rear+1)%M

Loc(aij

)=Loc(a11

)+

i-1(2n+

2

-

i)2

j

i

*

lLoc(aij

)=Loc(a11

)+

2設(shè)A為n階對稱矩陣，采用壓縮 存放于一維數(shù)組F[n(n+1)/2]中（從F[0]開始存放），請分別給出存放上三角陣時(shí)任一矩陣元素aij的地址計(jì)算公式和存放下三角陣時(shí)任一矩陣元素aij的地址計(jì)算公式。存放下三角陣時(shí)，任一矩陣元素aij（1≤i≤n,

1≤j≤i）的地址計(jì)算公式為：a103

……..a203

……..0an…3………....a11

a012a021

a22a01na02na0n1

a0n2存放上三角陣時(shí)，任一矩陣元素aij（1≤i≤n,i≤j≤n）的地址計(jì)算公式為：ann……………a…n-1…n-1.an-10n作業(yè)2A

002000070000055661447512三元組表i

jv01 23456寫出矩陣三元組表，鏈表11

4^512^^^447^^23

321

5268^^^^鏈表^作業(yè)2編程作業(yè)棧采用順序棧

，試設(shè)計(jì)算法實(shí)現(xiàn)將表達(dá)式轉(zhuǎn)換成后綴表達(dá)式輸出。例如，輸入表達(dá)式：

a+b/c-(d*e+f)*g輸出其后綴表達(dá)式：abc/+de*f+g*-SElemType

GetTop(SqStack

S){ SElemType

e;if(S.top>S.base)e=*(S.top-1);return

e;}Status

InOP(SElemType

c){

charOperators[]={'+','-','*','/','(',')','#','\0'};int

len=strlen(Operators);for(inti=0;i<len;i++)if(c==Operators[i])return

true;return

false;}void

Pass(

char

*Suffix,

SElemTypech){

*Suffix=ch;}void

main(){ char

Infix[N],Suffix[N];gets(Infix);Transform(Infix,Suffix);puts(Suffix);}SElemType

Precede(SElemType

curtop,SElemType

input){SElemType

order;switch(input){case

'+':case

'-':switch(curtop){case

'+':

case

'-':

case

'*':case

'/':

case

')':order='>';break;case

'(':

case

'#':}break;order='<';break;switch(curtop){case

'+':

case

'-':

case

'(':case

'#':order='<';break;case

'*':

case

'/':

case

')':}break;order='>';break;case

'*':case

'/':case

'(':switch(curtop){case

'+':

case

'-':

case

'*':

case

'/':

case

'(':}break;case

'#':order='<';break;case

')':switch(curtop){case

'+':

case

'-':

case

'*':case

'/':

case

')':break;order='>';break;order='=';case

'(':}break;case

'#':switch(curtop){case

'+':

case

'-':

case

'*':case

'/':

case

')':break;order='>';break;order='=';case

'#':}break;}return

order;}void

Transform(char

*Infix,

char

*Suffix

)SElemType

ch,e; int

flag=0,len;{ SqStack

S;InitStack(S);Push(S,

'#');len=strlen(Infix);*(Infix+len)='#';ch=

*Infix;while(!StackEmpty(S)){ if

(!InOP(ch))Pass(

Suffix++,

ch);else{

switch(Precede(GetTop(S),ch)){ case

'<':case

'=':case

'>':Push(S,ch);Pop(S,e);Pop(S,e);flag=0;flag=0;break;break;Pass(

Suffix++,

e);flag=1;

break;}}if(!flag)if(ch!='#')ch

=*++Infix;}Pass(Suffix,

'\0');DestroyStack(S);}請分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。作業(yè)3已知二叉樹的先序遍歷序列是EABDCFHGIKJ，中序遍歷序列是ABCDEFGHIJK，請構(gòu)造二叉樹，并寫出其層次遍歷序列和后序遍歷序列。ECBDIJHA

FGK層次：E

A

F

BH

DG

I

C

KJ后序---C

DB

A

G

JK

I

H

F

E森林轉(zhuǎn)換成一棵二叉樹AGKB

C

D

H

I

J

LE

FBACDFGEHIJKL二叉樹還原成森林ABCDGHIJKEFLMNACBF

HDMEGNJIKL作業(yè)3設(shè)二叉樹的后序遍歷序列為：DCFEBHJKIGA，中序序列為：CDBEFAHGJIK，請構(gòu)造這棵二叉樹。AGJHIKDCBEF二叉樹的中序遍歷序列為：DBHEIAFJKCG，層次遍歷序列為：ABCDEFGHIJK，請畫出該二叉樹ACJFGKHDBEI作業(yè)3假設(shè)用于通信的電文由7個(gè)字母組成{A,B,C,D,E,F,G}，字母在電文中出現(xiàn)的頻率分別為0.17、0.09、0.12、0.06、0.32、

0.03、0.21。試為這7個(gè)字母設(shè)計(jì)

編碼，并計(jì)算其帶權(quán)路徑長度WPL10.390.610.180.090.290.03

0.060.17A0.32E0.21

G0.09

0.12BDFWPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101

B:001

C:100

D:0001

E:11

F:0000

G:01作業(yè)3算法設(shè)計(jì)題二叉樹采用二叉鏈表

，試設(shè)計(jì)算法實(shí)現(xiàn)：CreateBT(BiTree&T)：從鍵盤輸入二叉樹的先序遍歷序列字符串（以”#”代表空結(jié)點(diǎn)），建立其二叉鏈表；如輸入：AB#D##CE#F###則建立如下圖所示二叉樹的二叉鏈表ExchangeBT(BiTree

T):

設(shè)計(jì)遞歸算法實(shí)現(xiàn)二叉樹中所有結(jié)點(diǎn)的左右孩子交換；CountLeaf(BiTree

T,

emType

x,int

&count):

統(tǒng)計(jì)以值為x的結(jié)點(diǎn)為根的子樹中葉子結(jié)點(diǎn)的數(shù)目；DispBiTree(BiTree

T,int

level):按樹狀打印二叉樹。作業(yè)3//輸入先序序列，創(chuàng)建二叉樹的二叉鏈表void

CreateBT(BiTree

&T){char

ch;scanf("%c",&ch);if

(ch

==

'#')

T

=

NULL;else{T

=

(BiTNode

*)malloc(sizeof(BiTNode));T->data

=

ch;CreateBT(T->lchild);CreateBT(T->rchild);}}//交換二叉樹中結(jié)點(diǎn)的左右孩子void

ExchangeBT(BiTree

T)B

CFAED{BiTree

temp;if(T){

temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ExchangeBT(T->lchild);ExchangeBT(T->rchild);}}AB#D##CE#F###BiTree

SearchTree(BiTree

T,char

X){BiTree

bt;if(T){

if(T->data==X)return

T;bt=SearchTree(T->lchild,X);if(bt==NULL)bt=SearchTree(T->rchild,X);return

bt;}return

NULL;}void

LeafCount

(BiTree

T, int

&count){ if

(

T

){ if

((T->lchild==NULL)&&

(T->rchild==NULL))LeafCount(

T->lchild,

count);LeafCount(

T->rchild,

count);}}count++;B

CFAED//按樹狀打印輸出二叉樹的元素,level表示結(jié)點(diǎn)的層次void

DispBiTree(BiTreeT,int

level){int

i;if(T){

DispBiTree(T->rchild,

level

+

1);for(i

=

0;

i

<

level;i++)printf("#");printf("%c\n",T->data);DispBiTree(T->lchild,

level

+

1);}}打印得到：#C###F##EA##D#BBCFAED作業(yè)4已知帶權(quán)有向圖如下,畫出該圖的鄰接矩陣 結(jié)構(gòu);用Dijkstra算法，求出頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑及其長度，寫出求解步驟；abcdefgha0b2cd6ef9gh0301050280730240210bde終點(diǎn)從a到各終點(diǎn)的最短路徑及其長度

f

gb2<a,b>-------------------------------c32<a,b,c>32<a,b,c>13<a,b,d,e,c>13<a,b,d,e,c>13<a,b,d,e,c>------d6<a,d>3<a,b,d>--------------------------------e5<a,b,d,e>---------------------------f9<a,f>9<a,f>9<a,f>9<a,f>------------------g12<a,b,d,e,g>12<a,b,d,e,g>-------------h<33a,b,d,e,g,h<18>a,b,d,e,c,h>Vjb:2<a,b>d:3<a,b,d>e:5<a,b,d,e>f:9<a,f>g:12<a,b,d,e,g>c:13<a,b,d,e,c><ah:18,b,d,e,c,h>ch作業(yè)48

88深度遍歷：456873245687作業(yè)4無向圖鄰接表 結(jié)構(gòu)

：畫出該無向圖；寫出在該鄰接表上，從頂點(diǎn)1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。深度優(yōu)先生成樹88

8廣度遍歷：456871328746

5廣度優(yōu)先生成樹作業(yè)4無向圖鄰接表 結(jié)構(gòu)

：畫出該無向圖；寫出在該鄰接表上，從頂點(diǎn)1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。已知帶權(quán)無向圖

：用Prim算法，求從頂點(diǎn)1出發(fā)的最小生成樹，畫出求解步驟；用Kruskal算法，求最小生成樹，畫出求解步驟Prim算法Kruskal算法作業(yè)4對下標(biāo)為1～9的有序表進(jìn)行二分法查找，畫出折半查找的判定樹；計(jì)算其ASL;52713

684

9ASL=(1+2*2+3*4+4*2)/9=25/9作業(yè)53

7

0

3

1

0

6

10

6

0

5

3設(shè)有關(guān)鍵字序列{25,

40,33,47,12,66,72,87,

94,

22,5,

58}散列表長為12，散列函數(shù)為h(key)=key%11，用線性探測再散列處理

，請畫出散列表，在等概率情況下，求查找成功平均查找長度0ASL=(1*6+2+3*2+5+6+9)/12=34/12作業(yè)53312662547227240941

1

3

1

2