2016數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案

習(xí)題一答案

1.填空題

（1）數(shù)據(jù)元素的有限集合，k上關(guān)系的有限集合

（2）順序存儲（連續(xù)），鏈?zhǔn)酱鎯Γú贿B續(xù)）

（3）有窮性，確定性，可行性，輸入，輸出

（4）時(shí)間復(fù)雜度，空間復(fù)雜度

2.簡述下列術(shù)語

（1）數(shù)據(jù)一是信息的載體，它是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算

機(jī)中被計(jì)算機(jī)程序識別、加工處理的信息的集合。

（2）數(shù)據(jù)元素一是數(shù)據(jù)的基本單位，是對一個(gè)客觀實(shí)體的數(shù)據(jù)描述。一個(gè)數(shù)據(jù)元

素可以由一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素也被稱為結(jié)點(diǎn)或記錄。

（3）數(shù)據(jù)對象一具有相同性質(zhì)的數(shù)據(jù)元素的集合就是一個(gè)數(shù)據(jù)對象，它是數(shù)據(jù)的

一個(gè)子集。

（4）數(shù)據(jù)結(jié)構(gòu)一數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間的相互關(guān)系（即數(shù)據(jù)的組織形式）及在這

些數(shù)據(jù)上定義的數(shù)據(jù)運(yùn)算方法的集合。

（5）存儲結(jié)構(gòu)一數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)部的表示或?qū)崿F(xiàn)，

又稱為數(shù)據(jù)的物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。

（6）數(shù)據(jù)類型一是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及定義在這個(gè)數(shù)據(jù)集合上的

一組操作的總稱。

3.舉例說明一下數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系。

通過公式：|程序=數(shù)據(jù)結(jié)構(gòu)鎮(zhèn)祖我們可以比較直觀地看出二者的關(guān)系，即數(shù)據(jù)結(jié)

構(gòu)（包個(gè)完整的程序括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)）的設(shè)計(jì)和算法的編寫是程序設(shè)計(jì)的兩個(gè)關(guān)

鍵步驟，一就是由一套合理的數(shù)據(jù)結(jié)構(gòu)和建立在該結(jié)構(gòu)上的算法構(gòu)成的。具體的說：在

進(jìn)行程序設(shè)計(jì)之前我們首先要為待處理的數(shù)據(jù)設(shè)計(jì)一個(gè)合理的邏輯結(jié)構(gòu)，進(jìn)而為之設(shè)計(jì)

一種適合的存儲結(jié)構(gòu)，因?yàn)楣庥羞壿嫿Y(jié)構(gòu)是不夠的，只有存儲結(jié)構(gòu)才是與計(jì)算機(jī)語言直

接相關(guān)的！有了這一套前期準(zhǔn)備，我們才能在這個(gè)基礎(chǔ)上設(shè)計(jì)算法，用一種計(jì)算機(jī)語言

去處理這些數(shù)據(jù)，最終達(dá)到程序設(shè)計(jì)的目的。當(dāng)然，隨著邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的不同，

我們設(shè)計(jì)的算法也會有所差別，這在以后的學(xué)習(xí)中會體會到。卜面通過個(gè)簡單的例子

說明這種關(guān)系。

假設(shè)我們要設(shè)計(jì)一個(gè)兩個(gè)n階方陣相乘的程序：已知兩個(gè)n階方陣A和B,我們要

計(jì)算它們的乘積，得到一個(gè)新的n階方陣C。那么在設(shè)計(jì)這個(gè)程序之前首先想到得就是

設(shè)計(jì)一種邏輯結(jié)構(gòu)表示方陣，這里我們用二維數(shù)組表示它們，因?yàn)槎S數(shù)組最能直觀地

表示這種結(jié)構(gòu)；有了邏輯結(jié)構(gòu)了自然還要為之設(shè)計(jì)一種存儲結(jié)構(gòu)，這里我們選擇順序存

儲方法，因?yàn)镃語言對這種存儲結(jié)構(gòu)給予了很好的支持，例如定義一個(gè)n階實(shí)型的二維

數(shù)組A只要用floatA[n][n];這條語句就可以了，C語言在內(nèi)存種為之分配了一個(gè)

n*n長度的順序存儲空間（注意：C語言默認(rèn)二維數(shù)組是按行優(yōu)先存儲的），是不是很

方便？有了這些準(zhǔn)備，我們就可以設(shè)計(jì)算法進(jìn)行計(jì)算了，其算法如下：

voidmatrixmult（floatA[n][n],floatB[n][n],floatC[n][n]）

inti,j,k；

floatx;

for(i=0;i<n;i++)

(

for(j=0;j<n;j++)

(

x=0;

for(k=0;k<n;k++)

(

x+=A[i][k]*B[k][j];

)

C[i][j]=x；

)

)

)

通過上面這個(gè)例子我們簡單的闡述了數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，更深入的內(nèi)涵

還要讀者在以后的學(xué)習(xí)中自己慢慢地體會。

4.設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為B=(K,R),K={kl,k2,......,k9}

r={<kl,k3>,<k3,k8>,<k2,k3>,<k2,k4>,<k2,k5〉，<k3,k9>,<k5,k6

>,<k8,k9>,<k9,k7>,<k4,k7〉，<k4,k6〉}畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并

確定相對于r哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？

通過以后的學(xué)習(xí)我們會知道這是一個(gè)有向圖，圖中共有9個(gè)結(jié)點(diǎn)，其中開始

結(jié)點(diǎn)有2個(gè)，分別為K1和K2；終端結(jié)點(diǎn)有2個(gè)，分別為K6和K7。

邏輯結(jié)構(gòu)圖表示如下：

7.何謂算法？試詳述算法設(shè)計(jì)的目的和算法必須滿足的條件。

算法是對特定問題求解步驟的一種描述，實(shí)際上是指令的有限序列，其中每

一條指令表示一個(gè)或多個(gè)操作。我們知道，程序設(shè)計(jì)的第一步是為待處理的數(shù)據(jù)

