2009級(jí)復(fù)習(xí)提綱及練習(xí)題

第一章緒論主要內(nèi)容本課程研究的主要內(nèi)容核心概念第一章緒論概念數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)(線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)、集合結(jié)構(gòu))、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))、抽象數(shù)據(jù)類型、算法、算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度;方法:1.根據(jù)二元組畫出圖示邏輯結(jié)構(gòu)(注意邊的方向);2.算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度的求解;第一章學(xué)習(xí)要點(diǎn)理解數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型等基本概念；理解抽象數(shù)據(jù)類型ADT的作用；理解線性結(jié)構(gòu)和非線性結(jié)構(gòu)的邏輯特征，順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特征；理解算法、算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度的概念及計(jì)算方法；數(shù)據(jù)的邏輯結(jié)構(gòu)：描述數(shù)據(jù)間的邏輯關(guān)系。典型的邏輯結(jié)構(gòu)：集合、線性、樹(shù)、圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的表示(映象)。典型的存儲(chǔ)結(jié)構(gòu)：順序和鏈?zhǔn)紸DT：定義了一個(gè)數(shù)據(jù)模型和在這個(gè)數(shù)據(jù)模型上的一組操作。

ADT是對(duì)數(shù)據(jù)結(jié)構(gòu)的抽象,包括數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作三個(gè)部分,ADT描述數(shù)據(jù)的邏輯關(guān)系和數(shù)據(jù)的基本操作。忽略了數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)。算法、算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度算法的時(shí)間復(fù)雜度.

隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間T(n)的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作T(n)=O(f(n))

稱作算法的漸近時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度的計(jì)算

算法中基本操作執(zhí)行的次數(shù)作為算法執(zhí)行時(shí)間的度量intf(inta[][]){for(i=0;i<n;i++)

for(j=1;j<=i-1;j++){++x;a[i,j]=x;}

}

基本操作++x;a[i,j]=x;執(zhí)行的次數(shù)為：

2(1+2+3+…+n-2)=(n-1)(n-2)

該算法時(shí)間復(fù)雜度為：O(n2)11、算法指的是______。(A)計(jì)算方法(B)排序方法(C)查找方法(D)解決問(wèn)題的有限運(yùn)算序列

12、算法設(shè)計(jì)需要達(dá)到的目標(biāo)是

。（A）正確性（B）高效率 （C）低存儲(chǔ) （D）全是13、對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有

、

、

、

四種。

14.建立具有n元素的單鏈表算法的時(shí)間復(fù)雜度為

A.O(n)B.O(1)C.O(log2n)D.O(n2)第二章線性表

主要內(nèi)容線性表的概念線性表兩種實(shí)現(xiàn)方法線性表應(yīng)用第二章線性表概念(包括有關(guān)術(shù)語(yǔ))

線性表、順序表、單鏈表、雙鏈表、循環(huán)鏈表、靜態(tài)鏈表方法

1.線性表的順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)

2.線性表的基本操作算法(插入、刪除、讀取)

3.線性表的應(yīng)用-線性表的其它操作算法

第二章線性表學(xué)習(xí)要點(diǎn)1.了解線性表的邏輯結(jié)構(gòu)特性，了解在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)特性——順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法(C語(yǔ)言描述)，以及線性表的基本操作算法。3.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的基本操作算法不同特點(diǎn)及其兩種存儲(chǔ)結(jié)構(gòu)適用場(chǎng)合。4.掌握線性表的其它操作的實(shí)現(xiàn)。建立線性鏈表——利用基本操作voidCreateList_L(LinkList&L,intn){

//輸入n個(gè)元素,建立順序表

InitList_L(L);//建空表

for(i=1;i<=n;i++){ read(e);//輸入一個(gè)元素e ListInsert_L(L,i,e);//將

e插入表

}}//CreateList_L

建立線性表(建立線性鏈表)算法時(shí)間復(fù)雜度O(n2)ssvoid

CreateList_L(LinkList&L,intn){//輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的線性鏈表

L=(LinkList)malloc(sizeof(LNode));//建空表

L->next=NULL;}//CreateList_Lfor(i=1;i<=n;i++){}p=L;

p->next=NULL;a1Lppa2ps=(LinkList)malloc(sizeof(LNode));//建立新結(jié)點(diǎn)

read(s->data); //讀入數(shù)據(jù)

p->next=s;//插入表尾

p=p->next;

算法時(shí)間復(fù)雜度O(n)線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)(也稱為順序表)用連續(xù)的存儲(chǔ)單元存放線性表的數(shù)據(jù)元素;通過(guò)元素存儲(chǔ)順序表示元素的邏輯順序;a1

a2ai-1aiai+1antypedefstruct{ElemType*elem;//存儲(chǔ)空間基址

intlength;//當(dāng)前長(zhǎng)度

intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList;L.elemL.lengthL.listsizen100

01i-2i-1in-199a1

a2ai-1aiai+1anSqListL;

插入操作ListInsert(&L,i,e)功能：在順序表L中第i個(gè)元素之前插入新元素e

a1

a2ai-1aian基本步驟:1)判表滿;2)anan-1,…ai依次后移一個(gè)位置;3)將新元素e寫入到第i個(gè)位置;4)表長(zhǎng)加1;a1

a2ai-1

eaian1)判表滿

L.length==L.listsize;2)anan-1,…ai依次后移一個(gè)位置

for(j=L.length-1;j<i;--j)

L.elem[j+1]=L,elem[j];

3)將新元素e寫入到第i個(gè)位置

L.elem[i-1]=e;

4)表長(zhǎng)加1

