數(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個(gè)頂點(diǎn)的有向圖最多有n（n1）條邊。2.在無向圖G的鄰接矩陣中，求第i個(gè)結(jié)點(diǎn)的度的方法是求鄰接矩陣第i行非零元素之和。3.堆排序通常采用順序存儲結(jié)構(gòu)。4.與快速排序和堆排序相比，歸并排序的最大特點(diǎn)是，它是一種穩(wěn)定的排序方法。5.

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

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

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

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

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