設(shè)計(jì)一種合理的數(shù)據(jù)結(jié)構(gòu)(包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu))，這一步固然重要，但這

不是我們的目的，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了在這個(gè)基礎(chǔ)上編寫算法進(jìn)而對

其進(jìn)行相關(guān)的操作(例如：遍歷，查找，排序，插入，刪除等)，如果不去編寫

相應(yīng)的算法那么設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)也就失去了它的意義，你所輸入到計(jì)算機(jī)的數(shù)據(jù)永

遠(yuǎn)都是''死數(shù)據(jù)"，程序設(shè)計(jì)也就成了空談！一句話：設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的目的是為

了對它們進(jìn)行處理，而數(shù)據(jù)處理正是通過相應(yīng)的算法實(shí)現(xiàn)的！

總的來說，一個(gè)算法應(yīng)具有以下5個(gè)重要特性：第一，有窮性：一個(gè)算法必

須總是(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)

間內(nèi)完成；第二，確定性：算法中每條指令必須有確切的含義，讀者理解時(shí)不會

產(chǎn)生二意性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對相同的

輸入只能得到相同的輸出；第三，可行性：一個(gè)算法是能行的，即算法中描述的

操作都是通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的；第四，輸入：一個(gè)算法

有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對象的集合；第五，輸出：一

個(gè)算法有一個(gè)或多個(gè)的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。

8.編寫一個(gè)算法，對三個(gè)兩位數(shù)按由大到小的順序進(jìn)行排序，描述構(gòu)造該算法

的思維程。

算法如下：

voidorder(shorta,shortb,shortc)

(

shortt;

if(a<b){t=a;a=b;b=t;}

if(a<c){t=a;a=c;c=t;}

if(b<c){t=b;b=c;c=t;}

printf('x%d%d%d\nz,,a,b,c);

}

算法對主函數(shù)傳遞過來的三個(gè)短整形變量(由于輸入三個(gè)兩位整數(shù)，所以定

義短整形就足夠了)兩兩進(jìn)行比較，如果前面的數(shù)小于后面的數(shù)的話則進(jìn)行交換,

交換的中間變量用t來存放，交換的最后結(jié)果是三個(gè)變量由大到小排列，最后將

結(jié)果打印輸出。

習(xí)題二答案

1.填空題

(1)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)

(2)p->next=p->next->next;

(3)Head->next==Head(Head為鏈表的頭結(jié)點(diǎn))，Head==NULL(Head

為鏈表的第一個(gè)結(jié)點(diǎn))

(4)Head->next=Head->next->next(Head為鏈表的頭結(jié)點(diǎn))；

Head=Head->next(Head為鏈表的第一個(gè)結(jié)點(diǎn))，以上均假設(shè)鏈表存在至少

兩個(gè)結(jié)點(diǎn)。

(5)D(因?yàn)轫樞虮砭哂须S即存取的優(yōu)點(diǎn))

2.動(dòng)態(tài)與靜態(tài)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲方式有何不同？各有何優(yōu)缺點(diǎn)？

參考答案：

靜態(tài)存儲方式(順序存儲)一邏輯相鄰，物理相鄰。優(yōu)點(diǎn)：便于數(shù)據(jù)的隨即存取，結(jié)點(diǎn)

存儲利用率高(不需要存儲指針)；缺點(diǎn)：存取數(shù)據(jù)時(shí)要移動(dòng)大量的元素，由于事先不

知道存儲結(jié)點(diǎn)的最大個(gè)數(shù)，所以應(yīng)該分配盡可能大的存儲空間，從而可能會造成空間浪

費(fèi)！

動(dòng)態(tài)存儲方式(鏈?zhǔn)酱鎯?一邏輯相鄰，物理不一定相鄰。優(yōu)點(diǎn)：動(dòng)態(tài)分配和釋放存儲

單元，避免了空間浪費(fèi)，插入刪除結(jié)點(diǎn)不需要移動(dòng)大量的其他結(jié)點(diǎn)，只需要修改有限的

指針變量；缺點(diǎn)：不具備順序存儲結(jié)構(gòu)隨即存取的優(yōu)點(diǎn)，查找結(jié)點(diǎn)需要從表頭開始，一

個(gè)結(jié)點(diǎn)的存儲利用率較低，以為每個(gè)結(jié)點(diǎn)都要存儲一個(gè)指向下個(gè)結(jié)點(diǎn)的指針變量。

3.描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)。

參考答案：頭指針一指向頭結(jié)點(diǎn)的指針變量；頭結(jié)點(diǎn)一為了操作鏈表方便而設(shè)置的一

個(gè)特殊的結(jié)點(diǎn)，該結(jié)點(diǎn)用于標(biāo)示一個(gè)鏈表結(jié)構(gòu)的存在，他不存儲實(shí)在的數(shù)據(jù)；第一個(gè)結(jié)

點(diǎn)一鏈表中的第一個(gè)實(shí)際存儲數(shù)據(jù)的結(jié)點(diǎn)，區(qū)別于頭結(jié)點(diǎn)！在有頭結(jié)點(diǎn)的鏈表中第一個(gè)

結(jié)點(diǎn)應(yīng)該是頭結(jié)點(diǎn)后面的那個(gè)結(jié)點(diǎn)。

4.試寫出一個(gè)計(jì)算線性鏈表P中結(jié)點(diǎn)個(gè)數(shù)的算法，其中指針P指向該表中第一個(gè)結(jié)點(diǎn),

尾結(jié)點(diǎn)的指針域?yàn)榭铡?/p>

intcount(datatype*p)/*假設(shè)結(jié)點(diǎn)存儲datatype型的數(shù)據(jù)*/

(

intnum=0;

while(p!=NULL)

(

++num;

p=p->next;

)

returnnum;

)

5.假設(shè)LA、LB為兩個(gè)遞增有序的線性鏈表，試寫出將這兩個(gè)線性鏈表歸并成?個(gè)線

性鏈表LC的操作算法。

/*注意，在主函數(shù)中已經(jīng)對LC數(shù)組進(jìn)行了初始化，長度等于LA和LB長度之和*/