++L.length;L.elemL.lengthL.listsizen100

01i-2i-1in-199a1

a2ai-1aiai+1an2.3線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):也稱為鏈表

任意一組內(nèi)存單元存儲(chǔ)線性表的數(shù)據(jù)元素;通過(guò)保存相關(guān)元素的存儲(chǔ)地址或存儲(chǔ)位置表示數(shù)據(jù)元素之間的邏輯關(guān)系;101010121014101610181020102210241026a4a3a1a2

0101010241014a3a1a2a4typedefstructLNode{

ElemTypedata;

StructLNode*next;

}LNode,*LinkList;aia1ai+1ai-1anLaia1ai+1ai-1anLLinkListL;頭指針L空指針頭結(jié)點(diǎn)

插入操作ListInsert_L(L,i,e)功能：在線性鏈表L的第i個(gè)元素結(jié)點(diǎn)之前插入新元素e的結(jié)點(diǎn);主要步驟1)查找第i-1個(gè)元素結(jié)點(diǎn);2)建立新元素結(jié)點(diǎn);3)修改指針,插入新結(jié)點(diǎn);

aia1ai-1anLeaia1ai-1anLp1)查找第i-1個(gè)元素結(jié)點(diǎn)

s->next=p->next;p->next=s;eaia1ai-1anLps3)修改指針,插入新結(jié)點(diǎn);p=L.;j=0;while(p&&j<i-1){p=p->next;++j;}2)建立新元素結(jié)點(diǎn);s=(LinkList)malloc(sizeof(LNode));

s->data=e;2.3.2循環(huán)鏈表循環(huán)鏈表L空循環(huán)鏈表aia1ai+1a1anaiai+1anL表尾結(jié)點(diǎn)指向表的第一個(gè)結(jié)點(diǎn)從一個(gè)結(jié)點(diǎn)出發(fā),可以找到鏈表的所有結(jié)點(diǎn);2.3.3雙向鏈表La1aiai-1anL每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向后繼結(jié)點(diǎn)，一個(gè)指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

p從一個(gè)結(jié)點(diǎn)可以很方便的找到它的前驅(qū)和后繼;從一個(gè)結(jié)點(diǎn)出發(fā),可以找到鏈表的所有結(jié)點(diǎn);2.3.4靜態(tài)鏈表用數(shù)組實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為靜態(tài)鏈表

012345678910a4

a3a1a2

0

1

8

3數(shù)組下標(biāo)地址a4a3a1a2101010121014101610181020102210241026

0101010241014鏈表存放在數(shù)組中鏈表直接存放在內(nèi)存中練習(xí)題-線性表1.在下列各項(xiàng)敘述中，正確的說(shuō)法是（）A.在線性表中，每個(gè)元素有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼

B.線性表中至少有一個(gè)元素

C.在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼

D.線性表中元素必須從大到小或從小到大排列C3、對(duì)于經(jīng)常要存取線性表任意指定位置元素的應(yīng)用，線性表應(yīng)采用的存儲(chǔ)結(jié)構(gòu)是（）

a.鏈?zhǔn)?/p>

b.線性鏈表

c.棧

d.順序2.用線性鏈表存儲(chǔ)線性表時(shí)，要求存儲(chǔ)空間（）

A.連續(xù)不連續(xù)都可以

B.部分元素的存儲(chǔ)空間必須是連續(xù)的

C.必須是連續(xù)的

D.必須是不連續(xù)的Ad5、線性表的順序存儲(chǔ)結(jié)構(gòu)是通過(guò)何種方式表示元素之間的關(guān)系（）

A.保存左、右孩子地址

B.后繼元素的數(shù)組下標(biāo)

C.元素的存儲(chǔ)順序

D.保存后繼元素地址4、在下列對(duì)順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為O(1)的是（）

a.訪問(wèn)第i個(gè)元素的前驅(qū)（1<i≤n）

b.對(duì)順序表中元素進(jìn)行排序

c.刪除第i個(gè)元素(1≤i≤n)d.在第i個(gè)元素之后插入一個(gè)新元素(1≤i≤n)aC6、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i(1≤i≤n+1)個(gè)位置之前插入一個(gè)新元素的算法時(shí)間復(fù)雜度為()a.O(n^2)b.O(n/2)c.O(n)d.O(log2n)7、在一個(gè)單鏈表中，已知指針p指向其中的某個(gè)結(jié)點(diǎn)，若在該結(jié)點(diǎn)前插入一個(gè)由指針s指向的結(jié)點(diǎn)，則需執(zhí)行()a.r=p->next;p->next=s;s->next=r;b.p->next=s;s->next=p;c.s->next=p->next;p->next=s;d.以上都不對(duì)cd8、在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，體現(xiàn)數(shù)據(jù)之間關(guān)系的是（）

a.數(shù)據(jù)在內(nèi)存的相對(duì)位置

b.數(shù)據(jù)元素存儲(chǔ)順序

c.指針

d.數(shù)據(jù)的存儲(chǔ)地址9、靜態(tài)鏈表與動(dòng)態(tài)鏈表相比，其缺點(diǎn)是（）

a.插入、刪除時(shí)需移動(dòng)較多數(shù)據(jù)

b.不能隨機(jī)存取

c.有可能浪費(fèi)較多存儲(chǔ)空間

d.以上都不是cc10、若某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用存儲(chǔ)結(jié)構(gòu)算法的時(shí)間效率最高的是（）

a.單鏈表

b.給出表尾指針的單循環(huán)鏈表

c.雙向鏈表

d.給出表尾指針雙向循環(huán)鏈表d14、在順序存儲(chǔ)結(jié)構(gòu)中，只要知道

