2023年研究生類研究生入學(xué)考試專業(yè)課計(jì)算機(jī)學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解

2023年研究生類研究生入學(xué)考試專業(yè)課計(jì)算機(jī)學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共25題)1.以下算法是在一個(gè)有n個(gè)數(shù)據(jù)元素的數(shù)組A中刪除第i個(gè)位置的數(shù)組元素，要求當(dāng)刪除成功時(shí)數(shù)組元素個(gè)數(shù)減1，求平均刪除一個(gè)數(shù)組元素需要移動(dòng)的元素個(gè)數(shù)是多少?其中，數(shù)組下標(biāo)從0至n-1。

intdelete(intA[],intn,inti)

{

intj;

if(i＜0||i＞n)

return0;

for(j=i+1;j＜n;++j)

A[j-1]=A[j];

--n;

return1;

}2.棧和隊(duì)列的主要區(qū)別在于______。A.它們的邏輯結(jié)構(gòu)不一樣B.它們的存儲(chǔ)結(jié)構(gòu)不一樣C.所包含的運(yùn)算不一樣D.插入和刪除運(yùn)算的限定不一樣3.以下有關(guān)平衡二叉樹的說法中正確的是______。A.平衡二叉樹是高度最小的二叉排序樹B.平衡二叉樹一定是豐滿樹C.平衡二叉樹上任一結(jié)點(diǎn)的平衡因子不能超過1D.有n個(gè)結(jié)點(diǎn)的平衡二叉樹的高度為O(log2n)4.編寫一個(gè)算法，將m(m≥2)個(gè)有序(從小到大)順序表合并成一個(gè)有序順序表，合并過程中不另設(shè)新的順序表存儲(chǔ)。5.下面函數(shù)的功能是實(shí)現(xiàn)分塊查找，空白處應(yīng)該添加的內(nèi)容是______。

intBlkSearch(int*nz,intkey,intblock,intBLK,intlen)

{

inti;

block=block-1;

if(len＜=0)

{

puts("表為空!");

return0;

}

if(BLK＞len)BLK=len;

for(i=block*BLK;i＜(block+1)*BLK&&nz[i]!=0;i++)

{

if(______)

{

printf("找到第%d個(gè)數(shù)是%d\n",i,key);

return0;

}

}

printf("\n");

printf("查找結(jié)束\n");

return0;

}A.nz[i]==keyB.nz[i]==BLKC.nz[1i]==blockD.nz[i]==06.對(duì)一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些?7.設(shè)線性表中有2n個(gè)元素，以下操作中，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高的是______。A.刪除指定元素B.在最后一個(gè)元素的后面插入一個(gè)新元素C.順序輸出前k個(gè)元素D.交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，…，n-1)8.就平均性能而言，目前最好的排序算法是______。A.選擇排序B.快速排序C.冒泡排序D.插入排序9.二叉排序樹采用二叉鏈表存儲(chǔ)。寫一個(gè)算法，刪除結(jié)點(diǎn)值是X的結(jié)點(diǎn)。要求刪除該結(jié)點(diǎn)后，此樹仍然是一棵二叉排序樹，并且高度沒有增長(注意：可不考慮被刪除的結(jié)點(diǎn)是根的情況)。10.設(shè)圖有n個(gè)頂點(diǎn)和e條邊，在采用鄰接矩陣時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為______；在采用鄰接表時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為O(n+e)。A.O(n)B.O(n2)C.O(e)D.O(n×e)11.根據(jù)一個(gè)結(jié)點(diǎn)數(shù)據(jù)類型為整型的單鏈表生成兩個(gè)單鏈表，第一個(gè)單鏈表中包含原單鏈表中所有數(shù)據(jù)值為奇數(shù)的結(jié)點(diǎn)，第二個(gè)單鏈表中包含原單鏈表中所有數(shù)據(jù)值為偶數(shù)的結(jié)點(diǎn)，原有單鏈表保持不變。12.使用散列函數(shù)：

H(k)=3kmod11

并采用開放地址法處理沖突，所求下一地址函數(shù)為

d1=H(k)

