廣東開放大學(xué)計(jì)算機(jī)思維實(shí)操實(shí)訓(xùn)-形成性考核（五）答案

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

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

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

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