，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。（A）基地址 （B）結(jié)點(diǎn)大?。–）向量大小 （D）基地址和結(jié)點(diǎn)大小16、單鏈表中指針P所指結(jié)點(diǎn)不為尾結(jié)點(diǎn)的條件是

。

17、在有頭結(jié)點(diǎn)的單鏈表中，第1個(gè)結(jié)點(diǎn)的地址存放在

中，其他結(jié)點(diǎn)的存儲(chǔ)地址存放在前驅(qū)結(jié)點(diǎn)的

域中。

DP->next!=NULL頭指針指針1、向具有n個(gè)不同元素的鏈表中插入一個(gè)數(shù)據(jù)元素,最壞情況下需要訪問(wèn)

個(gè)元素?[A]n[B]n/2[C]1[D]n/32、若鏈表中的元素有序,下列敘述哪一個(gè)正確?[A]找第k個(gè)元素的時(shí)間復(fù)雜度是O(1)[B]插入一個(gè)給定元素的時(shí)間復(fù)雜度是O(n2)[C]刪除一個(gè)給定元素的時(shí)間復(fù)雜度是O(1)[D]查找一個(gè)元素a是否屬于鏈表的時(shí)間復(fù)雜度是O(n)AD5、線性鏈表中各個(gè)結(jié)點(diǎn)之間的地址

。[A]必須連續(xù)[B]不一定連續(xù)[C]任意6、在非空鏈表中，在由p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)過(guò)程是：[A]p=q->next;p->next=q;[B]q->next=p->next;p->next=q;[C]q->next=p->next;p=q;[D]p->next=q;q->next=p;CBB4、若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用

存儲(chǔ)結(jié)構(gòu)。[A]散列[B]順序[C]鏈表[D]任意7、若刪除非空鏈表中由p所指向的結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的過(guò)程是：[A]r=p->next;p->next=r;free(r);[B]r=p->next;p->next=r->next;free(r);[C]r=p->next;p=r->next;free(r);[D]p->next=p->next->next->next;8、在非空雙向循環(huán)鏈表中，在由q指向結(jié)點(diǎn)前插入一個(gè)由p指向的結(jié)點(diǎn)的過(guò)程是：p->right=q;p->left=q->left;q->left=p,().[A]q->left=p;[B]q->left->right=p;[C]p->right->right[D]p->left->right=p;BDkey=24iiiiii

順序查找4561123372490539878intSearch_Seq(SqListL,ElemTypee){

/*在順序表L中順序查找值等于e的元素。若找到，則返回元素在表中的位置，否則為0*/

}//Search_Seq i=0; while(i<=L.length-1&&L.elem[i]!=e)i++;if(i<L.length)returni; return0;

012345678910m-1456112

3372490539878L.elemL.lengthLinkListLSearch_L(LinkListL,ElemTypee){

/*在鏈表L中順序查找值等于e的元素。若找到，則返回該元素結(jié)點(diǎn)的地址，否則為NULL*/

}//Search_L p=L->next; while(p!=NULL&&p->data!=e)p=p->next;returnp;aia1ai+1ai-1anLvoidReverse_Sq(SqListL){//順序表就地置逆}//Reverse_Sqa1a2a3a4a5a6a7a8a9n=L.length;m=2;for(i=0;i<m;i++){temp

=L.elem[i];L.elem[i]=L.elem[n-i+1];

L.elem[n-i+1]=temp;}012345678voidReverse_L(LinkListL){//單鏈表就地置逆}//Reverse_L

p=L->next;r=NULL;while(p){q=p->next;p->next=r;r=p;p=q;}L->next=r;a1a2an^a3Lqp掃描鏈表L是含n個(gè)數(shù)據(jù)元素的帶頭結(jié)點(diǎn)的單鏈表,P是數(shù)據(jù)元素為整數(shù)(<n)有序鏈表,編寫從L中刪除以P中整數(shù)為序號(hào)的元素的算法.

例如L=(a1,a2,a3,a4,a5,a6,a7,a8),P=(1,3,5),則刪除后L=(a2,a4,a6,a7,a8).voidDelete_P(LinkListL,LinkListP){lp=L;i=1;//i為計(jì)數(shù)器,lp為計(jì)數(shù)器所指結(jié)點(diǎn)的前驅(qū)

pp=P;while(pp){//lp后移到刪除元素的前驅(qū)

while(i<pp->data){i++;lp=lp->next;}q=lp->next;lp->next=q->next;free(q);i++;pp=pp->next;;}//while}a1a2an^a3L135^Pi=1plqL是含n個(gè)數(shù)據(jù)元素的順序表,P是數(shù)據(jù)元素為整數(shù)(<n)有序順序表,編寫從L中刪除以P中整數(shù)為序號(hào)的元素的算法.

例如L=(a1,a2,a3,a4,a5,a6,a7,a8),P=(1,3,5),則刪除后L=(a2,a4,a6,a7,a8).a1a2a3a4a5a6a7a8135LPa2a4a6a7a8L刪除后已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)。試寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素（O(1)表示算法的輔助空間個(gè)數(shù)為常量）。3715612174731561214item=7A.elemA.elemvioddelitem(SqListL,ElemTypeitem){//k為記錄當(dāng)前元素前移位置數(shù)的整型變量

i=0; while(i<L.length&&L.elem[i]!=item)i++;//查找L第一個(gè)值為item的元素

k=1; for(j=i+1;j<L.length;j++){if(L.elem[j]!=item)L.elem[j-k]=L.elem[j];elsek++;}}37156121747A.elem012345678ijjk=1k=2已知線性元素以值遞增排列有序，并以帶頭單鏈表作存儲(chǔ)結(jié)構(gòu)，試寫一高效的算法，刪除表中所有值大于min且小于max的元素（設(shè)表中存在這樣的元素）。voiddelete(LinkListL,intmin,intmax),并分析算法的時(shí)間復(fù)雜度。aiai+1akai+1>

minai<

=minak>=maxak-1ak-1<maxvoiddelete(LinkListL,intmin,intmax){pre=L;p=pre->next;while(p!=NULL)&&(p->data<=min){pre=p;p=p->next;}while(p!=NULL)&&(p->next<max){pre->next=p->next;free(p);//刪除pp=pre->next;//p刪除結(jié)點(diǎn)的后繼

}}//deleteaiai+1akai+1>

minai<

=minak>=maxak-1ak-1<maxpreppai+1<max

設(shè)用帶頭結(jié)點(diǎn)的單鏈表La和Lb分別表示集合A和B，則集合求并操作轉(zhuǎn)化為:將Lb中不在La的元素插入La。A={3，1，4，6}B={1，2，4，8}A=A∪B={3，1，4，6，2，8}例：設(shè)A和B是兩個(gè)集合,設(shè)計(jì)求解集合并集A=A∪B

的算法。1．從表Lb中依次讀取每個(gè)數(shù)據(jù)元素；2．在表La中查找e

；3．若不存在，則將e

插入La表尾;voidunions(LinkList&La,LinkListLb){

//該算法將Lb中元素并入La pb=Lb->next;while(pb!=NULL){//依次處理Lb中的數(shù)據(jù)元素

e=pb->data;pb=pb->next;//取元素

}//while

}//unions