di=(di-1+((7kmod10)+1)%11(i=2，3，…)

試在0～10的散列地址空間中對(duì)關(guān)鍵字序列(22，41，53，46，30，13，01，67)構(gòu)造哈希表，求等概率情況下查找成功的平均查找長度，并設(shè)計(jì)構(gòu)造哈希表的完整的算法。13.棧在______中應(yīng)用。A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.以上都是14.設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為

。A.3B.4C.5D.615.敗者樹的外結(jié)點(diǎn)存放的是各歸并段當(dāng)前參加歸并的記錄，如下圖所示，外結(jié)點(diǎn)的編號(hào)0，1，2，…，m-1代表各歸并段的編號(hào)，敗者樹的內(nèi)結(jié)點(diǎn)存放子女結(jié)點(diǎn)兩兩比較的敗者的歸并段編號(hào)，內(nèi)結(jié)點(diǎn)編號(hào)也是0，1，…，m-1。編號(hào)為i的外結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為______。

A．

B．

C．

D．16.關(guān)于B-樹，下列說法不正確的是______。A.B-樹是一種查找樹B.所有的葉結(jié)點(diǎn)具有相同的高度C.2-3樹中，所有非葉子結(jié)點(diǎn)有1或者3個(gè)孩子結(jié)點(diǎn)D.通常情況下，B-樹不是二叉樹17.已有鄰接表表示的有向圖，請(qǐng)編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡單路徑，若有則打印出該路徑上的頂點(diǎn)。18.設(shè)計(jì)一個(gè)算法指出一個(gè)無序數(shù)序中的任意一個(gè)元素是第幾大元素(從小到大數(shù))，要求比較的次數(shù)最少。19.用n個(gè)權(quán)值構(gòu)造出來的Huffman樹的結(jié)點(diǎn)個(gè)數(shù)是______。A.2n-1B.2nC.2n+1D.n+120.采用順序結(jié)構(gòu)存儲(chǔ)串，編寫一個(gè)函數(shù)index(s1，s2)，用于判定s2是否是s1的子串。若是子串，返回其在主串中的位置；否則返回-1。21.將下圖中的二叉樹按中序線索化，結(jié)點(diǎn)e的右指針和結(jié)點(diǎn)g的左指針分別指向______。

A.a，dB.b，cC.d，aD.c，a22.已知一個(gè)棧的進(jìn)棧序列為1，2，3，…，n，其輸出序列是p1，p2，p3，…，pn。若p1=3，則p2的值______。A.一定是2B.一定是1C.可能是1D.可能是223.執(zhí)行完下列語句段后，i值為______。

intf(intx){return((x＞0)?x*f(x-1);2);}

i=f(f(1));A.2B.4C.8D.無限遞歸24.在下列有關(guān)關(guān)鍵路徑的說法中錯(cuò)誤的是______。A.在AOE網(wǎng)絡(luò)中可能存在多條關(guān)鍵路徑B.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間C.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D.所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成25.自由樹(即無環(huán)連通圖)T=(V，E)的直徑是樹中所有點(diǎn)對(duì)點(diǎn)之間最短路徑長度的最大值，即T的直徑定義為d(u，v)的最大值(其中u，v∈V)。這里d(u，v)表示頂點(diǎn)u到頂點(diǎn)v的最短路徑長度(路徑長度為路徑中包含的邊數(shù))。如圖所示為一棵自由樹，其直徑為18。試寫算法求T的直徑，并分析算法的時(shí)間復(fù)雜度。

第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：當(dāng)刪除最后一個(gè)元素時(shí)，移動(dòng)的元素個(gè)數(shù)為0；當(dāng)刪除倒數(shù)第二個(gè)元素時(shí)，移動(dòng)的元素個(gè)數(shù)為1；…；當(dāng)刪除第一個(gè)元素時(shí)，移動(dòng)的元素個(gè)數(shù)為n-1。也就是說，當(dāng)刪除第i個(gè)元素時(shí)，移動(dòng)的元素個(gè)數(shù)為n-i，設(shè)P為刪除第i個(gè)位置上數(shù)據(jù)元素的概率，則有Pi=1/n，平均刪除一個(gè)數(shù)組元素需要移動(dòng)的元素個(gè)數(shù)是

2.參考答案：D棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，有可能包含的運(yùn)算不一樣，但不是其主要區(qū)別。任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)所包含的運(yùn)算都可能不同。所以正確答案是D。3.參考答案：D[解析]有n個(gè)結(jié)點(diǎn)的平衡二叉樹的最小高度hmin=rlog2(n+1)l，最大高度hmax＜1.44×log2(n+1)，因此選項(xiàng)D是正確的。由于平衡二叉樹的中低層有可能沒有填滿，存在度為1的結(jié)點(diǎn)，只要每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差的絕對(duì)值不超過1即可，所以其高度有可能不是最小，因此選項(xiàng)A不對(duì)。豐滿樹即理想平衡樹，要求除最底層外其他層都是滿的，平衡二叉樹沒有這樣高的要求，因此選項(xiàng)B不對(duì)。對(duì)于C選項(xiàng)，應(yīng)該是平衡二叉樹上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不能超過1。4.參考答案：將線性表A和B合并的過程如下：從A的最后一個(gè)元素和B的第一個(gè)元素開始分別向前、向后進(jìn)行比較，將較大的元素先定位在A中。

