軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2025/4/16）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2025/4/16

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2025/4/16）

試題四
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在對應(yīng)欄內(nèi)。
[說明]
對有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵?br />①初始時拓?fù)湫蛄袨榭眨?br />②任意選擇一個入度為0的頂點(diǎn)，將其放入拓?fù)湫蛄兄校瑫r從圖中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的??；
③重復(fù)②，直到不存在入度為0的頂點(diǎn)為止(若所有頂點(diǎn)都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判颍駝t由于有向圖中存在回路無法完成拓?fù)渑判?。
函數(shù)int* TopSort(LinkedDigraphG.的功能是對有向圖G中的頂點(diǎn)進(jìn)行拓?fù)渑判?，返回拓?fù)湫蛄兄械捻旤c(diǎn)編號序列，若不能完成拓?fù)渑判颍瑒t返回空指針。其中，圖G中的頂點(diǎn)從1開始依次編號，頂點(diǎn)序列為v1，v2，…，vn，圖G采用鄰接表表示，其數(shù)據(jù)類型定義如下：
#define MAXVNUM 50    /*最大頂點(diǎn)數(shù)*/
typedef struct ArcNode{    /*表結(jié)點(diǎn)類型*/
int adjvex;    /*鄰接頂點(diǎn)編號*/
struct ArcNode *nextarc;    /*指示下一個鄰接頂點(diǎn)*/
}ArcNode;
typedef struct AdjList {    /*頭結(jié)點(diǎn)類型*/
char vdata;    /*頂點(diǎn)的數(shù)據(jù)信息*/
ArcNode *fimstarc;    /*指向鄰接表的第一個表結(jié)點(diǎn)*/
}AdjList;
typedef struct LinkedDigraph {    /*圖的類型*/
int n;    /*圖中頂點(diǎn)個數(shù)*/
AdjList Vhead[MAXVNUM];    /*所有頂點(diǎn)的頭結(jié)點(diǎn)數(shù)組*/
}LinkedDigraph;
例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。

[C代碼]
int *TopSort(LinkedDigraphG.  {
ArcNode *p;    /*臨時指針，指示表結(jié)點(diǎn)*/
Queue Q;        /*臨時隊(duì)列，保存入度為0的頂點(diǎn)編號*/
int k=0;    /*臨時變量，用作數(shù)組元素的下標(biāo)*/
intj=0，w=0;    /*臨時變量，用作頂點(diǎn)編號*/
int *topOrder，*inDegree;
topOrder=(int *)malloc((G.n+1) *sizeof(int));
/*存儲拓?fù)湫蛄兄械捻旤c(diǎn)編號*/
inDegree=(int *)malloc((G.n+1) *sizeof(int));
/*存儲圖G中各頂點(diǎn)的入度*/
if(!inDegree || !topOrder) return NULL;
(1)  ;    /*構(gòu)造一個空隊(duì)列*/
for(j=1; j＜=G.n; j++){/*初始化*/
topOrder[j]=0;    inDegree[j]=0;
}
for(j=1;j＜=G.n;j++)  /*求圖G中各頂點(diǎn)的入度*/
for(p=G.Vhead[j].firstarc; P; P=P-＞nextarc)
inDegree[P-＞adjvex]+=1;
for(j=1; j＜=G.n;j++)    /*將圖G中入度為0的頂點(diǎn)保存在隊(duì)列中*/
if(0==inDegree[j])    EnQueue(＆Q,j);
while(!IsEmpty(Q)){
(2)  ;    /*隊(duì)頭頂點(diǎn)出隊(duì)列并用w保存該頂點(diǎn)的編號*/
topOrder[k++]=w;
/*將頂點(diǎn)w的所有鄰接頂點(diǎn)的入度減1(模擬刪除頂點(diǎn)w及從該頂點(diǎn)出發(fā)的弧的操作)*/
for(p=G.Vhead[w].firstarc;P; p=p-＞nextarc){
(3)  -=1;
if(0==  (4)  )  EnQueue(＆Q，P-＞adjvex);
1/{for$/
}/*while*/
free(inDegree);
if(  (5)  )
return NULL;
return topOrder;
}/*TopSort*/
【問題1】根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（5）。
【問題2】對于圖4-1所示的有向圖G，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄?。若將函?shù)TopSort中的隊(duì)列改為棧，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小?br />設(shè)某有向無環(huán)圖的頂點(diǎn)個數(shù)為n、弧數(shù)為e，那么用鄰接表存儲該圖時，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ暮瘮?shù)TopSort的時間復(fù)雜度是  （6） 。
若有向圖采用鄰接矩陣表示(例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示)，且將函數(shù)TopSort中有關(guān)鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點(diǎn)、e條弧的有向無環(huán)圖，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是  （7）  。