數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)

1、判斷題：在n個結(jié)點的無向圖中，若邊數(shù) n-1，則該圖必是連通圖。（）答：FALSE（該圖可能包含多個連通子圖，但其本身可以是不連通的。因為圖的定義是：如果 對于圖中任意兩個頂點v、v E,v和v都是連通的，則稱G是連通圖（Connected Graph）。）鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。（） 答：FALSE（鄰接表也可存儲無向圖）圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不一定是唯一的。（）答：TRUE有回路的圖不能進行拓撲排序。（）答：TRUE任何AOV網(wǎng)拓撲排序的結(jié)果都是唯一的。（）答：FALSE（拓撲排序不一定唯一，只要滿足偏序關(guān)系即可。）在AOV

2、-網(wǎng)中，如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)， 不能求關(guān)鍵路徑。（）答：TRUE圖的鄰接矩陣中矩陣元素的行數(shù)只與頂點個數(shù)有關(guān)（TRUE ）圖的鄰接矩陣中矩陣中非零元素個數(shù)與邊數(shù)有關(guān)（TRUE ）在拓撲排序序列中，任意兩個相繼結(jié)點V i和Vj都存在從V i到Vj的路徑（FALSE ）若一個圖的鄰接矩陣為對稱矩陣，則該圖必為無向圖。（TRUE ）任一 AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點到匯點的路徑中最長的一條（TRUE ）在有向圖中，入度為0的結(jié)點稱為葉子結(jié)點（或葉子）（FALSE ）單選題：在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍，在一個有向圖中，所

3、有頂 點的入度之和等于所有頂點出度之和的（）倍。1/2 B. 2 C. 1 D. 4答：BC具有n個頂點的有向圖最多有（）條邊。n B. n（n-1） C. n（n+1） D.答：B在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（）條邊。n B. n+1 C. n-1 D. n/2答：C一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為（）。0 B. 1 C. n D. n+1答：Bn個頂點的強連通圖至少有（）條邊。A. n B. n-1 C. n+1 D. n（n-1）答：A在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和 為（ ）。A.s B. s-1

4、C. s+1 D. n答：A對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為 （）；所有鄰接表中的結(jié)點總數(shù)是（）。A. n B. n+1 C. n-1 D. n+eA. e/2 B. e C. 2e D. n+e答：AC （為什么選C呢？因為在無向圖中鄰接表表示法中，每條邊作一次“第一 條”邊，再作一次其它邊的“相鄰接”邊.）對于一個有向圖，若一個頂點的入度為k1、出度為k2,則對應(yīng)鄰接表中該頂點的單鏈 表中的結(jié)點數(shù)為（）。A. k1 B. k2 C. k1-k2 D. k1+k2答：B在有向圖G的拓撲序列中，若頂點vi在頂點vj之前，則下列情況下不可能出現(xiàn)的是（）。

5、A. G中有弧 B. G中有一條從vi到vj的路徑C. G中沒有弧 D. G中有一條從vj到vi的路徑答：D在一個無向圖中，若兩個頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為（）。A.k B. k+1 C. k+2 D. 2k答：B采用鄰接表存儲的圖的深度優(yōu)先遍歷類似于二叉樹的（）。A.中序遍歷B.先序遍歷C.后序遍歷D.按層次遍歷答：B用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點 序列是（）。A.逆拓撲有序的B.拓撲有序的C.無序的答：A （請參見嚴蔚敏（c語言版）數(shù)據(jù)結(jié)構(gòu)P185.算法7.13、算法7.14）關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的（）。A.從源點到匯

6、點的最長路徑B.從源點到匯點的最短路徑C.最長的回路D.最短的路徑答：A下面不正確的說法是（）。（1）在AOE-網(wǎng)工程中，減少任一關(guān)鍵活動上的權(quán)值后，整個工期也就相應(yīng)的減?。?）AOE-網(wǎng)工程工期為關(guān)鍵活動上的權(quán)之和（3）在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必在關(guān)鍵路徑上A.（1） B. （2） C. （3） D. （1）（3）答：A （若網(wǎng)中有n條關(guān)鍵路徑時，僅減其中一條關(guān)鍵路徑的權(quán)值并不能使整個工期減少， 故選擇A.）下面的敘述中不正確的是（）。關(guān)鍵活動不按期完成就會影響整個工程的完成時間任何一個關(guān)鍵活動提前完成，將使整個工程提前完成所有關(guān)鍵活動都提前完成，則整個工程將提前完成某些

