中級軟件設計師2010上半年下午試題VIP

中級軟件設計師2010上半年下午試題試題一 閱讀下列說明和圖，回答問題1至問題4，將解答填入對應欄內。 說明 某大型企業(yè)的數據中心為了集中管理、控制用戶對數據的訪問并支持大量的連接需求，欲構建數據管理中問件，其主要功能如下： 1數據管理員可通過中間件進行用戶管理、操作管理和權限管理。用戶管理維護用戶信息，用戶信息(用戶名、密碼)存儲在用戶表中；操作管理維護數據實體的標準操作及其所屬的后端數據庫信息，標準操作和后端數據庫信息存放在操作表中；權限管理維護權限表，該表存儲用戶可執(zhí)行的操作信息。 2中間件驗證前端應用提供的用戶信息。若驗證不通過，返回非法用戶信息；若驗證通過，中間件將等待前端應用提交操作請求。 3前端應用提交操作請求后，中間件先對請求進行格式檢查。如果格式不正確，返回格式錯誤信息；如果格式正確，則進行權限驗證(驗證用戶是否有權執(zhí)行請求的操作)，若用戶無權執(zhí)行該操作，則返回權限不足信息，否則進行連接管理。 4連接管理連接相應的后臺數據庫并提交操作。連接管理先檢查是否存在空閑的數據庫連接，如果不存在，新建連接；如果存在，則重用連接。 5后端數據庫執(zhí)行操作并將結果傳給中間件，中間件對收到的操作結果進行處理后，將其返回給前端應用。 現采用結構化方法對系統(tǒng)進行分析與設計，獲得如圖1-1所示的頂層數據流圖和圖1-2所示的0層數據流圖。 1、使用說明中的詞語，給出圖1-1中的實體E1E3的名稱。 2、使用說明中的詞語，給出圖1-2中的數據存儲D1D3的名稱 3、給出圖1-2中加工P的名稱及其輸入、輸出流。名稱起點終點輸入流P輸出流P 除加工P的輸入與輸出流外，圖1-2還缺失了兩條數據流，請給出這兩條數據流的起點和終點。 起點終點 注：名稱使用說明中的詞匯，起點和終點均使用圖1-2中的符號或詞匯。 4、在繪制數據流圖時，需要注意加工的繪制。請給出三種在繪制加工的輸入、輸出時可能出現的錯誤。 試題二 閱讀下列說明，回答問題1至問題3，將解答填入對應欄內。 說明 某學校擬開發(fā)一套實驗管理系統(tǒng)，對各課程的實驗安排情況進行管理。 需求分析 一個實驗室可進行多種類型不同的實驗。由于實驗室和實驗員資源有限，需根據學生人數分批次安排實驗室和實驗員。一門課程可以為多個班級開設，每個班級每學期可以開設多門課程。一門課程的一種實驗可以根據人數、實驗室的可容納人數和實驗類型，分批次開設在多個實驗室的不同時問段。一個實驗室的一次實驗可以分配多個實驗員負責輔導實驗，實驗員給出學生的每次實驗成績。 (1)課程信息包括：課程編號、課程名稱、實驗學時、授課學期和丌課的班級等信息；實驗信息記錄該課程的實驗進度信息，包括：實驗名、實驗類型、學時、安排周次等信息，如表2-1所示。 表2-1 課程及實驗信息課程編號15054037課程名稱數字電視原刪實驗學時12班級電0501，信0501，計0501授課院系機械與電氣工程授課學期第三學期序號實驗名實驗類難度學時安排周次1505403701音視頻AD-DA實驗驗證性1231505403702音頻編碼實驗驗證性2251505403703視頻編碼實驗演示性0.519 (2)以課程為單位制定實驗安排計劃信息，包括：實驗地點，實驗時間、實驗員等信息，實驗計劃如表2-2所示。 表2-2 實驗安排計劃 課程編號15054037課程名稱數字電視原理安排學期2009年秋總人數220實驗編號實驗名實驗員實驗員地點批次號人數1505403701音視頻AD-DA丈驗盛，陳第3周周四晚上實驗三樓3101601505403701音視頻AD-DA實驗盛，陳第3周周四晚上實驗三樓3102601505403701音視頻AD-DA實驗吳，劉第3周周五晚上實驗三樓3113601505403701音視頻AD-DA實驗吳第3周周五晚上實驗三樓3114401505403702音頻編碼實驗盛，劉第5周周一下午實驗四樓410170 (3)由實驗員給出每個學生每次實驗的成績，包括：實驗名、學號、姓名、班級、實驗成績等信息，實驗成績如表2-3所示。 表2-3 實驗成績 實驗員： 盛 實驗名音視頻AD-DA實驗課程名數字電視原理學號姓名班級實驗成績030501001陳民信050187030501002劉志信050178040501001張勤計050186 (4)學生的實驗課程總成績根據每次實驗的成績以及每次實驗的難度來計算。 概念模型設計 根據需求階段收集的信息，設計的實體聯系圖(不完整)如圖2-1所示。 邏輯結構設計 根據概念模型設計階段完成的實體聯系圖，得出如下關系模式(不完整)： 課程(課程編號，課程名稱，授課院系，實驗學時) 班級(班級號，專業(yè)，所屬系) 開課情況( (1) ，授課學期) 實驗( (2) ，實驗類型，難度，學時，安排周次) 實驗計劃( (3) ，實驗時間，人數) 實驗員( (4) ，級別) 實驗室(實驗室編號，地點，開放時間，可容納人數，實驗類型) 學生( (5) ，姓名，年齡，性別) 實驗成績( (6) ，實驗成績，評分實驗員) 5、補充圖2-1中的聯系和聯系的類型。 根據圖2-1，將邏輯結構設計階段生成的關系模式中的空67補充完整并用下劃線指出這六個關系模式的主鍵。12、如果需要記錄課程的授課教師，新增加“授課教師”實體。請對圖2-1進行修改，畫出修改后的實體問聯系和聯系的類型。試題三閱讀下列說明和圖，回答問題1至問題3，將解答填入對應欄內。 說明 某運輸公司決定為新的售票機開發(fā)車票銷售的控制軟件。圖3-1給出了售票機的面板示意圖以及相關的控制部件。 售票機相關部件的作用如下所述： 13目的地鍵盤用來輸入行程目的地的代碼(例如，200表示總站)。 14乘客可以通過車票鍵盤選擇車票種類(單程票、多次往返票和座席種類)。 15繼續(xù)/取消鍵盤上的取消按鈕用于取消購票過程，繼續(xù)按鈕允許乘客連續(xù)購買多張票。 16顯示屏顯示所有的系統(tǒng)輸出和用戶提示信息。 17插卡口接受MCard(現金卡)，硬幣口和紙幣槽接受現金。 18打印機用于輸出車票。 假設乘客總是支付恰好需要的金額而無需找零，售票機的維護工作(取回現金、放入空白車票等)由服務技術人員完成。 系統(tǒng)采用面向對象方法開發(fā)，使用UML進行建模。系統(tǒng)的頂層用例圖和類圖分別如圖3-2和圖3-3所示。 13、根據說明中的描述，給出圖3-2中A1和A2所對應的參與者，U1所對應的用例，以及(1)、(2)處所對應的關系。 14、根據說明中的描述，給出圖3-3中缺少的C1C4所對應的類名以及(3)(6)處所對應的多重度。 15、圖3-3中的類圖設計采用了中介者(Mediator)設計模式，請說明該模式的內涵。 試題四 閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在對應欄內。 說明 對有向圖進行拓撲排序的方法是： (1)初始時拓撲序列為空； (2)任意選擇一個入度為0的頂點，將其放入拓撲序列中，同時從圖中刪除該頂點以及從該頂點出發(fā)的??； (3)重復(2)，直到不存在入度為0的頂點為止(若所有頂點都進入拓撲序列則完成拓撲排序，否則由于有向圖中存在回路無法完成拓撲排序)。 函數int* TopSort(LinkedDigraphG.的功能是對有向圖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 *fimstarc; /*指向鄰接表的第一個表結點*/ AdjList; typedef struct LinkedDigraph /*圖的類型*/ int n; /*圖中頂點個數*/ AdjList VheadMAXVNUM; /*所有頂點的頭結點數組*/ LinkedDigraph; 例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。 函數TopSort中用到了隊列結構(Queue的定義省略)，實現隊列基本操作的函數原型如下表所示： 函數原型說明void InitQueue(Queue *Q)初始化隊列(構造一個卒隊列)bool IsEmpty(Queue Q)判斷隊列是否為空，若是則返回true，否則返回falsevoid EnQueue(Queue *Q，int e)元素入隊列void DeQueue(Queue *Q，int *p)元素出隊列 C代碼 int *TopSort(LinkedDigraphG. ArcNode *p; /*臨時指針，指示表結點*/ Queue Q; /*臨時隊列，保存入度為0的頂點編號*/ int k=0; /*臨時變量，用作數組元素的下標*/ intj=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+)/*初始化*/ topOrderj=0; inDegreej=0; for(j=1;j=G.n;j+) /*求圖G中各頂點的入度*/ for(p=G.Vheadj.firstarc; P; P=P-nextarc) inDegreeP-adjvex+=1; for(j=1; j=G.n;j+) /*將圖G中入度為0的頂點保存在隊列中*/ if(0=inDegreej) EnQueue(Q,j); while(!IsEmpty(Q) (2) ; /*隊頭頂點出隊列并用w保存該頂點的編號*/ topOrderk+=w; /*將頂點w的所有鄰接頂點的入度減1(模擬刪除頂點w及從該頂點出發(fā)的弧的操作)*/ for(p=G.Vheadw.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*/根據以上說明和C代碼，填充C代碼中的空1617。21、對于圖4-1所示的有向圖G，寫出函數TopSort執(zhí)行后得到的拓撲序列。若將函數TopSort中的隊列改為棧，寫出函數TopSort執(zhí)行后得到的拓撲序列。 設某有向無環(huán)圖的頂點個數為n、弧數為e，那么用鄰接表存儲該圖時，實現上述拓撲排序算法的函數TopSort的時間復雜度是 22 。 若有向圖采用鄰接矩陣表示(例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示)，且將函數TopSort中有關鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點、e條弧的有向無環(huán)圖，實現上述拓撲排序算法的時間復雜度是 23 。 試題五閱讀下列說明和C+弋碼，將應填入 (n) 處的字句寫在對應欄內。 說明 某軟件公司現欲開發(fā)一款飛機飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機的飛行特征與起飛特征。需要模擬的飛機種類及其特征如表5-1所示。 表5-1飛機種類起飛特征飛行特征直升機(Helicopter)垂直起飛(VerticalTakeOff)亞音速飛行(SubSonicFly)客機(AirPlane)長距離起飛(LongDistanceTakeOff)亞音速飛行(SubSonicFly)殲擊機(Fighter)長距離起飛(LongDistanceTakeOff)超音速飛行(SuperSonicFly)鷂式戰(zhàn)斗機(Harrier)垂直起飛(VerticalTakeOff)超音速飛行(SuperSonicFly) 為支持將來模擬更多種類的飛機，采用策略設計模式(strategy)設計的類圖如圖5-1所示。 圖5-1中，AirCraft為抽象類，描述了抽象的飛機，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機種類，方法fly31和takeOff31分別表示不同飛機都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。 C+代碼 #includeiostream using namespace std; class FlyBehaVior public: virtual void fly31=0; ; class SubSonicFly: public FlyBehaVior public: void fly31cout亞音速飛行!endl;) ; class SupersonicFly: public FlyBehaVior public: void fly31cout超音速飛行!endl;) ; class TakeOffBehavior publie: virtual void takeOff31=0; ; class VerticalTakeOff: public TakeOffBehavior public: void takeOff31cout垂直起飛!endl ; class LongDistanceTakeOff: public TakeOffBehavior public: void takeOff31cout長距離起飛!endl; ; class AirCraft protected: 24 ; 25 ; public: void fly31 26 ; void takeoff31 27 ; ; ; class Helicopter: public AirCraft public: Helicopter 31 flyBehavior=new 28 ; takeoffBehavior=new 29 ; 30 if(!flyBehaVior) delete flyBehaVior; if(!takeoffBehavior) delete takeoffBehaVior; ; /其他代碼省略 試題六 閱讀下列說明和Java代碼，將應填入(n)處的字句寫在對應欄內。 說明 某軟件公司現欲開發(fā)一款飛機飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機的飛行特征與起飛特征。需要模擬的飛機種類及其特征如表6-1所示。 表6-1飛機種類起飛特征飛行特征直升機(Helicopter)垂直起飛(VerticalTakeOff)亞音速飛行(SubSonicFly)客機(AirPlane)長距離起飛(LongDistanceTakeOff)亞音速飛行(SubSonicFly)殲擊機(Fighter)長距離起飛(LongDistanceTakeOff)超音速飛行(SuperSonicFly)鷂式戰(zhàn)斗機(Harrier)垂直起飛(VerticalTakeOff)超音速飛行(SuperSonicFly) 為支持將來模擬更多種類的飛機，采用策略設計模式(Strategy)設計的類圖如圖6-1所示。 圖6-1中，AirCraft為抽象類，描述了抽象的飛機，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機種類，方法fly38和takeOff38分別表示不同飛機都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。 Java代碼 interface FlyBehavior public void fly38; ; class SubSonicFly implements FlyBehavior public void fly38(System.out.println(業(yè)音速飛行!);) ; class SuperSonicFly implements FlyBehavior public void fly38 System.out.println(超音速飛行!); ; interface TakeOffBehavior public void takeOff38; ; class VerticalTakeOff implements TakeOffBehavior public void takeOff38 System.out.println(垂直起飛!); ; class LongDistanceTakeOff implements TakeOffBehavior public void takeOff38 System.out.println(長距離起飛!); ; abstract class AirCraft protected 31 ; protected 32 ; public void fly38 33 ; public void takeOff38 34 ; ; class Helicopter 35 AirCraft public Helicopter38 flyBehavior=new 36 ; takeOffBehavior=new 37 ; ; /其他代碼省略 答案:試題一1、E1：前端應用 E2：數據管理員 E3：后端數據庫本問題考查頂層DFD。頂層DFD一般用來確定系統(tǒng)邊界，將待開發(fā)系統(tǒng)看作一個加工，因此圖中只有唯一的一個加工和一些外部實體，以及這兩者之間的輸入輸出數據流。題目要求根據描述確定圖中的外部實體。分析題目中的描述，并結合已經在頂層數據流圖中給出的數據流進行分析。題目中有信息描述：數據管理員可通過中間件進行用戶管理、操作管理和權限管理；前端應用提交操作請求；連接管理連接相應的后臺數據庫并提交操作。由此可知該中間件系統(tǒng)有數據管理員、前端應用和后端數據庫三個外部實體。從圖1-1中數據流和實體的對應關系可知，E1為前端應用，E2為數據管理員，E3為后端數據庫。2、D1：用戶表 D2：操作表 D3：權限表本問題考查0層DFD中數據存儲的確定。說明中描述：用戶信息(用戶名、密碼)存儲在用戶表中；標準操作和后端數據庫信息存放在操作表中；權限管理維護信息存放在權限表中。因此數據存儲為用戶表、操作表以及權限表。再根據圖1-2可知D1的輸入數據流從用戶管理來，D2的輸入數據流從操作管理來，D3的輸入數據流從權限管理來，所以D1為用戶表，D2為操作表，D3為權限表。3、P的名稱：操作結果處理 名稱起點終點輸入流操作結果E3P輸出流處理后的操作結果PE1 缺少的數據流： 起點終點D2權限驗證D3權限驗證本問題考查0層DFD中缺失的加工和數據流。比較圖1-1和圖1-2，可知頂層DFD中的操作結果和處理后的操作結果沒有在0層DFD中體現。再根據描述“后端數據庫執(zhí)行操作并將結果傳給中問件，中間件對收到的操作結果進行處理后，將其返回給前端應用”可知，需要有操作結果處理，因此P為操作結果處理，其輸入流為從后端數據庫E3來的操作結果，輸出結果為處理后的操作結果，并返回給前端應用E1。 考查完P及其輸入輸出流之后，對圖1-2的內部數據流進行考查，以找出缺失的另外2條數據流。從圖中可以看出D2和D3只有輸入流沒有輸出流，這是常見DFD設計時的錯誤，所以首先考查D2和D3的輸出流。描述中有“權限驗證是驗證用戶是否有權執(zhí)行請求的操作，若用戶有權執(zhí)行該操作，進行連接管理；連接管理連接相應的后臺數據庫并提交操作；權限表存儲用戶可執(zhí)行的操作信息”。因此，權限驗證有從權限表D3來的輸入數據流。而要連接后端數據庫，需要數據庫信息，從權限驗證的輸出流中包含有數據庫信息可知，權限驗證需要獲取到數據庫信息，所以還需從操作表D2來的輸入流。4、在繪制數據流圖的加工時，可能出現的輸入、輸出錯誤： 只有輸入而無輸出或者黑洞 只有輸出而無輸入或者奇跡 輸入的數據流無法通過加工產生輸出流或者灰洞 輸入的數據流與輸出的數據流名稱相同本問題考查在繪制數據流圖中加工繪制時的注意事項。繪制加工時可能出現的錯誤有：加工的輸入、輸出時可能出現只有輸入而無輸出、只有輸出而無輸入、輸入的數據流無法通過加工產生輸出流以及輸入的數據流與輸出的數據流名稱相同等錯誤。試題二5、根據題意，由“一門含實驗的課程可以開設給多個班級，每個班級每學期可以開設多門含實驗的課程”可知課程和班級之間的開設關系為m:n聯系。由“一個實驗室的一次實驗可以分配多個實驗員負責輔導實驗”可知實驗、實驗室與實驗員之問的安排關系為k:n:m聯系。由“實驗員給出學生的每次實驗成績”可知實驗、學生與實驗員之間的成績關系為k:n:m聯系。班級和學生之問的包含關系為1:n聯系。6、課程編號，班級號 7、實驗編號，課程編號 8、實驗編號，批次號，安排學期，實驗室編號，實驗員編號 9、實驗員編號，實驗員姓名 10、學號，班級號 11、實驗編號，學號 其他關系模式主鍵： 課程(課程編號，課程名稱，授課院系，實驗學時) 班級(班級號，專業(yè)，所屬系) 實驗室(實驗室編號，地點，開放時間，可容納人數，實驗課類型)根據題意可知課程編號是課程的主鍵，班級號是班級的主鍵。從表2-1可知，開課情況是體現課程與班級問的m:n聯系，因此開課情況關系模式應該包含課程編號和班級號，并共同作為主鍵。一門課程包含多次實驗，實驗與課程之間是m:1關系，因此，根據表2-1，實驗關系模式應包含實驗編號和課程編號，并且以實驗編號為主鍵，以課程編號為外鍵。在制定試驗計劃時，每個班的每次實驗可能按實驗室被分成多個批次，每個批次的實驗會有若干名實驗員來輔導學生實驗并打分。實驗員關系模式應該記錄實驗員編號和實驗員姓名，并以實驗員編號為主鍵。實驗室編號是實驗室的主鍵。從表2-2可見，實驗計劃關系模式應記錄實驗編號、批次號和授課學期，并且共同作為主鍵。從表2-3可見，實驗成績關系模式記錄每個學生的每次實驗成績，應包含學號和實驗編號，并共同作為主鍵。12、由于授課教師負責給若干個班級開設若干門課程，因此，課程、班級和授課教師之問的開設關系是k:n:m聯系。 試題三13、A1：乘客 A2：服務技術人員 U1：支付 (1)include (2)include本問題考查用例圖。用例圖用于確定系統(tǒng)邊界，識別與系統(tǒng)交互的參與者，通過判斷參與者發(fā)起的用例，建立和參與者之間的關聯，然后再確認用例之間的關系。 本題中對售票機的描述為“乘客可以通過車票鍵盤選擇車票種類(單程票、多次往返票和座席種類)；售票機的維護工作(取回現金、放入空白車票等)由服務技術人員完成”。由此可知，圖3-1中A1為乘客，A2為服務技術人員。 對購票用例，要選擇目的地和車票類型、通過插卡口進行支付才可完成購票。因此U2為支付。 在考查用例之間的關系時，購票過程可以取消，也允許乘客連續(xù)購買多張票，因此，購票時可以包含多次選擇目的地和車票類型、支付，即購票用例包含(關系include)選擇目的地和車票類型以及支付。14、C1：鍵盤 C2：目的地鍵盤 C3：車票鍵盤 C4：繼續(xù)/取消鍵盤 (3)(6)：1本問題考查類圖。類圖設計的重點是類的抽象和繼承關系以及多重度。售票機的面板由多個控制部件組成。根據說明這些控制部件有目的地鍵盤、車票鍵盤和繼續(xù)/取消鍵盤、顯示屏、卡驅動器、硬幣/紙幣槽、打印機。圖3-3中只有前3個部件在圖中沒有給出，而要填如4個類。從圖中已經抽象出的硬件組件，給出了抽象的思路，從而可以把鍵盤抽象出來。由C1與C2、C3、C4的繼承關系中C1為基類，可知C1為鍵盤。由C2、C3和C4給出的方法名稱可知，C2為目的地鍵盤獲取目的地代碼，C3為車票鍵盤選擇產品類型，C4為繼續(xù)/和取消動作。 本題中的重復度比較簡單。從圖3-1售票機的圖示中可以看出，一個售票機只包含一個目的地鍵盤、一個車票鍵盤和一個繼續(xù)/取消鍵盤，因此(3)(6)均為1。15、使用Mediator模式，可以使各個對象問的耦合松散，只需關心和Mediator的關系，使多對多的關系變成了一對多的關系，可以降低系統(tǒng)的復雜性，提高可修改擴展性。本問題考查設計模式。設計模式題目雖然比較難，但是本題題目中已經給出了所采用的設計模式為：Mediator模式，只需說明設計模式的內涵即可，也比較容易。使用Mediator模式，可以使各個對象問的耦合松散，只需關心和Mediator的關系，使多對多的關系變成了一對多的關系，可以降低系統(tǒng)的復雜性，提高可修改擴展性。試題四16、InitQueue(Q) 17、DeQueue(Q，w) 18、inDegreep-adjvex 或其等價形式 19、inDegreep-adjvex 或其等價形式 20、kGn 或k!=Gn 或其等價形式拓撲排序是將有向無環(huán)圖中所有頂點排成一個線性序列的過程，并且該序列滿足：若在有向圖中從頂點vi到vj有一條路徑，則在該線性序列中，頂點vi必然在頂點vj之前。 對AOE網進行拓撲排序的方法如下： 在AOE網中選擇一個入度為零(沒有前驅)的頂點且輸出它； 從網中刪除該頂點及其與該頂點有關的所有邊； 重復上述兩步，直至網中不存在入度為零的頂點為止。 在拓撲排序過程中，需要將入度為0的頂點臨時存儲起來。函數中用一個隊列暫存入度為0且沒有進入拓撲序列的頂點。顯然，空(1)處應填入InitOueue(Q)。 進行拓撲排序之前，應先求出網中每個頂點的入度并存入數組inDegree中，從而將“從網中刪除該頂點及其與該頂點有關的所有邊”的操作轉換為“相關頂點的入度減1”，一旦發(fā)現某個頂點的入度變?yōu)?，就將其編號壓入堆棧。從而將選擇入度為0的頂點操作轉化為令隊頭所代表的頂點出隊。 根據注釋，空(2)處應填入DeQueue(Q，w)，實現隊頭元素出隊列的處理。 題中圖采用鄰接表存儲結構，當指針p指向vi鄰接表中的結點時，p-adjvex表示vi的一個鄰接頂點，刪除vi至頂點p-adjvex的弧的操作實現為頂點p-adjvex的入度減1，因此，空(3)處應填入inDegreep-adjvex，當頂點p-adjvex的入度為0時，需要將其加入隊列，因此空(4)處也應填入inDegreep-adjvex。 空(5)處判斷是否所有頂點都加入了拓撲序列，算法中變量k用于對加入序列的頂點計數，因此，空(5)處應填入“kGn”或“k!=Gn”。21、隊列方式：v1 v2 v5 v4 v3 v7 v6 或者1 2 5 4 3 7 6 棧方式：v1 v2 v5 v4 v7 v3 v6 或者1 2 5 4 7 3 6使用棧和隊列的差別在于拓撲序列中頂點的排列次序可能不同。對于本題中的有向圖，在使用隊列的方式下： (1)開始時僅頂點v1的入度為O，因此頂點v1入隊； (2)隊頭頂點v1出隊，并進入拓撲序列，然后刪除從頂點v1出發(fā)的弧后，僅使頂點v2的入度為0，因此頂點v2入隊； (3)隊頭頂點v2出隊，并進入拓撲序列，然后刪除從頂點v2出發(fā)的弧后，僅使頂點v5的入度為0，因此頂點v5入隊； (4)隊頭頂點v5出隊，并進入拓撲序列，然后刪除從頂點v5出發(fā)的弧后，僅使頂點v4的入度為0，因此頂點v4入隊； (5)隊頭頂點v4出隊，并進入拓撲序列，然后刪除從頂點v4出發(fā)的弧后，僅使頂點v3和v7的入度為0，因此頂點v3和v7依次入隊； (6)隊頭頂點v3出隊，并進入拓撲序列，然后刪除從頂點v3出發(fā)的弧后，沒有產生新的入度為0的頂點； (7)隊頭頂點v7出隊，并進入拓撲序列，然后刪除從頂點v7出發(fā)的弧后，使頂點v6的入度為0，因此頂點v6入隊； (8)隊頭頂點v6出隊，并進入拓撲序列，然后刪除從頂點v6出發(fā)的弧后，沒有產生新的入度為0的頂點，隊列已空，因此結束拓撲排序過程，得到的拓撲序列為v1 V2 v5v4 v3 v7 v6。 使用棧保存入度為0的頂點時，前4步都是一樣的，因為每次僅有一個元素進棧，因此出棧序列與入棧序列一致。到第5步時，v3和v7依次入棧后，出棧時的次序為v7和v3，因此得到的拓撲序列為v1 v2 v5 v4 v7 v3 v6。22、O(n+e) 23、O(n2)以鄰接表為存儲結構時，計算各頂點入度的時問復雜度為O(e)，建立零入度頂點隊列的時間復雜度為O(n)。在拓撲排序過程中，(圖中無環(huán)情況下)每個頂點進出隊列各1次，入度減1的操作在while循環(huán)中共執(zhí)行e次，所以總的時間復雜度為O(n+e)。 以鄰接矩陣為存儲結構時，計算各頂點入度時需要遍歷整個矩陣，因此時間復雜度為O(n2)，建立零入度頂點隊列的時間復雜度為O(n)。在拓撲排序過程中，(圖中無環(huán)情況下)每個頂點進出隊列各1次，實現入度減1操作時需遍歷每個頂點的行向量1遍(時問復雜度為O(n)，所以總的時間復雜度為O(n2)。 試題五24、 FlyBehavior *flyBehavior 25、 TakeOffBehavjor *=takeOffBehavior 26、 flyBehavior-fly() 27、 takeOffBehavior-takeOff()_ 28、 SubSo