pre=La;pa=pre->next;while(pa!=NULL&&pa->data!=e)//在La中查找

{pre=pa;pa=pre->next;} if(pa==NULL)//La中不存在和e相同的元素，則插入

{pre->next=(LinkList)malloc(sizeof(LNode)); pre=pre->next;pre->data=e;pre->next=NULL; }//if

Lb4128431La6第三章棧和隊(duì)列主要內(nèi)容棧和隊(duì)列的概念棧和隊(duì)列的兩種實(shí)現(xiàn)棧和隊(duì)列的應(yīng)用第三章概念棧、隊(duì)列方法

1.棧、隊(duì)列的順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)

2.棧、隊(duì)列的基本操作算法

3.棧、隊(duì)列的應(yīng)用第三章學(xué)習(xí)要點(diǎn)1.掌握棧、隊(duì)列的特征和操作特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。2.熟練掌握棧的兩種實(shí)現(xiàn)方法，注意棧滿和?？盏呐袛鄺l件;3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，注意隊(duì)滿和隊(duì)空的判斷條件;4.理解遞歸算法執(zhí)行過(guò)程中棧的作用第三章棧和隊(duì)列棧：限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；棧的特點(diǎn)：后進(jìn)先出LIFO表(LastInFirstOut)主要操作

Push(S,e)Pop(S,e)ana2a1棧頂棧底出棧進(jìn)棧順序棧S.stacksizeS.topS.base

anan-1a2a110099 n-110#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10

typedefstruct{SElemType*base;//棧底

SElemType*top;//棧頂

intstacksize;//棧的大小}SqStack;Push(&S,e)：*S.top++=e;Pop(&S,&e)：e=*--S.top;鏈?zhǔn)綏ush(&S,e)：在鏈表表頭插入一個(gè)新結(jié)點(diǎn)Pop(&S,&e)：刪除鏈表第一個(gè)元素結(jié)點(diǎn)San…...a1^an-1第三章棧和隊(duì)列隊(duì)列：限定僅能在表尾插入表頭刪除的線性表;隊(duì)列的特點(diǎn)先進(jìn)先出線性FIFO表(FirstinFirstout)主要操作

EnQueue(Q,e)DelQueue(Q,e)a1an-1an出隊(duì)列進(jìn)隊(duì)列隊(duì)首隊(duì)尾順序隊(duì)列的類型定義#defineMAXQSIZE100typedefstruct{

QElemType*base;

//動(dòng)態(tài)數(shù)組的基址

intfront;

//隊(duì)頭指針

intrear;

//隊(duì)尾指針}SqQueue;99nn-1n-210

an

an-1a2a1Q.rearQ.frontQ.basen0SqQueueQ;循環(huán)隊(duì)列014325J4J6J530Q.baseQ.rearQ.front543210Q.rearQ.frontQ.base30

J6

J4

J5J7入隊(duì)操作前J7入隊(duì)操作后Q.rear=(Q.rear+1)%MAXQSIZE循環(huán)隊(duì)列:EnQueue(Q,e)Q.base[Q.rear]=e014325J4J6J503Q.baseQ.rearQ.front014325J7J4J6J513Q.baseQ.rearQ.front循環(huán)隊(duì)列：注意判斷隊(duì)列空和滿的條件Q.front=(Q.front+1)%MAXQSIZE循環(huán)隊(duì)列DelQueue(Q,e)e=Q.base[Q.rear];014325J7J4J6J513Q.baseQ.rearQ.front014325J7J4J6J514Q.baseQ.rearQ.frontJ4出隊(duì)操作前J4出入隊(duì)操作后循環(huán)隊(duì)列：注意判斷隊(duì)列空和滿的條件鏈隊(duì)列a2a1anQ.frontQ.rear第三章作業(yè)1、隊(duì)列和棧的共同點(diǎn)是【】A.LIFOB.都是線性表C.無(wú)共同點(diǎn)D.FIFO2、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為【】A.5和1B.1和5C.4和2D.2和4見(jiàn)測(cè)試題3、向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行的語(yǔ)句序列是【】A.s→next=h；h=h→next；

B.s→next=h→next；h→next=s；

C.h→next=s；

D.s→next=h；4、對(duì)于循環(huán)隊(duì)列，正確的是【】A.無(wú)法判斷隊(duì)列是否為滿

B.循環(huán)隊(duì)列不會(huì)滿

C.無(wú)法判斷隊(duì)列是否為空

D.以上說(shuō)法都是錯(cuò)誤的5、設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是b,d,c,f,e,a,g，則棧S的容量至少是【】A.2B.1C.3D.46、為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是，【】A.棧B.圖

C.樹(shù)D.隊(duì)列7、若一個(gè)棧的輸入序列為1，2，3，…，n，輸出序列的第1個(gè)元素為n，則第i個(gè)輸出的元素是()A.iB.n?iC.n?i+1D.可是其他任意元素8、用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)，()A.隊(duì)頭，隊(duì)尾指針都要修改

