1、試卷總分:10 得分:10_指的是從有向圖G=(V，E)中得到一個頂點的線性序列，滿足如果G包含邊(u，v)，則在該序列中，u就出現在v的前面。拓撲排序圖廣度優先搜索深度優先搜索答案:A2.計算出活動網絡中的_，就可以辨明哪些是影響整個工程進度的關鍵活動，以便科學合理地安排工作。關鍵路徑最小生成樹最大路徑關鍵活動答案:A3.關于“樹”，下列說法正確的是_?“樹”是一種能夠表達層次關系的數據結構。對于樹中任意一個結點，該結點與其下層的結點也構成樹結構，稱為子樹。樹中的每一個位置稱為一個結點，樹根部的結點稱為根結點。通常把從根結點到葉子結點的最長路徑上的結點數稱為樹的深度。答案:ABCD4.對于二

2、叉搜索樹的查詢過程，下列說法正確的事_?如果已沒有兒子節點，則宣布查找失敗。如果查詢關鍵詞大于當前結點的關鍵詞，則查找其左子樹。如果查詢關鍵詞等于當前結點的關鍵詞，則宣布查找成功。如果查詢關鍵詞小于當前結點的關鍵詞，則查找其右子樹。答案:AC5.關于圖，下列說法正確的是_?在無向圖中，頂點對(x，y)是無序的，(x，y)和(y，x)是同一條邊。圖的每一個頂點可以與多個其它頂點相關聯，各頂點之間的關系是任意的。在有向圖中，頂點對(x，y)是有序的，稱為從x到y的一條有向邊，這里(x，y)與(y，x)是不同的兩條邊圖可以分為有向圖和無向圖答案:ABCD6.關于深度優先搜索，下列說法正確的是_?深度

3、優先搜索的過程可以使用棧來模擬，當然也可以使用遞歸的形式來完成。每一步探查中，我們在當前頂點v的所有鄰接頂點中，找出尚未訪問過的一個，將其作為下一步探查的當前頂點，即我們永遠希望向著更“深”的層次去探索。深度優先搜索（depthfirstsearch）是一個不斷探查和回退的過程。在探查的每一步開始之前，算法都有一個當前頂點（最開始即是起始頂點）答案:ABCD7.關于廣度優先搜索，下列說法正確的是_?從起始點開始作為首層，然后對每層的所有頂點，都向外擴展訪問那些未被訪問過的鄰接頂點，而這些擴展出來的頂點就作為下一層的頂點，依此類推，直到所有頂點都被訪問為止。與深度優先搜索不同，廣度優先搜索（br

4、eadthfirstsearch）沒有探查和回退的過程，而是一個逐層遍歷的過程。廣度優先搜索一般使用隊列，以記憶正在訪問的這一層和上一層的結點，以便于向下一層的結點進行訪問。廣度優先搜索還能用來計算起始點到所有可達頂點之間的距離（即最少的邊數）答案:ABCD8.關于”最小生成樹”，下列說法正確的是_?“最小”，即連接網絡的總代價最小。Kruskal算法可以 解決最小生成樹問題用全部頂點和部分邊組成的樹，生成樹代價最小意味著樹中無環。Prim算法解可以決最小生成樹問題答案:ABCD9.關于Prim算法和Kruskal算法，下列說法正確的是_?Kruskal算法在執行過程的中間結果可能有多棵樹（稱為森林），最終才合并成我們所需的最小生成樹。有效實現Prim算法的關鍵是設法較為高效地選擇出已經在生成樹內和尚不在生成樹內的頂點之間的最小權值邊。Prim算法在生成樹集合擴展時，總是形成單棵樹。二叉搜索樹是一種能滿足Prim算法的數據結構。答案:A