數(shù)據(jù)結構試題：第七章的練習

1、數(shù)據(jù)結構復習題：圖單選題1、 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。A,1/2B,1C,2D,42、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量 的大小為。A,n B, n+1C,n-1 D,n+e3、具有n個頂點的無向完全圖，邊的總數(shù)為 條。A,n-1 B,n C,n+1D,n*(n-1)/24、 在無向圖G的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于。 TOC o 1-5 h z A,i+jB,i-j C,1D,05、 在n個結點的線索二叉樹中，線索的數(shù)目為.A,n-1 B,nC,n+1D,2n6、 在二叉排序中，凡是新插入的結點，都是沒

2、有 的.A孩子 B關鍵字 C平衡因子 D賦值 7、 深度為5的二叉樹至多有 個結點.A,16B,32C,31D,108、 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂 點的入度數(shù)之和為。A,s B,s-1C,s+1 D,n9、 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂 點的度數(shù)之和為。A,s B,s-1C,s+1 D,2s10、在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)之和為A,n B,e C,n+e D,2e11、在一個具有n個頂點的無向完全圖中，所含的邊數(shù)的。A,n B,n(n-1)C,n(n-1)/2D,n(n+1)/21

3、2、在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為。A,n B,n(n-1)C,n(n-1)/2D,n(n+1)/213、在一個無權圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為A,k B,k+1C,k+2 D,2k14、對于一個具有n個頂點的無向連通圖，它留念的連通分量的個數(shù)為A,0B,1 C,n D,n+115、若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點，則必須調用 次深度優(yōu)先于搜索遍歷的算法。A,k B,1C,k-1D,k+116、在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數(shù)為A,n B,n*e C,e D, 2*e17、在一個具有n個頂點

4、和e條邊的無向圖的鄰接表中，邊結點的個數(shù)為A,n B,n*e C,e D,2*e18、在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭 指針向量的大小至少為A,n B,2n C,e D,2e19、在一個無權圖的鄰接表表示中，每個邊結點至少包含 域。A, 1 B, 2 C, 3 D, 420、對于一個有向圖，若一個頂點的度為k1,出度為k2,則對應鄰接表中該頂點單 鏈表中的邊結點數(shù)為A,k1 B,k2 C,k1-k2D,k1+k221、對于一個有向圖，若一個頂點的度為k1,出度為k2,則對應鄰接表中該頂點單 鏈表中的邊結點數(shù)為。A,k1 B,k2 C,k1-k2D,k1+k2

5、22、 對于一個無向圖，下面 說法是正確的。A,每個頂點的入度等于出度B,每個頂點的度等于其入度出度之和C,每個頂點的入度為0D,每個頂點的出度為023、在一個有向圖的鄰接表中，每個頂點單鏈表中結點的個數(shù)等于該頂點的A,出邊數(shù) B入邊數(shù) C度數(shù) D度數(shù)減124、若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F),則從頂點A開始對該圖進 行深度優(yōu)先搜索，得到的頂點序列可能為。A: A,B,C,F,D,EB: A,C,F,D,E,B C: A,B,D,C,F,E D: A,B,D,F,E,C25、若一個圖的邊集為,則從頂點1開始對該 圖進行深度優(yōu)先搜索，得到的頂

6、點序列可能為。A, 1,2,5,4,3B,1,2,3,4,5C,1,2,5,3,4D,1,4,3,2,526、若一個圖的邊集為,則從頂點1開始對該 圖進行廣度優(yōu)先搜索，得到的頂點序列可能為。A,1,2,3,4,5B,1,2,4,3,5C,1,2,4,5,3D,1,4,2,5,329、在n個頂點的有向無環(huán)無權圖的鄰接矩陣中至少有 個零元素。A,n B,n(n-1)2C,n(n+1)2D,n(n-1)判斷題1、有回路的圖不能進行拓撲排序。T數(shù)據(jù)結構算法題1,設計一個將鄰接表轉換為鄰接矩陣的算法.void ListToMat(ALGraph *G,MGraph &g) int i,j,n=G-n;A