代碼如下：

intComb1(intA[],intna,intB[],intnb)

{

intn=na,m=0;

while(m＜nb)

if(n==0||A[n-1]＜B[m])

{

A[n+nb-m-1]=B[m];

//說明B[m]是第n+nb-m大的元素

++m;

}

else

{

A[n+nb-m-1]=A[n-1];

//說明A[n-1]是第n+nb-m大的元素

--n;

}

returnna+nb;

}5.參考答案：A如果當(dāng)前的值與所查找關(guān)鍵字相等，則完成查找。6.參考答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。遍歷不唯一的因素有：開始遍歷的頂點(diǎn)不同；存儲(chǔ)結(jié)構(gòu)不同；在鄰接表情況下鄰接點(diǎn)的順序不同。7.參考答案：A對(duì)于A，刪除指定元素，在順序表中需要移動(dòng)較多元素，而在單鏈表上執(zhí)行同樣的操作不需要移動(dòng)元素，因此單鏈表的效率要高一些。

對(duì)于B，在最后一個(gè)元素的后面插入一個(gè)新元素不需要移動(dòng)元素，順序表的效率和單鏈表相同。

對(duì)于C，順序輸出前k個(gè)元素，單鏈表和順序表的效率幾乎相同。

對(duì)于D，交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，…，n-1)，由于順序表可以實(shí)現(xiàn)隨機(jī)查找，因此順序表的效率會(huì)更高一些。8.參考答案：B[解析]目前，平均性能最好的排序是快速排序。9.參考答案：在二叉排序樹上刪除結(jié)點(diǎn)，首先要查找該結(jié)點(diǎn)。查找成功后，若該結(jié)點(diǎn)無左子樹，則可直接將其右子樹的根結(jié)點(diǎn)接到其雙親結(jié)點(diǎn)上；若該結(jié)點(diǎn)有左子樹，則將其左子樹中按中序遍歷的最后一個(gè)結(jié)點(diǎn)代替該結(jié)點(diǎn)，從而不增加樹的高度。