/*假設(shè)數(shù)組LA和LB中存儲著datatype類型的數(shù)據(jù)元素*/

VoidMergeList(datatypeLA[],datatypeLB[],datatypeLC[])

{‘

inti=O,j=O,k=O;

intlenthOfLA=sizeof(LA)/sizeof(datatype);

intlenthOfLB=sizeof(LB)/sizeof(datatype);

while(i<=lenthOfLA-l&&j<=lenthOfLB-l)

{

if(LA[i]<LBrj])

(

LC[k++]=LA[i++];

}

else{LC[k++]=LB[j++];}

)

if(i<=lenthOfLA-l)

(

while(i<=lenthOfLA-1)

(

LC[k++]=LA[i++];

}

)

else

(

while(j<=lenthOfLB-1)

(

LC[k++]=LBrj++]；

6.將學(xué)生成績按成績高低排列建立了一個(gè)有序單鏈表，每個(gè)結(jié)點(diǎn)包括：學(xué)號、姓名和

課程成績。

(1)輸入一個(gè)學(xué)號，如果與鏈表中的結(jié)點(diǎn)的學(xué)號相同，則將此結(jié)點(diǎn)刪除；

(2)在鏈表中插入一個(gè)學(xué)生的記錄，使得插入后鏈表仍然按成績有序排列。

算法提示：

/*聲明一個(gè)學(xué)生的結(jié)構(gòu)體變量*/

typedefstructstudent

(

unsignedid;

unsignedscore;

charname[20];

structstudent*next;

}stuNode;

/*假設(shè)已經(jīng)存在一個(gè)按成績由低到高排列的有序單鏈表*/

(1)/*刪除學(xué)號為idd的學(xué)生結(jié)點(diǎn)的算法，head為鏈表的頭接點(diǎn)*/

voidDelete(stuNode*head,intidd)

(

stuNode*p=head,*q,*s;

q=p；p=p->next;/*從鏈表的第一個(gè)結(jié)點(diǎn)開始查找*/

while(p!=NULL&&p->id!=idd)

q=p；p=p->next;

if(p!=NULL)/*找到要找的結(jié)點(diǎn)*/

(

s=p;q->next=p->next;free(s);/*刪除結(jié)點(diǎn)*/

)..................................

else{printf(''沒有找到您要找的結(jié)點(diǎn)\n〃);)

).................................................................

(2)/*插入學(xué)生結(jié)點(diǎn)node算法，假設(shè)node在主函數(shù)中已經(jīng)創(chuàng)建*/

voidInsertNode(stuNode*head,stuNode*node)

(

stuNode*p=head,*q;

g=p;p=p->next;/*從鏈表的第一個(gè)結(jié)點(diǎn)開始查找*/

if(node->score<p->score)

(

node->next=p;

q->next=node;/*將結(jié)點(diǎn)插入表頭*/

return;/*算法結(jié)束*/

)

while(p!=NULL&&p->score<node->score)

{

q=p；p=p->next;

)

if(p==NULL)

(

q->next=node;/*將結(jié)點(diǎn)插入鏈表的表尾*/

)

else/*插入結(jié)點(diǎn)*/

(

node->next=p;

q->next=node;

)

)

7.某倉庫中有一批零件，按其價(jià)格從低到高的順序構(gòu)成一個(gè)單鏈表存于計(jì)算機(jī)內(nèi)，鏈

表的每一個(gè)結(jié)點(diǎn)說明同樣價(jià)格的若干個(gè)零件?，F(xiàn)在又新有m個(gè)價(jià)格為s的零件需要進(jìn)入

倉庫，試寫出倉庫零件鏈表增加零件的算法。鏈表結(jié)點(diǎn)結(jié)構(gòu)如下：

算法提示：

/*定義一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一種零件的相關(guān)信息*/

typedefstructNODE

{............

floatprice;/*該零件的價(jià)格*/

unsignedlongnumber;/*該零件的數(shù)量*/

structNODE*next;

}Node;

/*在實(shí)結(jié)點(diǎn)為head的單鏈表中插入一個(gè)零件信息結(jié)點(diǎn)node的算法

如下*/

/*假設(shè)該結(jié)點(diǎn)node已經(jīng)在主函數(shù)中創(chuàng)建完畢*/

voidInsertNode(Node*head,Node*node)

{

Node*p=head,*q;

q=p;p=p->next;/*從鏈表的第一個(gè)結(jié)點(diǎn)開始查找*/

if(node->price<p->price)

{一

node->next=p;

q->next=node;/*將結(jié)點(diǎn)插入表頭*/

ruturn;/*算法結(jié)束*/

)

while(p!=NULL&&p->price<node->price)

(

q=p;p=p->next;

)

if(p==NULL)

{...............

q->next=node;/*將結(jié)點(diǎn)插入鏈表的表尾*/

)

else/*插入結(jié)點(diǎn)*/

(

node->next=p;

q->next=node;

)

)

8.設(shè)指針P指向單鏈表的首結(jié)點(diǎn)，指針x指向單鏈表中的任意一個(gè)結(jié)點(diǎn)，寫出在x前

插入一個(gè)結(jié)點(diǎn)i的算法。

算法提示：

/*假設(shè)該鏈表的頭結(jié)點(diǎn)為head,且鏈表中的結(jié)點(diǎn)用Node定義*/

/*在結(jié)點(diǎn)X之前插入結(jié)點(diǎn)i的算法如下*/

voidInsertNode(Node*head,Node*i,Node*X)

(

Node*p=head,*q;

q=p;p=p->next;/*依照題意，p指向鏈表的第一個(gè)結(jié)點(diǎn)*/

if(p==X)/*將結(jié)點(diǎn)插入頭結(jié)點(diǎn)和第一個(gè)結(jié)點(diǎn)之間*/

(

i->next=p;

q->next=i;

return;/*算法結(jié)束*/

)

while(p!=NULL&&p!=X)/*查找插入位置*/

(

q=p;p=p->next;

}

if(p==NULL){returnNULL;}/*查找失敗*/

else

(

i->next=p;

q->next=i;

)

)

9.設(shè)多項(xiàng)式A和B采用線性鏈表的存儲方式存放，試寫出兩個(gè)多項(xiàng)式相加的算法，要

求把相加結(jié)果存放在A中。

算法提示：請參考本章算法3.23和算法3.24。

10.設(shè)指針a和b分別為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針，編寫實(shí)現(xiàn)從單連表La中刪

除自第i個(gè)數(shù)據(jù)元素起，共length個(gè)數(shù)據(jù)元素、并把它們插入到單鏈表Lb中第j個(gè)

元素之前的算法。

算法提示：

voidDInsert(Node*a,Node*b,inti,intj,intlength)

(

Node*ap=a->next,*bp=b->next;/*定義了兩個(gè)分另U處理La和Lb的

兩個(gè)指針變量*/

Node*apl,*ap2,*ap3,*ap4;/*定義了用于處理La的4個(gè)指針變量*/

Node*bpl,*bp2;/*定義了用于處理Lb的2個(gè)指針變量*/

for(intk=l;k<i-l;++k){ap=ap->next;}

apl=ap;ap2=apl->next;

ap=ap2;

for(intk=l;k<length;++k){ap=ap->next;}

ap3=ap;ap4=ap3->next;

apl->next=ap4;/*將La中長度為length的子鏈脫鏈*/

for(intk=l;k<j-1;++k){bp=bp->next;}

bpl=bp;bp2=bpl->next;

ap3->next=bp2;bpl->next=ap2;/*將長度為length的子鏈掛接

到Lb相應(yīng)的位置*/

)

11.設(shè)La和Lb是兩個(gè)有序的循環(huán)鏈表，Pa和Pb分別指向兩個(gè)表的表頭結(jié)點(diǎn)，是寫

一個(gè)算法將這兩個(gè)表歸并為一個(gè)有序的循環(huán)鏈表。

算法提示：本題可以換個(gè)角度考慮，因?yàn)閷τ谘h(huán)鏈表考慮的因素較單鏈表多，所以我