7、rcNode *p;for (i=0;iadjlisti.firstarc;while (p!=NULL) g.edgesip-adjvex=1;p=p-nextarc;g.vexnum=n;g.arcnum=G-e;填空題1、在圖G的鄰接表表示中，每個頂點鄰接表中所含的結點數(shù)，對于無向圖來說 等于該頂點的，對于有向圖來說等于該頂點的。度數(shù)|出 度數(shù)2、已知一個無向圖的鄰接矩陣如下所示，則從頂點A出發(fā)按深度優(yōu)先搜索遍歷 得到的頂點序列為，按廣度優(yōu)先搜索遍歷得到的頂點序列為ABCDEF廠011010n A1 1010111B1 110100 1C1 0010011D1 1100011EL0101

8、10FABCDFE|ABCEFD3、對二叉排序樹進行_遍歷，可以得到按關鍵字從小到大排列的結點序列中序4、 任何一棵子樹的結點個數(shù)減邊數(shù)等于 總邊數(shù)等于各結點 之和.1|出度、扇出5、 己知一棵完全二叉樹中共有562個結點，則該樹中共有 個葉子結點.2816、 在一個具有n個頂點的無向完全圖中，包括有 條邊，在一個具有n個頂點的有向完全圖中，包含有 條件。n(n-1)2 | n(n-2)7、已知一個連通圖的邊集為(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5)10,(3,5)12,(4,5)2，則度為3的頂點個數(shù)有 個。48、一 個有向圖的頂點集為a,b,c,d,e,f,邊集

9、為, 則出度為0的頂點個數(shù)為，入度為1的頂點個數(shù)為。2|49、 在一個連通圖中存在著 個連通分量110、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為大。N|N11、對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點的個數(shù)分別為 和。e |2e12、在有向圖的鄰接和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有 和 結點。出邊|入邊13、一個圖的邊集為(a,c),(a,e),(b,e),(c,d),(d,e),從頂點a出發(fā)進行深度優(yōu)先搜索遍 歷得到的頂點序列為，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的 頂點序列為。 a,c,d,e,b| a,c,e

10、,d,b14、根據(jù)圖的存儲結構進行某種次序的遍歷，從某頂點出發(fā)得到的頂點序列是的唯一問答題1、無向圖G如下圖：B E/ /A D G/C F試給出該圖的鄰接矩陣。該圖的鄰接表。(3)從A出發(fā)的“深度優(yōu)先”遍歷序列。從A出發(fā)的“廣度優(yōu)先”遍歷序列。解答：(1)圖G的鄰接矩陣廠011000On|1001000|1001000|A=|0110110|0001001|0001001|L0000110鄰接表如見：1111|A|+|111一Tb| +1|11- c|刁八|12111|B|+I|111一Ta| +11111-_ D|1 八| 13111|c| +I|111一Ta| +11111- D| 11

11、八|I,r14111|D|+111一B| +11一c|Il 1111+TeLI-一一 f|I2、用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關？與邊的條數(shù)是否 有關？答：設圖的頂點個數(shù)為n（n0），則鄰接矩陣元素個數(shù)為n2,即頂點個數(shù)的平方， 與圖的邊數(shù)無關。3、對于稠密圖和稀疏圖，就存儲空間而言，采用鄰接矩陣和鄰接表哪個更好些？ 答：稠密圖采用鄰接矩陣好，稀疏圖采用鄰接表好。4、請回答下列關于圖的一些問題： 有n個頂點的有向強連通圖最多有多少條邊?這樣的圖應該是什么形狀？ 有n個頂點的有向強連通圖最少有多少條邊?這樣的圖應該是什么形狀？ 表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否為稀疏矩陣？答：（1）最多有n（n-1）條邊（2）最少有n條邊（3）106,不一定是稀疏矩陣（稀疏矩陣的定義是非零個數(shù)遠小于該矩陣元素個 數(shù)，且分布無規(guī)律）5、對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有 關問題？（1）圖中有多少條邊？任意兩個頂點i和j是否有邊相連？任意一個頂點的度是多少？答：無向圖采用鄰接表時， 邊表中的結點個數(shù)之和除以2。（2）第i個邊表中 是否含有結點j。該