數據結構總復習

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

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

線性表邏輯結構（掌握）

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

結構（掌握）

：次序約定（算法實現不要求）壓縮

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

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

構成特點(與頂點度關系)應用（掌握求解過程，不要求寫算法）最小生成樹（Prim與Kruscal）拓撲排序最短路徑（Dijkstra）第七章查找靜態(tài)查找表順序查找（掌握）折半查找（掌握）分塊查找（了解）適用條件、比較、ASL動態(tài)查找表（了解）二叉排序樹–定義–構造方法–生成、 、刪除與查找–中序遍歷二叉排序樹可得到結點有序序列判定樹哈希查找（掌握）定義、基本思想Hash函數構造方法處理

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

6,1,4,7,2,3,5作業(yè)145964結構ptail需要的變量：k：計數p:

指向當前結點pre：指向p的前驅結點上機實現提示：①編制建立循環(huán)鏈表算法②編制結點輸出算法(帶輸入參數k)③編制主程序作業(yè)1pre環(huán)(Joseph

Circle)void

CreateCirList(CirList

&T,int

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

法：隨機產生n個元素的{ 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)//表非空{ for(i=1;i<m;i++)//報數{pre=p;p=p->next;ode);}pre->next=p->next;//繞過結點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);//最后一個出環(huán)作業(yè)1}2.

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

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

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

int

ElemType;typedef

struct

LNode{

ElemType

data;struct

LNode

*next;}LNode,

*LinkList;作業(yè)1void

InsertAtTail(LinkList

&L,int

m,ElemType

b[])//

法:升序輸入m個元素的值，建立 結點的單鏈表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)建結點單鏈表L875^2typedef

int

ElemType;typedef

struct

LNode{

ElemType

data;struct

LNode

*next;}LNode,

*LinkList;作業(yè)1void

InsertAtHead(LinkList

&L,int

n,ElemType

a[])//頭插法：升序輸入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//刪除數據域值為奇數的所有元素

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若進棧序列為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)隊列隊滿和隊空的判別條件。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設A為n階對稱矩陣，采用壓縮 存放于一維數組F[n(n+1)/2]中（從F[0]開始存放），請分別給出存放上三角陣時任一矩陣元素aij的地址計算公式和存放下三角陣時任一矩陣元素aij的地址計算公式。存放下三角陣時，任一矩陣元素aij（1≤i≤n,

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

……..a203

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

a012a021

a22a01na02na0n1

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

002000070000055661447512三元組表i

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

4^512^^^447^^23

321

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

，試設計算法實現將表達式轉換成后綴表達式輸出。例如，輸入表達式：

a+b/c-(d*e+f)*g輸出其后綴表達式：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個結點的樹和3個結點的二叉樹的所有不同形態(tài)。作業(yè)3已知二叉樹的先序遍歷序列是EABDCFHGIKJ，中序遍歷序列是ABCDEFGHIJK，請構造二叉樹，并寫出其層次遍歷序列和后序遍歷序列。ECBDIJHA

FGK層次：E

A

F

BH

DG

I

C

KJ后序---C

DB

A

G

JK

I

H

F

E森林轉換成一棵二叉樹AGKB

C

D

H

I

J

LE

FBACDFGEHIJKL二叉樹還原成森林ABCDGHIJKEFLMNACBF

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

0.03、0.21。試為這7個字母設計

編碼，并計算其帶權路徑長度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算法設計題二叉樹采用二叉鏈表

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

T):

設計遞歸算法實現二叉樹中所有結點的左右孩子交換；CountLeaf(BiTree

T,

emType

x,int

&count):

統(tǒng)計以值為x的結點為根的子樹中葉子結點的數目；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);}}//交換二叉樹中結點的左右孩子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表示結點的層次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已知帶權有向圖如下,畫出該圖的鄰接矩陣 結構;用Dijkstra算法，求出頂點a到其他各個頂點的最短路徑及其長度，寫出求解步驟；abcdefgha0b2cd6ef9gh0301050280730240210bde終點從a到各終點的最短路徑及其長度

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無向圖鄰接表 結構

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

8廣度遍歷：456871328746

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

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

：用Prim算法，求從頂點1出發(fā)的最小生成樹，畫出求解步驟；用Kruskal算法，求最小生成樹，畫出求解步驟Prim算法Kruskal算法作業(yè)4對下標為1～9的有序表進行二分法查找，畫出折半查找的判定樹；計算其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設有關鍵字序列{25,

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

94,

22,5,

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

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

1

3

1

2