voidDelete(BSTreebst,keytypeX){

//在二叉排序樹bst上，刪除其關(guān)鍵字為X的結(jié)點(diǎn)

BSTreef,p=bst;

while(p&&p-＞key!=X)

//查找值為X的結(jié)點(diǎn)

if(p-＞key＞X){f=p;p=p-＞lchild;}

else{f=p;p=p-＞rchild;}

if(p==null){printf("無關(guān)鍵字為X的結(jié)點(diǎn)\n");exit(0);}

if(p-＞lchild==null){

//被刪結(jié)點(diǎn)無左子樹

if(f-＞lchild==p)f-＞lchild=p-＞rchild;

//將被刪結(jié)點(diǎn)的右子樹接到其雙親上

elsef-＞rchild=p-＞rchild;

}

else{q=p;s=p-＞lchild;

//被刪結(jié)點(diǎn)有左子樹

while(s-＞rchild!=null)

//查左子樹中最右下的結(jié)點(diǎn)(中序最后結(jié)點(diǎn))

{q=s;s=s-＞rchild;}

p-＞key=s-＞key;

//結(jié)點(diǎn)值用其左子樹最右下的結(jié)點(diǎn)的值代替

if(q==p)p-＞lchild=s-＞lchild;

//被刪結(jié)點(diǎn)左子樹的根結(jié)點(diǎn)無右子女

elseq-＞rchild=s-＞lchild;

//s是被刪結(jié)點(diǎn)左子樹中序序列最后一個(gè)結(jié)點(diǎn)

free(s);

}

}10.參考答案：B[解析]存儲(chǔ)結(jié)構(gòu)為鄰接矩陣的圖的遍歷算法要對(duì)所有頂點(diǎn)都訪問一次，每次訪問時(shí)為確定下一次要訪問哪個(gè)頂點(diǎn)，需遍歷該頂點(diǎn)的行向量，尋找該頂點(diǎn)的所有鄰接頂點(diǎn)，所以遍歷的時(shí)間復(fù)雜度為O(n2)。而對(duì)于存儲(chǔ)結(jié)構(gòu)為鄰接表的圖的遍歷算法也要對(duì)所有頂點(diǎn)訪問一次，每次訪問時(shí)為確定下一次要訪問哪個(gè)頂點(diǎn)，需遍歷該頂點(diǎn)的邊鏈表，所以時(shí)間復(fù)雜度為O(n+e)。11.參考答案：voidSeparate(LNode*&HL,LNode*&L1,LNode*&L2)

{

//將一個(gè)單鏈表HL按各個(gè)結(jié)點(diǎn)中數(shù)據(jù)的奇偶性拆分成兩個(gè)單鏈表L1和L2

LNode*r1,*r2,*p,*s;

r1=L1=(LNode*)malloc(sizeof(LNode));

r2=L2=(LNode*)malloc(sizeof(LNode));

p=HL→next;

//鏈表HL的掃描指針

while(p!=NULL)

//對(duì)原鏈表的結(jié)點(diǎn)逐個(gè)進(jìn)行檢測(cè)

{

s=(LNode*)malloc(sizeof(LNode));

//創(chuàng)建新結(jié)點(diǎn)

s→data=p→data;

if(p→data%2==1)

//奇數(shù)

{

r1→next=s;

r1=s;

}

else

//偶數(shù)

{

r2→next=s;

r2=s;

}

p=p→next;

}

r1→next=NULL;r2→next=NULL;

}12.參考答案：本題的哈希表構(gòu)造過程如下：

(1)H(22)=3*22mod11=0比較1次

(2)H(41)=3*41mod11=2比較1次

(3)H(53)=3*53mod11=5比較1次

(4)H(46)=3*46mod11=6比較1次

(5)H(30)=3*30mod11=2沖突

d1=H(30)=2

H(30)=(2+(7*30mod10)+1)mod11=3比較2次

(6)H(13)=3*13mod11=6沖突

d1=H(13)=6

H(13)=(6+(7*13mod10)+1)mod11=8比較2次

(7)H(1)=3*01mod11=3沖突

d1=H(1)=3

H(1)=(3+(1*7mod10)+1)mod11=0沖突

d2=H(1)=0

H(1)=(0+(1*7mod10)+1)mod11=8沖突

d3=H(1)=8

H(1)=(8+(1*7mod10)+1)mod11=5沖突

d4=H(1)=5

H(1)=(5+(1*7mod10)+1)mod11=2沖突

d5=H(1)=2

H(1)=(2+(1*7mod10)+1)mod11=10比較6次

(8)H(67)=3*67mod11=3沖突

d1=H(67)=3

H(67)=(3+(7*67mod10)+1)mod11=2沖突

d2=H(67)=2

H(67)=(2+(7*67mod10)+1)mod11=1比較3次

構(gòu)造本哈希表的程序代碼如下：

structhterm

{

intkey;

//關(guān)鍵字值

intsi;

//散列次數(shù)

};