B.隊(duì)頭，隊(duì)尾指針都可能要修改

C.僅修改隊(duì)頭指針

D.僅修改隊(duì)尾指針9、一個(gè)棧的輸入序列為：12345，則下列序列中不可能的輸出序列是，【】A.15432B.54231C.23415D.2314510、在算符優(yōu)先算法中，算符‘＋’和‘（’的優(yōu)先關(guān)系應(yīng)是，【】A.‘＋’<‘（’

B.‘＋’=‘（’

C.取決于它們出現(xiàn)的位置

D.‘＋’>‘（’

第五章數(shù)組和廣義表主要內(nèi)容數(shù)組的概念和實(shí)現(xiàn)兩類矩陣的壓縮存儲(chǔ)方法廣義表的概念和實(shí)現(xiàn)第五章數(shù)組和廣義表概念數(shù)組、特殊矩陣、稀疏矩陣、廣義表方法

1.數(shù)組的兩種存儲(chǔ)表示方法，掌握數(shù)組元素地址計(jì)算方法。

2.兩類矩陣的壓縮存儲(chǔ)方法;3.廣義表的分解方法-表頭表尾第五章學(xué)習(xí)要點(diǎn)1.了解數(shù)組的兩種存儲(chǔ)表示方法，掌握數(shù)組元素地址計(jì)算方法。2.了解兩類矩陣的壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，3.掌握廣義表的特點(diǎn)，了解對(duì)非空廣義表進(jìn)行分解方法：分解為表頭和表尾。第六章樹(shù)和二叉樹(shù)主要內(nèi)容二叉樹(shù)的概念二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)的應(yīng)用-Huffman樹(shù)、Huffman編碼樹(shù)的概念和實(shí)現(xiàn)第六章二叉樹(shù)概念

二叉樹(shù)、線索二叉樹(shù)(中序、前序、后序)、Huffman樹(shù)、Huffman編碼、

方法

1.二叉樹(shù)的性質(zhì)

2.二叉樹(shù)的存儲(chǔ)(鏈?zhǔn)?二叉鏈表的三叉鏈表

順序存儲(chǔ):完全二叉樹(shù))3.二叉樹(shù)的先序、中序、后序遍歷

4.二叉樹(shù)遞歸算法

5.構(gòu)造

Huffman樹(shù)、Huffman編碼第六章樹(shù)概念

樹(shù)、森林、方法

1.樹(shù)林的鏈?zhǔn)酱鎯?chǔ)

(1)孩子兄弟表示法

(2)雙親表示法

(3)孩子表示法

2.樹(shù)森林與二叉樹(shù)相互轉(zhuǎn)換

3.樹(shù)的先序、后序遍歷、按層遍歷

第六章學(xué)習(xí)要點(diǎn)掌握二叉樹(shù)的結(jié)構(gòu)特性和性質(zhì)，熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。3.遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。4.理解二叉樹(shù)線索化的實(shí)質(zhì)是在二叉樹(shù)結(jié)點(diǎn)加入某種遍歷序列的前驅(qū)或后繼信息，掌握在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。5.掌握樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法,掌握樹(shù)遍歷方法。6.了解哈夫曼樹(shù)特性，建立哈夫曼樹(shù)和哈夫曼編碼的方法。6.2.1二叉樹(shù)的概念二叉樹(shù)或?yàn)榭諛?shù),或由根及兩顆不相交的左子樹(shù)、右子樹(shù)構(gòu)成,并且左、右子樹(shù)本身也是二叉樹(shù)。二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；二叉樹(shù)每個(gè)結(jié)點(diǎn)度小于等于2；左、右子樹(shù)不能顛倒;二叉樹(shù)是遞歸結(jié)構(gòu)GFEDCBAFCGEDBA6.2.1二叉樹(shù)的概念二叉樹(shù)的五種基本形態(tài)空樹(shù)只有根結(jié)點(diǎn)只有左子樹(shù)只有右子樹(shù)左右子樹(shù)均非空φ6.2.2二叉樹(shù)性質(zhì)

性質(zhì)3設(shè)二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=

n2+1。G

A

F

E

D

C

Bn0=3

n2=2

n0=n2+1

性質(zhì)2深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)。

性質(zhì)1二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i1)6.2.2二叉樹(shù)性質(zhì)完全二叉樹(shù)如果一顆二叉樹(shù)只有最下一層結(jié)點(diǎn)數(shù)未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹(shù)；

A

E

D

F

C

B

A

F

E

D

C

B6.2.2二叉樹(shù)性質(zhì)

性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n

+1

A

F

E

D