7、關(guān)鍵活動若提前完成，將使整個工程提前完成答：B （理由同26題）采用鄰接表存儲的圖的廣度優(yōu)先遍歷類似于二叉樹的（）。A.按層次遍歷B.中序遍歷C.后序遍歷D.先序遍歷答：A一個圖中包含k個連通分量，若按深度優(yōu)先（DFS ）搜索方法訪問所有結(jié)點，則必須調(diào)用（） 次深度優(yōu)先遍歷算法。A. k B. 1 C. k-1 D. k+1答：A （一次深度優(yōu)先搜索只能遍歷一個連通分量，故選A.）以下說法正確的是（）。連通分量是無向圖中的極小連通子圖強連通分量是有向圖中的極大強連通子圖在一個有向圖的拓撲序列中若頂點a在頂點b之前，則圖中必有一條弧a,b對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜

8、索能訪問到每個頂點， 則該圖一定是完全圖答：B （A錯，連通分量是無向圖中的極大連通子圖；C錯，拓撲序列中頂點a在頂點b之前， 則圖中并不一定存在一條弧a,b； D錯，如果有向圖構(gòu)成雙向有環(huán)時，則從任一頂點出發(fā) 均能訪問到每個頂點，但該圖卻非完全圖；因此，選擇B.）下面關(guān)于圖的存儲的敘述中，哪一個是正確的。（）用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)而與邊數(shù)無關(guān)用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)而與結(jié)點個數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)答案：A對于如右

9、下圖所示的帶權(quán)有向圖，從頂點1到頂點5的最短路徑（）A. 1，4，5 B.1，2，3，5C. 1，4，3，5 D.1，2，4，3，5答案：DE2,則稱（）cV2,E1c33.設(shè) G1=（V1,E1）和 G2=（V2,E2）為兩個圖，V1A. G1是G2的子圖B.G2是G1的子圖C. G1是G2的連通分量D.G2是G1的連通分量答案：A帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）A、第i行非8的元素之和B、第i列非8的元素之和C、第i行非8且非0的元素個數(shù)D、第i列非8且非0的元素個數(shù)答案：D假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關(guān)的所有 弧的時間復(fù)雜

10、度是()A. O(n) B. O(e) C. O(n+e) D. O(n*e)答案：C填空題：一個無向圖有n個頂點和e條邊，則所有頂點的度的和即(表示頂點i的度)=。答：2e (一條邊被兩個頂點使用)若無向圖G的頂點度數(shù)的最小值大于或等于時，G至少有一條回路。答：2一個連通圖的 是一個極小連通子圖。(重大2000年研究生試題。)答：生成樹設(shè)無向圖G的頂點數(shù)為n,圖G最少有條邊，最多有條邊。若G為有向圖，有n個頂 點，則圖G最少有條邊，最多有條邊。具有n個頂點的無向完全圖，邊的總數(shù)為條；而 具有n個頂點的有向完全圖中，邊的總數(shù)有條。答：0 n(n-1)/2 0 n(n-1) n(n-1)/2 n

11、(n-1)(注*：設(shè)每個結(jié)點都有n-1條弧線從自己出發(fā)分別射向其它各個結(jié)點的話，則n個結(jié)點共有 n(n-1)條有向弧線存在；但是，如此一來任兩個結(jié)點之間都會有兩條相向而指的弧線存在， 這就是所謂的有向完全圖。如果我們限定任意兩個結(jié)點之間都有且僅有一條無向的連線存 在，則整個圖的連線總數(shù)就會比有向完全圖的弧線總數(shù)剛好少一半，即共有n(n-1)條邊， 也就是(n-1)條邊。此乃所謂(無向)完全圖。若能畫圖一試，則上述公式對錯立判。請參 考講義7.1.)在有n個頂點的有向圖中，每個頂點的度最大可達。答：2(n-1)(向其它每個頂點發(fā)出一條弧，則共發(fā)出n-1條，同時從其它每個頂點接收一條 弧，共接收n-1條，兩者合計為2(n-1)條。)在無向圖G的鄰接矩陣A中，若AIj等于1，則AjI等于。答：1在一個圖G的鄰接表表示中，每個頂點的鄰接表中所含的結(jié)點數(shù)，對于有向圖而言等于 該頂點的；而對于無向圖而言等于該頂點的。答：出度數(shù)度數(shù)對無向圖，若它有n個頂點e條邊，則其鄰接表中需要個結(jié)點。其中，個結(jié)點構(gòu)成鄰 接表，個結(jié)點構(gòu)成頂點表。答：2e+n 2e n已知一個圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是0答：求矩陣第i列非0元素的個數(shù)。已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法是答：將矩陣第i行全部置0遍歷圖的過程實質(zhì)上是。Breadth