們可以將兩個(gè)循環(huán)鏈表首先處理成兩個(gè)單鏈表(方法：將鏈表的最后一個(gè)結(jié)點(diǎn)的next

域設(shè)置為NULL),這樣問題就轉(zhuǎn)化為將兩個(gè)普通鏈表歸并的問題，最后再把歸并好的單

鏈表轉(zhuǎn)換成循環(huán)鏈表(方法：將鏈表的最后一個(gè)結(jié)點(diǎn)的next域指向該鏈表的頭結(jié)點(diǎn))。

下面我們僅給出單鏈表歸并的算法作為參考，具體的轉(zhuǎn)換由于比較簡單所以這里就不詳

述了：

voidMergeList(Node*pa,Node*pb)

Node*pc=pa;

Node*p1=pa->next,*p2=pb->next;

While(p1!=NULL&&p2!=NULL)

(

if(p1->data<p2->data)

(

pc->next=p1;pc=pc->next;p1=p1->next;

)

else

(

pc->next=p2;pc=pc->next;p2=p2->next;

)

)

if(p1!=NULL){pc->next=p1;}

else{pc->next=p2;}

)

12.已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：pre、data和next,其中

data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為一個(gè)指針域，但是他的值為

空(null),試編寫一個(gè)算法將此單鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)

點(diǎn)的指針域。

算法提示：/*假設(shè)鏈表的頭指針為head,用Node來定義一個(gè)結(jié)點(diǎn)*/

voidConvert(Node*head)

(

Node*p=head,*q;

q=p;p=p->next;/*從鏈表的第一個(gè)結(jié)點(diǎn)開始處理*/

while(p!=head)

(

p_〉pre=q;

q=p；

p=p->next;

}一

p->pre=q;/*構(gòu)成循環(huán)*/}

習(xí)題三答案

2.本題較簡單，可參考本章棧操作示意圖的畫法，答案略。

3.參考答案：棧和隊(duì)列都是操作受限的線性表，因此二者都具備線性表的一般特性；對于棧,

元素進(jìn)棧出棧的原則是“后進(jìn)先出”,即LIFO,對于隊(duì)列，元素進(jìn)出隊(duì)列的原則是“先進(jìn)先出”,

即FIFOo

4.參考答案：1和4。

6.算法提示：利用棧的L1FO特性，如果是左括號則將其壓入棧頂，然后讀取下一個(gè)

字符，如果仍然是左括號，再將其壓入棧頂，依次類推，直到出現(xiàn)右括號為止，這時(shí)將

最靠近棧頂?shù)淖罄ㄌ枏棾?，它一定與該右括號相匹配。下面以圓括號為例給出算法：

intmatch()

seqstacks;

charch;

initstack(&s)

while(2)

ch=getchar()；

if(ch=='$')break;

if(ch=='(')push(&s,ch)；

elseif(ch==')'>

if(stackempty($s))

printf("theparenthessmatchfailed!\n,5)；

return0;

elsepop(&s)；

)、、

if(stackempty(&s))

printf("theparenthnessmatchsuccess!\n,,)5

return1;

)

else

printf("theparenthnessmatchfailed!\n")；

return0;

)

)

8.參考答案：這是由棧的LIFO特性決定的，可參考圖4-4。

9.參考答案：優(yōu)點(diǎn)，不會出現(xiàn)線性隊(duì)列中的隊(duì)頭指針“追上”隊(duì)尾指針的情況，即“假溢出”;

判空條件：隊(duì)頭指針等于隊(duì)尾指針(front==rear)；判滿條件：隊(duì)頭指針指向隊(duì)尾指針的下

一個(gè)位置((rear+1)%MAXSIZE==front)(其中MAXSIZE為隊(duì)列的長度)，約定循環(huán)隊(duì)列

少用?個(gè)元素位。

10.參考答案：由于隊(duì)列是操作受限的線性表，所以該題可以參考第三章第五題的解答(因

為線性表的一般特性同時(shí)適用于隊(duì)列)，除此之外，要特別注意順序存儲的隊(duì)列會出現(xiàn)“假溢