C

B6.2.2二叉樹(shù)性質(zhì)性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行編號(hào)(1-n)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i

的結(jié)點(diǎn)：

1）若有左孩子(2i<n)

，則左孩子編號(hào)為2i；

2）若有右孩子(2i+1<n)，則右孩子編號(hào)為2i+1；

3）若有雙親(i1)

，則雙親結(jié)點(diǎn)編號(hào)為i/2；

A

F

E

D

C

B512346012345678910m-16.2.3二叉樹(shù)的存貯結(jié)構(gòu)二叉樹(shù)的順序結(jié)構(gòu)ABCDEF完全二叉樹(shù)

A

F

E

D

C

B5214366.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;∧

D

∧

A

B

C

∧∧

F

∧∧

G

∧T

E

∧先左（子樹(shù)）后右（子樹(shù)）的遍歷L:遍歷左子樹(shù)

D:訪問(wèn)根結(jié)點(diǎn)

R:遍歷右子樹(shù)DLR——-先序遍歷LDR——中序遍歷LRD——后序遍歷6.3二叉樹(shù)的遍歷GFEDCBA二叉樹(shù)的分解根結(jié)點(diǎn)左子樹(shù)右子樹(shù)先序遍歷遞歸算法voidPreTraverse(BiTreeT,void(*Visit)(TElemTypee))

{/*用二叉鏈表存儲(chǔ)二叉樹(shù)，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)，本算法先序遍歷以T為根指針的二叉樹(shù)*/if(T){Visit(T->data)；

PreTraverse(T->lchild,Visit);PreTraverse(T->rchild,Visit);}}

∧

D

∧

A

B

C

∧∧

F

∧∧

G

∧T

E

∧先序遍歷以T->lchild為根指針的左子樹(shù)先序遍歷以T->rchild為根指針的右子樹(shù)6.3二叉樹(shù)的遍歷

先序序列（DLR）G

A

F

E

D

C

BABDEGCF

中序序列（LDR）

后序序列（LRD）

二叉樹(shù)的遞歸算法

1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)

2、求二叉樹(shù)的深度

3、復(fù)制二叉樹(shù)

4、建立二叉樹(shù)

練習(xí)題-二叉樹(shù)練習(xí)題-樹(shù)具有n個(gè)頂點(diǎn)的二叉樹(shù)，共有多少邊？2、若一個(gè)具有N個(gè)頂點(diǎn)，K條邊的無(wú)向圖是一個(gè)森林(N>K)，那么該森林有多少棵樹(shù)？3、已知一棵度為m的樹(shù)中有N1個(gè)度為1的節(jié)點(diǎn)，N2個(gè)度為2的節(jié)點(diǎn)，…，Nm個(gè)度為m的節(jié)點(diǎn)。問(wèn)該樹(shù)有多少葉子節(jié)點(diǎn)？4、層數(shù)為k的二叉樹(shù)中，最大和最小節(jié)點(diǎn)數(shù)各為多少？5、有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，有m個(gè)葉子節(jié)點(diǎn)，問(wèn)非葉子節(jié)點(diǎn)中度為2和度為1的節(jié)點(diǎn)各有多少？n-1N－KN0=N2+2N3+……+(m-1)Nm+12k-1,kn2=m-1;n1=n-2m+1假定一棵樹(shù)的廣義表示為(A(B(C,D(E,F,G),H(,J)))，則樹(shù)中所含的結(jié)點(diǎn)數(shù)為（）個(gè)，樹(shù)的深度為（）個(gè)，樹(shù)的度為（）。10,4,32、在哈夫曼編碼中，若編碼長(zhǎng)度只允許小于等于4，則除了已對(duì)兩個(gè)字符編碼為0和10外，還可以最多對(duì)（）個(gè)字符編碼.4已知一棵樹(shù)的先根次序遍歷的結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示(長(zhǎng)子-兄弟表示)的前序遍歷結(jié)果相同,樹(shù)的后根次序遍歷結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示的中序遍歷結(jié)果相同。試問(wèn)利用樹(shù)的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹(shù)?用二叉鏈表作為二叉樹(shù)的存儲(chǔ)表示，統(tǒng)計(jì)二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)，請(qǐng)完成下列遞歸程序。intleaf(BiTNode*ptr)

