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

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

2、-網(wǎng)中，如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)， 不能求關(guān)鍵路徑。（）答：TRUE圖的鄰接矩陣中矩陣元素的行數(shù)只與頂點(diǎn)個(gè)數(shù)有關(guān)（TRUE ）圖的鄰接矩陣中矩陣中非零元素個(gè)數(shù)與邊數(shù)有關(guān)（TRUE ）在拓?fù)渑判蛐蛄兄校我鈨蓚€(gè)相繼結(jié)點(diǎn)V i和Vj都存在從V i到Vj的路徑（FALSE ）若一個(gè)圖的鄰接矩陣為對(duì)稱矩陣，則該圖必為無向圖。（TRUE ）任一 AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點(diǎn)到匯點(diǎn)的路徑中最長的一條（TRUE ）在有向圖中，入度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（或葉子）（FALSE ）單選題：在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍，在一個(gè)有向圖中，所

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

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

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

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

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

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

9、下圖所示的帶權(quán)有向圖，從頂點(diǎn)1到頂點(diǎn)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）為兩個(gè)圖，V1A. G1是G2的子圖B.G2是G1的子圖C. G1是G2的連通分量D.G2是G1的連通分量答案：A帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（）A、第i行非8的元素之和B、第i列非8的元素之和C、第i行非8且非0的元素個(gè)數(shù)D、第i列非8且非0的元素個(gè)數(shù)答案：D假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有 弧的時(shí)間復(fù)雜

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

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