出”狀態(tài)，為了解決這個(gè)問題，可以利用循環(huán)隊(duì)列這種存儲結(jié)構(gòu)，當(dāng)然對于鏈?zhǔn)酱鎯Φ年?duì)列

是不會出現(xiàn)這種問題的。

19.算法提示：

typedefstruct

(

datatypedata[maxsize];

intfront,rear;

intflag;

Jsequeue;

(1)初始化算法

initseq(sequeue*q)

q->data=malloc(maxsize*sizeof(datatype));

q->front=q->rear=-1;

q->flag=0;

)

(2)入隊(duì)列算法

insertseq(sequeue*q,intx)

(

if(q->flag==1)returnNULL;

elseif((q->rear+l)%maxsize==q->front)

(

q->rear=(q->rear+l)%maxsize;

q->data[q->rear]=x;

q->flag=l;

return1;

)

else

|

q->rear=(q->rear+l)%maxsize;

q->data[q->rear]=x;

)

(3)出隊(duì)列算法

datatypedelqueue(sequeue*q)

(

if(q->flag==0)returnNULL;

else

(

q->front=(q>front-1)%maxsize;

if(q->front==q->rear){q->flag=0;}

return(q->data[q->front]);

)

)

12.參考答案，算法提示

intG(intm,intn)

(

if(m==0&&n>=0)return0;

elsereturnG(m-l,2n);

)

棧變化示意圖略。

13.算法提示：

/*棧*/

datatypePop(seqstack*s)