{ if(

)return0; elseif(ptr->lChild==NULL

&&

ptr->rChild==NULL)return1;

elsereturn

+

;}typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;ptr==NULLleaf(ptr->lChild)leaf(ptr->rChild)已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)被順序存儲(chǔ)于一維數(shù)組的A[1]～A[n]元素中，試找出編號(hào)為i的結(jié)點(diǎn)的雙親和所有孩子。假設(shè)每一個(gè)元素用一個(gè)整數(shù)表示。完成下列程序voidRequest(intA[],intn,inti){//從數(shù)組A中打印出編號(hào)為i的結(jié)點(diǎn)的雙親和孩子

if(

)exit(1);printf("currentelement:%f”,A[i]);intj=i/2;//下標(biāo)為j的結(jié)點(diǎn)是下標(biāo)為i結(jié)點(diǎn)的雙親

if()printf(“parent:%f”，A[j]);elseprinf(“Noparent!");if(){printf("leftchild:%f”,A[2*i]);printf("rightchild:%f“,A[2*i+1];}elseif(

){printf("leftchild:%f",A[2*i]);printf("norightchild!";}elseprintf("nochildren!“);}i>nj>02*i<n2*i==n將下列森林轉(zhuǎn)化為二叉樹(shù)，然后對(duì)森林進(jìn)行先序和后序遍歷123456891012131415117將下列樹(shù)進(jìn)行中序線索化ABCDEGF中序：CBAGEDFABCDEGF試分別找出滿足以下條件的所有二叉樹(shù)二叉樹(shù)的前序序列與中序序列相同二叉樹(shù)的中序序列與后序序列相同二叉樹(shù)的前序序列與后序序列相同如果一棵Huffman樹(shù)有n0個(gè)葉子節(jié)點(diǎn)，那么該樹(shù)有多少節(jié)點(diǎn)？已知如下序列：8、5、3、2、7、23、9、11、2、35，請(qǐng)構(gòu)造一棵Huffman樹(shù)。2n0-1假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。先序序列DLREBADCFHGIKJ中序序列LDRABCDEFGHIJK

左子樹(shù)DLRBADC

右子樹(shù)LDRABCDC

E

D

A

B

左左子樹(shù)

DLRA

左左子樹(shù)LDRA

左右子樹(shù)

DLRDC

左右子樹(shù)LDRCD練習(xí)題-二叉樹(shù)2.設(shè)用二叉鏈表存貯二叉樹(shù)，試編寫判斷兩棵二叉樹(shù)是否相等的遞歸算法，要求函數(shù)的原型為intEqual_Bin(BiTreeT1,BiTreeT2)。

終止項(xiàng)：

1)若T1、T2均為空樹(shù)，返回1；

2)若T1為空樹(shù)、T2不為空樹(shù)或若T1不為空樹(shù)、T2為空樹(shù)，返回0；遞歸項(xiàng):

若T1、T2均不為空樹(shù)，T1->data==T2->data

且T1的左子樹(shù)=T2的左子樹(shù)、T1的右子樹(shù)=T2的右子樹(shù)，則返回1；否則返回0；Statusequal(BiTreeT1,.BiTreeT2){/*本算法在先序遍歷二叉樹(shù)的過(guò)程中，判斷兩棵二叉樹(shù)是否相等，若相等返回1，否則返回0;*/if((T1==NULL)&&(T2==NULL))return1;if((T1==NULL&&T2!=NULL)||(T1!=NULL&&T2==NULL))return0;elsereturn((T1->data==T2->data)&&equal(T1->lchild,T2->rchild)&&equal(T->rchild,T2->rchild));}(2007)所有分支結(jié)點(diǎn)的度為2的二叉樹(shù)稱為正則二叉樹(shù)，試用二叉鏈表做存儲(chǔ)結(jié)構(gòu)，編寫一遞歸函數(shù)intFormalTree(Bitreet)，判斷二叉樹(shù)是否為正則二叉樹(shù)。GFEDCBAGFEDCBA正則二叉樹(shù)intFormalTree(Bitreet){//t為根的二叉樹(shù)是正則二叉樹(shù),返回1,否則返回0

}if(t==NULL)return1;if(t->lchild==NULL||t->rchild==NULL)return0;if(t->lchild==NULL&&t->rchild==NULL)return1;return(FormalTree(t->lchild)&&FormalTree(t->rchild));第七章圖主要內(nèi)容圖的概念圖的實(shí)現(xiàn)圖的應(yīng)用:

最小生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑、關(guān)鍵活動(dòng);第七章圖概念圖、最小生成樹(shù)、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑、關(guān)鍵活動(dòng);方法

1.圖的存儲(chǔ)(鄰接矩陣表示法\鄰接表表示法)2.圖的遍歷(深度優(yōu)先、廣度優(yōu)先)

3.拓?fù)渑判?、最小生成?shù)Prime

、Kruskual、最短路徑Dijkstra

第七章學(xué)習(xí)要點(diǎn)熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解圖的基本操作、圖的應(yīng)用問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)的聯(lián)系；掌握?qǐng)D的兩種遍歷算法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。注意圖的遍歷算法與樹(shù)的遍歷算法之間的之間的類似和差異;。理解所討論的各種圖應(yīng)用的經(jīng)典算法（方法）

。

7.1圖的定義與術(shù)語(yǔ)圖是由頂點(diǎn)集合及邊集合組成的一種數(shù)據(jù)結(jié)構(gòu)。記作G=(V,E)。其中V是頂點(diǎn)的非空有限集合，E是邊的有限集合,可以是有向邊或無(wú)向邊。無(wú)向圖、有向圖BACDEF圖中任何兩個(gè)頂點(diǎn)都可能有關(guān)系A(chǔ)BECD<A,B>(A,B)(B,A)圖的鄰接矩陣無(wú)向圖0100101000110001010010011100000111007.2.1數(shù)組表示法(鄰接矩陣表示法)BACDEF圖的鄰接矩陣有向圖01001001000001011000001007.2.1數(shù)組表示法(鄰接矩陣表示法)ABECD7.2.2鄰接表表示法用鄰接表表示頂點(diǎn)的之間的鄰接關(guān)系A(chǔ):(A,B)(A,E)B:(B,A)(B,E)(B,F)C:(C,D)(C,F)D:(D,C)(D,F)E:(E,A)(E,B)F:(F,B)(F,C)(F,D)例BACDEF無(wú)向圖鄰接表

v對(duì)應(yīng)的鏈表存儲(chǔ)v的所有鄰接點(diǎn)(或關(guān)聯(lián)邊)鄰接點(diǎn)的位置0

A

141

B

0452

C

353

D

254

E

015

F

123

