數(shù)據(jù)結(jié)構(gòu)(專)階段練習(xí)4

1、第14頁華東理工大學(xué)網(wǎng)絡(luò)學(xué)院華東理工大學(xué)網(wǎng)絡(luò)學(xué)院（專科）（?？疲稊?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》ch7圖、圖、ch9排序排序班級班級學(xué)號學(xué)號姓名姓名成績成績一、填空題（每空一、填空題（每空1分，共分，共10分）分）1.具有n個頂點的有向圖最多有n（n1）條邊。2.在無向圖G的鄰接矩陣中，求第i個結(jié)點的度的方法是求鄰接矩陣第i行非零元素之和。3.堆排序通常采用順序存儲結(jié)構(gòu)。4.與快速排序和堆排序相比，歸并排序的最大特點是，它是一種穩(wěn)定的排序方法。5.

2、具有8個頂點的有向完全圖有56條弧。6.在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于1。7.在一個待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠(yuǎn)，則使用直接插入排序方法最好。8.已知有向圖的鄰接矩陣，要計算i號頂點的入度，計算方法是：將i列元素累加。9.n個頂點的強連通圖至少有n條邊，至多有n(n1)條邊。二、判斷正誤（對的用二、判斷正誤（對的用”T”表示，錯誤的用表示，錯誤的

3、用”F”表示。每小題表示。每小題1分，共分，共10分）分）1.(T)若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇?.(F)快速排序的速度在所有的排序方法中為最快，而且所需附加空間也最少。3.（F）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似二叉樹的按層次遍歷算法。4.（T）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。5.（T）圖的廣度優(yōu)先遍歷類似于樹的層次遍歷。6.（T）拓?fù)渑判驎r，總是在有向圖

4、中選擇入度為0的頂點輸出。7.（F）若要求一個稠密圖G的最小生成樹，最好用Kruscal算法來求解。8.（T）拓?fù)渑判蜉敵龅捻旤c數(shù)小于有向圖的頂點數(shù)，則該圖一定存在回路。9.（T）設(shè)有一稠密圖G，則G采用鄰接矩陣存儲較省空間。10.（F）n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復(fù)雜度為O(ne)。三、單項選擇題（每小題三、單項選擇題（每小題2分，共分，共20分）分）1.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按

5、廣度優(yōu)先遍歷的結(jié)點序列是C。第34頁1.設(shè)有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？2.說明在圖的遍歷中，設(shè)置訪問標(biāo)志數(shù)組的作用。圖中結(jié)點可能有多個前驅(qū)，設(shè)置訪問標(biāo)志數(shù)組主要是為了避免重復(fù)訪問同一個結(jié)點3.用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？用鄰接矩陣表示圖，矩陣元素的個數(shù)是頂點個數(shù)的平方，與邊的條數(shù)無

6、關(guān)。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)。五、綜合題（每小題五、綜合題（每小題10分，共分，共30分。分。）1.畫出1個頂點、2個頂點、3個頂點、4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數(shù)為n(n1)2。在有n個頂點的無向完全圖中，每一個頂點都有一條邊與其它某一頂點相連，所以每一個頂點有n1條邊與其他n1個頂點相連，總計n個頂點有n(n1)條邊。但在無向圖中，頂點i到頂點j與頂點j到頂點i是同一條邊，所以總共