structhtermhlist[M];

//假設(shè)M=11是已定義的常量

inti,adr,sum,d;

intx[N]={22,41,53,46,30,13,1,67};

//關(guān)鍵字賦值

//假設(shè)N=8是已定義的常量

floataverage;

voidchash()

//創(chuàng)建哈希表

{

for(i=0;i＜M;++i)

//置初值

{

hlist[i].key=0;

hlist[i].si=0;

}

for(i=0;i＜N;++i)

{

sum=0;

adr=(3*x[i])%M;

d=adr;

if(hlist[adr].key==0)

{

hlist[adr].key=x[i];

hlist[adr].si=1;

}

else

{

do

//處理沖突

{

d=(d+(x[i]*7)%10+1)%M;

sum=sum+1;

}while(hlist[d].key!=0);

hlist[d].key=x[i];

hlist[d].si=sum+1;

}

}

}13.參考答案：D[解析]棧的基本應(yīng)用有數(shù)制轉(zhuǎn)換(十轉(zhuǎn)N)，括號(hào)匹配的檢驗(yàn)，表達(dá)式求值，漢諾儀(Hanoi)塔；隊(duì)列的基本應(yīng)用是模擬事件發(fā)生的順序。14.參考答案：C由完全二叉樹原理可以知道，完全三叉樹如有n個(gè)葉結(jié)點(diǎn)，則高度為

log3n+1。15.參考答案：C[解析]編號(hào)為i的外結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為t=[(i+m)/2]。如下圖中外結(jié)點(diǎn)0的父結(jié)點(diǎn)為編號(hào)[(0+5)/2]=2的內(nèi)結(jié)點(diǎn)，外結(jié)點(diǎn)4的父結(jié)點(diǎn)為[(4+5)/2]=4編號(hào)的內(nèi)結(jié)點(diǎn)。

16.參考答案：C[解析]B-樹定義如下：

一棵m階B-樹，或者是空樹，或者是滿足以下性質(zhì)的m叉樹：

(1)根結(jié)點(diǎn)或者是葉子結(jié)果，或者至少有兩棵子樹，至多有m棵子樹；

(2)除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有1棵子樹，至多有m棵子樹；

(3)所有葉子結(jié)點(diǎn)都在樹的同一層上；

(4)每個(gè)結(jié)點(diǎn)應(yīng)包含如下信息：(n，A0，K1，A0，A1，A2，…，Kn，An)其中：

K(1≤i≤n)是關(guān)鍵字，且K＜Ki+1(1≤i≤n-1)

Ai(i=0，1，…，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki，Ai所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki；

n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且-1≤n≤m-1，n+1為子樹的棵數(shù)。17.參考答案：

voidAllpath(AdjListg,vertypeu,vertypev){

//求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡單路徑，初始調(diào)用形式

inttop=0,s[];

s[++top]=u;visited[u]=1;

while(top＞0||p){

p=g[s[top]].firstarc;

//第一個(gè)鄰接點(diǎn)

while(p!=null&&visited[p-＞adjvex]==1)p=p-＞next;

//下一個(gè)訪問鄰接點(diǎn)表

if(p==null)top--;

//退棧

else{

i=p-＞adjvex;

//取鄰接點(diǎn)(編號(hào))

if(i==v){

//找到從u到v的一條簡單路徑，輸出

for(k=1;k＜=top;k++)printf("%3d",s[k]);

printf("%3d\n",v);

}//if

else{visited[i]=1;s[++top]=i;}

//else深度優(yōu)先遍歷

}//else

}//while

}18.參考答案：對(duì)于給定的數(shù)k，將所有小于它的元素排到其前面，所有大于它的元素排到其后面，該數(shù)的位置即為有序中的序號(hào)(從0開始數(shù))，這樣最大的比較次數(shù)為n-1次。

實(shí)現(xiàn)本題功能的程序如下：

intdatai(intr[],intn,intk)

{

inti=0,j=n-1;

inttemp;

while(i＜=j)

{

while(i＜n&&r[i]＜=k)

++i;

while(j＞=0&&r[j]＞k)

--j;

if(i＜j)

{

temp=r[i];r[i]=r[j];r[j]=temp;

++i;

--j;

}

}

returnj;

}19.參考答案：A[解析]用n個(gè)權(quán)值構(gòu)造出來的Huffman樹共有2n-1個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)n個(gè)，度為2的非葉結(jié)點(diǎn)n-1個(gè)。20.參考答案：本題的算法思想是，設(shè)