{,

datatypep;

p=s->data[s->top-2];

s->data[s->top-2]=s->data[s->top-1];

-sotop;/*棧頂指針指向棧頂元素的下一個(gè)位置*/

returnp;/*用P返回其值*/

/*隊(duì)列*/

datatypePop(sequeue*q)

{'

datatypep;

p=q->data[q->front-2];

q->data[q->front-2]=q->data[q->front-1];

--q->front;/*隊(duì)頭指針指向補(bǔ)頭元素的卞一個(gè)位置*/

returnp;/*用P返回其值*/

習(xí)題四答案

1.參考答案：遞歸是軟件設(shè)計(jì)中一個(gè)重要的算法設(shè)計(jì)方法和技術(shù)，遞歸子程序是通過調(diào)用

自身來完成與自身要求相同的子問題的求解，并利用系統(tǒng)內(nèi)部功能自動(dòng)實(shí)現(xiàn)調(diào)用過程中信息

的保存與恢復(fù)。

2.算法提示：1*2+2*3+3*4+....+(n-1)*n

intCount(intn)

(

if(n==2)return2；

return(n*(n-1)+Count(n-1))；

}

3.參考答案：功能為計(jì)算0+1+2+3+……+n;改為非遞歸算法如下：

intfunc(intn)

{.n

intmax=();

inti;

for(i=n;i>=0;i—)

{

max+=i;

)

returnmax;

)

4.參考算法：利用遞歸工作棧的工作原理，算法如下：

#definemaxlen200

structst

{.

intno,ns;

charx,y,z;

}stack[maxlen];

其中no存放一個(gè)標(biāo)識，為0時(shí)表示直接移動(dòng)一個(gè)圓盤，為1時(shí)表示需進(jìn)一步分解；ns存放

當(dāng)前圓盤數(shù)；x,y和z表示三個(gè)塔座，由此得到如下函數(shù)：

voidhanoi(n,a,b,c)

intn;

inttop=l,nl,al,bl,cl;

stack[top].no=l;/*初值入棧*/

stack[top].ns=n;

stack[top].x=a;

stack[top].y=b;

stack[top].z=c;

while(top>0)

|

if(stack[topj.no==l)

(

nl=stack[top].ns;

al=stack[top].x;

bl=stack[top].y;

cl=stack[top].z;

stack[top].no=l;

stack[topj.ns=nl-l;

stack[top].x=bl;

stack[top].y=al;

stack[top].z=cl;

top++;

stack[topj.no=0;

stack[top].ns=nl;

stack[top].x=al;

stack[top].y=cl;

top++;

stack[top].no=l;

stack[top].ns=nl-l;

stack[top].x=al;

stack[top].y=cl;

stack[top].z=bl;

)

while(top>0&&(stack[topj.no==Ollstack[topJ.ns==1))

{.........................................

if(top>0&&stack[top].no==0)/*將第n個(gè)圓盤從x移到z

退棧*/

(

printf("\t將第％d個(gè)盤子從％d移動(dòng)

到％c\n”,stack[top].ns,

stack[top].x,stack[top].y);

top-;

)

if(top>0&&stack[top].ns==1)/*退棧*/

(

printf(7將第％d個(gè)盤子從％c移動(dòng)

到%c\n,,,stack[top].ns,

stack[top].x,stack[top].z)；

top--;

)

5.參考算法：

(1)datatypeakm(datatypem,datatypen)

{

if(m==0)returnn+1;

elseif(m!=0&&n==0)returnakm(m-1,1);

elsereturnakm(m-1,akm(m,n-l));

)

(2)同樣可以利用遞歸工作棧的工作原理將上面的遞歸算法進(jìn)行改寫，具體算法略。

6.參考答案：

(1)函數(shù)功能:打印“a/b”的結(jié)果。

(2)intp(inta,intb)

{

if(a<b)return0;

elsereturn(p(a-b,b)+1);

習(xí)題五答案

1.判斷題

(1)X(2)X(3)x(4)7(5)7

2.選擇題

(1)D(2)D(3)D(4)C(5)B(6)B

3.(1)空白串與空串有何區(qū)別？字符串中的空白符號有何意義？

參考答案：空白串(空格串)是由一個(gè)或多個(gè)空格組成的串。它不等于空串，它的

長度是串中包含的空格數(shù)?？沾怯闪銈€(gè)字符組成的串，空串中不包含任何字符，它的

長度是0。字符串中的空白符號表示這個(gè)位置是一個(gè)空格字符。

3.(2)假定串采用塊鏈接表示，試寫出刪除一個(gè)子串的算法。

參考答案：由于采用塊鏈接存儲結(jié)構(gòu)的串對于字符或者子串的插入刪除運(yùn)算存在著

極大的不方便性，所以這里我們將問題簡化：即刪除的子串恰好是該串中的一個(gè)接點(diǎn)(該

結(jié)點(diǎn)中存放著主串的一個(gè)子串)，這樣就把問題簡化為刪除鏈表中一個(gè)結(jié)點(diǎn)的問題，大

大簡化了操作。

/*定義一個(gè)塊結(jié)點(diǎn)*/

typedefstructStrNode

charch[maxOfNode];/*maxOfNode為一個(gè)接點(diǎn)存放子串的最大長度★/

structStrNode*next;/*next指向下—個(gè)接點(diǎn)*/

}StringNode;

/*在一個(gè)頭結(jié)點(diǎn)為head的塊鏈接存儲結(jié)構(gòu)的串string中查找子串str的算法

如下文/

StringNode*Delete(StringNode*headzchar*str)

(

StringNode*qz*p=head;

q=p;p=p->next;/*從第一個(gè)結(jié)點(diǎn)開始查找文/

while(strcmp(str,p->ch)!=0)/*開始查找合適的結(jié)點(diǎn)*/

(

q=p；

p=p->next;

)

q->next=p->next;

free(p);

returnhead;

}

3.(3)比較串的三種存儲方式的優(yōu)點(diǎn)和缺點(diǎn)。

參考答案：(1)順序存儲結(jié)構(gòu)一優(yōu)點(diǎn)：存儲密度高(不需要存儲指針變量)，可以

隨機(jī)存取串中的字符；缺點(diǎn)：存取字符時(shí)要移動(dòng)大量的元素，由于事先不知道存儲字符

的最大數(shù)目，所以應(yīng)該分配盡可能大的靜態(tài)存儲空間，從而造成了空間浪費(fèi)！

(2)單鏈表式存儲結(jié)構(gòu)一優(yōu)點(diǎn)：插入刪除一個(gè)結(jié)點(diǎn)不需要移動(dòng)大量的元素，只需

要修改有限的指針變量，可以隨機(jī)分配和釋放結(jié)點(diǎn)空間，避免了空間浪費(fèi)；缺點(diǎn)：結(jié)點(diǎn)

的存儲密度低(因?yàn)槊總€(gè)結(jié)點(diǎn)要存儲指向F-個(gè)結(jié)點(diǎn)的指針變量)，查找結(jié)點(diǎn)要從頭開

始順序查找，不具備隨即存取的機(jī)制！為此人們設(shè)計(jì)了一種叫做塊鏈結(jié)點(diǎn)的存儲結(jié)構(gòu)，

雖然在結(jié)點(diǎn)的存儲密度上較以前有了改進(jìn)，但是卻給插入刪除字符元素或者子串帶來了

意想不到的麻煩！

(3)堆結(jié)構(gòu)的存儲方式一優(yōu)點(diǎn)：動(dòng)態(tài)分配存儲空間，避免了空間浪費(fèi)。

3.(4)已知：s='xyz*',t='(x+y)*z'.試?yán)寐?lián)接、求子串和置換等基本運(yùn)算,將s轉(zhuǎn)換為

to

參考答案：

t=Concation(11(,,,SubString(sub1,s,1,1,

SubString(sub2,s,2,1),4€),,,swap(SubString(sub3,s,3,2)))

其中swap的作用是交換兩個(gè)字符的位置，SubString和Concation的作用分別是求子串

和串聯(lián)接。

3.⑸試分別寫出算法insert(a,i,b)和算法delete(a,b)。其中，insert(a,i,b)將串b插入在串a(chǎn)

中位置i之后；delete(a,b)將串a(chǎn)中的子串b刪掉。

參考答案：假設(shè)字符串按順序方式存儲。

voidinsert(char*a,inti,char*b)

intpos;

intp;

intlenthOfStra=sizeof(a)/sizeof(char);/*a串的長度*/

intlenthOfStrb=sizeof(b)/sizeof(char);/*b串的長度*/

for(pos=0;pos<i-l;++pos);/*pos指向位亶i-1,注意數(shù)組下標(biāo)

開始于0*/

for(p=lenthOfStra-l;p>=pos;—p)

(

a[p+LenthOfStrb]=a[p];/*給串b讓出足夠的空間*/

)

for(p=0;p<=lenthOfStrb-1;)

(

a[pos++]=b[p++];/*將串b插入到串a(chǎn)對應(yīng)的位置*/

)

)

voiddelete(char*a,char*b)

(

intlenthOfStra=sizeof(a)/sizeof(char);/*a串的長度*/

intlenthOfStrb=sizeof(b)/sizeof(char);/*b串的長度*/

/*調(diào)用KMP算法確定串a(chǎn)中首次出現(xiàn)串b的位置并賦值給

pos*/

intpos=KMPIndex(char*a,char*b);

intp;

for(p=pos+lenthOfStrb;p<=lenthOfStra-l;++p)

(

a[p-lenthOfStrb]=a[p];

)

a[p-lenthOfStrb]='\0’;

習(xí)題六答案

i.判斷題

（1）x（2）x（3）q（4）x（5）q（6）u（7）q

2.單選題

（1）B（2）C（3）E,A,B（4）C（5）D

習(xí)題七答案

1.判斷題

(1)Y(2)4(3)X(4)X(5)X(6)X(7)X(8)7(9)X

2.單選題

(1)B(2)B(3)A(4)D(5)B(6)C(7)A(8)B(9)D(10)C

3.(1)參考答案：

(1)由于樹結(jié)點(diǎn)的孩子沒有左右之分，所以三個(gè)結(jié)點(diǎn)的樹的形態(tài)只有2種:

00

00I

0

(2)由于二叉樹的結(jié)點(diǎn)孩子具有左右之分,所有四個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)有14種：

3.(2).參考答案：

(1)順序存儲方法存儲該二叉樹示意圖如下:

T:0123456789101112131415

結(jié)

點(diǎn)ABCDEFGH

(2)鏈接存儲方法存儲該二叉樹示意圖如下

IW。1NI■H|A|

3.(3)參考答案：

該二叉樹如下所示：

(4).參考答案：提示：葉子結(jié)點(diǎn)即度為0的結(jié)點(diǎn)，設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為no,并設(shè)樹中結(jié)點(diǎn)

的總數(shù)為N,由此可以得到兩個(gè)方程：

no+nl+n2+n34-.......+nm=N................(1)

nl+2*n2+3*n3+.......+m*nm=N-1.................(2)

解上面的方程組可得葉子結(jié)點(diǎn)的個(gè)數(shù)為：l+n2+2n3+3n4+........+(m-l)nm.

(5).參考答案:AA

C

(b)

(c)

(6).參考答案:

(7).參考答案：

(1)前序序列：ABDECFGHIJKLMNOP(等于與之對應(yīng)的二叉樹的先序遍歷)

(2)后序序列：EDBGFCAJKLIHPONM(等于與之對應(yīng)的二叉樹的中序遍歷)

(8).參考答案:

經(jīng)過計(jì)算該哈夫曼樹的WPL值為：(3+4)*4+7*3+(14+15+20)*2=147

4.1.算法設(shè)計(jì)思想：對該二叉樹進(jìn)行中序遍歷，將遍歷結(jié)果存放于一個(gè)一維全局?jǐn)?shù)組中，再

判斷該數(shù)組中的數(shù)據(jù)是否由小到大排列，如果是則該二叉數(shù)為一棵二叉排序樹。

intorder[maxsize];/*定義一個(gè)全局?jǐn)?shù)組，其中maxsize為該二叉樹的最大結(jié)點(diǎn)個(gè)數(shù)*/

inti=0;/*定義-一個(gè)記位指針i*/

typedefstructBtreeNode/*定義一個(gè)二叉樹的結(jié)點(diǎn)*/

(

intdata;

structBTreeNode*lchild;

structBTreeNode*rchild;

}*Btree;

/*中序遞歸遍歷二叉樹T*/

voidInorder(BtreeT)

(

if(T==NULL)

return;/*遞歸出口*/

/*中序遞歸遍歷二叉樹T->lchild*/

if(T->lchild!=NULL)

Inorder(T->lchild);

order[i++|=T->data;/*將訪問到的結(jié)點(diǎn)放入數(shù)組中，并對記位指針i加一*/

/*中序遍歷二叉樹T->rchild*/

if(T->rchild!=NULL)

Inorder(T->rchild);

/*判斷該數(shù)組里面的數(shù)據(jù)是否由小到大排列，若是則其為一棵二叉排序樹*/

voidTest(intorder[])

intj;

intk=sizeof(order)/sizeof(order[0]);/*計(jì)算數(shù)組的長度*/

for(j=0;j<k-l;j++)

(

if(order[j]>order[j+1])break;

)

if(j=k-l)printf(“該二叉樹為二叉排序樹\n")；

elseprintf(“該二叉樹不是二叉排序樹\n")；

)

4.2.具體算法如下：

typedefstructBtreeNode/*定義一個(gè)二叉樹的結(jié)點(diǎn)*/

(

intdata;

structBTreeNode*lchild;

structBTreeNode*rchild;

}*Btree

/*計(jì)算二叉樹高度的遞歸算法如下*/

intdepth(BtreeT)

(

intd,p=0;/*p記錄該二叉樹的高度，初始值等于0*/

if(T==NULL)returnp;/*空二叉樹的高度為0*/

else

(

d=depth(T->lchild);/*考慮該二叉樹的左子樹，遞歸調(diào)用*/

if(d>p)p=d;/*p始終記錄最大的子樹高度*/

d=depth(T->rchild);/*考慮該二叉樹的右子樹，遞歸調(diào)用*/

if(d>p)p=d;/*p始終記錄最大的子樹高度*/

)

return(p+1);/*子樹的最大高度加1為返回樹的高度*/

)

4.4.算法如下：

#defineTreeSize100

#defineStackSizeTreeSize/2

voidexit(int);

typedefstruct

(

charnodes[TreeSize];

intnum;

JBTree;

typedefstruct

intsfStackSize];

inttop;

}SeqStack;

voidInitStack(SeqStack*s)

{s->top=-l;}

intStackEmpty(SeqStack*s)

{returns->top==-1;}

voidpush(SeqStack*s,intx)

(

if(s->top>=StackSize){

printf(44Error:thestackisoverflow!\n^^);

exit(-2);

)

s->s[++s->top]=x;

)

intpop(SeqStack*s)

(

if(StackEmpty(s){

printfC4Error:thestackisoverflowin'');

exit(-2);

)

returns->s[s->top];

)

voidpreorders(BTree*tree)

(

inti=l;

SeqStacks;

InitStack(&s);

If(tree->num>0)

do

(

printfC%cM,tree->nodes[i]);

while(i*2<=tree->num){

if(i*2+1<=tree->num)push(&s,i*2+1);

i*=2;

printfC%c5,,tree->nodes[i];

)

if(!StackEmpty(&s))i=pop($s);

elsebreak;

}while(2);

4.5.遞歸算法如下：卜面的num和leaf函數(shù)分別計(jì)算二叉樹結(jié)點(diǎn)總數(shù)和葉子總數(shù)。

typedefchardatatype;

typedefstructnode{

datatyped;

structnode*lchild,*rchild;

JBinNode;

typedefBinNode*BinTree;

intnum(BinTreep)

(

if(!p)return0;

elsereturn1+num(p->lchild)+num(p->rchild);

)

intleaf(BinTreep)

(

if(!p)return0;

else

(

if(p->lchild==NULL&&p->rchild==NULL)return1;

elsereturn(leaf(p->lchild)+leaf(p->rchild);

)

)

4.6.參考答案：假設(shè)用于通信的電文與出現(xiàn)的概率依次為：a(7),b(19),c(2),d(6),e

(32),f(3),g(21),h(10),則最終得到的哈夫曼編碼依次為:a(0010),b(10),c(00000),d

(0001),e(01),f(00001),g(11),h(0011)；具體實(shí)現(xiàn)可以參考本章算法7.5。

37.計(jì)算二叉樹寬度的算法如下(計(jì)算二叉樹高度的算法可以參考本章習(xí)題15)：

typedefstruct{

intfront,rear;

intcount;

BinNode*datas[QueueSize];

JCirQueue;

voidInitQueue(CirQueue*Q)

{Q->front=Q->rear=Q->count=0;}

intQueueEmpty(CirQueue*Q)

{returnQ->front==0;}

intQueueFull(CirQueue*Q)

{returnQ->count==QueueSize;}

voidEnQueue(CirQueue*Q,BinNode*p)

(

if(QueueFull(Q))

(

print(uError:thequeueisfull!\n^^);

exit(-2);

Q->count++;

Q->data[Q->rear]=p;

Q->rear=(Q->rear+1)%QueueSize;

)

BinNode*DeQueue(CirQueue*Q)

{

BinQueue*t;

If(QueueEmpty(Q){

Printf(uError:thequeueisempty!\n");

Exit(-2);

)

t=Q->data[Q->front];

Q->count—;

Q->front=(Q->front+l)%QueueSize;

Returnt;

)

intwidth(BinNode*p)

{

CirQueueq;

BinNode*t;

intmax-width=O,width=O;

InitQueue(&q,p);

if(P)

(

EnQueue(&q,p);

EnQueue(&q,NULL);

While(!QueueEmpty(&q))

(

t=DeQueue(&q);

if(t)

(

width++;

if(t->lchild)EnQueue(&q,t->lchild);

if(t->rchild)EnQueue(&q,t->rchild);

)

else

if(!QueueEmpty(&q))EnQueue(&q,NULL);

if(width>max-width=width;

width=O;

returnmax-width;

)

習(xí)題八答案

1.答：(1)V(2)X(3)V(4)x(5)x(6)V(7)7(8)V(9)X(10)X(11)V

(12)7(13)7

2.答：(1)D(2)B(3)B(4)B(5)A(6)B(7)D(8)C(9)C、D(10)D(11)

A

5.答：①ID(A)=1OD(A)=3

ID(B)=2OD(B)=1

ID(C)=2OD(C)=1

ID(D)=2OD(D)=1

?

3.(2).答：①鄰接矩陣

3.(3).答：是連通圖。因?yàn)槊恳粚旤c(diǎn)間都有路徑存在，所以該圖是連通的。

深度優(yōu)先搜索遍歷：A,B,D,C,F,H,E

廣度優(yōu)先搜索遍歷：A,B,D,C,E,F,H

3.(4).答：①普里姆算法構(gòu)造過程如下：

3.(5).答：

①

(1)各結(jié)點(diǎn)的最早開始時(shí)間

VE(1)=O

VE(2)=VE(1)+dut?1,2?=0+8=8

VE(3)=VE(1)+dut?1,3?=0+6=6

VE(4)=Max{VE(2)+dut?2,4?+VE(3)+dut?3,4?}=Max{11,16)=16

VE(5)=VE(1)+dut?1,5?=0+7=7

VE(7)=Max{VE(3)+dut?3,7?,VE(5)+dut?5,7?}=Max{15,16)=16

VE(6)=VE(4)+dut?4,6?=16+4=20

VE(8)=Max{VE(5)+dut?5,8?,VE(7)+dut?7,8?}=Max{20,18}=20

VE(9)=Max{VE(4)+dut?4,9?,VE(7)+dut?7,9?,VE(8)+dut?8,9?}=Max{35,24,26}=35

VE(10)=Max{VE(6)+dut?6,10?,VE(9)+dut?9,10?}=Max{34,45)=45

(2)各結(jié)點(diǎn)的最遲發(fā)生時(shí)間

VL(10)=VE(10)=45

VL(9)=VL(10)-dut?9,10?=35

VL(8)=VL(9)-dut?8,9?=29

VL(7)=Min{VL(8)-dut?7,8?,VL(9)-dut?7,9?}=Min{27,27)=27

VL(6)=VL(10)-dut?6,10?=31

VL(5)=Min{VL(7)-dut?5,7?,VL(8)-dut?5,8?}=Min{18,16}=16

VL(4)=Min{VL(6)-dut?4,6?,VL(9)-dut?4,9?}=Min{27,16}=16

VL(3)=Min{VL(4)-dut?3,4?,VL(7)-dut?3,7?}=Min{6,18}=6

VL(2)=VL(4)-dut?2,4?=13

VL(l)=Min{VL(2)-dut?1,2?,VL(3)-dut?1,3?,VL(5)-dut?1,5?}=Min{5,0,9)=0

根據(jù)各結(jié)點(diǎn)的最早開始時(shí)間和最遲發(fā)生時(shí)間計(jì)算出各活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間

E?vl,v2?=0L?vl,v2?=5

E?vl,v3?=0L?vl,v3?=0

E?vl,v5?=0L?vl,v5?=9

E?v2,v4?=8L?v2,v4?=13

E?v3,v4?=6L?v3,v4?=6

E?v3,v7?=6L?v3,v7?=16

E?v5,v7?=7L?v5,v7?=16

E?v5,v8?=7L?v5,v8?=16

E?v4,v6>)=16L?v4,v6>)=27

E?v4,v9?=16L?v4,v9?=16

E?v7,v9?=16L?v7,v9>)=27

E?v7,v8?=16L?v7,v8?=27

E?v8,v9?=20L?v8,v9>)=29

E?v6,vl0?=20L?v6,vl0?=31

E?v9,vl0?=35L?v9,vl0〉)=35

②完成整個(gè)工程的最短時(shí)間是45

③網(wǎng)中的關(guān)鍵活動(dòng)：<vl,v3>,<v3,v4>,<v4,v9>,<v9,vl0>

四.⑴答:

ttdefinemaxnode30

Sinclude<stdio.h>

typedefintelemtype

typedefstructarc{

intadjvertex;

struct