數(shù)據(jù)結(jié)構(gòu)試題：第七章的練習(xí)

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：圖單選題1、 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。A,1/2B,1C,2D,42、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量 的大小為。A,n B, n+1C,n-1 D,n+e3、具有n個(gè)頂點(diǎ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個(gè)結(jié)點(diǎn)的線索二叉樹中，線索的數(shù)目為.A,n-1 B,nC,n+1D,2n6、 在二叉排序中，凡是新插入的結(jié)點(diǎn)，都是沒

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

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

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

5、22、 對(duì)于一個(gè)無向圖，下面 說法是正確的。A,每個(gè)頂點(diǎn)的入度等于出度B,每個(gè)頂點(diǎn)的度等于其入度出度之和C,每個(gè)頂點(diǎn)的入度為0D,每個(gè)頂點(diǎn)的出度為023、在一個(gè)有向圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)等于該頂點(diǎn)的A,出邊數(shù) B入邊數(shù) C度數(shù) D度數(shù)減124、若一個(gè)圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F),則從頂點(diǎn)A開始對(duì)該圖進(jìn) 行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為。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、若一個(gè)圖的邊集為,則從頂點(diǎn)1開始對(duì)該 圖進(jìn)行深度優(yōu)先搜索，得到的頂

6、點(diǎn)序列可能為。A, 1,2,5,4,3B,1,2,3,4,5C,1,2,5,3,4D,1,4,3,2,526、若一個(gè)圖的邊集為,則從頂點(diǎn)1開始對(duì)該 圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為。A,1,2,3,4,5B,1,2,4,3,5C,1,2,4,5,3D,1,4,2,5,329、在n個(gè)頂點(diǎn)的有向無環(huán)無權(quán)圖的鄰接矩陣中至少有 個(gè)零元素。A,n B,n(n-1)2C,n(n+1)2D,n(n-1)判斷題1、有回路的圖不能進(jìn)行拓?fù)渑判颉數(shù)據(jù)結(jié)構(gòu)算法題1,設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法.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的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無向圖來說 等于該頂點(diǎn)的，對(duì)于有向圖來說等于該頂點(diǎn)的。度數(shù)|出 度數(shù)2、已知一個(gè)無向圖的鄰接矩陣如下所示，則從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索遍歷 得到的頂點(diǎn)序列為，按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為ABCDEF廠011010n A1 1010111B1 110100 1C1 0010011D1 1100011EL0101

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

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

10、,d,b14、根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，從某頂點(diǎn)出發(fā)得到的頂點(diǎn)序列是的唯一問答題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í)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否 有關(guān)？答：設(shè)圖的頂點(diǎn)個(gè)數(shù)為n（n0），則鄰接矩陣元素個(gè)數(shù)為n2,即頂點(diǎn)個(gè)數(shù)的平方， 與圖的邊數(shù)無關(guān)。3、對(duì)于稠密圖和稀疏圖，就存儲(chǔ)空間而言，采用鄰接矩陣和鄰接表哪個(gè)更好些？ 答：稠密圖采用鄰接矩陣好，稀疏圖采用鄰接表好。4、請(qǐng)回答下列關(guān)于圖的一些問題： 有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?這樣的圖應(yīng)該是什么形狀？ 有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有多少條邊?這樣的圖應(yīng)該是什么形狀？ 表示一個(gè)有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素?是否為稀疏矩陣？答：（1）最多有n（n-1）條邊（2）最少有n條邊（3）106,不一定是稀疏矩陣（稀疏矩陣的定義是非零個(gè)數(shù)遠(yuǎn)小于該矩陣元素個(gè) 數(shù)，且分布無規(guī)律）5、對(duì)n個(gè)頂點(diǎn)的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時(shí)，如何判別下列有 關(guān)問題？（1）圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？答：無向圖采用鄰接表時(shí)， 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。（2）第i個(gè)邊表中 是否含有結(jié)點(diǎn)j。該