7.2.2鄰接表表示法BACDEFtypedefstructArcNode{intadjvex;//邊的另一頂點(diǎn)的位置

structArcNode*nextarc;//指向下一條邊結(jié)點(diǎn)}ArcNode;圖的鄰接表類型定義弧的結(jié)點(diǎn)結(jié)構(gòu)adjvexnextarcinfo

7.2.2鄰接表表示法//頂點(diǎn)和鄰接表的類型定義typedefstructVNode{//頂點(diǎn)結(jié)點(diǎn)和頂點(diǎn)表的類型定義

VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向該頂點(diǎn)鄰接點(diǎn)鏈表}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)

7.2.2鄰接表表示法圖鄰接表類型定義typedefstruct{

AdjListvexs;intvexnum,arcnum;}ALGraph;

7.2.2鄰接表表示法§7.3.1深度優(yōu)先遍歷圖中任一個(gè)頂點(diǎn)都可作為第一個(gè)被訪問(wèn)的結(jié)點(diǎn);頂點(diǎn)被訪問(wèn)之后，有可能沿回路又到達(dá)該頂點(diǎn);從一個(gè)頂點(diǎn)出發(fā)，只能夠訪問(wèn)它所在的連通分量上的所有頂點(diǎn);對(duì)于非連通圖，需要分別遍歷圖的所有連通分量;bgabchdekf7.3.1深度優(yōu)先遍歷Vw1w2w3w2…從圖的某頂點(diǎn)v出發(fā)，進(jìn)行深度優(yōu)先遍歷訪問(wèn)頂點(diǎn)v

：

for(v

的所有鄰接點(diǎn)w1、w2、w3…)

若wi未被訪問(wèn),則從wi出發(fā),進(jìn)行深度優(yōu)先遍歷;7.3.2廣度優(yōu)先遍歷圖中某頂點(diǎn)v出發(fā)：1）訪問(wèn)頂點(diǎn)v；2）訪問(wèn)v所有未被訪問(wèn)的鄰接點(diǎn)w1,w2,…wk；3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)其所有未被訪問(wèn)的鄰接點(diǎn);依此類推，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到;bgabchdekf編寫一個(gè)函數(shù)根據(jù)用戶輸入的偶對(duì)（以輸入0表示結(jié)束）建立其有向圖的鄰接表。假設(shè)有n個(gè)頂點(diǎn)。

練習(xí)題-圖voidCreatGraph(ALGraph&G){for(k=1;k<=n;k++){G.vexs[k].data=k;

;}printf("輸入一個(gè)偶對(duì):");scanf("%d,%d“,&i,&j);while(i!=0||j!=0){ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;

;

;

printf("輸入一個(gè)偶對(duì):");scanf("%d,%d“,&i,&j);

}}G.vexs[k].firstarc=NULLp->nextarc=G.vexs[i].firstarc;G.vexs[i].firstarc=p下列說(shuō)法不正確的是（）。A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次B．遍歷基本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個(gè)遞歸過(guò)程C2、無(wú)向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,bCD練習(xí)題-圖下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)：A．深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑3、當(dāng)各邊上的權(quán)值()時(shí)，BFS（廣度優(yōu)先遍歷）算法可用來(lái)解決單源最短路徑問(wèn)題。A．均相等B．均互不相等C．不一定相等D.以上說(shuō)法均不對(duì)2、在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為:A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)BBA判斷題：有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)鄰接多重表是無(wú)向圖和有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)。需要借助于一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)DFS算法無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判蛟趫DG的最小生成樹(shù)G1中，可能會(huì)有某條邊的權(quán)值超過(guò)未選邊的權(quán)值。不同求最小生成樹(shù)的方法得到的生成樹(shù)是相同的.當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑網(wǎng)絡(luò)的最小生成樹(shù)是唯一的FTFTFTTFFF求關(guān)鍵路徑013592467856634444331522<0><5><12><6><15><19><21><23><16><16><23><21><19><19><16><15><6><12><9><0>02346789第九章查找主要內(nèi)容查找表基本概念查找表的表示方法（組織方法）查找表查找/插入/刪除方法查找效率分析第九章查找概念靜態(tài)查找表、動(dòng)態(tài)查找表、查找、平均查找長(zhǎng)度、二叉排序樹(shù)、平衡二叉樹(shù)、B樹(shù)、B+樹(shù)、哈希表方法

1.順序查找、二分查找法檢索的判定樹(shù)、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)

2.二叉排序樹(shù)的構(gòu)造查找插入刪除

3.平衡二叉樹(shù)的構(gòu)造

4.B樹(shù)的插入刪除

5.哈希表

1)哈希函數(shù)

2)沖突處理方法

3)哈希表的構(gòu)造查找

第九章學(xué)習(xí)要點(diǎn)1.

掌握順序表和有序表的查找算法;2.掌握二叉排序樹(shù)的構(gòu)造和查找、插入、刪除方法;平衡二叉樹(shù)的構(gòu)造方法;3.理解B樹(shù)的特點(diǎn)以及查找的方法;4.掌握哈希表的構(gòu)造、查找方法，理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別;

5.掌握二叉排序樹(shù)、哈希表平均查找長(zhǎng)度的計(jì)算方法;練習(xí)題－查找1、從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為

和

。2、向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度

；從一棵B_樹(shù)刪除元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)比原樹(shù)的高度

。3、以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是

存儲(chǔ)的

表。4、以二分查找方法從長(zhǎng)度為12的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為

。1，3，+1，-1，順序，有序,37/12，練習(xí)題－查找判斷題：2、對(duì)兩個(gè)具有相同關(guān)鍵字而形狀不同的二叉查找樹(shù)，按照中序遍歷它們得到的序列是相同的。1、用雙鏈表表示的有序表可以用折半查找方法來(lái)提高查找速度。3、在查找樹(shù)（二叉排序樹(shù)）中插入一