軟件設計師案例分析當天每日一練試題地址：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：www.xomuzic.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/10/7）在線測試：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2022/10/7

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內容（2022/10/7）

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應欄內。
【說明】
對有向圖進行拓撲排序的方法是：
（1）初始時拓撲序列為空；
（2）任意選擇一個入度為0的頂點，將其放入拓撲序列中，同時從圖中刪除該頂點以及從該頂點出發(fā)的??；
（3）重復（2），直到不存在入度為0的頂點為止（若所有頂點都進入拓撲序列則完成拓撲排序，否則由于有向圖中存在回路無法完成拓撲排序）。
函數int* TopSort(LinkedDigraph G)的功能是對有向圖G中的頂點進行拓撲排序，返回拓撲序列中的頂點編號序列，若不能完成拓撲排序，則返回空指針。其中，圖G中的頂點從1開始依次編號，頂點序列為v1，v2，…，vn，圖G采用鄰接表示，其數據類型定義如下：
#define MAXVNUM 50  /*最大頂點數*/
typedef struct ArcNode{ /*表結點類型*/
int adjvex;    /*鄰接頂點編號*/
struct ArcNode *nextarc;   /*指示下一個鄰接頂點*/
}ArcNode;
typedef struct AdjList{ /*頭結點類型*/
char vdata;   /*頂點的數據信息*/
ArcNode *firstarc;   /*指向鄰接表的第一個表結點*/
}AdjList;
typedef struct LinkedDigraph{     /*圖的類型*/
int n;    /*圖中頂點個數*/
AdjList Vhead[MAXVNUM];   /*所有頂點的頭結點數組*/
}LinkedDigraph;
例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。

函數TopSort中用到了隊列結構(Queue的定義省略)，實現隊列基本操作的函數原型如下表所示：

函 數 原 型	說      明
void InitQueue（Queue*Q）	初始化隊列（構造一個空隊列）
bool IsEmpty（Queue Q）	判斷隊列是否為空，若是則返回true，否則返回false
void EnQueue（Queue*Q,int e）	元素入隊列
void DeQueue（Queue*Q,int*p）	元素出隊列

【C代碼】
int *TopSort(LinkedDigraph G) {
ArcNode *p;  /*臨時指針，指示表結點*/
Queue Q; /*臨時隊列，保存入度為0的頂點編號*/
int k = 0;    /*臨時變量，用作數組元素的下標*/
int j = 0， w = 0;    /*臨時變量，用作頂點編號*/
int *topOrder， *inDegree;
topOrder = (int *)malloc((G.n+1) * sizeof(int));   /*存儲拓撲序列中的頂點編號*/
inDegree = (int *)malloc((G.n+1) * sizeof(int));   /*存儲圖G中各頂點的入度*/
if (!inDegree || !topOrder) return NULL;
（1）  ;   /*構造一個空隊列*/
for ( j = 1; j <= G.n; j++ ) { /*初始化*/
topOrder[j] = 0;  inDegree[j] = 0;
}
for (j = 1; j <= G.n; j++) /*求圖G中各頂點的入度*/
for( p = G.Vhead[j].firstarc; p; p = p->nextarc )
inDegree[p-> adjvex] += 1;
for (j = 1; j <= G.n; j++) /*將圖G中入度為0的頂點保存在隊列中*/
if ( 0 == inDegree[j] ) EnQueue(&Q，j);
while (!IsEmpty(Q)) {
（2） ; /*隊頭頂點出隊列并用w保存該頂點的編號*/
topOrder[k++] = w;
/*將頂點w的所有鄰接頂點的入度減1（模擬刪除頂點w及從該頂點出發(fā)的弧的操作）*/
for(p = G.Vhead[w].firstarc; p; p = p->nextarc) {
（3）-= 1;
if (0 ==（4）) EnQueue(&Q， p->adjvex);
}/* for */
}/* while */
free(inDegree);
if (  （5）  )
return NULL;
return topOrder;
} /*TopSort*/
【問題1】（9分）
根據以上說明和C代碼，填充C代碼中的空（1）～（5）。
【問題2】（2分）
對于圖4-1所示的有向圖G，寫出函數TopSort執(zhí)行后得到的拓撲序列。若將函數TopSort中的隊列改為棧，寫出函數TopSort執(zhí)行后得到的拓撲序列。
【問題3】（4分）
設某有向無環(huán)圖的頂點個數為n、弧數為e，那么用鄰接表存儲該圖時，實現上述拓撲排序算法的函數TopSort的時間復雜度是（6）。
若有向圖采用鄰接矩陣表示（例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示），且將函數TopSort中有關鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點、e條弧的有向無環(huán)圖，實現上述拓撲排序算法的時間復雜度是（7）。

從下列的2道試題（試題五和試題六）中任選1道解答。如果解答的試題數超過1道，則題號小的1道解答有效。
信管網試題答案與解析：www.xomuzic.com/st/3809416600.html

信管網考友試題答案分享：

信管網試題答案與解析：www.xomuzic.com/st/3809416600.html