s1="a1a2…am"

s2="b1b2…bn"

從s1中找與b1匹配的字符ai，若ai=b1，則判斷是否ai+1=b2，…，ai+1=bn，若都相等，則s2為s1子串；否則繼續(xù)比較ai之后的字符。

本題代碼如下：

intindex(Str*s1,Str*s2)

{

inti=0,j,k;

while(i＜s1-＞length)

{

j=0;

if(s1-＞ch[i]==s2-＞ch[j])

{

k=i+1;++j;

while(k＜s1-＞length&&j＜s2-＞length&&s1-＞ch[k]==s2-＞ch[j])

{

++k;++j;

}

if(j==s2-＞length)

//s2終止時(shí)找到了子串

break;

else++i;

}

else++i;

}

if(i＞=s1-＞length)

return-1;

else

returni+1;

}21.參考答案：D[解析]進(jìn)行中序線索化后得到下圖所示的結(jié)果。在這棵線索二叉樹中結(jié)點(diǎn)e的右指針是中序后繼線索，它指向結(jié)點(diǎn)c；結(jié)點(diǎn)g的左指針是中序前驅(qū)線索，它指向結(jié)點(diǎn)a。

22.參考答案：D[解析]元素3第一個(gè)出棧時(shí)，元素1，2一定在棧內(nèi)，下一個(gè)出棧的元素是2，不可能是1。當(dāng)然還可以是元素2暫時(shí)不出棧，元素4，5，…進(jìn)棧。23.參考答案：B此題考查的知識(shí)點(diǎn)是遞歸算法的分析。根據(jù)題意可計(jì)算f(0)=2，f(1)=2，f(2)=4，所以選B。24.參考答案：C[解析]在AOE網(wǎng)絡(luò)中可能存在多條關(guān)鍵路徑，因此，任何一個(gè)關(guān)鍵活動(dòng)提前完成，只影響到其中某一條關(guān)鍵路徑，整個(gè)工程不一定能提前完成。但如果AOE網(wǎng)絡(luò)中存在“橋”，即所有關(guān)鍵路徑都要通過的關(guān)鍵活動(dòng)，它提前完成，整個(gè)工程可以提前。25.參考答案：利用深度優(yōu)先遍歷求出一個(gè)根結(jié)點(diǎn)v到每個(gè)葉子結(jié)點(diǎn)的距離，這是由diameter(v)函數(shù)實(shí)現(xiàn)的。該函數(shù)的時(shí)間復(fù)雜度為O(n+e)，n為頂點(diǎn)個(gè)數(shù)，e為邊數(shù)。然后，以每個(gè)頂點(diǎn)作為根結(jié)點(diǎn)調(diào)用diameter()函數(shù)，其中最大值即為T的直徑，本算法的時(shí)間復(fù)雜度為O(n(n+e))。

實(shí)現(xiàn)本題功能的程序代碼如下：

voiddfs(intparent,intchild,int&len)

//函數(shù)執(zhí)行結(jié)束后，len中存放從根結(jié)點(diǎn)到child結(jié)點(diǎn)所在子樹的葉子結(jié)點(diǎn)的最大距離

//cost是帶權(quán)鄰接矩陣，visited是已經(jīng)初始化的訪問標(biāo)記數(shù)組

//N是已定義的常量，即頂點(diǎn)個(gè)數(shù)

{

intclen,v=0,maxlen;

clen=len;

maxlen=len;

while(v＜N&&cost[child][v]==0)

//找與child相鄰的第一個(gè)頂點(diǎn)v

v++;

while(v＜N)

//存在鄰接頂點(diǎn)時(shí)循環(huán)

{

if(v!=parent)

{